為什麼所有的教科書中都不贊成手寫自底向上的語法分析器？

01-12

我看過很多國外的的編譯教科書，其自底向上語法分析部分全部採用工具生成（絕大多數是bison/yacc）。為什麼他們說：「不推薦手寫」呢？有沒有手寫的自底向上語法分析器？其難點在哪裡？

因為 bottom-up parser 的可讀性極差。根本無法手寫。

實際上 bottom-up parser 是一個本來不應該作為實際工程應用的純學術的東西。它的優點在當時主要是 recognition strength 比較強。LR(1) parser 的 recognition strength 可以超過 LL(k) parser。但 LL(k) parser generator 的運算複雜度是 O(|T| ^ k)，所以其自動化生成演算法認為是不可能工程化的。一度認為 LL(k) 只能手寫實現，而且 k 只能實際為一。

不過後來 Terence Parr，ANTLR 的作者，開發了 LL"(k) parser，把複雜度降低到 O(|T| x k)。LL"(k) 的 strength 小於 LL(k) 但大於 LL(k-1)。這就抵消了 LR 演算法的兩個重要優勢：自動生成和 parsing strength。

接下來還有幾個實際問題也抵消了 bottom-up parser 的必要性：

目前流行的 LR parser generator 是 LALR，其 parsing strength 弱於 LR(1)。所以還不能和任意 LL(k) 相比。
把 LL(k) 語法改寫為 LR(1) 是非常反直觀的做法。
Bottom-up parser 的優勢建立在嚴格的數學基礎上，要求語言必須是 context-free 語法。實際中嚴格的 context-free 語法很少。可讀性極好的 LL parser 可以任意加入 ad-hoc trick 來分析 context-sensitive 語法，乃至於使用回溯來分析 undetermined 語法。而 bottom-up parser 就無能為力了。
實際中設計語言可以盡量向 LL(1) 靠攏。注意這一條並不和上一條矛盾。一個語言可以是 99% 的 LL(1) 語法加上幾個 undetermined 語法的特例。這時用 bottom-up parser 是最尷尬的，parsing strength 在 99% 的情況下白白浪費（之所以說是浪費是因為這種 strength 是以 readability 為代價的），在 1% 的特例中還非常難於處理。

@vczh 的看法可能來自一些誤解。我的觀點不是 LL 多麼牛逼。而是：

LL"(k) 的發明說明 LL 沒有人們原本想像的那麼弱。
LL 經常用 recursive-descend 實現。而這種實現是最容易加入 ad-hoc trick 的方式。

@vczh 舉的例子基本上都是 LL 在純理論方面比 LR 弱的例子。這恰恰是我已經說明過的問題。比如 @vczh 說道：「再說了，語言設計成 LL(1) 的話，整個語法憋手蹩腳，你會發現根本沒有一個流行的語言是這麼做的」。我不能同意。寫一個純粹的 LL(1) 語法當然很反直觀，但是 99% 的 LL(1) 語法加上個別特例是非常常見的。Lua 語言就是幾乎 LL(1) 語法。

tokenizer和grammar analyzer對於compiler只是一小部分，概念多而不實用，各種實現對編譯速度影響不大，對目標代碼效率幾乎無影響。

「國外的編譯教科書語法分析用自動工具生成」，是為了留出時間講後面的。國內有些教材則過分糾結於詞法、語法分析的細節，它們不是難，只是繁雜，容易讓人失去耐心、信心，導致沒心思玩後面環節（語義分析、代碼生成等等）的東西了。

首先對@馮東的問題表達一點看法：LL再怎麼牛逼也不能解決大多數現存語言中的問題，譬如說C#的「a&.c();」。a到底應該parse成什麼，得你看到.才知道。可惜那個?可以是無限長，k多少LL在這裡都是沒有用的。我們用簡單的方法來擼這些語言的分析器的時候，會遇到LL(k)的幾個限制（也就是為什麼antlr不僅那麼難用而且性能也很低）

1：LL文法寫出來比LR的可讀性要差多了

2：正因為你是LL所以你往往需要一些超長的look ahead表。這個會嚴重干擾你的複雜度得到的性能的。所以那個O(|T|×k)根本就是個幻覺

再說了，語言設計成LL(1)的話，整個語法憋手蹩腳，你會發現根本沒有一個流行的語言是這麼做的。所以關鍵時刻，不能上ANTLR。那你說什麼比較好用？haskell有parsec，F#有fsyacc，C++有spirit（但是他編譯的時間太久了），實在不行還可以來http://gac.codeplex.com試一下我的parser generator。

=====================答案的分割線=====================

為什麼說我們手寫parser從來都是自頂向下沒有自底向上？這跟@馮東說得對，因為寫出來的東西沒法看，就跟你寫perl腳本一樣，是一次性的。我高中的時候就寫過一個這樣的語法分析器，為了讓你不感到那麼複雜我舉個簡單的例子。譬如說我要parse一個帶+-*/^()的四則運算式子，然後不許你用自頂向下的做法，也就是不給你遞歸，你會怎麼辦？

聰明的你一定會想到，就是把LALR的表直接人肉寫成帶有豐富的語義的代碼嘛。於是你就會發現你在解決這樣一件事情：

輸入1+2*3

首先輸入1，你得道了1

然後輸入+2，你生成了1+2的語法樹

然後看到*3，你發現不對，於是去修改1+2的語法樹，變成了1+(2*3)的語法樹。

……

所以說，到最後是要傻逼的。當然，parser combinator在對付特別多符號優先順序的表達式的時候，她就必須這樣做，因為不這麼做的話，會因為函數調用次數太多會有性能問題，而且這個問題很大。

謝謝邀請。

parser有手寫的。gcc和clang的parser都是手寫的，但都不是「自底向上」的。

parser界各種概念很多，很適合各種裝逼和吵架……其實很多概念只是各種處理字元串的自動機，怎麼寫好要看具體語言特點。而我覺得好的程序語言首先應該是設計給人用的，其次才是設計給機器parse的。

不推薦手寫可能的原因：

已經有（很多）不用你手寫的工具和語言了。
手寫出來的不容易寫好看，不好維護，尤其是各種自底向上的，往往到最後基本等同於自己寫了一遍yacc。

您可以自己手寫一個簡單的parser體驗一下（比如parse一下json？），在力所能及之內盡量把code整理得可讀一點，體驗一下箇中滋味，大概就心裡有譜了。教科書上那些古典的學術概念，在今天，我覺得知道個大概就行了。我不是搞PL的，不過他們搞PL的人自己都經常會懷疑他們各種parser概念實際上沒那麼大用，雖然他們的經典教科書里還是會花很大篇幅來講那些東西……

記得 Lua 就是第一版用yacc, 後面版本手寫，再後來又用yacc。

由此就可以看出用工具的優越性了。

真正原因是現有PL都是殘廢。LL好寫只是因為正好對應堆棧遞歸結構，LR沒這個對應就廢了。

老闆壓根寫不出來啊。。。。 LR用的狀態轉移表生成器代碼很好寫，但是靠人腦那一通 goto 和 closure 非不掛了不可。。換個說話，你要 hash 一個東西，比如用 md5 ，你自己給我用腦子算一個看看。。

這貨沒有LL可讀性好.最大的問題是手寫工作量太大了...一個功能完善的純正正則引擎不過十幾條文法規則的LALR的狀態少說200+以上...更別說各種編程語言了,為何不試試輕鬆的機器自動生成,自己擼個yacc呢~