[JavaScript Interpreter]動手寫一個JavaScript直譯器 | Part 4 語法結構(中)

使用直譯器解析基本的JavaScript語法

上一篇文章裡，我們讓直譯器能夠解析與執行抽象語法樹中變數定義與賦值的內容，並可以做到一些簡單的計算與記憶的工作，但要省略大量重複的程式碼，執行函數的能力是必不可少的。本篇文章要來實作的就是變數作用域與函數的部分，在文章最後，我們會做出一個能夠定義與執行函數、將結果透過console.log()的方式顯示出來的直譯器。

Variable Scope

我們先來看看變數作用域，一組{ }會建立一個BlockStatement，在Block裡面的新的變數聲明並不會影響到外部，而是在自己的作用域內運作。

要實作變數作用域，首先要修改TokenType與Lexer，因為我們要能夠解析 { 與 } 符號 :

src/token.ts

src/lexer.ts

接下來則是建立BlockStatement節點，BlockStatement只有一個body屬性 :

src/ast.ts

輪到Parser要解析Block，由於Block與Program解析的方式都一樣，因此我們將原先在Program內的解析過程獨立出來，作為一個body方法，並新增解析Block的部分，讓Block與Program能夠共用相同的解析過程 :

src/parser.ts

在解析body時若遇到 { ，我們便會建立一個BlockStatement，並且再次調用body()來解析BlockStatement的body部分，而我們也將skipNewLine抽出來，以便以後更好處理各種可能會換行的情況。

接下來則是最重要的Interpreter部分，由於JavaScript的歷史關係，用來定義變數的var與let、const有不同的作用域，且var變數可以被重新定義，而let、const不行，而我們原先預備用來處理嵌套作用域的Stack並無法處理如此複雜的行為，因此我們只能捨棄原來的符號表做法，改為定義一個新的SymbolTable類別來處理這個問題 :

src/symbolTable.ts

可以看到整個類別其實就是一個LinkedList，每個SymbolTable會指向他的前一個SymbolTable，除了原先用來儲存資料的HashMap外，另外加上了不同的Scope來處理作用域不同的問題。SymbolTable除了將HashMap的get，set做包裝外，又另外建立一個declare方法 :

1. get() : 若在當前table內有值則直接取出，若無則向前一個作用域取得，當所有作用域都找不到時會拋出ReferenceError。
2. set() : 變數賦值，如同get一樣向前尋找有該變數定義的作用域，當所有作用域都找不到時，會在第一個作用域(global)進行定義。而在賦值之前會先判斷變數定義的kind，若是嘗試對const賦值則會拋出TypeError。
3. declare() : 宣告變數，由於var的作用域只在function與global，因此若非這兩者(也就是當前作用域是block)，則會嘗試將var定義在前一個作用域。接著判斷當前作用域有沒有已定義該變數，若無便可以在當前作用域宣告新變數，但就算已有定義，如果原先定義與新的定義都是var，又可以被重新覆蓋，以上條件全都不符合則會拋出SyntaxError。

建立好SymbolTable類別後，將我們的Interpreter原先的SymbolTable稍加修改，並加上對應的visitBlockStatement方法 :

src/interpreter.ts

修改完成後，我們可以進行測試 :

let a = 0;
{
    a;
    const a = 1;
    a;
}
a;

應該會輸出這樣的結果 :

undefined
0,,1
0

我們觀察輸出的結果 :

1. 第一行undefined是因為variableDeclaration沒有回傳值。
2. 第二行實際上是一個array，是BlockStatement的執行結果，第一個數字是a這個Identifier的回傳值，因為當前作用域沒有定義a，因此會向前一個作用域取值，得到外層的a=0。第二個是variableDeclaration回傳的undefined，在這裡沒有顯示出來。第三個數字一樣是a的回傳值，但在此時內層的a已經被定義，因此得到a=1。
3. 第三行是在離開這個Block後再次取得a，由於已經不在剛剛a=1的作用域內了，因此取得到的會是最初定義的a=0。

測試成功 !

(這裡特別注意到，若直接以Node.js來執行這段程式，實際上會拋出一個錯誤 : ReferenceError: Cannot access 'a' before initialization，原因是V8引擎在解析JavaScript時，會先對程式碼進行靜態分析，而第三行的 "a;" 被認為使用了尚未初始化的值，因此出現這個錯誤。)

Functions

在有了作用域的概念後，要實作Function的功能就較為方便了，首先先來看看函數定義的抽象語法樹結構，這裡直接看一個較為複雜的結構 :

一般的函數定義，有一個ReturnStatement

ReturnStatement回傳一個匿名函數

這個範例可以直接看出JavaScript兩種不同的函數類型，一個是常見的具名函數定義，用的是FunctionDeclaration，另一種則是作為回傳值的匿名函數，用的是FunctionExpression，另外也可以看到return關鍵字會產生新的ReturnStatement，這些是接下來我們要實作的主要重點之一。

首先當然是要修改TokenType與Lexer來處理新的function與return 關鍵字 :

src/token.ts

src/lexer.ts

接下來是三種新的ASTNode :

src/ast.ts

這裡我們將function中一些像是async、generator之類的修飾詞先忽略，只專心處理最基本的元素。

有了新的抽象語法樹節點後，接下來要讓Parser能夠產生出對應的節點 :

src/parser.ts

因為funcExpression也是一種表達式，於是我們在factor()進行判斷，而funcDeclaration與ReturnStatement只能出現在Block裡面，因此在body()裡面進行解析。

這裡我們在解析funcDeclaration時，先將ID解析出來，將所有的參數都解析成Identifier(暫時忽略有預設值的可能)，最後呼叫body()來解析block。而funcExpression的處理上幾乎相同，差別只在funcExpression的ID可以為空。

最後則是核心的Interpreter部分 :

src/interpreter.ts

我們對Interpreter作了以下修改 :

1. 建立visitFunctionExpression，該方法直接回傳一個function，將一個新的symbolTable透過閉包傳進此function裡面，接著進行參數賦值與Block迭代，最後將迭代的結果回傳。
2. 建立visitFunctionDeclaration，呼叫visitFunctionExpression，將得到的function存在symbolTable裡面。
3. 將visitBlockStatement迭代body的部分獨立出來成為iterateBlock方法。
4. iterateBlock會判斷回傳的物件是否有return的標記，若有則進行return。
5. 建立visitReturnStatement方法，將argument執行結果標記後回傳。

Call Expression

現在我們的直譯器已經有建立function的能力了，但是若要執行function的話，還需要建立新的CallExpression :

執行function需要的括號我們已經有能力解析了，因此Token與Lexer不需要修改，只需要建立新的ASTNode :

src/ast.ts

callee是被執行的function，args是傳入的參數。

下一步是在Parser裡新增解析CallExpression的方法 :

src/parser.ts

同樣在factor解析時進行判斷，若Identifier後面接的是括號，則將這個組合解析成CallExpression，而這裡的while迴圈是為了處理callee不是Identifier而是其他Expression的情形，在底下的示意圖可以看到，這裡的callee是另外一個CallExpression。

CallExpression做為下一個Callexpression的callee

最後要做的就是在Interpreter裡為CallExpression新增對應的處理方法 :

src/interpreter.ts

這個部分就比較簡單一點，先將callee找出來後，判斷若不是function則直接拋出例外，接著將args依序走訪過後代入callee執行，再將結果回傳。

到目前為止function的部分就完成了，我們可以透過以下的程式碼進行測試 :

function add(a) {
    return function (b) {
        return a + b;
    };
}
add(1)(4);

應該可以得到以下結果 :

undefined
5

這裡的undefined是functionDeclaration的結果，而5則是真正的執行結果。

在以上的測試過程中應該可以看到，因為我們會印出每一行的執行結果，所以一直有undefined被顯示出來，影響我們的測試流程與觀看體驗，因此接下來我們要做的就是讓我們的直譯器能夠讀懂console.log()這樣的語法。

Member Expression

本篇文章最後一個部分是MemberExpression，也就是透過" . "來取得某物件的成員屬性的這個功能。

我們首先需要解析新的Token " . " :

src/token.ts

src/lexer.ts

接下來看看抽象語法樹，我們將console.log放到AST explorer上做解析 :

可以看到這裡有MemberExpression這個新的ASTNode，object是我們要存取的物件，而property則是該物件的屬性，在這個範例中，console是object，而log則是property。我們按需求將MemberExpression建立出來 :

src/ast.ts

接下來的任務是修改Parser來解析出MemberExpression，我們同樣在factor裡面進行解析 :

src/parser.ts

由於MemberExpression與CallExpression一樣可以鏈式呼叫，因此也將判斷的邏輯放在while迴圈裡。

再來是Interpreter的部分，直接使用JavaScript的特性來取得物件屬性 :

src/interpreter.ts

這樣MemberExpression的部分就處理完了，但是距離要使用console.log還差最後一步，那就是我們的直譯器會嘗試在symbolTable裡尋找console物件，但我們並沒有定義console，因此需要在Interpreter的建構子中預先定義好。

src/interpreter.ts

如此一來，當我們嘗試在symbolTable裡取得console的時候，就可以得到我們注入的console物件了。

撰寫一個簡單的console.log的程式碼來看看執行結果 :

console.log(123);

執行結果 :

123
undefined

這樣就成功了 !

最後我們將index.ts稍作整理，若是有指定文件路徑的執行，就不會印出執行結果 :

src/index.ts

我們來撰寫一段複雜一點的程式碼，測試看看執行結果是否正確 :

js/test.js

可以直接用node來執行看看這段程式與我們的直譯器輸出的結果是否相同。

本篇文章的內容到這裡就結束了，本篇我們介紹了變數作用域的概念，以及實作新的symbolTable來符合變數作用域的規則，我們也能夠定義與執行一般以及匿名的function，最後實作了MemberExpression，並通過注入Node.js執行環境的console來執行log這個function。

下一次我們會先調整目前直譯器的架構，來解決REPL模式中上下文無法繼承的問題(因為每行都相當於是新的直譯器在執行)，並且進行一些較為基礎而繁瑣的工作，包括各種數學、邏輯運算符號等等，來為迴圈以及流程控制做準備。

這個系列的完整內容可以到我的Github Repo上參考。

References :

AST explorer

[JavaScript Interpreter]系列所有文章

動手寫一個JavaScript直譯器 | Part 0 前言>

動手寫一個JavaScript直譯器 | Part 1 四則運算>

動手寫一個JavaScript直譯器 | Part 2 特殊符號>

動手寫一個JavaScript直譯器 | Part 3 語法結構(上)>

動手寫一個JavaScript直譯器 | Part 4 語法結構(中)>

如果對於我的文章或程式碼有任何問題，歡迎在下方留言指教。

若有幫助到你，也歡迎給文章拍手一下，讓我在寫文章的路上更加進步!