Python Lex-Yacc 实践之现代希腊语的拉丁转写

This is a placeholder for excerpt.

阅读这篇文章可能需要编译原理作为前置知识。

Python Lex-Yacc 简要介绍¶

Python Lex-Yacc（PLY）包含词法分析器（即 Lexer）和语法分析器（即 Parser）两个部分，它们的作用和编译原理中的词法分析和语法分析是一致的。

词法分析器负责将输入的字符串拆分为 token，而语法分析器则负责将 token 解析成结构化的输出（例如抽象语法树）。

例如，对于输入字符串 "3 + 4 * 2"，词法分析器将其拆分为 ["3", "+", "4", "*", "2"]，而语法分析器将其解析成 (3 + (4 * 2))。

下面以一个简单的例子（由 AI 辅助生成）来展示如何使用 PLY 实现一个简单的四则运算解析器。

词法分析器¶

import ply.lex as lex

# 1. 定义 token 列表
tokens = ('NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN')

# 2️. 定义正则表达式匹配规则
t_PLUS    = r'\+'
t_MINUS   = r'-'
t_TIMES   = r'\*'
t_DIVIDE  = r'/'
t_LPAREN  = r'\('
t_RPAREN  = r'\)'

# 3️. 处理数字
def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)  # 解析为整数
    return t

# 4️. 忽略空格和制表符
t_ignore = ' \t'

# 5️. 处理错误字符
def t_error(t):
    print(f"illegal character '{t.value[0]}'")
    t.lexer.skip(1)

# 6️. 构造词法分析器
lexer = lex.lex()

tokens 变量定义了所有可能的 token 类型，这里包括数字、加减乘除、左右括号。
在 PLY 的 Lexer 里，所有的 token 规则必须遵循 t_ 开头的命名规范。t_ 后面跟的是 tokens 变量中定义的名称，如 PLUS，必须和 tokens 变量里的名字完全匹配
. 作为变量的 t_xxx 用于定义简单的 token 规则，例如仅使用正则表达式就能够完成匹配和处理的 token。
作为函数的 t_xxx 用于定义复杂的 token 规则及其处理逻辑。返回值是一个 token 对象，其中 t.value 是 token 的值，t.type 是 token 的类型。
t_ignore 用于定义需要忽略的字符，直接附加在字符串中即可；t_error 用于处理错误字符。这两个是保留的函数名，不可更改。

语法分析器¶

import ply.yacc as yacc

# 1️. 定义运算优先级（PLY 默认遵循自底向上的 LALR(1) 解析）
precedence = (
    ('left', 'PLUS', 'MINUS'),      # `+` `-` 具有相同优先级，左结合
    ('left', 'TIMES', 'DIVIDE'),    # `*` `/` 具有相同优先级，左结合
    ('nonassoc', 'UMINUS'),         # `-` 负号单独优先（非结合性）
)

# 2️. 解析规则
# 处理加法、减法、乘法、除法
def p_expression_binop(p):
    '''expression : expression PLUS expression
                  | expression MINUS expression
                  | expression TIMES expression
                  | expression DIVIDE expression'''
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]
    elif p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]

# 处理 `-` 负号
def p_expression_uminus(p):
    '''expression : MINUS expression %prec UMINUS'''
    p[0] = -p[2]

# 处理括号 `()`
def p_expression_group(p):
    '''expression : LPAREN expression RPAREN'''
    p[0] = p[2]

# 处理数字
def p_expression_number(p):
    '''expression : NUMBER'''
    p[0] = p[1]

# 处理错误
def p_error(p):
    print("syntax error")

# 3️. 构造语法分析器
parser = yacc.yacc()

precedence 变量定义了运算符的优先级和结合性，自上而下的顺序表示优先级从高到低，left 表示左结合，right 表示右结合，nonassoc 表示非结合性。
在 PLY 的 Parser 里，约定遵循 p_ 开头的命名规范的函数都是语法规则的定义，p_ 后面跟的是语法规则的名称。
参数 p 包含了与当前正在处理的语法规则相关的所有符号的值，在语法分析过程中充当「值栈」的作用。其中，p[0] 是规则左侧的非终结符（结果），p[1]、p[2]、p[3] 等是规则右侧的元素。
语法规则使用 BNF 的形式定义，被包围在三引号中，如 '''expression : expression PLUS expression'''。PLY 解析器依赖 Python 的 docstring 读取 BNF 规则，并将其转换为语法规则。
这些函数内部的逻辑实现了属性文法的概念。在语法分析的同时，执行语义动作。例如在规则 p_expression_binop 中，语义动作是计算表达式的值，并将结果存储回 p[0]，以便在语法分析树中自底向上传递计算结果。在实际的编译器中，这一步可能是用来进行中间代码生成的。
规则 expression : MINUS expression %prec UMINUS 中，%prec UMINUS 是一个优先级指示器，作用于整个产生式，当有多个运算符时，整个规则使用 %prec 指定的优先级。对应于理论，当解析器遇到多个可能的规约选择时，将根据规则整体的优先级来决定所选择的规约。

Python Lex-Yacc 实践之现代希腊语的拉丁转写

Python Lex-Yacc 简要介绍¶

词法分析器¶

语法分析器¶

调用 Lexer 和 Parser¶