問(wèn)題

你想根據(jù)一組語(yǔ)法規(guī)則解析文本并執(zhí)行命令，或者構(gòu)造一個(gè)代表輸入的抽象語(yǔ)法樹(shù)。 如果語(yǔ)法非常簡(jiǎn)單，你可以不去使用一些框架，而是自己寫這個(gè)解析器。

解決方案

在這個(gè)問(wèn)題中，我們集中討論根據(jù)特殊語(yǔ)法去解析文本的問(wèn)題。 為了這樣做，你首先要以BNF或者EBNF形式指定一個(gè)標(biāo)準(zhǔn)語(yǔ)法。 比如，一個(gè)簡(jiǎn)單數(shù)學(xué)表達(dá)式語(yǔ)法可能像下面這樣：

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中，被包含在 {...}* 中的規(guī)則是可選的。*代表0次或多次重復(fù)(跟正則表達(dá)式中意義是一樣的)。

現(xiàn)在，如果你對(duì)BNF的工作機(jī)制還不是很明白的話，就把它當(dāng)做是一組左右符號(hào)可相互替換的規(guī)則。 一般來(lái)講，解析的原理就是你利用BNF完成多個(gè)替換和擴(kuò)展以匹配輸入文本和語(yǔ)法規(guī)則。 為了演示，假設(shè)你正在解析形如 3 + 4 * 5 的表達(dá)式。 這個(gè)表達(dá)式先要通過(guò)使用2.18節(jié)中介紹的技術(shù)分解為一組令牌流。 結(jié)果可能是像下列這樣的令牌序列：

NUM + NUM * NUM

在此基礎(chǔ)上， 解析動(dòng)作會(huì)試著去通過(guò)替換操作匹配語(yǔ)法到輸入令牌：

exprexpr ::= 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

下面所有的解析步驟可能需要花點(diǎn)時(shí)間弄明白，但是它們?cè)矶际遣檎逸斎氩⒃囍テヅ湔Z(yǔ)法規(guī)則。 第一個(gè)輸入令牌是NUM，因此替換首先會(huì)匹配那個(gè)部分。 一旦匹配成功，就會(huì)進(jìn)入下一個(gè)令牌+，以此類推。 當(dāng)已經(jīng)確定不能匹配下一個(gè)令牌的時(shí)候，右邊的部分(比如 { (*/) factor }* )就會(huì)被清理掉。 在一個(gè)成功的解析中，整個(gè)右邊部分會(huì)完全展開(kāi)來(lái)匹配輸入令牌流。

有了前面的知識(shí)背景，下面我們舉一個(gè)簡(jiǎn)單示例來(lái)展示如何構(gòu)建一個(gè)遞歸下降表達(dá)式求值程序：

#!/usr/bin/env python# -*- encoding: utf-8 -*-'''Topic: 下降解析器Desc :'''import reimport collections# Token specificationNUM = 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]))# TokenizerToken = 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# Parserclass 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 LPARENif __name__ == ’__main__’: descent_parser()

討論

文本解析是一個(gè)很大的主題， 一般會(huì)占用學(xué)生學(xué)習(xí)編譯課程時(shí)剛開(kāi)始的三周時(shí)間。 如果你在找尋關(guān)于語(yǔ)法，解析算法等相關(guān)的背景知識(shí)的話，你應(yīng)該去看一下編譯器書籍。 很顯然，關(guān)于這方面的內(nèi)容太多，不可能在這里全部展開(kāi)。

盡管如此，編寫一個(gè)遞歸下降解析器的整體思路是比較簡(jiǎn)單的。 開(kāi)始的時(shí)候，你先獲得所有的語(yǔ)法規(guī)則，然后將其轉(zhuǎn)換為一個(gè)函數(shù)或者方法。 因此如果你的語(yǔ)法類似這樣：

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

你應(yīng)該首先將它們轉(zhuǎn)換成一組像下面這樣的方法：

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

每個(gè)方法要完成的任務(wù)很簡(jiǎn)單 - 它必須從左至右遍歷語(yǔ)法規(guī)則的每一部分，處理每個(gè)令牌。 從某種意義上講，方法的目的就是要么處理完語(yǔ)法規(guī)則，要么產(chǎn)生一個(gè)語(yǔ)法錯(cuò)誤。 為了這樣做，需采用下面的這些實(shí)現(xiàn)方法：

如果規(guī)則中的下個(gè)符號(hào)是另外一個(gè)語(yǔ)法規(guī)則的名字(比如term或factor)，就簡(jiǎn)單的調(diào)用同名的方法即可。 這就是該算法中”下降”的由來(lái) - 控制下降到另一個(gè)語(yǔ)法規(guī)則中去。 有時(shí)候規(guī)則會(huì)調(diào)用已經(jīng)執(zhí)行的方法(比如，在 factor ::= ’(’expr ’)’ 中對(duì)expr的調(diào)用)。 這就是算法中”遞歸”的由來(lái)。 如果規(guī)則中下一個(gè)符號(hào)是個(gè)特殊符號(hào)(比如()，你得查找下一個(gè)令牌并確認(rèn)是一個(gè)精確匹配)。 如果不匹配，就產(chǎn)生一個(gè)語(yǔ)法錯(cuò)誤。這一節(jié)中的 _expect() 方法就是用來(lái)做這一步的。 如果規(guī)則中下一個(gè)符號(hào)為一些可能的選擇項(xiàng)(比如 + 或 -)， 你必須對(duì)每一種可能情況檢查下一個(gè)令牌，只有當(dāng)它匹配一個(gè)的時(shí)候才能繼續(xù)。 這也是本節(jié)示例中 _accept() 方法的目的。 它相當(dāng)于_expect()方法的弱化版本，因?yàn)槿绻粋€(gè)匹配找到了它會(huì)繼續(xù)， 但是如果沒(méi)找到，它不會(huì)產(chǎn)生錯(cuò)誤而是回滾(允許后續(xù)的檢查繼續(xù)進(jìn)行)。 對(duì)于有重復(fù)部分的規(guī)則(比如在規(guī)則表達(dá)式 ::= term { (’+’|’-’) term }* 中)， 重復(fù)動(dòng)作通過(guò)一個(gè)while循環(huán)來(lái)實(shí)現(xiàn)。 循環(huán)主體會(huì)收集或處理所有的重復(fù)元素直到?jīng)]有其他元素可以找到。 一旦整個(gè)語(yǔ)法規(guī)則處理完成，每個(gè)方法會(huì)返回某種結(jié)果給調(diào)用者。 這就是在解析過(guò)程中值是怎樣累加的原理。 比如，在表達(dá)式求值程序中，返回值代表表達(dá)式解析后的部分結(jié)果。 最后所有值會(huì)在最頂層的語(yǔ)法規(guī)則方法中合并起來(lái)。

盡管向你演示的是一個(gè)簡(jiǎn)單的例子，遞歸下降解析器可以用來(lái)實(shí)現(xiàn)非常復(fù)雜的解析。 比如，Python語(yǔ)言本身就是通過(guò)一個(gè)遞歸下降解析器去解釋的。 如果你對(duì)此感興趣，你可以通過(guò)查看Python源碼文件Grammar/Grammar來(lái)研究下底層語(yǔ)法機(jī)制。 看完你會(huì)發(fā)現(xiàn)，通過(guò)手動(dòng)方式去實(shí)現(xiàn)一個(gè)解析器其實(shí)會(huì)有很多的局限和不足之處。

其中一個(gè)局限就是它們不能被用于包含任何左遞歸的語(yǔ)法規(guī)則中。比如，假如你需要翻譯下面這樣一個(gè)規(guī)則：

items ::= items ’,’ item | item

為了這樣做，你可能會(huì)像下面這樣使用 items() 方法：

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

唯一的問(wèn)題是這個(gè)方法根本不能工作，事實(shí)上，它會(huì)產(chǎn)生一個(gè)無(wú)限遞歸錯(cuò)誤。

關(guān)于語(yǔ)法規(guī)則本身你可能也會(huì)碰到一些棘手的問(wèn)題。 比如，你可能想知道下面這個(gè)簡(jiǎn)單扼語(yǔ)法是否表述得當(dāng)：

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

這個(gè)語(yǔ)法看上去沒(méi)啥問(wèn)題，但是它卻不能察覺(jué)到標(biāo)準(zhǔn)四則運(yùn)算中的運(yùn)算符優(yōu)先級(jí)。 比如，表達(dá)式 '3 + 4 * 5' 會(huì)得到35而不是期望的23. 分開(kāi)使用”expr”和”term”規(guī)則可以讓它正確的工作。

對(duì)于復(fù)雜的語(yǔ)法，你最好是選擇某個(gè)解析工具比如PyParsing或者是PLY。 下面是使用PLY來(lái)重寫表達(dá)式求值程序的代碼：

from ply.lex import lexfrom ply.yacc import yacc# Token listtokens = [ ’NUM’, ’PLUS’, ’MINUS’, ’TIMES’, ’DIVIDE’, ’LPAREN’, ’RPAREN’ ]# Ignored characterst_ignore = ’ tn’# Token specifications (as regexs)t_PLUS = r’+’t_MINUS = r’-’t_TIMES = r’*’t_DIVIDE = r’/’t_LPAREN = r’(’t_RPAREN = r’)’# Token processing functionsdef t_NUM(t): r’d+’ t.value = int(t.value) return t# Error handlerdef t_error(t): print(’Bad character: {!r}’.format(t.value[0])) t.skip(1)# Build the lexerlexer = lex()# Grammar rules and handler functionsdef 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()

這個(gè)程序中，所有代碼都位于一個(gè)比較高的層次。你只需要為令牌寫正則表達(dá)式和規(guī)則匹配時(shí)的高階處理函數(shù)即可。 而實(shí)際的運(yùn)行解析器，接受令牌等等底層動(dòng)作已經(jīng)被庫(kù)函數(shù)實(shí)現(xiàn)了。

下面是一個(gè)怎樣使用得到的解析對(duì)象的例子：

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

如果你想在你的編程過(guò)程中來(lái)點(diǎn)挑戰(zhàn)和刺激，編寫解析器和編譯器是個(gè)不錯(cuò)的選擇。 再次，一本編譯器的書籍會(huì)包含很多底層的理論知識(shí)。不過(guò)很多好的資源也可以在網(wǎng)上找到。 Python自己的ast模塊也值得去看一下。

以上就是Python實(shí)現(xiàn)一個(gè)簡(jiǎn)單的遞歸下降分析器的詳細(xì)內(nèi)容，更多關(guān)于Python實(shí)現(xiàn)遞歸下降分析器的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！