Parser Combinator 在語法解析的當中處於怎樣的位置?

01-28

很棒的方案, 但是看網上的文章對比語法解析理論就沒展開說它:
Laurence Tratt: Parsing: The Solved Problem That Isn"t

Parser Combinator是一種實現的技巧，在講理論的東西裡面當然沒有提到他，正如同面向對象的理論基礎裡面也基本不會有《深入理解C++對象模型》的東西一樣。

當然這東西也是發過論文的，典型的有parsec。

一句話回答：Ninputer/VBF · GitHub

一個GLR的Parser Combinator，支持錯誤恢復，支持歧義文法，支持左遞歸左公因式等一切東西，實際上它支持任何CFG。對LR(k)文法任何k均是O(N)的。

本質上這不是一個Combinator而是一個語言集成的文法編寫器+運行時Generator。但是考慮到JIT都已經用了這麼多年了，小小的一次性生成開銷無傷大雅。各種日常生活的Parser，DSL級別的文法都可以在今天的計算機上快速處理。VBF簡潔的Combinator式文法表達，寬容友好的文法支持，自然地AST生成或單次利用Parse結果，再加上對錯誤處理方便而專業的支持，絕對可以滿足您的大多數需求，徹底擺脫antlr/yacc等額外工具。這完全是一個專業級的語法分析解決方案而非玩具。PS.其他回答中某些陳年ParserCombinator無用論你們可以跳過不看了。

結論先行：parser combinator 在正經的編譯相關研究沒有提及，是因為它沒有解決任何新的演算法問題，只是換了一種方式來編寫非左遞歸文法。換言之，它在語法解析演算法研究領域裡沒有價值。

（如果是看見 combinator 或 Monad 兩個詞就莫名興奮的朋友，後面可以不用看了，直接點反對就好。今年碰巧編譯原理又是必修課的朋友可以考慮看下去，不虧。）

如果要看詳細的解釋，就必須從語法分析的兩個基本演算法看起。

從演算法上說，語法分析的思路分為自頂向下和自底向上兩類。兩者對輸入文本的分類是類似的：它們都將輸入劃分為終結符和產生式（或者說，表達式），而區別在於遍歷的方法：自頂向下方法通過獲取向前數第 k 個終結符猜測整句表達式究竟屬於哪個產生式並將後續展開進行後續計算；而自底向上方法通過不停地遍歷終結符（所謂移進，shift），直到發現已經獲取的終結符序列滿足某一個已知的產生式，從而將已知的終結符序列合併成產生式（即所謂規約，reduce）。所以自頂向下文法的一個特徵就是，它不能很好地支持左遞歸文法，因為自頂向下方法要求所有能夠被它解析的文法，總是必須在前若干個終結符上看出區別，這也是所謂 ANTLR 的 LL(k) 文法中的 k 的含義。自底向上方法不受這個限制，相反地，為了能夠處理二義文法，自底向上演算法需要決定可以規約時應該繼續看下一個終結符，還是選擇直接合併產生式，這也就是 Yacc/Bison 里用的 LALR 演算法著名的移進/規約衝突和規約/規約衝突。順便說一句，前面 @vczh 梓翰說的 Generalized LR 其實也沒有解決衝突，它只是將所有的選擇列出來，而 LALR 選擇自動丟棄部分選擇。但從語法的解析能力上看，兩者沒有區別。

那麼，parser combinator 是不是跳出兩者之外的第三種方法？我們可以拿一個典型的 parser combinator 來做例子，即 Haskell 的 parsec。我不知道這裡的朋友有多少熟悉這個庫，只說一點。Parsec 的 &<|&> 操作符——它的右端要求必須是在左端出錯並且沒有接收任何輸入的前提下，才會轉入右端。這實際上就是說，它的左端和右端不能有公共左因子，而這一點，正是它支持遞歸下降文法的典型特徵。對其行為有疑問的，可以查閱 Real World Haskell 對 backtracing 和 Try 操作符的說明和在線評論：http://book.realworldhaskell.org/read/using-parsec.html。

我猜看到這裡，熟悉 parsec 的朋友可能要拿 Try 算符來反駁我。然而 Try 算符的存在，恰恰說明 parsec 並不是以一致的方式處置語法規則的。一般從工程角度上說，即便是寫不出上下文無關文法的語言，也一樣可以用上下文無關分析器分析。一個很常見的例子是 Perl 和它的怪異變體，Powershell，程序員實際上可以在語法分析過程中引入一些分析的小技巧以及合理地參考語義信息，來讓它被正確解析。同樣的技巧也可以被用在遞歸下降文法上。Parsec 的 Try 和 Optional，它們都是通過在遞歸過程中增加一些回溯的操作來允許一定程度的回溯，從而獲得更強的表達能力，代價則是時間複雜度上升，這一點 Real World Haskell 也有說明。其實這沒有什麼特別，很多編譯器開發者也都是這麼做的。事實上，由於 Haskell 運行時大量使用惰性求值和圖規約技術，遞歸操作是相對低代價的，所以 Haskell 更能容忍深度的遞歸調用。但這是實現細節，而非演算法差異。與之對比，Yacc/Bison 允許程序員自由書寫左遞歸文法而不需要任何顯式標註，這是它在演算法層面處理能力更強的明證。

所以，parser combinator 其實就是自頂向下分析演算法的一種。所謂 parser combinator 和 parser generator 的區別，實際上就是將演算法的狀態表示為一個整數（Yacc/Bison 的做法）和一個類（ANTLR 的做法）的分別，看上去寫法完全不同，然而寫法並不決定表達能力。雖然我必須承認，從工程角度上，combinator 不需要單獨寫語法定義文件，調試起來確實比 Yacc/Bison 舒服很多。

===

順便說一句，記得之前我在某個問題下寫回答批評 Haskell 社區時，有一位很不服氣的朋友拿 parsec 為例，說明 Haskell 在編譯器前端開發領域「很牛」。那時候我沒理解他想說什麼，所以用 ANTLR 和 Bison 回復他，然而他堅持說那是 parser combinator，和 parser generator 不是一類東西。不知道如今他還能不能看到這篇回答，但我想今天的回復可以算是一個正式的答覆：

「從演算法角度上看，parser combinator 不牛，一點都不。從工程角度看，它有一些優點。」

===

對了，既然前面有彭飛說的論文，我也不妨趁這個機會說一說 Yacc/Bison 「死亡」的問題。事實上，Yacc/Bison 在過去的幾十年里已經不是工業級編譯器前端編寫的首選工具。最主要的原因是 LALR 演算法生成代碼確實難以閱讀和調試，原因前面彭飛已經解釋過了，大體不差。出於調試便利性的考慮，程序員們還是更習慣手寫語法分析模塊。典型的例子是 gcc，它自 3.4 版本以後從 bison 語言定義切換到了手寫的遞歸下降分析器。另外根據我自己做的一些小型測試，我有證據猜測 Visual Studio 2010 的 C++ 編譯器也是遞歸下降編寫的前端（後續的版本沒有測試過，不確定）。加上後來有 ANTLR 這樣的新秀，事實上 Yacc/Bison 更多地被用於某些項目中輔助性編程語言的生成工作。順便說一句，GHC 反倒用的是 Yacc 風格的語法生成（嚴格意義上說是 Happy），不過也不奇怪，相對規則的語言比較容易用規範的語法表示。

最後，儘管這麼說可能會得罪人，但我必須指出，前面彭飛的回答存在大量的錯誤。他提到的那篇論文，Yacc is dead，是一篇證據不足的論文，也沒有通過評審。我閱讀了論文和它給出的用例，它甚至都沒有給出正確的例子（正文標明的是分析上下文無關文法，論文中的例子鏈接 http://www.ucombinator.org/projects/parsing/ 給出的只有詞法分析），僅僅在後來的 Yacc is dead: An update 內容中，才針對 Russ Cox 的質疑增補了一個非常簡單的語法錯誤檢測用例。在原始鏈接中 http://arxiv.org/abs/1010.5023，它的狀態被標為 rejected，本身也說明了這個問題。

很不幸，這樣一篇莫名其妙的「論文」（原諒我加了引號，因為它實在不滿足我對論文嚴謹性的要求），經過彭飛君回答中過譽之詞的反覆渲染，結果被捧成了一篇歷史上結束學界難題的標誌性文章。

不得不說，這是非常令人遺憾的。

@彭飛答案里提到的Matt Might等人的Parsing with Derivatives那項工作有進展了。今年PLDI"16有一篇On the Complexity and Performance of Parsing with Derivatives，abstract里說：

In this paper, we reexamine the performance of parsing with derivatives. We have discovered that it is not exponential but, in fact, cubic. Moreover, simple (though perhaps not obvious) modifications to the implementation by Might et al. (2011) lead to an implementation that is not only easy to understand but also highly performant in practice.

所以看起來bound的問題解決了。是不是容易實現且高性能，等我要到了preprint研究一下吧。

（以下為答非所問的內容

如果只是希望做到實時解析，用某種編程語言來書寫語法規則，那麼可以使用一些元編程的把戲，做一個前端的前端，以期用最優雅的方式來實現CFG語法和語義，在不引入DSL的前提下滿足日常分析文本的需要。至於後端是用GLR，用LL(k)，用LR(1)，對於最終的應用也許並沒有那麼重要。

以下是利用Python 3元編程實現的一個轉換器，可以同時書寫語法和語義。

1. 準備一個對象Rule（也叫Production），以及將函數聲明轉化成Rule的修飾符rule。這裡的Rule同時包含了語法聲明和語義聲明；

import re import inspect


from collections import namedtuple

from collections import OrderedDict
Rule = namedtuple("Rule", "lhs rhs semantics")

def rule(func): "A decorator to translate function syntax into Rule definition. " lhs = func.__name__ # 用符號最後一位數字來避免語義函數聲明中參數重名 rhs = [x[:-1] if x[-1].isdigit() else x for x in inspect.signature(func).parameters] return Rule(lhs, rhs, func)

2. 準備一個輔助類，用於代理元類中聲明登記屬性的方法；

class pairlist(list):


    def __setitem__(self, k, v):

        ls = super(pairlist, self)

        ls.append((k, v))

def __getitem__(self, k0): for k, v in self: if k == k0: return v raise KeyError()

3. 聲明元類，即一類可以表達CFG的Python class；

class cfgmeta(type):


    def __prepare__(mcls, *a, **kw):

        return pairlist()
    def __new__(mcls, name, bases, tplst):
        _dict0 = {}

        lexes = OrderedDict()

        rules = []
        for k, v in tplst:
            # Handle lexical declaration.

            if not k.startswith("_") and isinstance(v, str):

                lexes[k] = re.compile(v)
            # Handle rule declaration.

            elif isinstance(v, Rule):

                rules.append(v)
            # Handle normal attributes.

            else:

                _dict0[k] = v

_dict0["lexes"] = lexes _dict0["rules"] = rules _dict0["parser"] = MyParser(lexes, rules) return super().__new__(mcls, name, bases, _dict0)

4. 最後，可以使用Python的語法來聲明CFG了；

class GrammarParen(metaclass=cfgmeta):


    """ A sample definition for grammar of paired parenthesises. """
    END      = r"$"

    IGNORED  = r"

"

    LEFT     = r"("

    RIGHT    = r")"
    @rule

    def top(S, END):

        return S
    @rule

    def S(LEFT, S1, RIGHT, S2):        # 用末尾的1和2消除S的重名問題

        return "&<" + S1 + "&>" + S2

@rule def S(): return ""

相應的BNF形式為：

S" ::= S S ::= ( S ) S S ::= ε

聲明完成後可以查看語法定義的結果：

In [10]: GrammarParen.lexes Out[10]: OrderedDict([("END", re.compile(r"$", re.UNICODE)), ("IGNORED", re.compile(r" ", re.UNICODE)), ("LEFT", re.compile(r"(", re.UNICODE)), ("RIGHT", re.compile(r")", re.UNICODE))])

In [11]: GrammarParen.rules Out[11]: [Rule(lhs="top", rhs=["S", "END"], semantics=&), Rule(lhs="S", rhs=["LEFT", "S", "RIGHT", "S"], semantics=&), Rule(lhs="S", rhs=[], semantics=&)]

對比Yacc或者Bison中的語法定義方式，個人覺得這種方式優雅得多，沒有DSL的既視感，而且可拓展性好，可以在語義函數中使用任意python支持的庫函數，設置斷點供解析過程中調試一類的。

這裡我使用了自製的Earley Parser（最易手工實現的Parser...當然也可以用別的Parser），並內置地預先聲明了詞法規則IGNORED和END以及入口的top Rule，結合用戶聲明的其他信息，構造了一個Parser的實例作為這些語法類的一個屬性。

以下是兩個最弱雞的用例：

- 解釋邱奇數：

class GChurch(metaclass=cfgmeta):


    ZERO = r"zero"

    SUCC = r"succ"
    @rule

    def num(ZERO):

        return 0
    @rule

    def num(SUCC, num):

        return num + 1
_, v = GChurch.parser.parse("succ succ succ zero")

In [1]: v Out[1]: 3

- 解析算術式：

class GArith(metaclass=cfgmeta):


    PLUS  = r"+"

    TIMES = r"*"

    NUMB  = r"d+"

    LEFT  = r"("

    RIGHT = r")"
    @rule

    def expr(expr, PLUS, term):

        return expr + term
    @rule

    def expr(term):

        return term
    @rule

    def term(term, TIMES, factor):

        return term * factor
    @rule

    def term(factor):

        return factor 
    @rule

    def factor(atom):

        return atom 
    @rule

    def factor(LEFT, expr, RIGHT):

        return expr 
    @rule

    def atom(NUMB):

        return int(NUMB)
inp = "3 + 2 * 5 + 11"

_, v = GArith.parser.parse(inp)

In [2]: v Out[2]: 24

當然，Parse過程中也可以先構造語法樹，再遍歷語法樹執行語義得到結果。上述例子中的Parser採用的是One-pass，直接在歸約的時候利用語義求值了。

總結一下...有了元編程，是否在實際中使用Parser Combinator也許並沒有那麼重要了吧...？（霧）

（沒有涉及核心內容，求不摺疊，大神輕拍...

parsec 組合子優點

01 最大的好處——靈活，可以在運行期進行各種定製，比如改優先順序，改關鍵字等等。Alex和happy編譯後完整個語言是完全確定不可變的

02 直接用原生語言的調試功能進行調試，方便分塊調試和單元測試。Alex與happy有時候生成代碼不出錯，但是編譯時出問題，所以每次debug要debug兩層 ╮(╯▽╰)╭

缺點

01 性能低

02 難寫難用，處理簡單的東西可以，大的就別考慮了。比起Alex和happy的DSL複雜！

關於理論

parsec支持的是LL(n)，原則上n任意大。理論其實不用考慮，因為工程實踐中它是絕對夠用了，主要看好不好用

Haskell社區在2011年前就很明確parsec並不適合做編譯器的詞法分析，並且給出了適合做詞法分析的Parser Combinator，為啥這裡還在樹一個錯誤的靶子，且打得很high呢？

monadic parser中如何添加額外信息比如字元位置？ - Tang Boyun 的回答