?第一步：標(biāo)記化
處理表達(dá)式的第一步就是將其轉(zhuǎn)化為包含一個(gè)個(gè)獨(dú)立符號(hào)的列表。這一步很簡(jiǎn)單，且不是本文的重點(diǎn)，因此在此處我省略了很多。
首先，我定義了一些標(biāo)記（數(shù)字不在此中，它們是默認(rèn)的標(biāo)記）和一個(gè)標(biāo)記類型：
?
token_map = {'+':'ADD', '-':'ADD',
'*':'MUL', '/':'MUL',
'(':'LPAR', ')':'RPAR'}
Token = namedtuple('Token', ['name', 'value'])
下面就是我用來(lái)標(biāo)記 `expr` 表達(dá)式的代碼：
?
split_expr = re.findall('[\d.]+|[%s]' % ''.join(token_map), expr)
tokens = [Token(token_map.get(x, 'NUM'), x) for x in split_expr]
第一行是將表達(dá)式分割為基本標(biāo)記的技巧，因此
?
'1.2 / ( 11+3)' --> ['1.2', '/', '(', '11', '+', '3', ')']
下一行命名標(biāo)記，這樣分析器就能通過(guò)分類識(shí)別它們：
?
['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 中的標(biāo)記被假定為數(shù)字。我們的分詞器缺少稱為驗(yàn)證的屬性，以防止非數(shù)字被接受，但幸運(yùn)的是，運(yùn)算器將在以后處理它。
就是這樣
第二步: 語(yǔ)法定義
我選擇的解析器實(shí)現(xiàn)自一個(gè)本地垂直解析器，其來(lái)源于LL解析器的一個(gè)簡(jiǎn)單版本。它是一個(gè)最簡(jiǎn)單的解析器實(shí)現(xiàn)，事實(shí)上，只有僅僅14行代碼。它是一種自上而下的解析器，這意味著解析器從最上層規(guī)則開(kāi)始解析（like:expression），然后以遞歸方式嘗試按照其子規(guī)則方式解析，直至符合最下層的規(guī)則（like:number）。換句話解釋，當(dāng)自底向上解析器（LR）逐步地收縮標(biāo)記，使規(guī)則被包含在其它規(guī)則中，直到最后僅剩下一個(gè)規(guī)則，而自頂向下解析器（LL）逐步展開(kāi)規(guī)則并進(jìn)入到少數(shù)的抽象規(guī)則，直到它能夠完全匹配輸入的標(biāo)記。
在深入到實(shí)際的解析器實(shí)現(xiàn)之前，我們可對(duì)語(yǔ)法進(jìn)行討論。在我之前發(fā)表的文章中，我使用過(guò)LR解析器，我可以像如下方式定義計(jì)算器語(yǔ)法（標(biāo)記使用大寫字母表示）：
?
add: add ADD mul | mul;
mul: mul MUL atom | atom;
atom: NUM | '(' add ')' | neg;
neg: '-' atom;
(如果您還不理解上述語(yǔ)法，請(qǐng)閱讀我之前發(fā)表的文章)
現(xiàn)在我使用LL解析器，以如下方式定義計(jì)算器的語(yǔ)法：
?
rule_map = {
'add' : ['mul ADD add', 'mul'],
'mul' : ['atom MUL mul', 'atom'],
'atom': ['NUM', 'LPAR add RPAR', 'neg'],
'neg' : ['ADD atom'],
}
大家可以看到，這里有一個(gè)微妙的變化。有關(guān)"add and mul"的遞歸定義被反轉(zhuǎn)了。這是個(gè)非常重要的細(xì)節(jié)，我會(huì)向大家詳細(xì)說(shuō)明這一點(diǎn)。
LR版本使用了左遞歸的模式。當(dāng)LL解析器遇到遞歸的時(shí)候，它會(huì)嘗試去匹配規(guī)則。所以，當(dāng)左遞歸發(fā)生是，解析器會(huì)進(jìn)入無(wú)窮遞歸。甚至連聰明的LL解析器例如ANTLR也逃避不了這個(gè)問(wèn)題，它會(huì)以友好的錯(cuò)誤提示代替無(wú)窮的遞歸，而不像我們這個(gè)玩具解析器那樣。
左遞歸可以很容易的轉(zhuǎn)變?yōu)橛疫f歸，我就這么做的。但是解析器并不是那么簡(jiǎn)單，它又會(huì)產(chǎn)生另一個(gè)問(wèn)題：當(dāng)左遞歸正確的解析 3-2-1 為(3-2)-1，而右遞歸卻錯(cuò)誤的解析為3-(2-1)。我還沒(méi)想到一個(gè)簡(jiǎn)單的解決辦法，所以為了讓事情簡(jiǎn)單，我決定讓它繼續(xù)使用錯(cuò)誤的解析格式，并在后面處理這個(gè)問(wèn)題（請(qǐng)看步驟4）
第三步：解析為一個(gè)AST
算法其實(shí)很簡(jiǎn)單。我們會(huì)定義一個(gè)接收兩個(gè)參數(shù)的遞歸方法：第一個(gè)參數(shù)是我們要嘗試匹配的規(guī)則名稱，第二個(gè)參數(shù)是我們要保留的標(biāo)識(shí)列表。我們從add（最上層規(guī)則）方法開(kāi)始，其已包含完整的標(biāo)識(shí)列表，遞歸調(diào)用已非常明確。方法將返回一個(gè)數(shù)組，其包含元素為：一個(gè)是當(dāng)前匹配項(xiàng)，另一個(gè)是保留匹配的標(biāo)識(shí)列表。我們將實(shí)現(xiàn)標(biāo)識(shí)匹配功能，以使這段代碼可用（它們都是字符串類型；一個(gè)是大寫格式，另一個(gè)是小寫格式）。
以下是解析器實(shí)現(xiàn)的代碼：
?
RuleMatch = namedtuple('RuleMatch', ['name', 'matched'])
def match(rule_name, tokens):
if tokens and rule_name == tokens[0].name: # 是否匹配標(biāo)識(shí)?
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 # 運(yùn)氣不好，跳出循環(huán)，處理下一個(gè)擴(kuò)展定義!
matched_subrules.append(matched)
else:
return RuleMatch(rule_name, matched_subrules), remaining_tokens
return None, None # 無(wú)匹配結(jié)果
代碼4至5行說(shuō)明：如果規(guī)則名稱（rule_name)確實(shí)是一個(gè)標(biāo)識(shí)，并被包含在標(biāo)識(shí)列表（tokens）中，同時(shí)檢查其是否匹配當(dāng)前標(biāo)識(shí)。如果是，表達(dá)式將返回匹配方法，標(biāo)識(shí)列表任然進(jìn)行使用。
代碼第6行說(shuō)明：迭代將循環(huán)檢查是否匹配該規(guī)則名稱對(duì)應(yīng)的子規(guī)則，通過(guò)遞歸實(shí)現(xiàn)每條子規(guī)則的匹配。如果規(guī)則名稱滿足匹配標(biāo)識(shí)的條件，get()方法將返回一個(gè)空數(shù)組，同時(shí)代碼將返回空值（見(jiàn)16行）。
第9-15行，實(shí)現(xiàn)迭代當(dāng)前的sub-rule，并嘗試順序地匹配他們。每次迭代都盡可能多的匹配標(biāo)識(shí)。如果某一個(gè)標(biāo)識(shí)無(wú)法匹配，我們就會(huì)放棄整個(gè)sub-rule。但是，如果所有的標(biāo)識(shí)都匹配成功，我們就到達(dá)else語(yǔ)句，并返回rule_name的匹配值，還有剩下標(biāo)識(shí)。
現(xiàn)在運(yù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é)果是一個(gè)tuple，當(dāng)然我們并沒(méi)有看到有剩下的標(biāo)識(shí)。匹配結(jié)果并不易于閱讀，所以讓我吧結(jié)果畫成一個(gè)圖：
?
add
mul
atom
NUM '1.2'
MUL '/'
mul
atom
LPAR '('
add
mul
atom
NUM '11'
ADD '+'
add
mul
atom
NUM '3'
RPAR ')'
這就是概念上的AST。通過(guò)你思維邏輯，或者在紙上描繪，想象解析器是如何運(yùn)作的，這樣是個(gè)很好的鍛煉。我不敢說(shuō)這樣是必須的，除非你想神交。你可以通過(guò)AST來(lái)幫助你實(shí)現(xiàn)正確的算法。
到目前為止，我們已經(jīng)完成了可以處理二進(jìn)制運(yùn)算，一元運(yùn)算，括號(hào)和操作符優(yōu)先權(quán)的解析器。
現(xiàn)在只剩下一個(gè)錯(cuò)誤待解決，下面的步驟我們將解決這個(gè)錯(cuò)誤。
第四步：后續(xù)處理
我的解析器并非在任何場(chǎng)合管用。最重要的一點(diǎn)是，它并不能處理左遞歸，迫使我把代碼寫成右遞歸方式。這樣導(dǎo)致，解析 8/4/2 這個(gè)表達(dá)式的時(shí)候，AST結(jié)果如下：
?
add
mul
atom
NUM 8
MUL '/'
mul
atom
NUM 4
MUL '/'
mul
atom
NUM 2
如果我們嘗試通過(guò)AST計(jì)算結(jié)果，我們將會(huì)優(yōu)先計(jì)算4/2，這當(dāng)然是錯(cuò)誤的。一些LL解析器選擇修正樹(shù)里面的關(guān)聯(lián)性。這樣需要編寫多行代碼;)。這個(gè)不采納，我們需要使它扁平化。算法很簡(jiǎn)單：對(duì)于AST里面的每個(gè)規(guī)則 1)需要修正 2)是一個(gè)二進(jìn)制運(yùn)算 （擁有sub-rules）3) 右邊的操作符同樣的規(guī)則：使后者扁平成前者。通過(guò)“扁平”，我意思是在其父節(jié)點(diǎn)的上下文中，通過(guò)節(jié)點(diǎn)的兒子代替這個(gè)節(jié)點(diǎn)。因?yàn)槲覀兊拇┰绞荄FS是后序的，意味著它從樹(shù)的邊緣開(kāi)始，并一直到達(dá)樹(shù)根，效果將會(huì)累加。如下是代碼：
?
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)的加法或乘法表達(dá)式變成一個(gè)平面列表（不會(huì)混淆）。括號(hào)會(huì)破壞順序，當(dāng)然，它們不會(huì)受到影響。
基于以上的這些，我可以把代碼重構(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)
但是，我并不會(huì)這樣做。我需要更少的代碼，并且把計(jì)算代碼換成處理列表會(huì)比重構(gòu)整棵樹(shù)需要更少的代碼。
第五步：運(yùn)算器
對(duì)樹(shù)的運(yùn)算非常簡(jiǎn)單。只需用與后處理的代碼相似的方式對(duì)樹(shù)進(jìn)行遍歷（即 DFS 后序），并按照其中的每條規(guī)則進(jìn)行運(yùn)算。對(duì)于運(yùn)算器，因?yàn)槲覀兪褂昧诉f歸算法，所以每條規(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ù)進(jìn)行加法和減法運(yùn)算（以及它們的同階運(yùn)算）。它以左結(jié)合的方式計(jì)算列表中的這些運(yùn)算，這使得我們的 LL語(yǔ)法不太容易獲取結(jié)果。
第六步：REPL
最樸實(shí)的REPL：
?
if __name__ == '__main__':
while True:
print( calc(raw_input('> ')) )
不要讓我解釋它 :)
附錄：將它們合并：一個(gè)70行的計(jì)算器
?
'''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('> ')) )
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
