王垠：談談Parser
一直很了解人們對于 parser 的誤解，可是一直都提不起興趣來闡述對它的觀點。然而我覺得是有必要解釋一下這個問題的時候了。我感覺得到大部分人對于 parser 的誤解之深，再不澄清一下，恐怕這些謬誤就要寫進歪曲的歷史教科書，到時候就沒有人知道真相了。
什么是 Parser
首先來科普一下。所謂 parser，一般是指把某種格式的文本（字符串）轉換成某種數據結構的過程。最常見的 parser，是把程序文本轉換成編譯器內部的一種叫做“抽象語法樹”（AST）的數據結構。也有簡單一些的 parser，用于處理 CSV，JSON，XML 之類的格式。
舉個例子，一個處理算數表達式的 parser，可以把“1+2”這樣的，含有1，+，2三個字符的字符串，轉換成一個對象（object）。這個對象就像new BinaryExpression (ADD, new Number (1)， new Number (2))這樣的 Java 構造函數調用生成出來的那樣。
之所以需要做這種從字符串到數據結構的轉換，是因為編譯器是無法直接操作“1+2”這樣的字符串的。實際上，代碼的本質根本就不是字符串，它本 來就是一個具有復雜拓撲的數據結構，就像電路一樣。“1+2”這個字符串只是對這種數據結構的一種“編碼”，就像 ZIP 或者 JPEG 只是對它們壓縮的數據的編碼一樣。
這種編碼可以方便你把代碼存到磁盤上，方便你用文本編輯器來修改它們，然而你必須知道，文本并不是代碼本身。所以從磁盤讀取了文本之后，你必須先“解碼”，才能方便地操作代碼的數據結構。比如，如果上面的 Java 代碼生成的 AST 節點叫node，你就可以用node.operator來訪問ADD，用node.left來訪問1，node.right來訪問2。這是很方便的。
對于程序語言，這種解碼的動作就叫做 parsing，用于解碼的那段代碼就叫做 parser。
Parser 在編譯器中的地位
那么貌似這樣說來，parser 是編譯器里面很關鍵的一個部分了？顯然，parser 是必不可少的，然而它并不像很多人想象的那么重要。Parser 的重要性和技術難度，被很多人嚴重的夸大了。一些人提到“編譯器”，就跟你提 LEX，YACC，ANTLR 等用于構造 parser 的工具，仿佛編譯器跟 parser 是等價的似的。還有些人，只要聽說別人寫了個 parser，就覺得這人編程水平很高，開始膜拜了。這些其實都顯示出人的膚淺。
我喜歡把 parser 稱為“萬里長征的第 0 步”，因為等你 parse 完畢得到了 AST，真正精華的編譯技術才算開始。一個先進的編譯器包含許多的步驟：語義分析，類型檢查/推導，代碼優化，機器代碼生成，…… 這每個步驟都是在對某種中間數據結構（比如 AST）進行分析或者轉化，它們完全不需要知道代碼的字符串形式。也就是說，一旦代碼通過了 parser，在后面的編譯過程里，你就可以完全忘記 parser 的存在。所以 parser 對于編譯器的地位，其實就像 ZIP 之于 JVM，就像 JPEG 之于 PhotoShop。Parser 雖然必不可少，然而它比起編譯器里面最重要的過程，是處于一種輔助性，工具性，次要的地位。
鑒于這個原因，好一點的大學里的程序語言（PL）課程，都完全沒有關于 parser 的內容。學生們往往直接用 Scheme 這樣代碼數據同形的語言，或者直接使用 AST 數據結構來構造程序。在 Kent Dybvig 這樣編譯器大師的課程上，學生直接跳過 parser 的構造，開始學習最精華的語義轉換和優化技術。實際上，Kent Dybvig 根本不認為 parser 算是編譯器的一部分。因為 AST 數據結構其實才是程序本身，而程序的文本只是這種數據結構的一種編碼形式。
Parser 技術發展的誤區
既然 parser 在編譯器中處于次要的地位，可是為什么還有人花那么大功夫研究各種炫酷的 parser 技術呢。LL，LR，GLR，LEX, YACC，Bison，parser combinator，ANTLR，PEG，…… 制造 parser 的工具似乎層出不窮，每出現一個新的工具都號稱可以處理更加復雜的語法。
很多人盲目地設計復雜的語法，然后用越來越復雜的 parser 技術去 parse 它們，這就是 parser 技術仍然在發展的原因。其實，向往復雜的語法，是程序語言領域流傳非常廣，危害非常大的錯誤傾向。在人類歷史的長河中，留下了許多難以磨滅的歷史性糟粕， 它們固化了人類對于語言設計的理念。很多人設計語言似乎不是為了拿來好用的，而是為了讓用它的人迷惑或者害怕。
有些人假定了數學是美好的語言，所以他們盲目的希望程序語言看起來更加像數學。于是他們模仿數學，制造了各種奇怪的操作符，制定它們的優先級，這樣你就可以寫出2 << 7 - 2 * 3這樣的代碼，而不需要給子表達式加上括號。還有很多人喜歡讓語法變得“簡練”，就為了少打幾個括號，分號，花括號，…… 可是由此帶來的結果是復雜，不一致，有多義性，難擴展的語法，以及障眼難讀，模棱兩可的代碼。
更有甚者，對數學的愚蠢做法執迷不悟的人，設計了像 Haskell 和 Coq 那樣的語言。在 Haskell 里面，你可以在代碼里定義新的操作符，指定它的“結合律”（associativity）和“優先級”（precedence）。這樣的語法設計，要求 parser 必須能夠在 parse 過程中途讀入并且加入新的 parse 規則。Coq 試圖更加“強大”一些，它讓你可以定義“mixfix 操作符”，也就是說你的操作符可以連接超過兩個表達式。這樣你就可以定義像if...then...else...這樣的“操作符”。
制造這樣復雜難懂的語法，其實沒有什么真正的好處。不但給程序員的學習造成了不必要的困難，讓代碼難以理解，而且也給 parser 的作者帶來了嚴重的挑戰。可是有些人就是喜歡制造問題，就像一句玩笑話說的：有困難要上，沒有困難，制造困難也要上！
如果你的語言語法很簡單（像 Scheme 那樣），你是不需要任何高深的 parser 理論的。說白了，你只需要知道如何 parse 匹配的括號。最多一個小時，幾百行 Java 代碼，我就能寫出一個 Scheme 的 parser。
可是很多人總是嫌問題不夠有難度，于是他們不停地制造更加復雜的語法，甚至會故意讓自己的語言看起來跟其它的不一樣，以示“創新”。當然了，這樣的語言就得用更加復雜的 parser 技術，這正好讓那些喜歡折騰復雜 parser 技術的人洋洋得意。
編譯原理課程的誤導
程序員們對于 parser 的誤解，很大程度上來自于大學編譯原理課程照本宣科的教育。很多老師自己都不理解編譯器的精髓，所以就只有按部就班的講一些“死知識”，灌輸“業界做法”。一般大學里上編譯原理課，都是捧著一本大部頭的“龍書”或者“虎書”， 花掉一個學期1/3 甚至2/3 的時間來學寫 parser。由于 parser 占據了大量時間，以至于很多真正精華的內容都被一筆帶過：語義分析，代碼優化，類型推導，靜態檢查，機器代碼生成，…… 以至于很多人上完了編譯原理課程，記憶中只留下寫 parser 的痛苦回憶。
“龍書”之類的教材在很多人心目中地位是如此之高，被譽為“經典”，然而其實除了開頭很大篇幅來講 parser 理論，這本書其它部分的水準其實相當低。大部分學生的反應其實是“看不懂”，然而由于一直以來沒有更好的選擇，它經典的地位真是難以動搖。“龍書”后來的 新版我瀏覽過一下，新加入了類型檢查/推導的部分，可是我看得出來，其實作者們自己對于類型理論都是一知半解，所以也就沒法寫清楚，讓人可以看懂了。
龍書作者的水平，跟 Dan Friedman，Kent Dybvig 這樣真正的大師比起來，其實差的老遠。如果你想真的深入理解編譯理論，最好是從 PL 課程的讀物，比如 EOPL 開始。我可以說 PL 這個領域，真的是高于編譯器領域的。請不要指望編譯器的作者能夠輕易設計出好的語言，因為他們可能根本不理解很多語言設計的東西，他們只是會按部就班地實 現某些別人設計的語言。可是反過來，理解了 PL 的理論，編譯器的東西只不過是把一種語言轉換成另外一種語言（機器語言）而已。工程的細枝末節很麻煩，可是當你掌握了精髓的原理，那些都容易摸索出來。
我寫 parser 的心得和秘訣
雖然我已經告訴你，給過度復雜的語言寫 parser 其實是很苦逼，沒有意思的工作，然而有些歷史性的錯誤已經造成了深遠的影響，所以很多時候雖然心知肚明，你也不得不妥協一下。由于像 C++，Java，JavaScript，Python 之類語言的流行，有時候你是被迫要給它們寫 parser。在這一節，我告訴你一些秘訣，也許可以幫助你更加容易的寫出這些語言的 parser。
很多人都覺得寫 parser 很難，一方面是由于語言設計的錯誤思想導致了復雜的語法，另外一方面是由于人們對于 parser 構造過程的思維誤區。很多人不理解 parser 的本質和真正的用途，所以他們總是試圖讓 parser 干一些它們本來不應該干的事情，或者對 parser 有一些不切實際的標準。當然，他們就會覺得 parser 非常難寫，非常容易出錯。
-
盡量拿別人寫的 parser 來用。維護一個 parser 是相當繁瑣耗時，回報很低的事情。一旦語言有所改動，你的 parser 就得跟著改。所以如果你能找到免費的 parser，那就最好不要自己寫。現在的趨勢是越來越多的語言在標準庫里提供可以 parse 它自己的 parser，比如 Python 和 Ruby。這樣你就可以用那語言寫一小段代碼調用標準的 parser，然后把它轉換成一種常用的數據交換格式，比如 JSON。然后你就可以用通用的 JSON parser 解析出你想要的數據結構了。
如果你直接使用別人的 parser，最好不要使用它原來的數據結構。因為一旦 parser 的作者在新版本改變了他的數據結構，你所有的代碼都會需要修改。我的秘訣是做一個“AST 轉換器”，先把別人的 AST 結構轉換成自己的 AST 結構，然后在自己的 AST 結構之上寫其它的代碼，這樣如果別人的 parser 修改了，你可以只改動 AST 轉換器，其它的代碼基本不需要修改。
用別人的 parser 也會有一些小麻煩。比如 Python 之類語言自帶的 parser，丟掉了很多我需要的信息，比如函數名的位置，等等。我需要進行一些 hack，找回我需要的數據。相對來說，這樣小的修補還是比從頭寫一個 parser 要劃得來。但是如果你實在找不到一個好的 parser，那就只好自己寫一個。
</li> -
很多人寫 parser，很在乎所謂的“one-pass parser”。他們試圖掃描一遍代碼文本就構造出最終的 AST 結構。可是其實如果你放松這個條件，允許用多 pass 的 parser，就會容易很多。你可以在第一遍用很容易的辦法構造一個粗略的樹結構，然后再寫一個遞歸樹遍歷過程，把某些在第一遍的時候沒法確定的結構進行 小規模的轉換，最后得到正確的 AST。
想要一遍就 parse 出最終的 AST，可以說是一種過早優化（premature optimization）。有些人盲目地認為只掃描一遍代碼，會比掃描兩遍要快一些。然而由于你必須在這一遍掃描里進行多度復雜的操作，最終的性能也許 還不如很快的掃完第一遍，然后再很快的遍歷轉換由此生成的樹結構。
</li> -
另外一些人試圖在 parse 的過程中做一些本來不屬于它做的事情，比如進行一些基本的語義檢查。有些人會讓 parser 檢查“使用未定義的變量”等語義錯誤，一旦發現就在當時報錯，終止。這種做法其實混淆了 parser 的作用，造成了不必要的復雜性。
就像我說的，parser 其實只是一個解碼器。parser 要做的事情，應該是從無結構的字符串里面，解碼產生有結構的數據結構。而像“使用未定義的變量”這樣的語義檢查，應該是在生成了 AST 之后，使用單獨的樹遍歷來進行的。人們常常混淆“解碼”，“語法”和“語義”三者的不同，導致他們寫出過度復雜，效率低下，難以維護的 parser。
</li> -
另一種常見的誤區是盲目的相信 YACC，ANTLR 之類所謂“parser generator”。實際上 parser generator 的概念看起來雖然美好，可是實際用起來幾乎全都是噩夢。事實上最好的 parser，比如 EDG C++ parser，幾乎全都是直接用普通的程序語言手寫而成的，而不是自動生成的。
這是因為 parser generator 都要求你使用某種特殊的描述語言來表示出語法，然后自動把它們轉換成 parser 的程序代碼。在這個轉換過程中，這種特殊的描述語言和生成的 parser 代碼之間，并沒有很強的語義連接關系。如果生成的 parser 有 bug，你很難從生成的 parser 代碼回溯到語法描述，找到錯誤的位置和原因。你沒法對語法描述進行 debug，因為它只是一個文本文件，根本不能運行。
所以如果你真的要寫 parser，我建議你直接用某種程序語言手寫代碼，使用普通的遞歸下降（recursive descent）寫法，或者 parser combinator 的寫法。只有手寫的 parser 才可以方便的 debug，而且可以輸出清晰，人類可理解的出錯信息。
</li> -
有些人喜歡死扣 BNF 范式，盲目的相信“LL”，“LR”等語法的區別，所以他們經常落入誤區，說“哎呀，這個語法不是 LL 的”，于是采用一些像 YACC 那樣的 LR parser generator，結果落入非常大的麻煩。其實，雖然有些語法看起來不是 LL 的，它們的 parser 卻仍然可以用普通的 recursive descent 的方式來寫。
這里的秘訣在于，語言規范里給出的 BNF 范式，其實并不是唯一的可以寫出 parser 的做法。BNF 只是一個基本的參照物，它讓你可以對語法有個清晰的概念，可是實際的 parser 卻不一定非得按照 BNF 的格式來寫。有時候你可以把語法的格式稍微改一改，變通一下，卻照樣可以正確地 parse 原來的語言。其實由于很多語言的語法都類似于C，所以很多時候你寫 parser 只需要看一些樣例程序，然后根據自己的經驗來寫，而不需要依據 BNF。
Recursive descent 和 parser combinator 寫出來的 parser 其實可以非常強大，甚至可以超越所謂“上下文無關文法”，因為在遞歸函數里面你可以做幾乎任意的事情，所以你甚至可以把上下文傳遞到遞歸函數里，然后根據 上下文來決定對當前的節點做什么事情。而且由于代碼可以得到很多的上下文信息，如果輸入的代碼有語法錯誤，你可以根據這些信息生成非常人性化的出錯信息。
</li> </ol>總結
所以你看到了，parser 并不是編譯器，它甚至不屬于編譯里很重要的東西。程序語言和編譯器里面有比 parser 重要很多，有趣很多的東西。Parser 的研究，其實是在解決一些根本不存在，或者人為制造的問題。復雜的語法導致了復雜的 parser 技術，它們仍然在給計算機世界帶來不必要的困擾和麻煩。對 parser 寫法的很多誤解，過度工程和過早優化，造成了很多人錯誤的高估寫 parser 的難度。
能寫 parser 并不是什么了不起的事情，其實它是非常苦逼，真正的程序語言和編譯器專家根本不屑于做的事情。所以如果你會寫 parser，請不要以為是什么了不起的事情，如果你看到有人寫了某種語言的 parser，也不要表現出讓人哭笑不得的膜拜之情。
來自: www.yinwang.org本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！