2.19 實現一個簡單的遞歸下降分析器 · Python3 CookBook中文版

## 問題你想根據一組語法規則解析文本并執行命令，或者構造一個代表輸入的抽象語法樹。如果語法非常簡單，你可以自己寫這個解析器，而不是使用一些框架。 ## 解決方案在這個問題中，我們集中討論根據特殊語法去解析文本的問題。為了這樣做，你首先要以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` 的表達式。這個表達式先要通過使用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 }*` )就會被清理掉。在一個成功的解析中，整個右邊部分會完全展開來匹配輸入令牌流。有了前面的知識背景，下面我們舉一個簡單示例來展示如何構建一個遞歸下降表達式求值程序： #!/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+)' 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(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() ## 討論文本解析是一個很大的主題，一般會占用學生學習編譯課程時剛開始的三周時間。如果你在找尋關于語法，解析算法等相關的背景知識的話，你應該去看一下編譯器書籍。很顯然，關于這方面的內容太多，不可能在這里全部展開。盡管如此，編寫一個遞歸下降解析器的整體思路是比較簡單的。開始的時候，你先獲得所有的語法規則，然后將其轉換為一個函數或者方法。因此如果你的語法類似這樣： 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 為了這樣做，你可能會像下面這樣使用 `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模塊也值得去看一下。