Python进阶编程：编写更高效、优雅的Python代码
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

2.8　简单的递归下降分析器实现

解析器可以通过语法规则解析文本并执行命令实现，或者构造一个代表输入的抽象语法树实现。如果语法非常简单，可以不使用框架，而是自己手动实现解析器。

要想手动实现解析器，需根据特殊语法去解析文本。首先以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}*）就会被清理掉。在一个成功的解析中，整个令牌右边部分会完全展开来匹配输入令牌流。

下面通过一个简单示例来展示如何构建一个递归下降表达式求值程序，相关代码（simple_recursion_1.py）示例如下：

"""
下降解析器
"""
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+)'

master_pat = re.compile('|'.join([NUM, PLUS, MINUS, TIMES,
                            DIVIDE, LPAREN, RPAREN, WS]))
# Tokenizer
Token = collections.namedtuple('Token', ['type', 'value'])


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)
        self.tok = None  # Last symbol consumed
        self.nexttok = None  # Next symbol tokenized
        self._advance()  # Load first lookahead token
        return self.expr()

    def _advance(self):
        'Advance one token ahead'
        self.tok, self.nexttok = self.nexttok, next(self.tokens, None)

    def _accept(self, toktype):
        'Test and consume the next token if it matches toktype'
        if self.nexttok and self.nexttok.type == toktype:
            self._advance()
            return True
        else:
            return False

    def _expect(self, toktype):
        'Consume next token if it matches toktype or raise SyntaxError'
        if not self._accept(toktype):
            raise SyntaxError('Expected ' + toktype)

    # Grammar rules follow
    def expr(self):
        "expression ::= term { ('+'|'-') term }*"
        exprval = self.term()
        while self._accept('PLUS') or self._accept('MINUS'):
            op = self.tok.type
            right = self.term()
            if op == 'PLUS':
                exprval += right
            elif op == 'MINUS':
                exprval -= right
        return exprval

    def term(self):
        "term ::= factor { ('*'|'/') factor }*"
        termval = self.factor()
        while self._accept('TIMES') or self._accept('DIVIDE'):
            op = self.tok.type
            right = self.factor()
            if op == 'TIMES':
                termval *= right
            elif op == 'DIVIDE':
                termval /= right
        return termval
    def factor(self):
        "factor ::= NUM | ( expr )"
        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(f"parse 2 result:{e.parse('2')}")
    print(f"parser 2 + 3 result:{e.parse('2 + 3')}")
    print(f"parser 2 + 3 * 4 result:{e.parse('2 + 3 * 4')}")
    print(f"parser 2 + (3 + 4) * 5 result:{e.parse('2 + (3 + 4) * 5')}")
    print(f"parser 2 + (3 + * 4) result:{e.parse('2 + (3 + * 4)')}")


if __name__ == '__main__':
    descent_parser()

执行py文件，输出结果如下：

parse 2 result:2
parser 2 + 3 result:5
parser 2 + 3 * 4 result:14
parser 2 + (3 + 4) * 5 result:37
Traceback (most recent call last):
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 112, in <module>
    descent_parser()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 108, in descent_parser
    print(f"parser 2 + (3 + * 4) result:{e.parse('2 + (3 + * 4)')}")
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 46, in parse
    return self.expr()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 71, in expr
    right = self.term()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 80, in term
    termval = self.factor()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 95, in factor
    exprval = self.expr()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 71, in expr
    right = self.term()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 80, in term
    termval = self.factor()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 99, in factor
    raise SyntaxError('Expected NUMBER or LPAREN')
SyntaxError: Expected NUMBER or LPAREN

文本解析是一个很大的主题，如果你在学习关于语法、解析算法等相关的背景知识，建议看一些编译器书籍。关于解析方面的内容太多，这里不能全部展开讲解。

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

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

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

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

则将它们转换成如下的方法：

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

每个方法要完成的任务很简单——从左至右遍历语法规则，处理每个令牌。从某种意义上讲，上述方法的目的要么是处理完语法规则，要么是产生一个语法错误，具体如下。

1）如果规则中的下一个符号是另外一个语法规则的名字（比如：term或factor），简单地调用同名的方法即可，这就是该算法中下降的由来。有时候，规则会调用已经执行的方法（比如，在factor::='('expr')'中对expr的调用），这就是算法中递归的由来。

2）如果规则中的下一个符号是一个特殊符号，比如()，则需要查找下一个令牌并确认其是一个精确匹配。如果令牌不匹配，就产生一个语法错误。上面示例中，_expect()方法就是用来做这一步的。

3）如果规则中的下一个符号为一些可能的选择项（比如：+或-），必须对每一种可能情况检查下一个令牌，只有当它匹配一个令牌的时候才能继续。这也是上面示例中_accept()方法的目的。它相当于_expect()方法的弱化版本，因为如果一个匹配找到了它会继续，但是如果没找到，不会产生错误而是回滚（允许后续的检查继续进行）。

4）对于有重复部分的规则（比如在规则表达式::=term{('+'|'-')term}*中），重复动作通过一个while循环来实现。循环主体会收集或处理所有的重复元素，直到找不到其他元素。

5）一旦整个语法规则处理完成，每个方法会返回某种结果给调用者。这就是在解析过程中值累加的原理。如在表达式求值程序中，返回值代表表达式解析后的部分结果。

6）最后所有值会在最顶层的语法规则方法中合并起来。

递归下降解析器可以用来实现非常复杂的解析。如Python语言本身是通过一个递归下降解析器去解释的。如果你对此感兴趣，可以通过查看Python代码文件Grammar来研究底层语法机制。

其实，通过手动方式去实现一个解析器会有很多局限。其中，一个局限就是它们不能被用于包含任何左递归的语法规则。如需翻译如下规则：

items ::= items ',' item
    | item

为了翻译上面的规则，可能会使用items()方法，代码如下：

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

不过，这个方法根本不能工作，它会产生一个无限递归错误。

语法规则本身也存在一定的局限。如我们想知道下面这个简单语法表述是否得当：

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()

该示例中，所有代码位于一个比较高的层次，只需要为令牌写正则表达式和规则匹配时的高阶处理函数。实际上，运行解析器、接收令牌等底层动作已经被库函数实现了。

如果你想在编程过程中来点挑战和刺激，编写解析器和编译器是不错的选择。

本周热推：
ASP.NET Core技术内幕与项目实战：基于DDD与前后端分离Rust编程：入门、实战与进阶SEO实战密码HTML+CSS+JavaScript网页制作：从入门到精通（第4版）MySQL数据库管理实战
上一章目录下一章