[JavaScript 통역]자바스크립트 | 제1부

반응형

上一篇文章我們製作出了一個可以回應使用者輸入的程式，接下來我們會介紹一個直譯器的基礎架構，並實作語法解析與執行的部分，讓我們的程式能夠真正讀懂輸入的文字，本篇文章的最後會做出一個可以進行基本四則運算

基本架構

直接看圖

上面的圖示簡單說明了一個解釋器的基本架構，以及如何分析、執行程式碼，最後輸出結果的流程，以下會針對每一個部分進行更完整的介紹。

 

text : 文字檔案

再複雜的程式碼也是一般的文字檔案，我們的直譯器需要取得文字內容來進行分析，取得文字的方式在我們上一篇文章已經實作完成了，若還沒有看過可以先回到上一篇文章，把專案建立起來後再繼續進行下去。

lexer : 詞法分析器

將獲得的文字內容進行分類、組合，轉換成我們的程式所需要的token，現在有許多方便、開源的lexer可以選擇，像是lex，不過為了學習，我們會自己動手創造一個。

以我們這次要建立的四則運算直譯器來做舉例 : "12+34"這樣的文字內容，可以被lexer轉換為토큰(NUM, 12) token토큰(ADD, +)토큰(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作為bin

ast : 抽象語法樹

ast的全稱是abstract syntax tree，也就是抽象語法樹，一些諸如if-else、括號之類的改變程式執行結構的符號並不會出現在樹的節點上面，而是直接的影響整棵抽象語法樹的結構，因此整棵抽象語法樹就代表著整個程式碼的執

舉例來說，"1+23"與"(1+2)3"兩者產生的抽象語法樹結構是完全不同的，因此執行順序與執行結果也都會不一樣。

 

통역사 : 直譯 interpre

直譯器是我們的程式執行的最後一步，也是與直譯器與編譯器最大的差別所在。如果是編譯式的程式，通常在parser產生出抽象語法樹之後，會先對抽象語法樹進行靜態分析，包括型別檢查、變數聲明檢查、結構優化等等，然

而直譯器則通常直接對抽象語法樹解釋並執行，這樣就不用像傳統編譯器一樣花一大堆時間在進行靜態分析與編譯，特別是在追求開發效率的今日，可以大幅加快從產出到測試的週期。但取而代之的是執行效率與穩定性的犧牲

 

在我們的直譯器裡，我們會利用一個訪問者來遍歷抽象語法樹，對每個節點進行對應的操作來取值，以剛剛的"12+34"為例，首先看到的會是binop節點，這個節點會先將左右子節點取值後，再回傳兩個節點值相加的和，

在瞭解完一個直譯器的大致架構之後，接下來就要開始進行實作了，本次的目標是做出一個可以進行四則運算的直譯器。

實作四則運算

토큰

先ccsrc/token.ts，的的的토큰的클래스與TokenType義 token

 

tt是tokentype的意思，因為會常常需要用到，因此將他簡寫為tt，tt是一個enum，裡面定義目前所有token的類型，包括 :

• 代表數字的num
• 代表四則運算符號的add、sub、물레디브
• 代表結束的eof。

token沒有任何的function，只負責儲存type與value兩個屬性 :

• 유형: TT : 代토큰的읽기 전용 type
• 값: 문자열 : 代토큰的읽기 전용 value

렉서

 

lexer的工作是解析輸入的文字並轉換為有意義的token，我們將lexer實作在src/lexer.ts裡面，內容如下 :

我們的lexer具有以下的屬性 :

• text: string : 輸入的待解析文字。
• index: number : 當前的解析字元的位置。
• currChar: 문자열 : this.text[this.index]입니다.

렉서 함수 :

• 오류(msg: 문자열): 一個錯誤訊息的包裝器，讓我們方便追蹤錯誤。
• advance(): 將解析位置往後移動到下一個字元。
• isNum(str: 문자열): 判斷當前的解析字元是否為數字。
• 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

測試成功 !

 

추상 구문 트리

接下來在src/ast.ts定義抽象語法樹的節點結構 :

這裡我們定義了一個基本的抽象語法樹節點 : astnode，astnode一定需要一個token。這裡加上abstract並不是因為他是"抽象"語法樹，而是因為我們不能直接實例化astnode本身，要被實例化的是繼承astnode的子類別。

我們另外定義了兩個子類別來繼承astnode :

• Num(토큰, 값) : 【ASTNode】값】
• binop(token, left, right) : 代表二元運算符(ex. +| - | * | / )的astnode，left、right為左右節點。

 

파서

파세리치token按照語法規則建構出一棵抽象語法樹，因為本篇文章目標是建構出能夠進行四則運算的直譯器，因此我們需要先來了解一下四則運算的語法規則。

四則運算的規則有兩個，一是先乘除後加減，二是由左至右執行。

首先是先乘除後加減的部分，因為乘除法與加減法有不同的優先順序，因此會分為兩個不同的function來解析他們，我們會優先解析加減法，再解析乘除法，以"1+2*3 - 4"這個式子來做範例 :

我們先解析加減法的部分，可以將這個式子理解為"(1)+(23) - (4)"，其中1與4的部分可以直接取得值，但是23的部分還需要再進行一次乘除法解析，獲得計算結果後才會再與1、4進行加減法計算。

 

再來是由左至右執行的部分，由於lexer原本的解析方向就是由左至右，因此我們只需要依序解析lexer給的token就好，這裡要注意的是我們binop的左右子節點順序，需要將左邊的解析結果放到左子節點，右邊的解析結果放到右子節點，才不會打亂執行順序。

解析出來的抽象語法樹會長這個樣子 :

這裡可以多加練習，將不同的算式轉換為抽象語法樹，並實際模擬一次執行的過程，理解四則運算的規則後，我們就可以按照規則做出parser了。

以下是半成品parser的程式碼，實作在src/parser.ts，這段程式碼可以用來解析並建構含有數字與加減法的抽象語法樹 :

 

我們的parser具有以下的屬性 :

• lexer: lexer : 透過依賴注入來的lexer，內含要解析的文字。
• currToken: 토큰: 當Token erToken erToken.next())Token cur

파서 함수 :

• 오류(msg: 문자열): 一個錯誤訊息的包裝器，讓我們方便追蹤錯誤。
• 먹는 것(타입: TT): cur커르token的類型與傳入的預期type符合，則將currtoken換成下一個token，若不符合則會拋出錯誤。
• factor(): 從當前節點開始解析一個數字，若當前curr토큰 유형。num，則可以成功解析並回傳一個num節點，該num節點的value可由token的value直接轉換得來。若curr토큰 유형。num則會拋出語法錯誤。
• expr(): 從當前位置開始解析加減法規則，先呼叫factor來解析數字，作為目前抽象語法樹的根節點，接下來向後檢查，若遇到add、sub則建構一個binop節點，並將原根節點作為binop的左節點，再呼叫factor來解析出bin
• 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，建構的抽象語法樹根節點都是"+" :

 

這樣確保了我們先進行乘法運算後，才會接著進行加法運算。

방문자

到了這一個階段，我們已經成功建構了一棵抽象語法樹，接下來要做的事情就是透過走訪這整棵樹來執行程式。

首先我們先在src/visitor.ts建立一個抽象的訪問者(nodevisitor)類別 :

 

這個抽象的訪問者類別定義了兩個方法 :

• visit(node: astnode) : nodevisitor的核心方法，賦予繼承者走訪抽象語法樹的能力，透過constructor.name來動態取得node的classname並決定要呼叫的方法名稱，接著透過eval來執行該方法。
• err(name: string) : 若visit時找不到對應的方法，則會拋出此錯誤。著我在csrc/ts立ttsttst建ts建인터프리터 NodeVisitor:
   
  interpreter類別裡面傳入了一個parser，用來建構抽象語法樹，並加入了visitnum()以及visitbinop()，分別用來定義遇到num節點與binop節點所要做的事情，最後提供一個公開的interprete()，呼叫parser的parse()開始建接著進行測試 :
• js> 1+2+3 6 js> 1+4/2-3*5 -12 js> 3+56*4/7-28 7
• 到這裡我們的四則運算直譯器就完成了，讓我們修改src/index.ts來測試是否可以成功執行 :
• 통역사

 

測試成功 !

以下是我們剛剛所產生的抽象語法樹結構，可以驗證一下自己是否能夠將輸入文字解析成抽象語法樹結構，並照著此結構計算出結果。

以上就是這篇文章的全部內容了，在這篇文章裡我們講解了直譯器的基本架構，並實作一個可以進行基礎四則運算的直譯器，但這個直譯器還有許多不足之處，包括無法處理正負號、空白字元、小數點、括號等等。

因此在下一篇文章中，我們將會實作這些功能，加強我們的直譯器。

 

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

참조:

간단한 통역사를 만들어 봅시다.

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

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