如何寫好一個parser？

01-16

試著瞎寫了一個東西，目標是把數學表達式parse成AST，支持變數/函數重載等等…
但是寫下來覺得代碼結構亂成一鍋粥，怎麼看怎麼不順眼，幾乎沒法繼續維護。
https://github.com/cpdyj/calc
高中黨，沒正式學過編譯原理，啥都不懂就知道一個逆波蘭表達式，一直在自己摸索

（因為沒做測試，結果是不是正確的不太清楚，蜜汁自信）
=======
感謝各位，我還是老老實實去學LL(1)文法去吧…

瞎寫啥，都用java了，為啥不用antlr。

我來講個笑話，因為高中的時候，記憶力不行，為了搞這個，我至少重新發明了三遍 shunting yard algorithm (因為忘記已經寫過了) ... 好像因為不自量力想自行實現浮點數，怎麼都寫不對，每次都爛尾了 ... 還不如學點Erlang (很遺憾那時候孤陋寡聞沒聽說過Erlang)

同樣沒有接觸編譯原理，我也沒花多久，現在感覺還挺滿意的。

要是對某門語言已足夠熟練，十幾分鐘寫好它的parser我覺得ok。當然我是自己寫了parser gen框架的。

我就說說這種框架怎麼設計。

從信息量入手，parser的關鍵信息是什麼。

不過是產生式。一個bnf文件一定能代表其所有信息。

你從token好的片語里挖出一個ast，不過就是從tokenized的片語開頭，做一次部分模式匹配，然後消耗掉一些詞。

模式匹配可能出現死結，比如左遞歸啥的。這種解決辦法其實很簡單，你根據parsed詞數和當前parser的名字(一個bnf的等式就定義一個ast的parser)生成二元組的歷史記錄，然後，對任意parser，片語喂進來parse完(注意可能並不匹配當前parser)之後，歷史記錄的條數不會變多或變少。

但在這個過程中，一般parser是嵌套的，比如 Expr ::= LambdaDef | OrExpr，而歷史記錄是整體共享的，所以被嵌套的parser會比外部得parser多一條歷史記錄。

parse完後，你需要在當前parser里pop一下之前push的歷史記錄，如果parse成功，parsed詞數就需要更新，否則不變。

那死結就很好想了:

當歷史記錄中有兩組完全相同的記錄，比如(Expr, 50)出現兩次，那麼這就是個死結了(除開左遞歸的情形)。

把這個死結當做處理失敗就ok。

如果有斷句符號就更簡單了，左遞歸情形從右邊開始parse就可以了。

到這也能看出來我這個框架暫時也不是那麼萬能。比如今天我要寫c++那種類型定義, e.g int(int)(int, int)，是接收int返回int-&>int的類型

Type ::= Type "(" [TypeList] ")" | Identifier

TypeList ::= Type ( "," Type)*

這個就出了問題，因為，用上面那種死結消除會跳過Type的第一種可能性，除非Type是最高級語法節點(但這顯然是tan 90deg)，所以對左遞歸解析不太好。

不過我要是有時間明天就能搞定這個問題，比如我把之前那個歷史記錄里的(parser名, parsed詞數)改成(parser名, parsed詞數, 出現次數)。然後把出現次數上限做成可選參數，默認是1，那麼把Type這個Parser的上限改成是2，就完美解決了這個問題。

雖然更簡單的做法是我直接改一行代碼(把檢查歷史記錄是否重複的操作，變成重複記錄的數量上限檢查)就能解決這個問題，但這有點打補丁，我不喜歡。

所以，題主你看，具體想清楚問題，parser是不是很簡單呢？

你需要學習遞歸下降和LL(k)型文法，忘掉什麼符號棧表達式棧這些鬼東西

我是從C++入門的，我推薦C++之父的那本C++程序設計原理與實踐，裡面有一段就是教你用遞歸下降寫一個表達式計算器。

這裡還有一篇文章Parsing Expressions by Recursive Descent 教你如何手寫遞歸下降

遞歸下降和ll(k)是對人腦最友好的一種演算法/文法，用它來寫parser，熟練了之後就只剩苦力活了

那就來看看我寫的小玩具吧~無聊時寫的，當時YY寫一個能解決高數書上所有問題的程序，但目前看來項目是擱置了哈哈哈哈（我會繼續寫的）

不僅支持數學表達式parse成AST，還支持函數求導和表達式展開（去括弧）哦，當然求個值也不在話下。（詳見readme）

高數書上的求導題（包括偏導）基本都能得到答案，我也用了一些方法，盡量讓程序輸出一個可讀的結果。

就用了LL(1)，你可以參考一下我對lexer和parser的設計。

文法設計在.cpp里

啊對了，有人如果讀完了代碼可以幫我實現幾個友好的介面呀~項目停工的時候還在測試呢

鏈接：https://github.com/ChisBread/ChisMath

同高中黨，但編譯原理還是學了學，沒怎麼按理論來瞎寫了個四不像的Parser，題主可以參考下，C++寫的： https://github.com/covscript/covscript

編譯原理後邊有用Java編寫的完整的編譯器前端示例，題主可以參考一下，非常基礎的寫法，不記得了好像是LL(1)型文法。

其他答主也放了一些乾貨，無奈文筆不好，時間也不太多，沒寫過相關的文章。個人感覺代碼是最好的老師，古話說得好，盡信書則不如無書。

見我專欄：【CEval系列】實現四則運算https://zhuanlan.zhihu.com/p/29632312

c++，不用現成解析器和正則表達式。

採用ll1解析法，然而我沒用遞歸。

https://github.com/wkgcass/Latte-lang

確實容易寫成一坨，但是遞歸下降已經相對很清晰了。能寫生成式就能寫遞歸下降。

同高中黨，我專欄有兩篇講用Haskell寫Parser的文章，看完就會，你甚至不需要會Haskell。

千里冰封被吊打的日常 - 使用 Haskell 編寫靈活的 Parser （上）（分享自知乎網）https://zhuanlan.zhihu.com/p/28133484

使用 Haskell 編寫靈活的 Parser （下）（分享自知乎網）https://zhuanlan.zhihu.com/p/28162006

寫出來賊美觀，基本上就是換了個語法的ebnf，可維護性極高。

antlr解決你的煩惱

那就了解下編譯原理吧，也不用學得太深，能知道lex/yacc的用法就好。

複雜點的解析，不是簡單的弄兩個棧就能實現的，需要學習LL和LR相關文法；

不過這玩意學起來累，實現起來更累，好在前人提供了現成的工具lex/yacc，只要把語法規則寫出來，就能一鍵獲得生成AST的程序，包攬lexer/parser/semant

編譯器前端這種已經有完整並且成熟實現的，直接拿來用好了；自己摸索簡直是浪費時間；把這些時間用在開拓未探索未成熟的領域上多好。

可以試著用ANTLR，直接生成一個ast，用裡面的walker遛著走，簡直比我被我家狗遛都快。

不如試試Haskell，我覺得FP做這種事情在設計上有天然的優勢。

我覺得寫計算器大概分兩步？

1 一個Parser把AST傳給Evaluator

2 Evaluator對AST進行求職

這兩個大部件的設計要分開，然後各自都要有好的拓展性

圖靈機學過了嗎？自動機明白什麼意思嗎？還有文法規則會了嗎。不會寫啥Parser！因為你寫了也不懂為什麼這個叫Parser！