【Python Cookbook】字符串和文本（五）：递归下降分析器

20.实现一个简单的递归下降分析器

开始本文的学习前，我们需要首先了解一下什么是 BNF 和 EBNF。

🚀 BNF（Backus-Naur Form，巴科斯-诺尔范式）和 EBNF（Extended Backus-Naur Form，扩展巴科斯-诺尔范式）是用于描述编程语言或其他形式语言语法的元语言（描述语言的语言）。它们是编译器设计、文档规范和协议定义中的基础工具。

20.1 BNF（基础形式）

BNF 最初由 John Backus 和 Peter Naur 在 1950-60 年代提出，用于描述 ALGOL 60 语言的语法。

核心组成：

• 非终结符（Non-terminal）：用 < > 括起，表示需要进一步展开的语法单元。
  • 例如：<expression>、<statement>
• 终结符（Terminal）：语言中的实际符号（如关键字、运算符等）。
  • 例如："if"、"+"、"123"
• 产生式规则（Production rule）：用 ::= 表示定义。
  • 例如：<digit> ::= "0" | "1" | ... | "9"

示例（简单算术表达式）：

<expression> ::= <term> "+" <expression> | <term>
<term>       ::= <factor> "*" <term> | <factor>
<factor>     ::= "(" <expression> ")" | <number>
<number>     ::= <digit> | <number> <digit>
<digit>      ::= "0" | "1" | ... | "9"

20.2 EBNF（扩展形式）

EBNF 在 BNF 基础上添加了更简洁的表达方式，被现代语言规范（如 Python、SQL 标准）广泛使用。

扩展符号：

• 可选项：用 [ ] 表示。
  • 例如："if" <condition> "then" [ "else" <statement> ]
• 重复项：用 { } 表示（0 次或多次）。
  • 例如：<number> ::= <digit> { <digit> }
• 分组：用 ( ) 明确优先级。
  • 例如：("+" | "-") <expression>
• 终结符通常不再加引号（依规范而定）。

示例（同上的算术表达式，用 EBNF）：

expression = term { "+" term } ;
term       = factor { "*" factor } ;
factor     = "(" expression ")" | number ;
number     = digit { digit } ;
digit      = "0" | "1" | ... | "9" ;

关键区别

20.3 案例

你想根据一组语法规则解析文本并执行命令，或者构造一个代表输入的抽象语法树。如果语法非常简单，你可以不去使用一些框架，而是自己写这个解析器。

在这个问题中，我们集中讨论根据特殊语法去解析文本的问题。为了这样做，你首先要以 BNF 或者 EBNF 形式指定一个标准语法。比如，一个简单数学表达式语法可能像下面这样：

expr ::= expr + term
    |   expr - term
    |   term

term ::= term * factor
    |   term / factor
    |   factor

factor ::= ( expr )
    |   NUM

或者，以 EBNF 形式：

expr ::= term { (+|-) term }*

term ::= factor { (*|/) factor }*

factor ::= ( expr )
    |   NUM

在 EBNF 中，被包含在 {...}* 中的规则是可选的。* 代表 0 次或多次重复（跟正则表达式中意义是一样的）。

现在，如果你对 BNF 的工作机制还不是很明白的话，就把它当做是一组左右符号可相互替换的规则。一般来讲，解析的原理就是你利用 BNF 完成多个替换和扩展以匹配输入文本和语法规则。为了演示，假设你正在解析形如 3 + 4 * 5 的表达式。这个表达式先要分解为一组令牌流，结果可能是像下列这样的令牌序列：

NUM + NUM * NUM

在此基础上， 解析动作会试着去通过替换操作匹配语法到输入令牌：

expr
expr ::= term { (+|-) term }*
expr ::= factor { (*|/) factor }* { (+|-) term }*
expr ::= NUM { (*|/) factor }* { (+|-) term }*
expr ::= NUM { (+|-) term }*
expr ::= NUM + term { (+|-) term }*
expr ::= NUM + factor { (*|/) factor }* { (+|-) term }*
expr ::= NUM + NUM { (*|/) factor}* { (+|-) term }*
expr ::= NUM + NUM * factor { (*|/) factor }* { (+|-) term }*
expr ::= NUM + NUM * NUM { (*|/) factor }* { (+|-) term }*
expr ::= NUM + NUM * NUM { (+|-) term }*
expr ::= NUM + NUM * NUM

下面所有的解析步骤可能需要花点时间弄明白，但是它们原理都是查找输入并试着去匹配语法规则。第一个输入令牌是 NUM，因此替换首先会匹配那个部分。一旦匹配成功，就会进入下一个令牌 +，以此类推。当已经确定不能匹配下一个令牌的时候，右边的部分（比如 { (*/) factor }* ）就会被清理掉。在一个成功的解析中，整个右边部分会完全展开来匹配输入令牌流。

有了前面的知识背景，下面我们举一个简单示例来展示如何构建一个递归下降表达式求值程序：

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
Topic: 下降解析器
Desc :
"""
import re
import collections

# Token specification
NUM = r'(?P<NUM>\d+)'        # 匹配数字
PLUS = r'(?P<PLUS>\+)'       # 匹配加号
MINUS = r'(?P<MINUS>-)'      # 匹配减号
TIMES = r'(?P<TIMES>\*)'     # 匹配乘号
DIVIDE = r'(?P<DIVIDE>/)'    # 匹配除号
LPAREN = r'(?P<LPAREN>\()'   # 匹配左括号
RPAREN = r'(?P<RPAREN>\))'   # 匹配右括号
WS = r'(?P<WS>\s+)'          # 匹配空白字符

# 使用 (?P<NAME>...) 命名捕获组，方便后续识别 token 类型
master_pat = re.compile('|'.join([NUM, PLUS, MINUS, TIMES,
                                  DIVIDE, LPAREN, RPAREN, WS]))
# Tokenizer
Token = collections.namedtuple('Token', ['type', 'value'])

# 将输入字符串 text 拆分为一系列 Token（包含类型和值）
def generate_tokens(text):
    scanner = master_pat.scanner(text)
    for m in iter(scanner.match, None):
        tok = Token(m.lastgroup, m.group())
        if tok.type != 'WS':
            yield tok


# Parser
class ExpressionEvaluator:
    '''
    Implementation of a recursive descent parser. 
    Each method implements a single grammar rule. 
    Use the ._accept() method to test and accept the current lookahead token. 
    Use the ._expect() method to exactly match and discard the next token on on the input
    (or raise a SyntaxError if it doesn't match).
    '''

    def parse(self, text):
        self.tokens = generate_tokens(text) # 生成 token 流
        self.tok = None                     # 记录当前已消费的 token（即最近处理过的 token）
        self.nexttok = None                 # 保存下一个待处理的 token（即“预读”的 token，用于语法分析中的“向前看”）
        self._advance()                     # 移动到下一个 token
        return self.expr()                  # 从最高优先级规则开始解析  

	# 移动到下一个 token
    def _advance(self):
        self.tok, self.nexttok = self.nexttok, next(self.tokens, None)
	
	# 如果下一个 token 匹配 toktype 则消费它
    def _accept(self, toktype):
        if self.nexttok and self.nexttok.type == toktype:
            self._advance()
            return True
        else:
            return False

	# 必须匹配 toktype，否则报错（用于强制语法规则）
    def _expect(self, toktype):
        if not self._accept(toktype):
            raise SyntaxError('Expected ' + toktype)

    # 处理加减法
    # expression ::= term { ('+'|'-') term }*
    def expr(self):
        exprval = self.term() # 先解析更高优先级的 term
        while self._accept('PLUS') or self._accept('MINUS'):
            op = self.tok.type
            right = self.term() # 解析右侧 term
            if op == 'PLUS':
                exprval += right
            elif op == 'MINUS':
                exprval -= right
        return exprval

	# 处理乘除法
	# term ::= factor { ('*'|'/') factor }*
    def term(self):
        termval = self.factor() # 先解析更高优先级的 factor
        while self._accept('TIMES') or self._accept('DIVIDE'):
            op = self.tok.type
            right = self.factor() # 解析右侧 factor
            if op == 'TIMES':
                termval *= right
            elif op == 'DIVIDE':
                termval /= right
        return termval

	# 处理数字和括号
	# factor ::= NUM | ( expr )
    def factor(self):
        if self._accept('NUM'):
            return int(self.tok.value) # 返回数字值
        elif self._accept('LPAREN'):
            exprval = self.expr()      # 递归解析括号内表达式
            self._expect('RPAREN')     # 必须匹配右括号
            return exprval
        else:
            raise SyntaxError('Expected NUMBER or LPAREN')


def descent_parser():
    e = ExpressionEvaluator()
    print(e.parse('2'))
    print(e.parse('2 + 3'))
    print(e.parse('2 + 3 * 4'))
    print(e.parse('2 + (3 + 4) * 5'))
    # print(e.parse('2 + (3 + * 4)'))
    # Traceback (most recent call last):
    #    File "<stdin>", line 1, in <module>
    #    File "exprparse.py", line 40, in parse
    #    return self.expr()
    #    File "exprparse.py", line 67, in expr
    #    right = self.term()
    #    File "exprparse.py", line 77, in term
    #    termval = self.factor()
    #    File "exprparse.py", line 93, in factor
    #    exprval = self.expr()
    #    File "exprparse.py", line 67, in expr
    #    right = self.term()
    #    File "exprparse.py", line 77, in term
    #    termval = self.factor()
    #    File "exprparse.py", line 97, in factor
    #    raise SyntaxError("Expected NUMBER or LPAREN")
    #    SyntaxError: Expected NUMBER or LPAREN


if __name__ == '__main__':
    descent_parser()

以输入 "2 + (3 + 4) * 5" 为例：

1. 词法分析生成 tokens：

   [NUM(2), PLUS(+), LPAREN((), NUM(3), PLUS(+), NUM(4), RPAREN()), TIMES(*), NUM(5)]
   

2. 语法分析过程：
   • expr() 调用 term() → factor() → 返回 2
   • 遇到 +，解析右侧 term()：
     • 遇到 (，进入新的 expr() 计算 3 + 4 = 7
     • 遇到 *，计算 7 * 5 = 35
   • 最终结果：2 + 35 = 37

文本解析是一个很大的主题， 一般会占用学生学习编译课程时刚开始的三周时间。如果你在找寻关于语法，解析算法等相关的背景知识的话，你应该去看一下编译器书籍。很显然，关于这方面的内容太多，不可能在这里全部展开。

尽管如此，编写一个递归下降解析器的整体思路是比较简单的。开始的时候，你先获得所有的语法规则，然后将其转换为一个函数或者方法。因此如果你的语法类似这样：

expr ::= term { ('+'|'-') term }*

term ::= factor { ('*'|'/') factor }*

factor ::= '(' expr ')'
    | NUM

你应该首先将它们转换成一组像下面这样的方法：

class ExpressionEvaluator:
    ...
    def expr(self):
    ...
    def term(self):
    ...
    def factor(self):
    ...

每个方法要完成的任务很简单 - 它必须从左至右遍历语法规则的每一部分，处理每个令牌。从某种意义上讲，方法的目的就是要么处理完语法规则，要么产生一个语法错误。为了这样做，需采用下面的这些实现方法：

• 如果规则中的下个符号是另外一个语法规则的名字（比如 term 或 factor），就简单的调用同名的方法即可。这就是该算法中 下降 的由来 - 控制下降到另一个语法规则中去。有时候规则会调用已经执行的方法（比如，在 factor ::= '('expr ')' 中对expr的调用）。这就是算法中 递归 的由来。
• 如果规则中下一个符号是个特殊符号（比如 ()，你得查找下一个令牌并确认是一个精确匹配）。如果不匹配，就产生一个语法错误。这一节中的 _expect() 方法就是用来做这一步的。
• 如果规则中下一个符号为一些可能的选择项（比如 + 或 -），你必须对每一种可能情况检查下一个令牌，只有当它匹配一个的时候才能继续。这也是本节示例中 _accept() 方法的目的。它相当于_expect() 方法的弱化版本，因为如果一个匹配找到了它会继续，但是如果没找到，它不会产生错误而是回滚（允许后续的检查继续进行）。
• 对于有重复部分的规则（比如在规则表达式 ::= term { ('+'|'-') term }* 中），重复动作通过一个 while 循环来实现。循环主体会收集或处理所有的重复元素直到没有其他元素可以找到。
• 一旦整个语法规则处理完成，每个方法会返回某种结果给调用者。这就是在解析过程中值是怎样累加的原理。比如，在表达式求值程序中，返回值代表表达式解析后的部分结果。最后所有值会在最顶层的语法规则方法中合并起来。

尽管向你演示的是一个简单的例子，递归下降解析器可以用来实现非常复杂的解析。比如，Python 语言本身就是通过一个递归下降解析器去解释的。如果你对此感兴趣，你可以通过查看 Python 源码文件 Grammar/Grammar 来研究下底层语法机制。看完你会发现，通过手动方式去实现一个解析器其实会有很多的局限和不足之处。

其中一个局限就是它们不能被用于包含任何左递归的语法规则中。比如，假如你需要翻译下面这样一个规则：

items ::= items ',' item
    | item

• 逻辑矛盾：直接按照该规则实现会导致无限递归。
• 正确理解：该规则的实际含义是 “一个或多个由逗号分隔的 item”，应该用 循环 而非递归实现。

为了这样做，你可能会像下面这样使用 items() 方法：

def items(self):
    itemsval = self.items()
    if itemsval and self._accept(','):
        itemsval.append(self.item())
    else:
        itemsval = [ self.item() ]

唯一的问题是这个方法根本不能工作，事实上，它会产生一个无限递归错误。

• 原因：items() 方法内部直接调用了 self.items()，导致无限递归，最终触发 RecursionError。
• 修复：应该先尝试解析第一个 item，再判断是否有后续的 ',' item。修正后的逻辑：

  def items(self):
      itemsval = [self.item()]  # 先解析第一个 item
      while self._accept(','):   # 如果遇到逗号，继续解析后续 item
          itemsval.append(self.item())
      return itemsval
  

• 避免递归：原始 BNF 是左递归的（items 在产生式开头调用自身），而递归下降解析器无法处理左递归。

假设输入是 "A, B, C"：

• 错误版本：会无限递归，直到崩溃。
• 修正版本：
  • 第一次调用：解析 "A" → itemsval = ["A"]
  • 遇到 ","，解析 "B" → itemsval = ["A", "B"]
  • 遇到 ","，解析 "C" → itemsval = ["A", "B", "C"]
  • 返回最终结果 ["A", "B", "C"]

关于语法规则本身你可能也会碰到一些棘手的问题。比如，你可能想知道下面这个简单扼语法是否表述得当：

expr ::= factor { ('+'|'-'|'*'|'/') factor }*

factor ::= '(' expression ')'
    | NUM

这个语法看上去没啥问题，但是它却不能察觉到标准四则运算中的运算符优先级。比如，表达式 "3 + 4 * 5" 会得到 35 而不是期望的 23。分开使用 expr 和 term 规则可以让它正确的工作。

对于复杂的语法，你最好是选择某个解析工具比如 PyParsing 或者是 PLY。下面是使用 PLY 来重写表达式求值程序的代码：

from ply.lex import lex
from ply.yacc import yacc

# Token list
tokens = [ 'NUM', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN' ]
# Ignored characters
t_ignore = ' \t\n'
# Token specifications (as regexs)
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'

# Token processing functions
def t_NUM(t):
    r'\d+'
    t.value = int(t.value)
    return t

# Error handler
def t_error(t):
    print('Bad character: {!r}'.format(t.value[0]))
    t.skip(1)

# Build the lexer
lexer = lex()

# Grammar rules and handler functions
def p_expr(p):
    '''
    expr : expr PLUS term
        | expr MINUS term
    '''
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]


def p_expr_term(p):
    '''
    expr : term
    '''
    p[0] = p[1]


def p_term(p):
    '''
    term : term TIMES factor
    | term DIVIDE factor
    '''
    if p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]

def p_term_factor(p):
    '''
    term : factor
    '''
    p[0] = p[1]

def p_factor(p):
    '''
    factor : NUM
    '''
    p[0] = p[1]

def p_factor_group(p):
    '''
    factor : LPAREN expr RPAREN
    '''
    p[0] = p[2]

def p_error(p):
    print('Syntax error')

parser = yacc()

这个程序中，所有代码都位于一个比较高的层次。你只需要为令牌写正则表达式和规则匹配时的高阶处理函数即可。而实际的运行解析器，接受令牌等等底层动作已经被库函数实现了。

下面是一个怎样使用得到的解析对象的例子：

>>> parser.parse('2')
2
>>> parser.parse('2+3')
5
>>> parser.parse('2+(3+4)*5')
37
>>>

如果你想在你的编程过程中来点挑战和刺激，编写解析器和编译器是个不错的选择。再次，一本编译器的书籍会包含很多底层的理论知识。不过很多好的资源也可以在网上找到。Python 自己的 ast 模块也值得去看一下。

20.4 关键 self 操作解析

在 Python 类中，self 是一个指向 当前对象实例 的引用，用于访问实例的属性和方法。在上述代码中，self 的用法涉及 词法分析器（Lexer）和语法解析器（Parser）的状态管理。下面我会逐步拆解这些 self 操作的作用：

self.tokens 和 self.tok / self.nexttok

def parse(self, text):
    self.tokens = generate_tokens(text)  # 存储 token 生成器
    self.tok = None       # 当前消费的 token
    self.nexttok = None   # 下一个待处理的 token
    self._advance()       # 初始化：预加载第一个 token

• self.tokens: 保存从 generate_tokens() 返回的 token 生成器（一个可迭代对象），用于逐个读取 token。
• self.tok: 记录 当前已消费的 token（即最近处理过的 token）。
• self.nexttok: 保存 下一个待处理的 token（即 “预读” 的 token，用于语法分析中的 “向前看”）。

self._advance()：移动到下一个 token

def _advance(self):
    self.tok, self.nexttok = self.nexttok, next(self.tokens, None)

• 作用：
  1. 将 self.nexttok 的值赋给 self.tok（表示当前 token 已消费）。
  2. 通过 next(self.tokens, None) 读取生成器的 下一个 token，存入 self.nexttok。
  3. 如果 token 流结束，next() 返回 None。
• 示例：假设 tokens 为 [NUM(2), PLUS(+), NUM(3)]：
  • 第一次调用 _advance() 后：self.tok = None, self.nexttok = NUM(2)
  • 第二次调用后：self.tok = NUM(2), self.nexttok = PLUS(+)
  • 第三次调用后：self.tok = PLUS(+), self.nexttok = NUM(3)

self._accept(toktype)：尝试匹配并消费 token

def _accept(self, toktype):
    if self.nexttok and self.nexttok.type == toktype:
        self._advance()  # 消费匹配的 token
        return True
    return False

• 作用：
  • 检查下一个 token (self.nexttok) 是否与 toktype 匹配（如 'PLUS'）。
  • 如果匹配，调用 _advance() 消费该 token，并返回 True。
  • 否则返回 False。
• 示例：当前 self.nexttok = PLUS(+)，调用 _accept('PLUS') 会返回 True，并更新 self.tok 和 self.nexttok。

self._expect(toktype)：强制匹配 token

def _expect(self, toktype):
    if not self._accept(toktype):
        raise SyntaxError('Expected ' + toktype)

• 作用：
  • 必须匹配 toktype，否则抛出语法错误。
  • 用于处理语法中的强制性规则（如右括号 ) 必须闭合）。
• 示例：在 factor() 中解析括号表达式时：

  if self._accept('LPAREN'):
      exprval = self.expr()  # 解析括号内的表达式
      self._expect('RPAREN')  # 必须遇到右括号
  

self.expr() / self.term() / self.factor()：递归解析

这些方法通过 self 访问和更新 token 状态，实现表达式的递归下降解析：

def expr(self):
    exprval = self.term()  # 解析高优先级的 term
    while self._accept('PLUS') or self._accept('MINUS'):
        op = self.tok.type  # 当前操作符（通过 self.tok 获取）
        right = self.term()  # 解析右侧 term
        exprval += right if op == 'PLUS' else -right
    return exprval

• self.tok：在 _accept() 后存储 最近消费的 token（如操作符 +）。
• self.term()：递归调用解析更高优先级的子表达式。

状态流转示例

以解析 "2 + 3" 为例：

1. 初始化：

   • self.tokens = 生成器生成 [NUM(2), PLUS(+), NUM(3)]
   • self.tok = None, self.nexttok = None
   • 调用 _advance() → self.tok = None, self.nexttok = NUM(2)

2. 解析 expr()：

   • 调用 term() → 调用 factor() → _accept('NUM') 为 True：
     • 消费 NUM(2)，返回 2
     • 现在 self.tok = NUM(2), self.nexttok = PLUS(+)
   • 遇到 while 循环，_accept('PLUS') 为 True：
     • 消费 PLUS(+)，self.tok = PLUS(+), self.nexttok = NUM(3)
     • 解析右侧 term() → 返回 3
   • 计算 2 + 3，返回 5

总结

• self.tok / self.nexttok：跟踪 token 流的状态，实现 “预读” 和 “消费”。
• self._advance()：推进 token 流，更新当前和下一个 token。
• self._accept() / self._expect()：控制语法规则的匹配和错误处理。
• 递归方法：通过 self 共享状态，实现表达式的优先级和嵌套解析。

这种设计是 递归下降解析器 的典型实现，self 用于在方法间传递和维护解析状态。