如何寫一個解釋器(1):編譯原理

最近在看dsl的東西，對于外部dsl，寫一個解釋器是必不可少的。我試圖歸納一下我學到的，以寫一個解釋器為目标，講一下如果來實作一個可用的解釋器。一個解釋器通常可以分為一下幾個階段：

詞法分析(lexer)

文法分析(parser, bnf, cfg, ast)

語義分析(ast的處理， annotated ast)

目智語言生成(stack-based)

這裡的解釋器不包括目智語言的執行和運作時環境，如果需要類似于python/ruby的解析執行器的話，還需要bytecode-compiler,

bytecode-interpreter和runtime。我們這裡隻談解釋的部分，不談執行的部分。作為dsl我們大多都有宿主語言，通常也就我們生成的目智語言，有關執行這部分，我們交給目智語言去解決。換個說法，我們隻讨論一個完整解釋執行器的前端。

目前編譯技術已經得到極大發展，對于詞法分析和文法分析，我們可以借助成熟的工具或庫很快的完成，極大簡化了寫解釋器的難度。對于一個解釋器來說我們需要自己處理的部分基本上集中于語義的分析，即ast的處理和目智語言的生成。其實這裡的ast的處理結果相當于一個與執行環境無關的中間語言表示，而目智語言的生成就是針對目智語言的特性，将annotated

ast轉換為目智語言以友善在目智語言的運作環境中運作。

繼續扯扯淡，lisp語言的文法基本上就是直接寫ast，直接用ast的表示法來表示程式，是以lisp文法是最貼近于編譯器的中間表示，開始可能根本就不是給一般人用的，誰知道這麼多人喜歡用。lisp之是以叫list

processer那是因為lisp直接處理ast的資料結構表示即nested list，是以才叫list

processor，一點都沒有謙虛的意思。在資料結構裡，表示樹這種資料結構的，最簡單直接的辦法就是nested

list(通過linked-list了來實作)。而且這種結構利于遞歸周遊，友善stack-based執行或者代碼的生成。

詞法分析是将源代碼轉換成tokens，這些tokens有些事關鍵字，有些是變量，有些是字面量，有些是文法結構，等等。比如：

var s = 5; if(s > 0){   print “greater than 5” }

輸出的tokens是[var, s, 5, ;, if, (, s, >, 0, ), {, print, “greater than 5”,

}]，這些tokens是有順序的，但是沒有具體的文法和語義。我們的詞法分析器就是将源代碼作為輸入，輸出就是這個tokens的序列。

詞法分析中我們會遇到一些問題，比如當我們看到whe的時候我們不知道這個是個變量名還是when關鍵字，這個需要看連續的4個字元才可以知道，這個就是ll(4)，ll代表從左邊依次讀取，從最左邊的w->wh-whe->when依次來推導出這個是關鍵字還是變量。

這個我們這裡不多講，細節可以找本編譯器的書來看看。有很多現成的工具和類庫幫我們完成這樣的工作，比如lex, flex, ply,等等。

文法分析是幫我們分析這個token序列是否符合我們的文法，并且将文法分析結果用ast表示出來。既然是檢查文法和按文法抽取出ast，那麼我們就需要表示文法，通常我們使用backs-naur

format，也就是我們常說的bnf表示法。不過好笑的是bnf本身是個規範，不是具體的實作。也就是說同樣bnf，不同的實作有不同的表示。比如:

statement ::= statement | empty

這個表示稱為statement的産生式，也就是statement的文法規則，同樣的有的bnf表示法是這樣表示的

statement –> statement or empty

其中::=和->, |和or，是一樣的意思。

文法分析的結果就是符合文法的ast，也可以說是符合文法的一個執行個體。

文法分析階段我們也需要處理一些問題，比如為了解決算術的二義性，我們需要引入優先級(precedence)，和結合性(associative)。

文法分析也有現成的工具和類庫可以使用比如yacc, bison, antlr, ply等等。

符合文法的源代碼不一定有意義，比如a/0，這個就是沒有意義的，這個我們需要在語義處理階段解決。

待續…