基於表驅動實現的詞法分析的一點疑問？

01-06

看了斯坦福大學編譯器公開課，表驅動的詞法解析好像就是先通過正則畫出nfa圖形，在根據nfa畫出dfa的圖形，然後根據dfa裡面的狀態在一個二維數組裡面一一做填充，實際上編程的操作真的這麼麻煩么？還要手動操作填充數組，然後才開始實現詞法分析。還是說實際上，一般是通過編程直接從正則-&>nfa-&>dfa-&>表驅動詞法解析實現？

實際上，一般都是狀態機，可以參考我這一篇文章基於LLVM開發編譯器（02）：詞法分析原理和這一篇文章基於LLVM開發編譯器（03）：詞法分析器的實現

我已經寫完了第四篇語法分析原理了，但是我還一直沒有上傳，因為我的代碼還沒有寫完，我現在是準備語法分析和語意分析一起做完了上傳，不過目前發現我要實現幾乎所有的Pascal 90標準的東西，工作量有點大，而且由於是教程，所以我在想辦法讓代碼更加清晰易讀。

是這樣做沒錯，不過通常都是寫代碼來實現的，不是讓你人肉實現：《構造正則表達式引擎》新鮮出爐啦！

你的想法是對的。通過編程直接從正則-&>nfa-&>dfa-&>表驅動詞法解析一條龍自動生成。比如我的一個玩具詞法分析器，若要分析3種正則表達式(整型、浮點、字元串)、17個保留字、27個運算符的詞法，自動生成的表格有410個狀態，222個終結態。當然狀態數量是有可能優化的，主要是正則表達式的形式可以優化。

https://github.com/nklofy/Compiler

正在做的一個玩具編譯器，用Java語言編寫。已經完成了詞法分析器和LR(1) parser表格的生成器。也就是模仿了lex和yacc的功能。詞法可以定義正則表達式、保留字、運算符，正則表達式目前支持[ - ] 多選一，( ) 括弧，* ? + 科林閉包，| 二選一這幾種表達方式。語法部分，現在只完成由語法式自動生成LR(1) parser表格。後續在寫根據規約式自動構造語法樹的功能。

其實我很不贊同學寫parser 尤其是scanner 的時候一上來就看各種自動機。

直接回答你的疑問就是：在實際中手寫詞法分析器時，你所說的「RE -&> NFA -&> DFA -&> Scanning Table」一個都不會出現。原因有二：

1. 書上說的這麼複雜的一系列計算都是為了做scanner generator（比如flex）。自動生成的scanner 一般有兩部分，一部分是固定的一段代碼，相當於一個interpreter，它讀入scanning table 和源程序，生成一系列的token；另一部分就是scanning table，它直接對應你給的詞法規則，而要通過「程序」生成這個table 就需要你說的那一長串計算。然而你手寫scanner 的時候根本不用考慮這些，@藍色大大給出的代碼就是典型的encoding switch 方法實現scanner（雖然我從沒寫過C++，但能看出他的C++ 寫的很漂亮）。你別看他的代碼里有很多state 這樣的變數名，但實際上你寫的時候根本不用去想什麼狀態機的狀態轉換，你只需要知道三件事：都有哪些種類的token（keyword，id，literature…），每種token 都長什麼樣，有哪些token 有公共前綴（比如除法/和注釋開頭/*就有公共前綴，你需要在看到/之後分情況）。然後就可以寫一個基於向前看字元的scanner了！如圖，

2. 你所說的手動計算並填寫數組是一件吃力不討好的事，因為table driven 的scanner 運行效率很低下，根據我實際測試：table &<&< switch &< pack

那是詞法分析器的生成器的實現原理，這種生成器有現成的，

如果你想用這種途徑寫詞法分析器，那麼只需要輸入正則表達式就好了，

否則，你就根據你定義的詞法規則直接代碼判斷就好了。

但是如果你想練習一下，也可以試著實現這個生成器………

像lex這種詞法分析器生成器，一般是通過正則表達式定義詞法，程序構造出nfa-&>dfa-&>詞法解析器。但是工程上大多數編譯器考慮到性能和效率，都會採用手工構造的方式直接編寫詞法解析器。

這種方式一般parse生成器會使用；手寫的話，一般自己寫狀態機就搞定了