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

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

11 min readDec 30, 2021

上一篇文章中我們修改了我們的直譯器，讓他可以完成計算機的基本功能，但距離要讀懂常見的JavaScript的語法還有很長一段路要走，因此在本篇文章裡，我們會介紹JavaScript程式碼的基本組成，主要著重在變量的型別、賦值與計算。

要讀懂更複雜的語法結構，首先就要知道JavaScript的程式碼結構大致長什麼樣子，這裡十分推薦AST explorer這個網站，它可以將JavaScript的程式碼轉換為抽象語法樹，本篇文章也會參考預設的acorn的解析方式來擴展我們的Parser。

Program & Expression

首先我們來看一個空的結構 :

可以看到即使是空的結構，仍然可以被解析出AST，那是因為JavaScript是腳本語言，可以直接被逐行執行，而不用像Golang或是C一樣需要有一個main function當作明確的進入點，因此最外層需要一個節點將所有內容包起來，作為程式執行時的真正進入點。

我們加入一個1+2來觀察抽象語法樹的變化 :

可以看到body這個array多了一個代表1+2的ExpressionStatement，表達式(Expression)指的就是有回傳值的結構，而裡面的BinaryExpression就是我們的BinOp。

要實作這個部份很簡單，我們只需要在Parser解析時解析出一個Program就好，但由於有些ASTNode本身不需要任何的Token，例如這裡的Program，因此我們需要修改原先對ASTNode的定義，把Token作為可選的選項。

src/ast.ts

注意到我們把原先ASTNode所需要的Token移除了。

接下來我們加入新的ProgramNode，Program有一個名為body的ASTNode Array，同時我們也將目前所有的Node重新命名 :

src/ast.ts

記得要將目前所有用到舊命名的地方也進行修改。

接下來要做的事情是，在Parser解析時要解析出Program :

src/parser.ts

我們將不斷的去解析表達式，直到輸入結束，並把結果放到body裡面。

接下來要新增執行Program Node時的行為，我們應該要循序執行body裡每一個元素，並把結果回傳，我們把它定義在Interpreter裡面 :

src/interpreter.ts

並且visit方法不只會傳回數字結果，也需要修改一下 :

src/visitor.ts

最後則是執行的時候，需要把每個執行結果都印出來，修改index.ts :

src/index.ts

接下來可以嘗試執行看看，測試功能是否正常 :

js> 123+456
579
js> 123 456
123
456

NewLine

可以看到輸入123+456，被解析為一個表達式，但輸入123 456的話，則會被解析為兩個表達式，這看起來與JavaScript的語法不同，主要是因為我們目前是單行執行命令，並沒有以分號或換行來做為結尾，為此我們需要新增一個透過讀取檔案來執行直譯器的方式。

src/index.ts

然後在根目錄創建一個js/test.ts來作為我們的執行目標，裡面只有 :

1+2;

修改TokenType，加上對換行的支援 :

src/token.ts

接下來是Lexer的next方法 :

src/lexer.ts

最後是Parser對換行的處理，我們期望Program body被換行分段 :

src/parser.ts

可以直接yarn start js/test.js來進行讀取檔案並執行的測試，也可以新增到scripts裡面方便未來持續測試 :

package.json

然後改為執行 :

yarn js

可以看到印出3，代表測試成功。當然也可以故意改為錯誤的Syntax，測試看看是否會拋出錯誤。

Variable Declaration & Identifier

接下來是變數定義的部分，我們解析看看var的AST :

可以發現三個新的節點類型 :

VariableDeclaration : 變數定義的區塊，kind部分代表接下來的變數都是var類型。
VariableDeclarator : 變數賦值的區塊，id是變數名稱，init則是初始值，在這裡是null。
Identifier : 變數名稱，name可以直接由Token取得。

因此為了解析變數定義的結構，我們需要增加這些ASTNode ，這裡特別注意到，由於只有表達式具有回傳值，因此我們會一起新增一個表達式的基本類型，經過修改後會變成底下這樣 :

src/ast.ts

接下來新增代表保留字與其他Identifier的TokenType :

src/token.ts

下一步就是要讓Lexer能夠解析我們的Token了，與number的部分類似，我們會將英文字母或底線開頭，並且包含後面連續的英文字母、數字、底線的部分來解析成一個整體的Id Token ，並且在解析時，還需要先判斷是否是var、let、const之類的保留字，因此加入一個Map來處理 :

src/lexer.ts

在加入Lexer後，可以進行測試，先直接將Token印出來

src/index.ts

將js/test.js改為

var a;
let b;
const c;

在執行之後應該可以看到以下結果 :

[VAR:var]
[ID:a]
[NEWLINE:]
[LET:let]
[ID:b]
[NEWLINE:]
[CONST:const]
[ID:c]
[NEWLINE:]

接下來看到變數定義同時指定初始值的部分，以const a = 3做範例 :

可以看到這裡有一個新符號”=”需要解析，因此需要修改TokenType與Lexer :

src/token.ts

src/lexer.ts

十分簡單，接下來進行測試const a = 3，得到 :

[CONST:const]
[ID:a]
[ASSIGN:=]
[NUM:3]
[NEWLINE:]

測試成功，接下來要開始解析抽象語法樹了。

src/parser.ts

首先在解析program時進行判斷，若currToken為var、let、const，則開始解析變數定義。

src/parser.ts

解析變數定義時，若kind為const的話則一定要有初始值，let、var則透過有無等號來判斷，初始值使用expr()解析表達式來計算。

Symbol Table

接下來我們要實作Interpreter的部分，要將一個變數名稱以及數值做對應，最有效的方式就是建立一個Map，我們叫它SymbolTable，而由於變數作用域會影響存取變數的行為，因此我們用Array當作Stack來實現嵌套作用域 :

src/interpreter.ts

可以看到在我們新增變數定義的時候，我們是新增在最後一個符號表內，而在呼叫變數時，則從最後一個符號表依序往前尋找，找不到時就拋出錯誤。

這裡symbolTables設為公開是為了測試方便，讓我們可以在index.ts裡面將符號表印出來 :

src/index.ts

將test.js改為以下 :

var a = 1;
let b;
const c = 3;

執行後印出結果 :

[ Map(3) { 'a' => 1, 'b' => undefined, 'c' => 3 } ]

測試成功 !

接下來我們稍作修改，讓Parser可以同時接受多個變數定義，以下是多個變數定義的語法 :

每個定義之間用逗號隔開，因此需要從TokenType與Lexer開始修改 :

src/token.ts

src/lexer.ts

接下來要修改Parser ，我們將VariableDeclarator的部分單獨抽出來，每個VariableDeclarator由逗號隔開，注意到VariableDeclarator前面需要清理所有的newLine :

src/parser.ts

這樣就完成了，修改test.js進行測試 :

let a,
  b = 5 + 1,
  c;
const d = 2 * 4, e = (6 - 3) / -3;

執行後可以得到結果 :

[
  Map(5) {
    'a' => undefined,
    'b' => 6,
    'c' => undefined,
    'd' => 8,
    'e' => -1
  }
]

因為變數會回傳對應的值，可以拿來做四則運算，因此若我們要將變數值拿來使用的話，只需要對factor()做擴充就好 :

src/parser.ts

將test.js改為如下所示 :

const a = 7;
const b = a * 2;

執行後可以得到這樣的結果 :

[ Map(2) { 'a' => 7, 'b' => 14 } ]

測試成功 !

Assignment

在變數初始化後，我們也要能夠重新對變數賦值，因此我們先解析一下變數賦值的結構 :

可以看到是由AssignmentExpression來負責賦值的行為，這個ASTNode還需要left、right兩個屬性，left必須是Identifier，right則是Expression:

src/ast.ts

接下來修改Parser，需要注意到AssignmentExpression一樣是Expression，因此我們可以做到這樣的事情 :

let a = 1;
const b = a = 2;

這裡會先進行a = 2的賦值後，再將a的結果傳遞給b做初始化，看過這個的範例後，我們接著來思考如何產生AssignmentExpression。

在解析第二行的時候，Parser知道b的初始值需要一個Expression，但以我們目前的解析方式，當看到b = a的時候，Parser以為要使用a這個變數表達式，因此執行了b = a，再往後解析就會出錯。

要避免這個問題，我們必須在Parser解析Identifier時，再繼續看下一個Token，若下個Token是等號就能夠確定是AssignmentExpression :

src/parser.ts

解析好抽象語法樹之後，將Interpreter對應的方法也實作出來 :

src/interpreter.ts

修改一下test.js :

let a = 1;
const b = (a = 2);

接著執行，可以得到以下結果 :

[ Map(2) { 'a' => 2, 'b' => 2 } ]

測試成功 !

接下來可以將原先印出執行結果的部分還原 :

src/index.ts

接著將test.js稍作修改 :

let a = 1;
const b = (a = 2);
a;
b;

可以看到印出了每一段程式碼的執行結果 :

undefined
undefined
2
2

關於變數賦值的部分，還有一個錯誤需要修正，那就是const定義的常數還是可以被重新賦值，為此我們需要修正符號表的定義以及操作方式 :

src/interpreter.ts

如此一來就解決這個問題了，將test.js修改一下做為測試 :

const a = 1;
a = 5;

應該可以看到成功的拋出了錯誤。

本篇文章的內容到這裡就結束了，我們這次介紹了newLine以及變數的語法結構，包括如何定義與賦值等等，並且可以直接讀取文本作為輸入。至此我們的直譯器已經可以完成一些簡單的操作了，但是若要進行更複雜的行為，我們還需要增加對Array、物件、if-else、迴圈、函數等等重要功能的支持，這些將會在接下來的文章中一一介紹與實作，敬請期待。

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

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