為什麼很多語言的實現裡面的 Lexer 都沒有使用 DFA？

01-06

最近看完龍書的 Front end 部分，也參觀了很多語言的實現，比如 Python（CPython）、Lua、Ruby（CRuby），發現他們在詞法分析部分基本上都沒有使用 DFA 來寫，請問，龍書花了那麼多篇幅講的有限自動機為什麼沒有在這些語言的實現裡面看到？

因為大家有閑唄。其實手寫的lexer/scanner也是一種實現DFA的方式，只是狀態遷移可能隱含在代碼中而沒有一個顯式的「狀態」變數。

單獨拿出來說，正則表達式在大量程序里都有應用，背後的原理可以是基於DFA/NFA。

但為啥題主說的那些語言實現沒有用lex/flex之類的、指定詞法並自動生成基於顯式狀態遷移的lexer？多半不是技術原因；也有可能是不適用。

以CPython為例，lexer的入口在：cpython/tokenizer.c，它的詞法相當簡單，與其依賴一個外部工具由詞法規則（正則表達式）生成lexer，還不如直接手寫方便。當然這是見仁見智的。

CPython的parser也是手寫的。

Lua也是同理：詞法語法都簡單，而且要盡量不依賴外部工具，所以選擇手寫是很自然的。

畢竟，自己手寫的代碼，邏輯全部都浮現在代碼中，容易讓人讀懂，也容易調試。

生成的代碼（特別是基於表驅動方式的代碼）通常都遠不如手寫代碼可讀。ANTLR可能算是個例外吧。

以CRuby為例，它的lexer是手寫的，但parser是用bison（yacc變種）生成的，這又怎麼說？flex+bison不是常見組合么？

Ruby的詞法和語法極其複雜，它的詞法分析其實是上下文相關的，必須要讓parser能反過來向lexer傳遞狀態才可以繼續分析下去。這超出了flex的常見使用場景，用它寫反而不方便，於是就手寫了。同樣的情況在IronRuby也可以看到，parser是用GPPG生成的，但lexer是手寫的。

上面是手寫lexer的情況，再給個「反方」比較好。

Groovy就是個好例子。Groovy語法：groovy-core/groovy.g，parser和lexer都是用ANTLR生成出來的。不過Groovy的實現好不好也見仁見智…

上面各位大大說得很對了，但我在這裡想黑一下龍書。

龍書的一大特點就是parsing部分講得特別多（足足有半本啊），但這也導致了一個最大的缺點：對於新手來說，細節掩蓋了本質。

另一本書《Programming Language Pragmatic》把parsing 部分講得很簡略，就是簡單粗暴的三步：需要做什麼（描述問題）、怎麼做（描述演算法）、怎麼寫成程序。比如詞法分析部分講完automaton後直接告訴你，DFA有兩種實現方式：

1. Nested case statement （手寫）

2. table-driven （自動生成）

然後給了你代碼框架（這裡以nested case statement 為例）：

然後告訴你最外層case覆蓋DFA的所有狀態，內層每個case覆蓋這個狀態的所有轉換。特別清晰簡單有木有！！！編程時候直接填空就行了！！

所以，龍書就是專門坑新手的，不懂不是你的錯。

或者你了解一些原理之後可以去看《編程語言實現模式》，這本書里的詞法分析直接用了LL(1)，教你直接從正則表達式轉換程序，連DFA都省了，你聰明的話順便還悟出了scannerless parser 的原理，多好。

這個得看怎麼說。如果你看的是這本書（我還要推薦一次，國內有影印版）：Compiler Construction: Principles and Practice: Kenneth C. Louden: 9780534939724: Amazon.com: Books。裡面提到 Automaton 的三種形式：

代碼位置隱含；
switch-case 加 state 變數；
table-based。

Lua lexer 就是第一種，怎麼能說不是呢？

DFA這樣的東西是用來實現自動化工具的，但是「人肉」實現Lexer就完全不必了，不過狀態機是重要而且需要的，與此同理，語法分析器也有First和Follow集合等理論（也是用於ANTLR等自動化工具），其實實際編寫也很多是「人肉觀察法」加直接遞歸下降就完了，很少去分析其First和Follow集合。LLVMPascalCompiler/scanner.cpp at master · FrozenGene/LLVMPascalCompiler · GitHub

產品級別的編譯器需要對源代碼中的各種錯誤給出友好的提示信息。而DFA在這方面無法滿足需要。