以鶸ice為例，手擼一個解釋器（一）明確目標

github.com

# HelloWorld.iceprint("hello, world")

前言（廢話）

其實從開始學習編譯原理到現在已經有快半年的時間了，但是其間常常不能堅持看下去龍書（經常三天打魚兩天晒網，更何況每次打魚不到半小時就累得不行又會放下書（笑）），截至到現在只勉強看完了前六章的部分，半年間其它事也沒有做，其實想想上大學已經快兩年了還是一事無成，知識也沒有學到，不免覺得很羞愧。

暑假也要到了，這個學期馬上也要結束了，臨近大二結束之際，還是嘗試著寫一下以前想寫的玩具吧，而本系列就是對這段過程的記錄，也算是對龍書前六部分的一個小實踐&總結（後面的部分可能看完了我也寫不出什麼東西來）。

其實再寫這個解釋器之前，我是拿lex + yacc + llvm照著tutorial試著拼過一個編譯器，但是llvm對我來說可能有些太難了（苦笑）。殘破不堪的代碼在lyli分支上。

這個系列的教程（如果可以算作教程的話），其實主要還是實現了前端部分（一樣有很多bug），而parser早就被研究透了，所以本教程基本上沒有什麼價值，可能唯一具有優勢的地方就是我跟願意看這幾篇文章的讀者大概是相同的入門（或者還未入門）的水平。

本教程分為四章

1. 明確目標 & 設計語言
2. 實現詞法分析器
3. 實現語法分析器
4. 實現基礎數據類型

且希望能達到在讀者閱讀完本系列後，能完成一個支持以下幾項的解釋器語言

1. 整型、浮點型以及字元串類型
2. 常見雙目運算符
3. 變數定義
4. 函數定義及調用
5. 基本控制流語句
6. lambda表達式

適合讀者

1. 對編譯原理感興趣，但是還尚未正式的開始學習
2. 嘗試完成一個玩具解釋器但不知道如何下手

正文

在正式手擼之前，我們要先確立我們要擼的是個什麼玩意兒（你這不是廢話嗎摔）。畢竟在後期想要增加一些新的騷操作（新特性）的時候，若沒有在一開始進行設計，難免會出現各種重構上令人煩躁的問題（雖然如果你按照本教程擼出來的解釋器必然會帶來重構上各種糟糕的問題，但是重構本身就是一件會帶來各種糟糕的問題的事情（所以就不要介意了）），但是在正式寫代碼之前進行設計，總是一件應該做的事。

解釋什麼

從解釋器角度來說，我們解釋的是字元串，在驗證字元串滿足規則後進行解釋，在解釋完之後將其按照語義正確執行，而這個規則就是我們Ice的語法規則。

從語法分析的角度來說，我們解釋的是token序列，且通過預測分析法依據token序列選擇正確的產生式並返回抽象語法樹（Abstract Syntax Tree）。

輸入形式

只考慮互動式輸入（即一行一行的輸入）

如何解釋

本項目中主要包含以下幾個類：

• Token：實例化的Token對象包含一個詞素的類型以及詞素值
• LexicalAnalyzer：解析輸入字元串，返回token序列
• Node：實例化的Node及其派生類對象包含AST中一個節點所應具有的信息
• SyntaxAnalyzer：根據token序列預測分析，返回AST（實質是一個Node或其派生類實例）
• IceObject：包括自身類型信息，以及實現相關運算

• Env：符號表，存儲Ice運行時的對象信息
• Interpreter：只提供run()介面供main函數調用，隱藏內部邏輯

好了，基本上結構就是這樣，下面可以著手考慮Ice具備怎麼樣的語法了。

Ice 語法

整形、浮點型以及字元串類型

11.0"hello, world"

常見雙目運算符

1 + 1(100 + 20) * 6 / 310 = 105 <= 3

變數定義

@a: 1

函數定義及調用

@add(a, b): a + b@mul(a, b){ return a * b}mul(mul(2, 3), add(2, 3))

基本控制流語句

@fib(n){ if (n = 0) + (n = 1) { return 1 } else { return fib(n-1) + fib(n-2) }}fib(10) # 89@a: 3while a{ print(a) @a: a - 1}@a: 0do { @a: a + 1 if a = 3 { break } print(a)} while a < 5for 1 to 5{ @a: a + 1 if a = 3 { continue } print(a)}

lambda表達式

@add(a, b): a + b@mul: @(a, b){ return a * b}@(a, b){ return a / b }(9, 3)@quadraticSum: @(a, b){ @sqrt: @(n){ return n * n } return @(a, b){ return a + b }(sqrt(a), sqrt(b))}

基本上就是這樣，那麼如果你還繼續打算看的話，下一章將會開始手擼Ice的詞法分析器。