Python技法之簡(jiǎn)單遞歸下降Parser的實(shí)現(xiàn)方法
1. 算術(shù)運(yùn)算表達(dá)式求值
在上一篇博文《Python技法：用re模塊實(shí)現(xiàn)簡(jiǎn)易tokenizer》中，我們介紹了用正則表達(dá)式來(lái)匹配對(duì)應(yīng)的模式，以實(shí)現(xiàn)簡(jiǎn)單的分詞器。然而，正則表達(dá)式不是萬(wàn)能的，它本質(zhì)上是一種有限狀態(tài)機(jī)（finite state machine，F(xiàn)SM）, 無(wú)法處理含有遞歸語(yǔ)法的文本，比如算術(shù)運(yùn)算表達(dá)式。
要解析這類文本，需要另外一種特定的語(yǔ)法規(guī)則。我們這里介紹可以表示上下文無(wú)關(guān)文法（context free grammer）的語(yǔ)法規(guī)則巴科斯范式(BNF)和擴(kuò)展巴科斯范式(EBNF)。實(shí)際上，小到一個(gè)算術(shù)運(yùn)算表達(dá)式，大到幾乎所有程序設(shè)計(jì)語(yǔ)言，都是通過(guò)上下文無(wú)關(guān)文法來(lái)定義的。
對(duì)于簡(jiǎn)單的算術(shù)運(yùn)算表達(dá)式，假定我們已經(jīng)用分詞技術(shù)將其轉(zhuǎn)化為輸入的tokens流，如NUM+NUM*NUM（分詞方法參見(jiàn)上一篇博文）。
在此基礎(chǔ)上，我們定義BNF規(guī)則定義如下：
expr ::= expr + term
| expr - term
| term
term ::= term * factor
| term / factor
| factor
factor ::= (expr)
| NUM
當(dāng)然，這種計(jì)法還不夠簡(jiǎn)潔明了，我們實(shí)際采用的為EBNF形式：
expr ::= term { (+|-) term }*
term ::= factor { (*|/) factor }*
factor ::= (expr)
| NUM
BNF和EBNF每一條規(guī)則(形如::=的式子)都可以看做是一種替換，即左側(cè)的符號(hào)可以被右側(cè)的符號(hào)所替換。而解析的過(guò)程中我們嘗試將輸入文本同語(yǔ)法規(guī)則做匹配，通過(guò)BNF/EBNF來(lái)完成各種替換和擴(kuò)展。其中，EBNF中包含在{...}*中的規(guī)則是可選的，*意味著零個(gè)或多個(gè)重復(fù)項(xiàng)（參考正則表達(dá)式）。
下圖形象地展示了遞歸下降解析器(parser)中“遞歸”和“下降”部分和ENBF的關(guān)系：
在實(shí)際的解析過(guò)程中，我們對(duì)tokens流從左到右進(jìn)行掃描，在掃描的過(guò)程中處理token，如果卡住就產(chǎn)生一個(gè)語(yǔ)法錯(cuò)誤。對(duì)于規(guī)則，我們將每一條語(yǔ)法規(guī)則轉(zhuǎn)變?yōu)橐粋€(gè)函數(shù)或方法，比如上面的ENBF規(guī)則就轉(zhuǎn)換為下列的方法：
class ExpressionEvaluator():
...
def expr(self):
...
def term(self):
...
def factor(self):
...在調(diào)用某個(gè)規(guī)則對(duì)應(yīng)方法的過(guò)程中，如果我們發(fā)現(xiàn)接下來(lái)的符號(hào)需要采用另一個(gè)規(guī)則來(lái)匹配，則我們就會(huì)“下降”到另一個(gè)規(guī)則方法（如在expr中調(diào)用term，term中調(diào)用factor），則也就是遞歸下降中“下降”的部分。
有時(shí)也會(huì)調(diào)用已經(jīng)在執(zhí)行的方法（比如在expr中調(diào)用term，term中調(diào)用factor后，又在factor中調(diào)用expr，相當(dāng)于一條銜尾蛇），這也就是遞歸下降中“遞歸”的部分。
對(duì)于語(yǔ)法中出現(xiàn)的重復(fù)部分（例如expr ::= term { (+|-) term }*），我們則通過(guò)while循環(huán)來(lái)實(shí)現(xiàn)。
下面我們來(lái)看具體的代碼實(shí)現(xiàn)。首先是分詞部分，我們參照上一篇介紹分詞博客的代碼。
import re
import collections
# 定義匹配token的模式
NUM = r'(?P<NUM>\d+)' # \d表示匹配數(shù)字，+表示任意長(zhǎng)度
PLUS = r'(?P<PLUS>\+)' # 注意轉(zhuǎn)義
MINUS = r'(?P<MINUS>-)'
TIMES = r'(?P<TIMES>\*)' # 注意轉(zhuǎn)義
DIVIDE = r'(?P<DIVIDE>/)'
LPAREN = r'(?P<LPAREN>\()' # 注意轉(zhuǎn)義
RPAREN = r'(?P<RPAREN>\))' # 注意轉(zhuǎn)義
WS = r'(?P<WS>\s+)' # 別忘記空格，\s表示空格，+表示任意長(zhǎng)度
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': # 過(guò)濾掉空格符
yield tok
下面是表達(dá)式求值器的具體實(shí)現(xiàn)：
class ExpressionEvaluator():
""" 遞歸下降的Parser實(shí)現(xiàn)，每個(gè)語(yǔ)法規(guī)則都對(duì)應(yīng)一個(gè)方法，
使用 ._accept()方法來(lái)測(cè)試并接受當(dāng)前處理的token，不匹配不報(bào)錯(cuò)，
使用 ._except()方法來(lái)測(cè)試當(dāng)前處理的token，并在不匹配的時(shí)候拋出語(yǔ)法錯(cuò)誤
"""
def parse(self, text):
""" 對(duì)外調(diào)用的接口 """
self.tokens = generate_tokens(text)
self.tok, self.next_tok = None, None # 已匹配的最后一個(gè)token，下一個(gè)即將匹配的token
self._next() # 轉(zhuǎn)到下一個(gè)token
return self.expr() # 開(kāi)始遞歸
def _next(self):
""" 轉(zhuǎn)到下一個(gè)token """
self.tok, self.next_tok = self.next_tok, next(self.tokens, None)
def _accept(self, tok_type):
""" 如果下一個(gè)token與tok_type匹配，則轉(zhuǎn)到下一個(gè)token """
if self.next_tok and self.next_tok.type == tok_type:
self._next()
return True
else:
return False
def _except(self, tok_type):
""" 檢查是否匹配，如果不匹配則拋出異常 """
if not self._accept(tok_type):
raise SyntaxError("Excepted"+tok_type)
# 接下來(lái)是語(yǔ)法規(guī)則，每個(gè)語(yǔ)法規(guī)則對(duì)應(yīng)一個(gè)方法
def expr(self):
""" 對(duì)應(yīng)規(guī)則： expression ::= term { ('+'|'-') term }* """
exprval = self.term() # 取第一項(xiàng)
while self._accept("PLUS") or self._accept("DIVIDE"): # 如果下一項(xiàng)是"+"或"-"
op = self.tok.type
# 再取下一項(xiàng)，即運(yùn)算符右值
right = self.term()
if op == "PLUS":
exprval += right
elif op == "MINUS":
exprval -= right
return exprval
def term(self):
""" 對(duì)應(yīng)規(guī)則： term ::= factor { ('*'|'/') factor }* """
termval = self.factor() # 取第一項(xiàng)
while self._accept("TIMES") or self._accept("DIVIDE"): # 如果下一項(xiàng)是"+"或"-"
op = self.tok.type
# 再取下一項(xiàng)，即運(yùn)算符右值
right = self.factor()
if op == "TIMES":
termval *= right
elif op == "DIVIDE":
termval /= right
return termval
def factor(self):
""" 對(duì)應(yīng)規(guī)則： factor ::= NUM | ( expr ) """
if self._accept("NUM"): # 遞歸出口
return int(self.tok.value)
elif self._accept("LPAREN"):
exprval = self.expr() # 繼續(xù)遞歸下去求表達(dá)式值
self._except("RPAREN") # 別忘記檢查是否有右括號(hào)，沒(méi)有則拋出異常
return exprval
else:
raise SyntaxError("Expected NUMBER or LPAREN")
我們輸入以下表達(dá)式進(jìn)行測(cè)試：
e = ExpressionEvaluator()
print(e.parse("2"))
print(e.parse("2+3"))
print(e.parse("2+3*4"))
print(e.parse("2+(3+4)*5"))
求值結(jié)果如下：
2
5
14
37
如果我們輸入的文本不符合語(yǔ)法規(guī)則：
print(e.parse("2 + (3 + * 4)"))
則會(huì)拋出SyntaxError異常：Expected NUMBER or LPAREN。
綜上，可見(jiàn)我們的表達(dá)式求值算法運(yùn)行正確。
2. 生成表達(dá)式樹(shù)
上面我們是得到表達(dá)式的結(jié)果，但是如果我們想分析表達(dá)式的結(jié)構(gòu)，生成一棵簡(jiǎn)單的表達(dá)式解析樹(shù)呢？那么我們需要對(duì)上述類的方法做一定修改：
class ExpressionTreeBuilder(ExpressionEvaluator):
def expr(self):
""" 對(duì)應(yīng)規(guī)則： expression ::= term { ('+'|'-') term }* """
exprval = self.term() # 取第一項(xiàng)
while self._accept("PLUS") or self._accept("DIVIDE"): # 如果下一項(xiàng)是"+"或"-"
op = self.tok.type
# 再取下一項(xiàng)，即運(yùn)算符右值
right = self.term()
if op == "PLUS":
exprval = ('+', exprval, right)
elif op == "MINUS":
exprval -= ('-', exprval, right)
return exprval
def term(self):
""" 對(duì)應(yīng)規(guī)則： term ::= factor { ('*'|'/') factor }* """
termval = self.factor() # 取第一項(xiàng)
while self._accept("TIMES") or self._accept("DIVIDE"): # 如果下一項(xiàng)是"+"或"-"
op = self.tok.type
# 再取下一項(xiàng)，即運(yùn)算符右值
right = self.factor()
if op == "TIMES":
termval = ('*', termval, right)
elif op == "DIVIDE":
termval = ('/', termval, right)
return termval
def factor(self):
""" 對(duì)應(yīng)規(guī)則： factor ::= NUM | ( expr ) """
if self._accept("NUM"): # 遞歸出口
return int(self.tok.value) # 字符串轉(zhuǎn)整形
elif self._accept("LPAREN"):
exprval = self.expr() # 繼續(xù)遞歸下去求表達(dá)式值
self._except("RPAREN") # 別忘記檢查是否有右括號(hào)，沒(méi)有則拋出異常
return exprval
else:
raise SyntaxError("Expected NUMBER or LPAREN")
輸入下列表達(dá)式測(cè)試一下：
print(e.parse("2+3"))
print(e.parse("2+3*4"))
print(e.parse("2+(3+4)*5"))
print(e.parse('2+3+4'))
以下是生成結(jié)果：
('+', 2, 3)
('+', 2, ('*', 3, 4))
('+', 2, ('*', ('+', 3, 4), 5))
('+', ('+', 2, 3), 4)
可以看到表達(dá)式樹(shù)生成正確。
我們上面的這個(gè)例子非常簡(jiǎn)單，但遞歸下降的解析器也可以用來(lái)實(shí)現(xiàn)相當(dāng)復(fù)雜的解析器，例如Python代碼就是通過(guò)一個(gè)遞歸下降解析器解析的。您要是對(duì)此跟感興趣可以檢查Python源碼中的Grammar文件來(lái)一探究竟。然而，下面我們接著會(huì)看到，自己動(dòng)手寫(xiě)一個(gè)解析器會(huì)面對(duì)各種陷阱和挑戰(zhàn)。
左遞歸和運(yùn)算符優(yōu)先級(jí)陷阱
任何涉及左遞歸形式的語(yǔ)法規(guī)則，都沒(méi)法用遞歸下降parser來(lái)解決。所謂左遞歸，即規(guī)則式子右側(cè)最左邊的符號(hào)是規(guī)則頭，比如對(duì)于以下規(guī)則：
items ::= items ',' item
| item
完成該解析你可能會(huì)定義以下方法：
def items(self):
itemsval = self.items() # 取第一項(xiàng)，然而此處會(huì)無(wú)窮遞歸！
if itemsval and self._accept(','):
itemsval.append(self.item())
else:
itemsval = [self.item()]
這樣做會(huì)在第一行就無(wú)窮地調(diào)用self.items()從而產(chǎn)生無(wú)窮遞歸錯(cuò)誤。
還有一種是語(yǔ)法規(guī)則自身的錯(cuò)誤，比如運(yùn)算符優(yōu)先級(jí)。我們?nèi)绻鲆曔\(yùn)算符優(yōu)先級(jí)直接將表達(dá)式簡(jiǎn)化如下：
expr ::= factor { ('+'|'-'|'*'|'/') factor }*
factor ::= '(' expr ')'
| NUM
這個(gè)語(yǔ)法從技術(shù)上可以實(shí)現(xiàn)，但是沒(méi)有遵守計(jì)算順序約定，導(dǎo)致"3+4*5"的運(yùn)算結(jié)果為35，而不是預(yù)期的23。故此處需要用獨(dú)立的expr和term規(guī)則來(lái)確保計(jì)算結(jié)果的正確性。
3. 相關(guān)包
最后，對(duì)于真正復(fù)雜的語(yǔ)法解析，建議采用PyParsing或PLY這樣的解析工具。如果你對(duì)Python代碼的抽象語(yǔ)法樹(shù)感興趣，可以看下Python自帶的ast模塊。
參考
- [1] Martelli A, Ravenscroft A, Ascher D. Python cookbook[M]. " O'Reilly Media, Inc.", 2015.
- [2] https://cs61a.org/study-guide/regex/
- [3] https://cs61a.org/study-guide/bnf/
- [4] https://zh.wikipedia.org/wiki/巴科斯范式
總結(jié)
到此這篇關(guān)于Python技法之簡(jiǎn)單遞歸下降Parser實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Python遞歸下降Parser內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了python先序遍歷二叉樹(shù)問(wèn)題，簡(jiǎn)單分析了問(wèn)題，然后向大家分享了代碼示例，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11
python 默認(rèn)參數(shù)問(wèn)題的陷阱
本文給大家講述的是python 默認(rèn)參數(shù)問(wèn)題的陷阱，有需要的小伙伴可以參考下2016-02-02
詳解python 字符串和日期之間轉(zhuǎn)換 StringAndDate
這篇文章主要介紹了python 字符串和日期之間轉(zhuǎn)換 StringAndDate簡(jiǎn)單實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了python基礎(chǔ)教程之序列詳解,本文的序列包含元組（tuple）、列表（list）等數(shù)據(jù)類型,需要的朋友可以參考下2014-08-08
將python圖片轉(zhuǎn)為二進(jìn)制文本的實(shí)例
今天小編就為大家分享一篇將python圖片轉(zhuǎn)為二進(jìn)制文本的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-01-01
新手入門(mén)Python編程的8個(gè)實(shí)用建議
這篇文章主要介紹了Python編程的8個(gè)實(shí)用建議,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07
Python使用matplotlib時(shí)顯示中文亂碼解決方法(或更改字體)
這篇文章主要給大家介紹了關(guān)于Python使用matplotlib時(shí)顯示中文亂碼的解決方法(或更改字體),在Matplotlib中,中文亂碼問(wèn)題通常出現(xiàn)在圖表的標(biāo)題、標(biāo)簽和刻度上,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-12-12
最新PyCharm從安裝到PyCharm永久激活再到PyCharm官方中文漢化詳細(xì)教程
這篇文章涵蓋了最新版PyCharm安裝教程，最新版PyCharm永久激活碼教程，PyCharm官方中文(漢化)版安裝教程圖文并茂非常詳細(xì),需要的朋友可以參考下2020-11-11
這篇文章主要介紹了生成Jupyter Lab快捷方式的小技巧，操作迅猛，花費(fèi)時(shí)間少，步驟詳細(xì)，有需要的朋友可以參考下，希望可以對(duì)廣大讀者朋友有所幫助2021-09-09
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)俄羅斯方塊小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04