使用70行Python代碼實現(xiàn)一個遞歸下降解析器的教程

更新時間：2015年04月17日 16:05:01 投稿：goldensun

這篇文章主要介紹了使用70行Python代碼實現(xiàn)一個遞歸下降解析器的教程,文章分步講解最后整合出代碼,需要的朋友可以參考下

第一步：標(biāo)記化

處理表達(dá)式的第一步就是將其轉(zhuǎn)化為包含一個個獨立符號的列表。這一步很簡單，且不是本文的重點，因此在此處我省略了很多。
首先，我定義了一些標(biāo)記（數(shù)字不在此中，它們是默認(rèn)的標(biāo)記）和一個標(biāo)記類型：

token_map = {'+':'ADD', '-':'ADD',
       '*':'MUL', '/':'MUL',
       '(':'LPAR', ')':'RPAR'}
 
Token = namedtuple('Token', ['name', 'value'])

下面就是我用來標(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)' --&gt; ['1.2', '/', '(', '11', '+', '3', ')']

下一行命名標(biāo)記，這樣分析器就能通過分類識別它們：

['1.2', '/', '(', '11', '+', '3', ')']
-&gt;
[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ù)字。我們的分詞器缺少稱為驗證的屬性，以防止非數(shù)字被接受，但幸運的是，運算器將在以后處理它。
就是這樣
第二步: 語法定義

我選擇的解析器實現(xiàn)自一個本地垂直解析器，其來源于LL解析器的一個簡單版本。它是一個最簡單的解析器實現(xiàn)，事實上，只有僅僅14行代碼。它是一種自上而下的解析器，這意味著解析器從最上層規(guī)則開始解析（like:expression），然后以遞歸方式嘗試按照其子規(guī)則方式解析，直至符合最下層的規(guī)則（like:number）。換句話解釋，當(dāng)自底向上解析器（LR）逐步地收縮標(biāo)記，使規(guī)則被包含在其它規(guī)則中，直到最后僅剩下一個規(guī)則，而自頂向下解析器（LL）逐步展開規(guī)則并進(jìn)入到少數(shù)的抽象規(guī)則，直到它能夠完全匹配輸入的標(biāo)記。
在深入到實際的解析器實現(xiàn)之前，我們可對語法進(jìn)行討論。在我之前發(fā)表的文章中，我使用過LR解析器，我可以像如下方式定義計算器語法（標(biāo)記使用大寫字母表示）：

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)了。這是個非常重要的細(xì)節(jié)，我會向大家詳細(xì)說明這一點。

LR版本使用了左遞歸的模式。當(dāng)LL解析器遇到遞歸的時候，它會嘗試去匹配規(guī)則。所以，當(dāng)左遞歸發(fā)生是，解析器會進(jìn)入無窮遞歸。甚至連聰明的LL解析器例如ANTLR也逃避不了這個問題，它會以友好的錯誤提示代替無窮的遞歸，而不像我們這個玩具解析器那樣。

左遞歸可以很容易的轉(zhuǎn)變?yōu)橛疫f歸，我就這么做的。但是解析器并不是那么簡單，它又會產(chǎn)生另一個問題：當(dāng)左遞歸正確的解析 3-2-1 為(3-2)-1，而右遞歸卻錯誤的解析為3-(2-1)。我還沒想到一個簡單的解決辦法，所以為了讓事情簡單，我決定讓它繼續(xù)使用錯誤的解析格式，并在后面處理這個問題（請看步驟4）

第三步：解析為一個AST

算法其實很簡單。我們會定義一個接收兩個參數(shù)的遞歸方法：第一個參數(shù)是我們要嘗試匹配的規(guī)則名稱，第二個參數(shù)是我們要保留的標(biāo)識列表。我們從add（最上層規(guī)則）方法開始，其已包含完整的標(biāo)識列表，遞歸調(diào)用已非常明確。方法將返回一個數(shù)組，其包含元素為：一個是當(dāng)前匹配項，另一個是保留匹配的標(biāo)識列表。我們將實現(xiàn)標(biāo)識匹配功能，以使這段代碼可用（它們都是字符串類型；一個是大寫格式，另一個是小寫格式）。

以下是解析器實現(xiàn)的代碼：

RuleMatch = namedtuple('RuleMatch', ['name', 'matched'])
 
def match(rule_name, tokens):
  if tokens and rule_name == tokens[0].name:   # 是否匹配標(biāo)識?
    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)，處理下一個擴(kuò)展定義!
      matched_subrules.append(matched)
    else:
      return RuleMatch(rule_name, matched_subrules), remaining_tokens
  return None, None  # 無匹配結(jié)果

代碼4至5行說明：如果規(guī)則名稱（rule_name)確實是一個標(biāo)識，并被包含在標(biāo)識列表（tokens）中，同時檢查其是否匹配當(dāng)前標(biāo)識。如果是，表達(dá)式將返回匹配方法，標(biāo)識列表任然進(jìn)行使用。

代碼第6行說明：迭代將循環(huán)檢查是否匹配該規(guī)則名稱對應(yīng)的子規(guī)則，通過遞歸實現(xiàn)每條子規(guī)則的匹配。如果規(guī)則名稱滿足匹配標(biāo)識的條件，get()方法將返回一個空數(shù)組，同時代碼將返回空值（見16行）。

第9-15行，實現(xiàn)迭代當(dāng)前的sub-rule，并嘗試順序地匹配他們。每次迭代都盡可能多的匹配標(biāo)識。如果某一個標(biāo)識無法匹配，我們就會放棄整個sub-rule。但是，如果所有的標(biāo)識都匹配成功，我們就到達(dá)else語句，并返回rule_name的匹配值，還有剩下標(biāo)識。

現(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，當(dāng)然我們并沒有看到有剩下的標(biāo)識。匹配結(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)完成了可以處理二進(jìn)制運算，一元運算，括號和操作符優(yōu)先權(quán)的解析器。

現(xiàn)在只剩下一個錯誤待解決，下面的步驟我們將解決這個錯誤。

第四步：后續(xù)處理

我的解析器并非在任何場合管用。最重要的一點是，它并不能處理左遞歸，迫使我把代碼寫成右遞歸方式。這樣導(dǎo)致，解析 8/4/2 這個表達(dá)式的時候，AST結(jié)果如下：

add
  mul
    atom
      NUM 8
    MUL '/'
    mul
      atom
        NUM 4
      MUL '/'
      mul
        atom
          NUM 2

如果我們嘗試通過AST計算結(jié)果，我們將會優(yōu)先計算4/2，這當(dāng)然是錯誤的。一些LL解析器選擇修正樹里面的關(guān)聯(lián)性。這樣需要編寫多行代碼;)。這個不采納，我們需要使它扁平化。算法很簡單：對于AST里面的每個規(guī)則 1)需要修正 2)是一個二進(jìn)制運算（擁有sub-rules）3) 右邊的操作符同樣的規(guī)則：使后者扁平成前者。通過“扁平”，我意思是在其父節(jié)點的上下文中，通過節(jié)點的兒子代替這個節(jié)點。因為我們的穿越是DFS是后序的，意味著它從樹的邊緣開始，并一直到達(dá)樹根，效果將會累加。如下是代碼：

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á)式變成一個平面列表（不會混淆）。括號會破壞順序，當(dāng)然，它們不會受到影響。

基于以上的這些，我可以把代碼重構(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)整棵樹需要更少的代碼。

第五步：運算器

對樹的運算非常簡單。只需用與后處理的代碼相似的方式對樹進(jìn)行遍歷（即 DFS 后序），并按照其中的每條規(guī)則進(jìn)行運算。對于運算器，因為我們使用了遞歸算法，所以每條規(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)行加法和減法運算（以及它們的同階運算）。它以左結(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('> ')) )

您可能感興趣的文章: