使用70行Python代碼實現(xiàn)一個遞歸下降解析器的教程
第一步：標記化
處理表達式的第一步就是將其轉(zhuǎn)化為包含一個個獨立符號的列表。這一步很簡單，且不是本文的重點，因此在此處我省略了很多。
首先，我定義了一些標記（數(shù)字不在此中，它們是默認的標記）和一個標記類型：
token_map = {'+':'ADD', '-':'ADD',
'*':'MUL', '/':'MUL',
'(':'LPAR', ')':'RPAR'}
Token = namedtuple('Token', ['name', 'value'])
下面就是我用來標記 `expr` 表達式的代碼：
split_expr = re.findall('[\d.]+|[%s]' % ''.join(token_map), expr)
tokens = [Token(token_map.get(x, 'NUM'), x) for x in split_expr]
第一行是將表達式分割為基本標記的技巧，因此
'1.2 / ( 11+3)' --> ['1.2', '/', '(', '11', '+', '3', ')']
下一行命名標記，這樣分析器就能通過分類識別它們：
['1.2', '/', '(', '11', '+', '3', ')']
->
[Token(name='NUM', value='1.2'), Token(name='MUL', value='/'), Token(name='LPAR', value='('), Token(name='NUM', value='11'), Token(name='ADD', value='+'), Token(name='NUM', value='3'), Token(name='RPAR', value=')')]
任何不在 token_map 中的標記被假定為數(shù)字。我們的分詞器缺少稱為驗證的屬性，以防止非數(shù)字被接受，但幸運的是，運算器將在以后處理它。
就是這樣
第二步: 語法定義
我選擇的解析器實現(xiàn)自一個本地垂直解析器，其來源于LL解析器的一個簡單版本。它是一個最簡單的解析器實現(xiàn)，事實上，只有僅僅14行代碼。它是一種自上而下的解析器，這意味著解析器從最上層規(guī)則開始解析（like:expression），然后以遞歸方式嘗試按照其子規(guī)則方式解析，直至符合最下層的規(guī)則（like:number）。換句話解釋，當自底向上解析器（LR）逐步地收縮標記，使規(guī)則被包含在其它規(guī)則中，直到最后僅剩下一個規(guī)則，而自頂向下解析器（LL）逐步展開規(guī)則并進入到少數(shù)的抽象規(guī)則，直到它能夠完全匹配輸入的標記。
在深入到實際的解析器實現(xiàn)之前，我們可對語法進行討論。在我之前發(fā)表的文章中，我使用過LR解析器，我可以像如下方式定義計算器語法（標記使用大寫字母表示）：
add: add ADD mul | mul;
mul: mul MUL atom | atom;
atom: NUM | '(' add ')' | neg;
neg: '-' atom;
(如果您還不理解上述語法，請閱讀我之前發(fā)表的文章)
現(xiàn)在我使用LL解析器，以如下方式定義計算器的語法：
rule_map = {
'add' : ['mul ADD add', 'mul'],
'mul' : ['atom MUL mul', 'atom'],
'atom': ['NUM', 'LPAR add RPAR', 'neg'],
'neg' : ['ADD atom'],
}
大家可以看到，這里有一個微妙的變化。有關(guān)"add and mul"的遞歸定義被反轉(zhuǎn)了。這是個非常重要的細節(jié)，我會向大家詳細說明這一點。
LR版本使用了左遞歸的模式。當LL解析器遇到遞歸的時候，它會嘗試去匹配規(guī)則。所以，當左遞歸發(fā)生是，解析器會進入無窮遞歸。甚至連聰明的LL解析器例如ANTLR也逃避不了這個問題，它會以友好的錯誤提示代替無窮的遞歸，而不像我們這個玩具解析器那樣。
左遞歸可以很容易的轉(zhuǎn)變?yōu)橛疫f歸，我就這么做的。但是解析器并不是那么簡單，它又會產(chǎn)生另一個問題：當左遞歸正確的解析 3-2-1 為(3-2)-1，而右遞歸卻錯誤的解析為3-(2-1)。我還沒想到一個簡單的解決辦法，所以為了讓事情簡單，我決定讓它繼續(xù)使用錯誤的解析格式，并在后面處理這個問題（請看步驟4）
第三步：解析為一個AST
算法其實很簡單。我們會定義一個接收兩個參數(shù)的遞歸方法：第一個參數(shù)是我們要嘗試匹配的規(guī)則名稱，第二個參數(shù)是我們要保留的標識列表。我們從add（最上層規(guī)則）方法開始，其已包含完整的標識列表，遞歸調(diào)用已非常明確。方法將返回一個數(shù)組，其包含元素為：一個是當前匹配項，另一個是保留匹配的標識列表。我們將實現(xiàn)標識匹配功能，以使這段代碼可用（它們都是字符串類型；一個是大寫格式，另一個是小寫格式）。
以下是解析器實現(xiàn)的代碼：
RuleMatch = namedtuple('RuleMatch', ['name', 'matched'])
def match(rule_name, tokens):
if tokens and rule_name == tokens[0].name: # 是否匹配標識?
return RuleMatch(tokens[0], tokens[1:])
for expansion in rule_map.get(rule_name, ()): # 是否匹配規(guī)則?
remaining_tokens = tokens
matched_subrules = []
for subrule in expansion.split():
matched, remaining_tokens = match(subrule, remaining_tokens)
if not matched:
break # 運氣不好，跳出循環(huán)，處理下一個擴展定義!
matched_subrules.append(matched)
else:
return RuleMatch(rule_name, matched_subrules), remaining_tokens
return None, None # 無匹配結(jié)果
代碼4至5行說明：如果規(guī)則名稱（rule_name)確實是一個標識，并被包含在標識列表（tokens）中，同時檢查其是否匹配當前標識。如果是，表達式將返回匹配方法，標識列表任然進行使用。
代碼第6行說明：迭代將循環(huán)檢查是否匹配該規(guī)則名稱對應(yīng)的子規(guī)則，通過遞歸實現(xiàn)每條子規(guī)則的匹配。如果規(guī)則名稱滿足匹配標識的條件，get()方法將返回一個空數(shù)組，同時代碼將返回空值（見16行）。
第9-15行，實現(xiàn)迭代當前的sub-rule，并嘗試順序地匹配他們。每次迭代都盡可能多的匹配標識。如果某一個標識無法匹配，我們就會放棄整個sub-rule。但是，如果所有的標識都匹配成功，我們就到達else語句，并返回rule_name的匹配值，還有剩下標識。
現(xiàn)在運行并看看1.2/(11+3)的結(jié)果。
>>> tokens = [Token(name='NUM', value='1.2'), Token(name='MUL', value='/'), Token(name='LPAR', value='('), Token (name='NUM', value='11'), Token(name='ADD', value='+'), Token(name='NUM', value='3'), Token(name='RPAR', value=')')]
>>> match('add', tokens)
(RuleMatch(name='add', matched=[RuleMatch(name='mul', matched=[RuleMatch(name='atom', matched=[Token(name='NUM', value='1.2')]), Token(name='MUL', value='/'), RuleMatch(name='mul', matched=[RuleMatch(name='atom', matched=[Token(name='LPAR', value='('), RuleMatch(name='add', matched=[RuleMatch(name='mul', matched=[RuleMatch(name='atom', matched=[Token(name='NUM', value='11')])]), Token(name='ADD', value='+'), RuleMatch(name='add', matched=[RuleMatch(name='mul', matched=[RuleMatch(name='atom', matched=[Token(name='NUM', value='3')])])])]), Token(name='RPAR', value=')')])])])]), [])
結(jié)果是一個tuple，當然我們并沒有看到有剩下的標識。匹配結(jié)果并不易于閱讀，所以讓我吧結(jié)果畫成一個圖：
add
mul
atom
NUM '1.2'
MUL '/'
mul
atom
LPAR '('
add
mul
atom
NUM '11'
ADD '+'
add
mul
atom
NUM '3'
RPAR ')'
這就是概念上的AST。通過你思維邏輯，或者在紙上描繪，想象解析器是如何運作的，這樣是個很好的鍛煉。我不敢說這樣是必須的，除非你想神交。你可以通過AST來幫助你實現(xiàn)正確的算法。
到目前為止，我們已經(jīng)完成了可以處理二進制運算，一元運算，括號和操作符優(yōu)先權(quán)的解析器。
現(xiàn)在只剩下一個錯誤待解決，下面的步驟我們將解決這個錯誤。
第四步：后續(xù)處理
我的解析器并非在任何場合管用。最重要的一點是，它并不能處理左遞歸，迫使我把代碼寫成右遞歸方式。這樣導(dǎo)致，解析 8/4/2 這個表達式的時候，AST結(jié)果如下：
add
mul
atom
NUM 8
MUL '/'
mul
atom
NUM 4
MUL '/'
mul
atom
NUM 2
如果我們嘗試通過AST計算結(jié)果，我們將會優(yōu)先計算4/2，這當然是錯誤的。一些LL解析器選擇修正樹里面的關(guān)聯(lián)性。這樣需要編寫多行代碼;)。這個不采納，我們需要使它扁平化。算法很簡單：對于AST里面的每個規(guī)則 1)需要修正 2)是一個二進制運算 （擁有sub-rules）3) 右邊的操作符同樣的規(guī)則：使后者扁平成前者。通過“扁平”，我意思是在其父節(jié)點的上下文中，通過節(jié)點的兒子代替這個節(jié)點。因為我們的穿越是DFS是后序的，意味著它從樹的邊緣開始，并一直到達樹根，效果將會累加。如下是代碼：
fix_assoc_rules = 'add', 'mul'
def _recurse_tree(tree, func):
return map(func, tree.matched) if tree.name in rule_map else tree[1]
def flatten_right_associativity(tree):
new = _recurse_tree(tree, flatten_right_associativity)
if tree.name in fix_assoc_rules and len(new)==3 and new[2].name==tree.name:
new[-1:] = new[-1].matched
return RuleMatch(tree.name, new)
這段代碼可以讓任何結(jié)構(gòu)的加法或乘法表達式變成一個平面列表（不會混淆）。括號會破壞順序，當然，它們不會受到影響。
基于以上的這些，我可以把代碼重構(gòu)成左關(guān)聯(lián)：
def build_left_associativity(tree):
new_nodes = _recurse_tree(tree, build_left_associativity)
if tree.name in fix_assoc_rules:
while len(new_nodes)>3:
new_nodes[:3] = [RuleMatch(tree.name, new_nodes[:3])]
return RuleMatch(tree.name, new_nodes)
但是，我并不會這樣做。我需要更少的代碼，并且把計算代碼換成處理列表會比重構(gòu)整棵樹需要更少的代碼。
第五步：運算器
對樹的運算非常簡單。只需用與后處理的代碼相似的方式對樹進行遍歷（即 DFS 后序），并按照其中的每條規(guī)則進行運算。對于運算器，因為我們使用了遞歸算法，所以每條規(guī)則必須只包含數(shù)字和操作符。代碼如下：
bin_calc_map = {'*':mul, '/':div, '+':add, '-':sub}
def calc_binary(x):
while len(x) > 1:
x[:3] = [ bin_calc_map[x[1]](x[0], x[2]) ]
return x[0]
calc_map = {
'NUM' : float,
'atom': lambda x: x[len(x)!=1],
'neg' : lambda (op,num): (num,-num)[op=='-'],
'mul' : calc_binary,
'add' : calc_binary,
}
def evaluate(tree):
solutions = _recurse_tree(tree, evaluate)
return calc_map.get(tree.name, lambda x:x)(solutions)
我使用 calc_binary 函數(shù)進行加法和減法運算（以及它們的同階運算）。它以左結(jié)合的方式計算列表中的這些運算，這使得我們的 LL語法不太容易獲取結(jié)果。
第六步：REPL
最樸實的REPL：
if __name__ == '__main__':
while True:
print( calc(raw_input('> ')) )
不要讓我解釋它 :)
附錄：將它們合并：一個70行的計算器
'''A Calculator Implemented With A Top-Down, Recursive-Descent Parser'''
# Author: Erez Shinan, Dec 2012
import re, collections
from operator import add,sub,mul,div
Token = collections.namedtuple('Token', ['name', 'value'])
RuleMatch = collections.namedtuple('RuleMatch', ['name', 'matched'])
token_map = {'+':'ADD', '-':'ADD', '*':'MUL', '/':'MUL', '(':'LPAR', ')':'RPAR'}
rule_map = {
'add' : ['mul ADD add', 'mul'],
'mul' : ['atom MUL mul', 'atom'],
'atom': ['NUM', 'LPAR add RPAR', 'neg'],
'neg' : ['ADD atom'],
}
fix_assoc_rules = 'add', 'mul'
bin_calc_map = {'*':mul, '/':div, '+':add, '-':sub}
def calc_binary(x):
while len(x) > 1:
x[:3] = [ bin_calc_map[x[1]](x[0], x[2]) ]
return x[0]
calc_map = {
'NUM' : float,
'atom': lambda x: x[len(x)!=1],
'neg' : lambda (op,num): (num,-num)[op=='-'],
'mul' : calc_binary,
'add' : calc_binary,
}
def match(rule_name, tokens):
if tokens and rule_name == tokens[0].name: # Match a token?
return tokens[0], tokens[1:]
for expansion in rule_map.get(rule_name, ()): # Match a rule?
remaining_tokens = tokens
matched_subrules = []
for subrule in expansion.split():
matched, remaining_tokens = match(subrule, remaining_tokens)
if not matched:
break # no such luck. next expansion!
matched_subrules.append(matched)
else:
return RuleMatch(rule_name, matched_subrules), remaining_tokens
return None, None # match not found
def _recurse_tree(tree, func):
return map(func, tree.matched) if tree.name in rule_map else tree[1]
def flatten_right_associativity(tree):
new = _recurse_tree(tree, flatten_right_associativity)
if tree.name in fix_assoc_rules and len(new)==3 and new[2].name==tree.name:
new[-1:] = new[-1].matched
return RuleMatch(tree.name, new)
def evaluate(tree):
solutions = _recurse_tree(tree, evaluate)
return calc_map.get(tree.name, lambda x:x)(solutions)
def calc(expr):
split_expr = re.findall('[\d.]+|[%s]' % ''.join(token_map), expr)
tokens = [Token(token_map.get(x, 'NUM'), x) for x in split_expr]
tree = match('add', tokens)[0]
tree = flatten_right_associativity( tree )
return evaluate(tree)
if __name__ == '__main__':
while True:
print( calc(raw_input('> ')) )
- python 使用遞歸的方式實現(xiàn)語義圖片分割功能
- Python裝飾器結(jié)合遞歸原理解析
- python實現(xiàn)文法左遞歸的消除方法
- python遞歸函數(shù)求n的階乘,優(yōu)缺點及遞歸次數(shù)設(shè)置方式
- Python遞歸函數(shù)特點及原理解析
- python 使用遞歸實現(xiàn)打印一個數(shù)字的每一位示例
- python json 遞歸打印所有json子節(jié)點信息的例子
- Python遞歸調(diào)用實現(xiàn)數(shù)字累加的代碼
- Python實現(xiàn)鏈表反轉(zhuǎn)的方法分析【迭代法與遞歸法】
- Python實現(xiàn)一個簡單的遞歸下降分析器
相關(guān)文章
python selenium禁止加載某些請求的實現(xiàn)
本文主要介紹了python selenium禁止加載某些請求的實現(xiàn)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
Python3+Pygame實現(xiàn)射擊游戲完整代碼
這篇文章主要介紹了Python3+Pygame實現(xiàn)射擊游戲完整代碼，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-03-03
在本篇文章里小編給大家整理的是一篇關(guān)于python中entry用法講解內(nèi)容，有興趣的朋友們可以學(xué)習(xí)參考下。2020-12-12
這篇文章主要為大家詳細介紹了windows下numpy下載與安裝圖文教程，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-04-04
python實現(xiàn)csdn全部博文下載并轉(zhuǎn)PDF
我們學(xué)習(xí)編程，在學(xué)習(xí)的時候，會有想把有用的知識點保存下來，我們可以把知識點的內(nèi)容爬下來轉(zhuǎn)變成pdf格式，方便我們拿手機可以閑時翻看，是很方便的，本文就介紹一下如何實現(xiàn)2021-06-06
TarFile類就是tar壓縮包，其由member塊組成, member塊則包括header塊和data塊. 每個member以TarInfo對象形式描述. 所以TarFile就是TarInfo的序列2023-02-02
這篇文章主要為大家詳細介紹了python線程池threadpool的使用方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-04-04
python通過函數(shù)屬性實現(xiàn)全局變量的方法
這篇文章主要介紹了python通過函數(shù)屬性實現(xiàn)全局變量的方法,實例分析了Python中函數(shù)屬性的相關(guān)使用技巧,需要的朋友可以參考下2015-05-05
今天小編就為大家分享一篇python 獲取當天每個準點時間戳的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-05-05
混淆矩陣是ROC曲線繪制的基礎(chǔ),同時它也是衡量分類型模型準確度中最基本,最直觀,計算最簡單的方法,下面這篇文章主要給大家介紹了關(guān)于pytorch分類模型繪制混淆矩陣以及可視化的相關(guān)資料,需要的朋友可以參考下2022-04-04