Python技法之简单递归下降Parser的实现方法

一. 算术运算表达式求值

对于简单的算术运算表达式，假定我们已经用分词技术将其转化为输入的tokens流，如NUM+NUM*NUM。

在此基础上，我们定义BNF规则定义如下：

1. expr ::= expr + term
   
2.      | expr - term
   
3.      | term
   
4. term ::= term * factor
   
5.      | term / factor
   
6.      | factor
   
7. factor ::= (expr)
   
8.      | NUM
   
9. 
   

复制代码

当然，这种计法还不够简洁明了，我们实际采用的为EBNF形式：

1. expr ::= term { (+|-) term }*
   
2. term ::= factor { (*|/) factor }*
   
3. factor ::= (expr)
   
4.        | NUM
   
5. 
   

复制代码

BNF和EBNF每一条规则(形如::=的式子)都可以看做是一种替换，即左侧的符号可以被右侧的符号所替换。而解析的过程中我们尝试将输入文本同语法规则做匹配，通过BNF/EBNF来完成各种替换和扩展。其中，EBNF中包含在{…}*中的规则是可选的，*意味着零个或多个重复项（参考正则表达式）。

下图形象地展示了递归下降解析器(parser)中“递归”和“下降”部分和ENBF的关系：

在实际的解析过程中，我们对tokens流从左到右进行扫描，在扫描的过程中处理token，如果卡住就产生一个语法错误。对于规则，我们将每一条语法规则转变为一个函数或方法，比如上面的ENBF规则就转换为下列的方法：

1. class ExpressionEvaluator():
   
2.     ...
   
3.     def expr(self):
   
4.         ...
   
5.     def term(self):
   
6.         ...
   
7.     def factor(self):
   
8.         ...
   

复制代码

在调用某个规则对应方法的过程中，如果我们发现接下来的符号需要采用另一个规则来匹配，则我们就会“下降”到另一个规则方法（如在expr中调用term，term中调用factor），则也就是递归下降中“下降”的部分。

有时也会调用已经在执行的方法（比如在expr中调用term，term中调用factor后，又在factor中调用expr，相当于一条衔尾蛇），这也就是递归下降中“递归”的部分。

对于语法中出现的重复部分（例如expr ::= term { (+|-) term }*），我们则通过while循环来实现。

下面我们来看具体的代码实现。首先是分词部分，我们参照上一篇介绍分词博客的代码。

1. import re
   
2. import collections
   
3. 
   
4. # 定义匹配token的模式
   
5. NUM = r'(?P<NUM>\d+)'  # \d表示匹配数字，+表示任意长度
   
6. PLUS = r'(?P<PLUS>\+)'  # 注意转义
   
7. MINUS = r'(?P<MINUS>-)'
   
8. TIMES = r'(?P<TIMES>\*)'  # 注意转义
   
9. DIVIDE = r'(?P<DIVIDE>/)'
   
10. LPAREN = r'(?P<LPAREN>\()'  # 注意转义
    
11. RPAREN = r'(?P<RPAREN>\))'  # 注意转义
    
12. WS = r'(?P<WS>\s+)'  # 别忘记空格，\s表示空格，+表示任意长度
    
13. 
    
14. master_pat = re.compile(
    
15.     '|'.join([NUM, PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN, WS]))
    
16. 
    
17. # Tokenizer
    
18. Token = collections.namedtuple('Token', ['type', 'value'])
    
19. 
    
20. 
    
21. def generate_tokens(text):
    
22.     scanner = master_pat.scanner(text)
    
23.     for m in iter(scanner.match, None):
    
24.         tok = Token(m.lastgroup, m.group())
    
25.         if tok.type != 'WS':  # 过滤掉空格符
    
26.             yield tok
    
27. 
    

复制代码

下面是表达式求值器的具体实现：

1. class ExpressionEvaluator():
   
2.     """ 递归下降的Parser实现，每个语法规则都对应一个方法，
   
3.     使用 ._accept()方法来测试并接受当前处理的token，不匹配不报错，
   
4.     使用 ._except()方法来测试当前处理的token，并在不匹配的时候抛出语法错误
   
5.     """
   
6. 
   
7.     def parse(self, text):
   
8.         """ 对外调用的接口 """
   
9.         self.tokens = generate_tokens(text)
   
10.         self.tok, self.next_tok = None, None  # 已匹配的最后一个token，下一个即将匹配的token
    
11.         self._next()  # 转到下一个token
    
12.         return self.expr()  # 开始递归
    
13. 
    
14.     def _next(self):
    
15.         """ 转到下一个token """
    
16.         self.tok, self.next_tok = self.next_tok, next(self.tokens, None)
    
17. 
    
18.     def _accept(self, tok_type):
    
19.         """ 如果下一个token与tok_type匹配，则转到下一个token """
    
20.         if self.next_tok and self.next_tok.type == tok_type:
    
21.             self._next()
    
22.             return True
    
23.         else:
    
24.             return False
    
25. 
    
26.     def _except(self, tok_type):
    
27.         """ 检查是否匹配，如果不匹配则抛出异常 """
    
28.         if not self._accept(tok_type):
    
29.             raise SyntaxError("Excepted"+tok_type)
    
30. 
    
31.     # 接下来是语法规则，每个语法规则对应一个方法
    
32.    
    
33.     def expr(self):
    
34.         """ 对应规则： expression ::= term { ('+'|'-') term }* """
    
35.         exprval = self.term() # 取第一项
    
36.         while self._accept("PLUS") or self._accept("DIVIDE"): # 如果下一项是"+"或"-"
    
37.             op = self.tok.type
    
38.             # 再取下一项，即运算符右值
    
39.             right = self.term()
    
40.             if op == "PLUS":
    
41.                 exprval += right
    
42.             elif op == "MINUS":
    
43.                 exprval -= right
    
44.         return exprval
    
45.             
    
46.     def term(self):
    
47.         """ 对应规则： term ::= factor { ('*'|'/') factor }* """
    
48.         
    
49.         termval = self.factor() # 取第一项
    
50.         while self._accept("TIMES") or self._accept("DIVIDE"): # 如果下一项是"+"或"-"
    
51.             op = self.tok.type
    
52.             # 再取下一项，即运算符右值
    
53.             right = self.factor()
    
54.             if op == "TIMES":
    
55.                 termval *= right
    
56.             elif op == "DIVIDE":
    
57.                 termval /= right
    
58.         return termval         
    
59.             
    
60.         
    
61.     def factor(self):
    
62.         """ 对应规则： factor ::= NUM | ( expr ) """
    
63.         if self._accept("NUM"): # 递归出口
    
64.             return int(self.tok.value)
    
65.         elif self._accept("LPAREN"):
    
66.             exprval = self.expr() # 继续递归下去求表达式值
    
67.             self._except("RPAREN") # 别忘记检查是否有右括号，没有则抛出异常
    
68.             return exprval
    
69.         else:
    
70.             raise SyntaxError("Expected NUMBER or LPAREN")
    
71. 
    

复制代码

我们输入以下表达式进行测试：

1. e = ExpressionEvaluator()
   
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)*5"))
   
6. 
   

复制代码

求值结果如下：

2
5
14
37

如果我们输入的文本不符合语法规则：

1. print(e.parse("2 + (3 + * 4)"))
   
2. 
   

复制代码

则会抛出SyntaxError异常：Expected NUMBER or LPAREN。
综上，可见我们的表达式求值算法运行正确。

二. 生成表达式树

上面我们是得到表达式的结果，但是如果我们想分析表达式的结构，生成一棵简单的表达式解析树呢？那么我们需要对上述类的方法做一定修改：

1. class ExpressionTreeBuilder(ExpressionEvaluator):
   
2.     def expr(self):
   
3.             """ 对应规则： expression ::= term { ('+'|'-') term }* """
   
4.             exprval = self.term() # 取第一项
   
5.             while self._accept("PLUS") or self._accept("DIVIDE"): # 如果下一项是"+"或"-"
   
6.                 op = self.tok.type
   
7.                 # 再取下一项，即运算符右值
   
8.                 right = self.term()
   
9.                 if op == "PLUS":
   
10.                     exprval = ('+', exprval, right)
    
11.                 elif op == "MINUS":
    
12.                     exprval -= ('-', exprval, right)
    
13.             return exprval
    
14.    
    
15.     def term(self):
    
16.         """ 对应规则： term ::= factor { ('*'|'/') factor }* """
    
17.         
    
18.         termval = self.factor() # 取第一项
    
19.         while self._accept("TIMES") or self._accept("DIVIDE"): # 如果下一项是"+"或"-"
    
20.             op = self.tok.type
    
21.             # 再取下一项，即运算符右值
    
22.             right = self.factor()
    
23.             if op == "TIMES":
    
24.                 termval = ('*', termval, right)
    
25.             elif op == "DIVIDE":
    
26.                 termval = ('/', termval, right)
    
27.         return termval         
    
28.    
    
29.     def factor(self):
    
30.         """ 对应规则： factor ::= NUM | ( expr ) """
    
31.         if self._accept("NUM"): # 递归出口
    
32.             return int(self.tok.value) # 字符串转整形
    
33.         elif self._accept("LPAREN"):
    
34.             exprval = self.expr() # 继续递归下去求表达式值
    
35.             self._except("RPAREN") # 别忘记检查是否有右括号，没有则抛出异常
    
36.             return exprval
    
37.         else:
    
38.             raise SyntaxError("Expected NUMBER or LPAREN")
    
39. 
    

复制代码

输入下列表达式测试一下：

1. print(e.parse("2+3"))
   
2. print(e.parse("2+3*4"))
   
3. print(e.parse("2+(3+4)*5"))
   
4. print(e.parse('2+3+4'))
   
5. 
   

复制代码

以下是生成结果：

1. <span style="color: rgb(85, 86, 102); font-family: -apple-system, " sf="" ui="" text",="" arial,="" "pingfang="" sc",="" "hiragino="" sans="" gb",="" "microsoft="" yahei",="" "wenquanyi="" micro="" hei",="" sans-serif;="" font-variant-ligatures:="" no-common-ligatures;"="">(‘+’, 2, 3)</span>
   
2. <span style="color: rgb(85, 86, 102); font-family: -apple-system, " sf="" ui="" text",="" arial,="" "pingfang="" sc",="" "hiragino="" sans="" gb",="" "microsoft="" yahei",="" "wenquanyi="" micro="" hei",="" sans-serif;="" font-variant-ligatures:="" no-common-ligatures;"="">(‘+’, 2, (‘</span><em style="box-sizing: border-box; outline: 0px; color: rgb(85, 86, 102); font-family: -apple-system, " sf="" ui="" text",="" arial,="" "pingfang="" sc",="" "hiragino="" sans="" gb",="" "microsoft="" yahei",="" "wenquanyi="" micro="" hei",="" sans-serif;="" font-variant-ligatures:="" no-common-ligatures;"="">‘, 3, 4))
   
3. (’+‘, 2, (’</em><span style="color: rgb(85, 86, 102); font-family: -apple-system, " sf="" ui="" text",="" arial,="" "pingfang="" sc",="" "hiragino="" sans="" gb",="" "microsoft="" yahei",="" "wenquanyi="" micro="" hei",="" sans-serif;="" font-variant-ligatures:="" no-common-ligatures;"="">’, (‘+’, 3, 4), 5))</span>
   
4. <span style="color: rgb(85, 86, 102); font-family: -apple-system, " sf="" ui="" text",="" arial,="" "pingfang="" sc",="" "hiragino="" sans="" gb",="" "microsoft="" yahei",="" "wenquanyi="" micro="" hei",="" sans-serif;="" font-variant-ligatures:="" no-common-ligatures;"="">(‘+’, (‘+’, 2, 3), 4)</span>

复制代码

可以看到表达式树生成正确。

我们上面的这个例子非常简单，但递归下降的解析器也可以用来实现相当复杂的解析器，例如Python代码就是通过一个递归下降解析器解析的。您要是对此跟感兴趣可以检查Python源码中的Grammar文件来一探究竟。然而，下面我们接着会看到，自己动手写一个解析器会面对各种陷阱和挑战。

三、左递归和运算符优先级陷阱

任何涉及左递归形式的语法规则，都没法用递归下降parser来解决。所谓左递归，即规则式子右侧最左边的符号是规则头，比如对于以下规则：

1. items ::= items ',' item
   
2.       | item
   
3. 
   

复制代码

完成该解析你可能会定义以下方法：

1. def items(self):
   
2.     itemsval = self.items() # 取第一项，然而此处会无穷递归！
   
3.     if itemsval and self._accept(','):
   
4.         itemsval.append(self.item())
   
5.     else:
   
6.         itemsval = [self.item()]
   
7. 
   

复制代码

这样做会在第一行就无穷地调用self.items()从而产生无穷递归错误。
还有一种是语法规则自身的错误，比如运算符优先级。我们如果忽视运算符优先级直接将表达式简化如下：

1. expr ::= factor { ('+'|'-'|'*'|'/') factor }*
   
2. factor ::= '(' expr ')'
   
3.        | NUM
   
4. 
   

复制代码

PYTHON 复制 全屏
这个语法从技术上可以实现，但是没有遵守计算顺序约定，导致"3+4*5"的运算结果为35，而不是预期的23。故此处需要用独立的expr和term规则来确保计算结果的正确性。

四. 相关包

最后，对于真正复杂的语法解析，建议采用PyParsing或PLY这样的解析工具。如果你对Python代码的抽象语法树感兴趣，可以看下Python自带的ast模块。

6

Dick 发表于 2022-12-24 00:14
6

5+1