前言

如果你會Python，並接觸過parser和interpreter的知識，知道上下文無關語言（CFG），那你很可能對這個模塊感興趣（項目地址和README）。項目結構目前還不成熟T.T，有興趣的童鞋可以下載metaparse.py單獨使用（觀眾：...）。歡迎幫忙測試並提出意見。

之前@陳天 老師寫過一篇文章文章推廣parser的概念，頗受歡迎。文中有一個有趣的問題，人們為何不像使用正則一般地使用CFG parser？是否因為工具不足？

有了Python這種靈活簡潔的語言，事情可以很簡單優雅地解決，不遜於instaparse。話不多說，我們馬上寫一個計算器，支持加、乘、乘方表達式和變數賦值。

示例：簡易計算器

第一步，設計文法：

stmt → ID = exprstmt → exprexpr → NUMexpr → ( expr )expr → expr? + expr?expr → expr? * expr?expr → expr? ** expr?

第二步，用Python方法簽名形式模擬該文法：

def stmt(ID, EQ, expr): ...def stmt(expr): ...def expr(ID): ...def expr(NUM): ...def expr(L, expr, R): ...def expr(expr_1, ADD, expr_2): ...def expr(expr_1, MUL, expr_2): ...def expr(expr_1, POW, expr_2): ...

會不會給人一種天然統的感覺…？

第三步，基於metaparse做三個微小的工作：詞法聲明，句法聲明及實現文法語義：

# 導入cfg元類和LALR解析器from metaparse import cfg, LALR# 全局變數table = {}class G_Calc(metaclass=cfg): # 詞法（基於正則，順序匹配） IGNORED = rs+ L = r( R = r) EQ = r= NUM = rd+ ID = rw+ POW = r**, 3 # 指配Token的優先順序，幫助LALR消歧 MUL = r* , 2 ADD = r+ , 1 # 句法和語義（句法制導翻譯，即Yacc的SDT風格） def stmt(ID, EQ, expr): table[ID] = expr return expr def stmt(expr): return expr def expr(ID): if ID in table: return table[ID] else: raise ValueError(ID yet bound: {}.format(ID)) def expr(NUM): return int(NUM) def expr(L, expr, R): return expr def expr(expr_1, ADD, expr_2): # TeX風格下標區分重名的形參 return expr_1 + expr_2 def expr(expr, MUL, expr_1): # 下標足以區分即可 return expr * expr_1 def expr(expr, POW, expr_1): return expr ** expr_1

第四步，用這個Grammar構建Parser：

>>> type(G_Calc)<class metaparse.Grammar>>>> calc = LALR(G_Calc)

然後變數計算器就完工了，在REPL中亦可賽艇：

>>> Calc.interpret( (3) )3>>> Calc.interpret( x = 3 )3>>> Calc.interpret( y = 4 * x ** (2 + 1) * 2)216>>> table{x: 3, y: 216}

如果我們需要語法樹，用parse方法替換interpret方法即可：

>>> tr = Calc.parse(" w = 1 + 2 * 3 ** 4 + 5 ")>>> tr(assign, [(ID: w)@[1:2], (EQ: =)@[4:5], (expr, [(expr, [(expr, [(NUM: 1)@[6:7]]), (ADD: +)@[8:9], (expr, [(expr, [(NUM: 2)@[10:11]]), (MUL: *)@[12:13], (expr, [(expr, [(NUM: 3)@[14:15]]), (POW: **)@[16:18], (expr, [(NUM: 4)@[19:20]])])])]), (ADD: +)@[21:22], (expr, [(NUM: 5)@[23:24]])])])

然後用tr.translate()方法可以得到語法樹的遍歷執行結果。由於LALR的特性，interpret過程中是不顯式生成語法樹的。

內核：元編程

由於對元類metaclass的支持問題，以上寫法只在Python 3裡面有效。元類的目的很簡單：

• 在聲明類的過程中，按順序記錄一個類的屬性；
• 允許記錄重名屬性實例。

用來記錄這些的結構可以是一個key-value-pair list（即assoc-list），支持__setitem__和__getitem__即可。詳情可見官方文檔中__prepare__和__new__的說明，以及David Beazley的教程。

成功獲取屬性列表之後，藉助inspect.getargspec(func)得到其中函數對象的簽名，利用它們構造一個兼具形式和語義的Rule對象，基於它們來構造Grammar對象。

深度元編程和ast模塊

若不依賴metaclass（比如在Python 2中），我們放棄class結構，轉而使用def結構。metaparse提供了一個decorator，如下使用可以得到和以上相同的結果：

@cfg.v2def Calc(): IGNORED = rs+ ... <same-stuff> ...

簡而言之cfg.v2做了幾件事：

• 藉助inspect.getsource得到源碼字元串；
• 用ast.parse解析得到語法樹；
• 遍歷語法樹，從子結構中搜集對象來構造Grammar。

關於ast的文檔比較少，但是它已經被廣泛用於構造DSL和模板引擎之類的工具。篇幅所限，這裡不再展開。以後可以寫一篇文章和大家探討。

關於Parser後端

上面提到的這些元編程的tricks只提供了一種便捷地方式來聲明CFG，而後端parsing演算法可以有多種實現。目前模塊除了實現LALR，還有簡單孱弱的Weak-LL(1)（之所以weak因為沒有用FOLLOW）以及可以處理歧義文法的GLR和Earley（暫不支持包含loop的文法——會導致死循環）。

對於某種LL(1)文法，我們可以使用WLL1，比如萌萌的LISP:

class LISP(metaclass=cfg): IGNORED = rs+ LAMBDA = r(s*lambda LEFT = r( RIGHT = r) SYMBOL = r[^()s]+ def sexp(var): return var def sexp(abst): return abst def sexp(appl): return appl def var(SYMBOL): return SYMBOL def abst(LAMBDA, LEFT, parlist, RIGHT_1, sexp, RIGHT_2): return (LAMBDA, parlist, sexp) def appl(LEFT, sexp, sexps, RIGHT): return [sexp, sexps] def parlist(SYMBOL, parlist): return [SYMBOL] + parlist def parlist(): return [] def sexps(sexp, sexps): return [sexp] + sexps def sexps(): return []p_lisp = WLL1(LISP)>>> p_lisp.interpret((lambda (x y) (+ x y)))(LAMBDA, [x, y], [+, [x, y]])

或者對於歧義文法用GLR，比如Dangling-Else:

class G_IfThenElse(metaclass=cfg): IF = rif THEN = rthen ELSE = relse EXPR = rd+ SINGLE = rw+ def stmt(IF, EXPR, THEN, stmt): return (i-t, stmt) def stmt(IF, EXPR, THEN, stmt_1, ELSE, stmt_2): return (i-t-e, stmt_1, stmt_2) def stmt(SINGLE): return SINGLEp_ite = GLR(G_IfThenElse)>>> p_ite.interpret_many(if 1 then if 2 then if 3 then a else b else c)[(i-t, (i-t-e, (i-t-e, a, b), c)), (i-t-e, (i-t, (i-t-e, a, b)), c), (i-t-e, (i-t-e, (i-t, a), b), c)]

上面計算器的文法也是歧義文法，只不過藉助了Token的優先順序指配消除了歧義，這裡也可以通過給ELSE高於THEN的優先順序來消除歧義，具體情形不再贅述。

後話

這個模塊目前還不太成熟，但我個人認為前端很好用，而後端的演算法也可以在未來不斷優化。希望有興趣的童鞋可以幫助測試這個模塊並給予反饋。大家可以去開ISSUE，互相交流學習。

更多文檔和例子參見項目地址，歡迎fork。