在軟體開發過程,我們很可能得寫大量的程式碼來完成一些繁瑣、平凡的工作,避開這個窠臼的辦法就是「自動化」。誠如 Kernighan 和 Pike 在 The Practice of Programming 一書所闡述的,優秀的軟體設計運用幾個基本原則:簡單(simplicity)、清晰(clarity)、一般性(generality)、自動化(automation)。
舉個例子, IC designers 常會跟 f/w 人員一起關起門來,私下協調出各種用途的 registers (memory mapped I/O),這些開放給 f/w 人員使用的 register 介面,會有一份以 Verilog 形式存在,另一份則以 C code 的形式存在,在 IC 開發過程,這些 registers 會經歷多次的變更(例如改名字、改位址、添加 registers、刪減 registers 等)。可以想見,要手動讓這些 registers 在 Verilog 及 C 間維持一致,是件繁瑣、容易出錯的事。
電腦在處理這類格式轉換工作時,得有個 parser 來剖析源文件;偏偏要建構 parser 也有好些瑣碎的東西必須處理。幸好 Compiler 是門發展已久的學問,有許多 parser generators 可以讓這些繁瑣的建構過程自動化。
早期的 parser generators (例如: Yacc )幾乎都是 LR 系列的,一個主要的原因是,教科書告訴我們 LL parser 是不切實際的,只有 LR parsers 才能有高效的表現;另一個理由是, LR parsers 想要手寫,大概也很難 :)
好玩的是後來出現了幾個廣為流行的 parser generators (例如: JavaCC, ANTLR, Boost.Spirit),都走 LL 風。這勾起我的好奇心,細查下才發現 LL 風的 parser generators 在 90 年代有了新的技術突破,我該 update 一下之前教科書塞進我腦袋的資訊了 =.="
如果大家也想複習一下學校教的 Compiler 技術,可以不用翻箱子找課本了,因為維基百科對這方面的資料,紀錄還滿完整的。文末附上我為相關條目所作的分類,相信可以為大家省卻一些時間。
- Parse Tree (Concrete Syntax Tree)
- Abstract Syntax Tree (Syntax Tree)
- Parsing (syntactic analysis)
- Top-down parsing
- Backtracking parser
- trial-and-error
- Predictive parser
- Recursive descent parser
- LL parser / LL(k) parser
- parses the input from Left to right, and
- constructs a Leftmost derivation of the sentence
- k tokens of look-ahead
- Bottom-up parsing (shift-reduce parsing)
- LR parser / LR (k) parser
- reads input from Left to right
- produces a Rightmost derivation
- k unconsumed "look ahead" input symbols used in making parsing decisions.
- SLR parser: Simple LR parser
- LALR parser: Lookahead LR parser
- GLR parser: Generalized LR parser