[JavaScript Interpreter]動手寫一個JavaScript直譯器 | Part 1 四則運算
上一篇文章我們製作出了一個可以回應使用者輸入的程式，接下來我們會介紹一個直譯器的基礎架構，並實作語法解析與執行的部分，讓我們的程式能夠真正讀懂輸入的文字，本篇文章的最後會做出一個可以進行基本四則運算的直譯器。
基本架構
直接看圖
上面的圖示簡單說明了一個解釋器的基本架構，以及如何分析、執行程式碼，最後輸出結果的流程，以下會針對每一個部分進行更完整的介紹。
Text : 文字檔案
再複雜的程式碼也是一般的文字檔案，我們的直譯器需要取得文字內容來進行分析，取得文字的方式在我們上一篇文章已經實作完成了，若還沒有看過可以先回到上一篇文章，把專案建立起來後再繼續進行下去。
Lexer : 詞法分析器
將獲得的文字內容進行分類、組合，轉換成我們的程式所需要的Token，現在有許多方便、開源的Lexer可以選擇，像是Lex，不過為了學習，我們會自己動手創造一個。
以我們這次要建立的四則運算直譯器來做舉例 : "12+34"這樣的文字內容，可以被Lexer轉換為Token('NUM', '12')、Token('ADD', '+')、Token('NUM', '34')這三個Token。
Token : 符號
每一個Token都會有兩個屬性，一個是type，代表這個Token的類型，例如'NUM'、'ADD'、'EOF'等等，另一個是value，代表這個Token的值，通常就是該Token對應的文字內容。
Parser : 語法解析器
Parser的用途是遍歷Lexer解析出來的Token，並根據程式語言的語法將Token包裝成不同的Node，最後組合成抽象語法樹，Yacc是開源的Parser，不過這裡我們一樣會自己製作一個(絕對不是為了重造輪子)。
再以剛剛的"12+34"為例，Token('NUM', '12')以及Token('NUM', '34')都是單純的數字，因此都會建構出Num這個Node，而中間的Token('ADD', '+')跟左右兩邊的Node有關，所以會建構出代表二元運算的BinOp這個Node，並且把12、34兩個Num作為BinOp的左右節點。
AST : 抽象語法樹
AST的全稱是Abstract Syntax Tree，也就是抽象語法樹，一些諸如if-else、括號之類的改變程式執行結構的符號並不會出現在樹的節點上面，而是直接的影響整棵抽象語法樹的結構，因此整棵抽象語法樹就代表著整個程式碼的執行順序。
舉例來說，"1+2*3"與"(1+2)*3"兩者產生的抽象語法樹結構是完全不同的，因此執行順序與執行結果也都會不一樣。
Interpreter : 直譯器
直譯器是我們的程式執行的最後一步，也是與直譯器與編譯器最大的差別所在。如果是編譯式的程式，通常在Parser產生出抽象語法樹之後，會先對抽象語法樹進行靜態分析，包括型別檢查、變數聲明檢查、結構優化等等，然後再把抽象語法樹解析為Assembly Language，最後通過Assembler來輸出可執行檔。
而直譯器則通常直接對抽象語法樹解釋並執行，這樣就不用像傳統編譯器一樣花一大堆時間在進行靜態分析與編譯，特別是在追求開發效率的今日，可以大幅加快從產出到測試的週期。但取而代之的是執行效率與穩定性的犧牲，執行效率固然不提，有的錯誤要在執行時期才能得知，若沒有經過完善測試，有可能到了正式環境才發現問題，不可不慎。
在我們的直譯器裡，我們會利用一個訪問者來遍歷抽象語法樹，對每個節點進行對應的操作來取值，以剛剛的"12+34"為例，首先看到的會是BinOp節點，這個節點會先將左右子節點取值後，再回傳兩個節點值相加的和，而對兩個Num子節點取值會直接獲得對應的數值，也就是最後會回傳12+34 = 46。
在瞭解完一個直譯器的大致架構之後，接下來就要開始進行實作了，本次的目標是做出一個可以進行四則運算的直譯器。
實作四則運算
Token
首先建立src/token.ts，裡面是我們Token的Class與TokenType定義。
TT是TokenType的意思，因為會常常需要用到，因此將他簡寫為TT，TT是一個enum，裡面定義目前所有Token的類型，包括 :
- 代表數字的NUM
- 代表四則運算符號的ADD、SUB、MUL、DIV
- 代表結束的EOF。
Token沒有任何的function，只負責儲存type與value兩個屬性 :
- type: TT : 代表這個Token的類型，readonly。
- value: string : 代表這個Token的原始值，同樣是readonly。
Lexer
Lexer的工作是解析輸入的文字並轉換為有意義的Token，我們將Lexer實作在src/lexer.ts裡面，內容如下 :
我們的Lexer具有以下的屬性 :
- text: string : 輸入的待解析文字。
- index: number : 當前的解析字元的位置。
- currChar: string : 當前的解析字元，也就是this.text[this.index]。
Lexer的function :
- err(msg: string): 一個錯誤訊息的包裝器，讓我們方便追蹤錯誤。
- advance(): 將解析位置往後移動到下一個字元。
- isNum(str: string): 判斷當前的解析字元是否為數字。
- number(): 從當前解析位置開始解析一串數字，並將解析結果回傳，這裡的做法是先記錄開始的位置，再不斷往後移，直到不是數字為止，再將前面數字的部分一次傳回(仍然是傳回字串)。
- next(): 是唯一對外開放的方法，從當前解析字元的內容來判斷如何解析並回傳對應的Token，若無法解析成Token就會拋出錯誤。這裡目前只有先實作數字以及加法的部分，其他的待會再實作。
到這裡要花時間理解一下number與next這兩個較為複雜的function所做的事情，因為這是Lexer的核心功能。
我們可以對index.ts稍作修改，來測試Lexer是否有解析功能 :
這裡所做的事是在原先的基礎上，讓Lexer解析輸入的文字，並將所有解析到的Token印出來，執行專案後，應該可以看到類似以下的輸出結果 :
js> 123+456+789
[NUM:123]
[ADD:+]
[NUM:456]
[ADD:+]
[NUM:789]
123+456+789這樣就代表我們可以成功解析輸入的文字了。
剛剛next()裡只有先實作解析加法的部分，接下來我們將另外三個也補上，大家可以先嘗試自己動手做看看，並測試看看是否有正確解析。
以下是實作完另外三種Token後的next() :
進行測試，看看所有類型的Token是否都有被正確解析 :
js> 1+2-3*4/5
[NUM:1]
[ADD:+]
[NUM:2]
[SUB:-]
[NUM:3]
[MUL:*]
[NUM:4]
[DIV:/]
[NUM:5]
1+2-3*4/5測試成功 !
Abstract Syntax Tree
接下來在src/ast.ts定義抽象語法樹的節點結構 :
這裡我們定義了一個基本的抽象語法樹節點 : ASTNode，ASTNode一定需要一個Token。這裡加上abstract並不是因為他是"抽象"語法樹，而是因為我們不能直接實例化ASTNode本身，要被實例化的是繼承ASTNode的子類別。
我們另外定義了兩個子類別來繼承ASTNode :
- Num(token, value) : 代表數字的ASTNode，value為對應的數值。
- BinOp(token, left, right) : 代表二元運算符(ex. +| - | * | / )的ASTNode，left、right為左右節點。
Parser
Parser負責將Token按照語法規則建構出一棵抽象語法樹，因為本篇文章目標是建構出能夠進行四則運算的直譯器，因此我們需要先來了解一下四則運算的語法規則。
四則運算的規則有兩個，一是先乘除後加減，二是由左至右執行。
首先是先乘除後加減的部分，因為乘除法與加減法有不同的優先順序，因此會分為兩個不同的Function來解析他們，我們會優先解析加減法，再解析乘除法，以"1+2*3 - 4"這個式子來做範例 :
我們先解析加減法的部分，可以將這個式子理解為"(1)+(2*3) - (4)"，其中1與4的部分可以直接取得值，但是2*3的部分還需要再進行一次乘除法解析，獲得計算結果後才會再與1、4進行加減法計算。
再來是由左至右執行的部分，由於Lexer原本的解析方向就是由左至右，因此我們只需要依序解析Lexer給的Token就好，這裡要注意的是我們BinOp的左右子節點順序，需要將左邊的解析結果放到左子節點，右邊的解析結果放到右子節點，才不會打亂執行順序。
解析出來的抽象語法樹會長這個樣子 :
這裡可以多加練習，將不同的算式轉換為抽象語法樹，並實際模擬一次執行的過程，理解四則運算的規則後，我們就可以按照規則做出Parser了。
以下是半成品Parser的程式碼，實作在src/parser.ts，這段程式碼可以用來解析並建構含有數字與加減法的抽象語法樹 :
我們的Parser具有以下的屬性 :
- lexer: Lexer : 透過依賴注入來的Lexer，內含要解析的文字。
- currToken: Token: 當前的Token，可以透過lexer.next()取得下一個Token。
Parser的function :
- err(msg: string): 一個錯誤訊息的包裝器，讓我們方便追蹤錯誤。
- eat(type: TT): 若currToken的類型與傳入的預期type符合，則將currToken換成下一個Token，若不符合則會拋出錯誤。
- factor(): 從當前節點開始解析一個數字，若當前currToken type是NUM，則可以成功解析並回傳一個Num節點，該Num節點的value可由token的value直接轉換得來。若currToken type不是NUM則會拋出語法錯誤。
- expr(): 從當前位置開始解析加減法規則，先呼叫factor來解析數字，作為目前抽象語法樹的根節點，接下來向後檢查，若遇到ADD、SUB則建構一個BinOp節點，並將原根節點作為BinOp的左節點，再呼叫factor來解析出BinOp的右節點，最後將BinOp做為新的根節點。解析完全部的Token後，將根節點回傳。
- parse(): 是唯一對外開放的方法，嘗試將所有的Token透過一個expr來解析為抽象語法樹並回傳，若解析結束後還有未解析的Token，則拋出語法錯誤。
透過修改src/index.ts來確認Parser是否可以正確建構抽象語法樹，由於樹狀結構較難測試，因此我們先簡單印出根節點的Token來確認 :
執行後輸入簡單的結構來進行測試 :
js> 1
[NUM:1]
1
js> 1+2
[ADD:+]
1+2
js> 1+2-3
[SUB:-]
1+2-3以上的輸入相當於產生以下的抽象語法樹 :
接著我們利用term()來擴充Parser，讓Parser能夠解析乘法與除法 :
接著執行程式並進行測試 :
js> 1*2
[MUL:*]
1*2
js> 1+2*3
[ADD:+]
1+2*3
js> 1*2+3
[ADD:+]
1*2+3
js> 1*2/3
[DIV:/]
1*2/3可以看到無論是1 + 2 * 3還是1 * 2 + 3，建構的抽象語法樹根節點都是"+" :
這樣確保了我們先進行乘法運算後，才會接著進行加法運算。
Visitor
到了這一個階段，我們已經成功建構了一棵抽象語法樹，接下來要做的事情就是透過走訪這整棵樹來執行程式。
首先我們先在src/visitor.ts建立一個抽象的訪問者(NodeVisitor)類別 :
這個抽象的訪問者類別定義了兩個方法 :
- visit(node: ASTNode) : NodeVisitor的核心方法，賦予繼承者走訪抽象語法樹的能力，透過constructor.name來動態取得node的ClassName並決定要呼叫的方法名稱，接著透過eval來執行該方法。
- err(name: string) : 若visit時找不到對應的方法，則會拋出此錯誤。
Interpreter
接著我們在src/interpreter.ts建立Interpreter類別來繼承NodeVisitor :
Interpreter類別裡面傳入了一個Parser，用來建構抽象語法樹，並加入了visitNum()以及visitBinOp()，分別用來定義遇到Num節點與BinOp節點所要做的事情，最後提供一個公開的interpret()，呼叫Parser的parse()開始建構抽象語法樹，再透過繼承來的visit()從根節點開始走訪這棵樹，最後將走訪的結果回傳。
到這裡我們的四則運算直譯器就完成了，讓我們修改src/index.ts來測試是否可以成功執行 :
接著進行測試 :
js> 1+2+3
6
js> 1+4/2-3*5
-12
js> 3+56*4/7-28
7測試成功 !
以下是我們剛剛所產生的抽象語法樹結構，可以驗證一下自己是否能夠將輸入文字解析成抽象語法樹結構，並照著此結構計算出結果。
以上就是這篇文章的全部內容了，在這篇文章裡我們講解了直譯器的基本架構，並實作一個可以進行基礎四則運算的直譯器，但這個直譯器還有許多不足之處，包括無法處理正負號、空白字元、小數點、括號等等。
因此在下一篇文章中，我們將會實作這些功能，加強我們的直譯器。
這個系列的完整內容可以到我的Github Repo上參考。
下一篇
動手寫一個JavaScript直譯器 | Part 2 特殊符號>
References :
如果對於我的文章或程式碼有任何問題，歡迎在下方留言指教。
若有幫助到你，也歡迎給文章拍手一下，讓我在寫文章的路上更加進步!
