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

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

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

第一步：標(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)' --&gt; ['1.2', '/', '(', '11', '+', '3', ')']

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

['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ù)字。我們的分詞器缺少稱為驗(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)記使用大寫(xiě)字母表示）：

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è)是大寫(xiě)格式，另一個(gè)是小寫(xiě)格式）。

以下是解析器實(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é)果畫(huà)成一個(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)是，它并不能處理左遞歸，迫使我把代碼寫(xiě)成右遞歸方式。這樣導(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)性。這樣需要編寫(xiě)多行代碼;)。這個(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('> ')) )

您可能感興趣的文章: