问题
我们需要根据一组语法规则来解析文本，以此执行相应的操作或构建一个抽象语法树来表示输入。语法规则很简单，因此我们倾向于自己编写解析器而不是使用某种解析器框架。
解决方案
在这个问题中，我们把重点放在根据特定的语法来解析文本上。要做到这些，应该以 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 中，部分包括在{ ... }*中的规则是可选的。*意味着零个或更多重复项（和在正则表达式中的意义相同）。
现在，如果我们对 BNF 还不熟悉的话，可以把它看做是规则替换或取代的一种规范形式，左侧的符号可以被右侧的符号所取代（反之亦然）。一般来说，在解析的过程中我们会尝试将输入的文本同语法做匹配，通过 BNF 来完成各种替换和扩展。为了说明，假设正在解析一个类似于 3 + 4 * 5 这样的表达式。这个表达式首先应该被分解为标记流，这可以使用 2.18 节中描述的技术来实现。得到的结果可能是下面这样的标记序列：
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 }）就会消失。在一个成功的解析过程中，整个右手侧部分会完全根据匹配到的输入标记流来相应地扩展。
有了前面这些基础，下面就向各位展示如何构建一个递归下降的表达式计算器：
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')
下面是以交互式的方式使用 ExpressionEvaluator 类的示例：
>>> e = ExpressionEvaluator() >>> e.parse('2') 2 >>> e.parse('2 + 3') 5 >>> e.parse('2 + 3 * 4') 14 >>> e.parse('2 + (3 + 4) * 5') 37 >>> 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 >>>
如果我们想做的不只是纯粹的计算，那就需要修改 ExpressionEvaluator 类来实现。比如，下面的实现构建了一棵简单的解析树：
class ExpressionTreeBuilder(ExpressionEvaluator): 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 = ('+', exprval, right) elif op == 'MINUS': exprval = ('-', 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 = ('*', termval, right) elif op == 'DIVIDE': termval = ('/', 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')
下面的示例展示了它是如何工作的：
>>> e = ExpressionTreeBuilder() >>> e.parse('2 + 3') ('+', 2, 3) >>> e.parse('2 + 3 * 4') ('+', 2, ('*', 3, 4)) >>> e.parse('2 + (3 + 4) * 5') ('+', 2, ('*', ('+', 3, 4), 5)) >>> e.parse('2 + 3 + 4') ('+', ('+', 2, 3), 4) >>>
讨论
文本解析是一个庞大的主题，一般会占用学生们编译原理课程的前三周时间。如果你正在寻找有关语法、解析算法和其他相关信息的背景知识，那么应该去找一本编译器方面的图书来读。无需赘言，本书是不会重复那些内容的。
然而，要编写一个递归下降的解析器，总体思路还是比较简单的。我们要将每一条语法规则转变为一个函数或方法。因此，如果我们的语法看起来是这样的：
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()方法的目的所在。这有点像_except()的弱化版，在_accept()中如果有匹配满足，就前进到下一步，但如果没有匹配，它只是简单的回退而不会引发一个错误（这样检查才可以继续进行下去）。
-
对于语法规则中出现的重复部分（例如 expr ::=term { ('+' | '-') term }*）,这是通过 while 循环来实现的。一般在循环体中收集或处理所有的重复项，直到无法找到更多的重复项为止。
-
一旦整个语法规则都已经处理完，每个方法就返回一些结果给调用者。这就是在解析过程中将值进行传递的方法。比如，在计算器表达式中，表达式解析的部分结果会作为值来返回。最终它们会结合在一起，在最顶层的语法规则方法中得到执行。
尽管本节给出的例子很简单，但递归下降解析器可以用来实现相当复杂的解析器。例如，Python 代码本身也是通过一个递归下降解析器来解释的。如果对此很感兴趣，可以通过检查 Python 源代码中的 Grammar/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()
在这份代码中会发现所有的东西都是以一种更高层的方式来定义的。我们只需编写匹配标记符号的正则表达式，以及当匹配各种语法规则时所需要的高层处理函数就行了。而实际运行解析器、接收符号标记等都完全由库来实现。
下面是如何使用解析器对象的示例：
>>> parser.parse('2') 2 >>> parser.parse('2+3') 5 >>> parser.parse('2+(3+4)*5') 37 >>>
如果想在编程中增加一点激动兴奋的感觉，编写解析器和编译器会是非常有趣的课题。再次说明，一本编译器方面的教科书会涵盖许多理论之下的底层细节。但是，在网上同样也能找到许多优秀的在线资源。Python 自带的 ast 模块也同样值得去看看。
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于