不知道你是不是和我一樣,看到“編譯器”三個字的時候,就感覺非常高大上,同時心底會升起一絲絲“害怕”!
我始終認為編譯器是很復雜...很復雜的東西,不是我這種小白能懂的。而且一想到要學習編譯器的知識,腦海里就浮現(xiàn)出那種 500 頁起的厚書。
一直到我發(fā)現(xiàn) the-super-tiny-compiler 這個寶藏級的開源項目,它是一個僅 1000 行左右的迷你編譯器,其中注釋占了代碼量的 80%,實際代碼只有 200 行!麻雀雖小但五臟俱全,完整地實現(xiàn)了編譯器所需基本功能,通過 代碼+注釋+講解 讓你通過一個開源項目入門編譯器。
地址:https://github.com/jamiebuilds/the-super-tiny-compiler
中文:https://github.com/521xueweihan/OneFile/blob/main/src/javascript/the-super-tiny-compiler.js
下面我將從介紹 什么是編譯器 開始,使用上述項目作為示例代碼,更加細致地講解編譯的過程,把編譯器入門的門檻再往下砍一砍。如果你之前沒有接觸過編譯器相關(guān)的知識,那這篇文章可以讓你對編譯器所做的事情,以及原理有一個初步的認識!
準備好變強了嗎?那我們開始吧!
一、什么是編譯器
從概念上簡單講:
編譯器就是將“一種語言(通常為高級語言)”翻譯為“另一種語言(通常為低級語言)”的程序。
對于現(xiàn)代程序員來說我們最熟悉的 JavaScript、Java 這些都屬于高級語言,也就是便于我們編程者編寫、閱讀、理解、維護的語言,而低級語言就是計算機能直接解讀、運行的語言。
編譯器也可以理解成是這兩種語言之間的“橋梁”。編譯器存在的原因是因為計算機 CPU 執(zhí)行數(shù)百萬個微小的操作,因為這些操作實在是太“微小”,你肯定不愿意手動去編寫它們,于是就有了二進制的出現(xiàn),二進制代碼也被理解成為機器代碼。很顯然,二進制看上去并不好理解,而且編寫二進制代碼很麻煩,因此 CPU 架構(gòu)支持把二進制操作映射作為一種更容易閱讀的語言——匯編語言。
雖然匯編語言非常低級,但是它可以轉(zhuǎn)換為二進制代碼,這種轉(zhuǎn)換主要靠的是“匯編器”。因為匯編語言仍然非常低級,對于追求高效的程序員來說是無法忍受的,所以又出現(xiàn)了更高級的語言,這也是大部分程序員使用且熟悉的編程語言,這些抽象的編程語言雖然不能直接轉(zhuǎn)化成機器操作,但是它比匯編語言更好理解且更能夠被高效的使用。所以我們需要的其實就是能理解這些復雜語言并正確地轉(zhuǎn)換成低級代碼的工具——編譯器。
![41551264-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVKAdwwjAAH30ew5GaQ181.png)
我覺得對于初學者來說到這里有個大致的了解就可以了。因為接下去要分析的這個例子非常簡單但是能覆蓋大多數(shù)場景,你會從最真實最直接的角度來直面這個“大敵”——編譯器。
二、“迷你”編譯器
下面我們就用 the-super-tiny-compiler 為示例代碼,帶大家來簡單了解一下編譯器。
不同編譯器之間的不同階段可能存在差別,但基本都離不開這三個主要組成部分:解析、轉(zhuǎn)換和代碼生成。
![41707a68-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVKABUofAAFSmt-q_2o867.png)
其實這個“迷你”編譯器開源項目的目的就是這些:
-
證明現(xiàn)實世界的編譯器主要做的是什么
-
做一些足夠復雜的事情來證明構(gòu)建編譯器的合理性
-
用最簡單的代碼來解釋編譯器的主要功能,使新手不會望而卻步
以上就解釋了這個開源項目存在的意義了,所以如果你對編譯器有很濃厚的興趣希望一學到底的,那肯定還是離不開大量的閱讀和鉆研啦,但是如果你希望對編譯器的功能有所了解,那這篇文章就別錯過啦!
現(xiàn)在我們就要對這個項目本身進行進一步的學習了,有些背景需要提前了解一下。這個項目主要是把 LISP 語言編譯成我們熟悉的 JavaScript 語言。
那為什么要用 LISP 語言呢?
LISP 是具有悠久歷史的計算機編程語言家族,有獨特和完全用括號的前綴符號表示法。起源于 1958 年,是現(xiàn)今第二悠久仍廣泛使用的高端編程語言。
首先 LISP 語言和我們熟悉的 C 語言和 JavaScript 語言很不一樣,雖然其他的語言也有強大的編譯器,但是相對于 LISP 語言要復雜得多。LISP 語言是一種超級簡單的解析語法,并且很容易被翻譯成其他語法,像這樣:
![41973ba8-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVKATWoiAABrikH7Plk617.png)
所以到這里你應該知道我們要干什么了吧?那讓我們再深入地了解一下具體要怎么進行“翻譯”(編譯)吧!
三、編譯過程
前面我們已經(jīng)提過,大部分的編譯器都主要是在做三件事:
- 解析
- 轉(zhuǎn)換
- 代碼生成
下面我們將分解 the-super-tiny-compiler 的代碼,然后進行逐行解讀。
讓我們一起跟著代碼,弄清楚上述三個階段具體做了哪些事情~
3.1 解析
解析通常分為兩個階段:詞法分析和句法分析
-
詞法分析:獲取原始代碼并通過一種稱為標記器(或詞法分析器 Tokenizer)的東西將其拆分為一種稱為標記(Token)的東西。標記是一個數(shù)組,它描述了一個獨立的語法片段。這些片段可以是數(shù)字、標簽、標點符號、運算符等等。
-
語法分析:獲取之前生成的標記(Token),并把它們轉(zhuǎn)換成一種抽象的表示,這種抽象的表示描述了代碼語句中的每一個片段以及它們之間的關(guān)系。這被稱為中間表示(intermediate representation)或抽象語法樹(Abstract Syntax Tree, 縮寫為AST)。AST 是一個深度嵌套的對象,用一種更容易處理的方式代表了代碼本身,也能給我們更多信息。
![41ac1fc8-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVKAL8nbAAHIVpk2Bcw126.png)
比如下面這個語法:
(add2(subtract42))
拆成 Token 數(shù)組就像這樣:
[
{type:'paren',value:'('},
{type:'name',value:'add'},
{type:'number',value:'2'},
{type:'paren',value:'('},
{type:'name',value:'subtract'},
{type:'number',value:'4'},
{type:'number',value:'2'},
{type:'paren',value:')'},
{type:'paren',value:')'},
]
代碼思路:
因為我們需要去解析字符串,就需要有一個像指針/光標來幫我們辨認目前解析的位置是哪里,所以會有一個 current
的變量,從 0 開始。而我們最終的目的是獲取一個 token 數(shù)組,所以也先初始化一個空數(shù)組 tokens
。
//`current`變量就像一個指光標一樣讓我們可以在代碼中追蹤我們的位置
letcurrent=0;
//`tokens`數(shù)組用來存我們的標記
lettokens=[];
既然要解析字符串,自然少不了遍歷啦!這里就用一個 while 循環(huán)來解析我們當前的字符串。
//在循環(huán)里面我們可以將`current`變量增加為我們想要的值
while(current//我們還將在`input`中存儲`current`字符
letchar=input[current];
}
如何獲取字符串里面的單個字符呢?答案是用像數(shù)組那樣的中括號來獲?。?/span>
varchar=str[0]
這里新增一個知識點來咯!在 JavaScript 中 String 類的實例,是一個類數(shù)組,從下面這個例子可以看出來:
![41da5eb0-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVKAaXsPAAC8O4wRZw4827.png)
可能之前你會用 charAt
來獲取字符串的單個字符,因為它是在 String 類型上的一個方法:
![41feaaf4-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVOAHndVAAFGT8gxa6U153.png)
這兩個方法都可以實現(xiàn)你想要的效果,但是也存在差別。下標不存在時 str[index]
會返回 undefined
,而 str.charAt(index)
則會返回 ""
(空字符串):
![4230d254-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVOAWXSWAACQ3q70Eyo647.png)
隨著光標的移動和字符串中字符的獲取,我們就可以來逐步解析當前字符串了。
那解析也可以從這幾個方面來考慮,以 (add 2 (subtract 4 2))
這個為例,我們會遇到這些:(
左括號、字符串、空格、數(shù)字、)
右括號。對于不同的類型,就要用不同的 if
條件判斷分別處理:
- 左右括號匹配代表一個整體,找到對應的括號只要做上標記就好
-
空格代表有字符分割,不需要放到我們的
token
數(shù)組里,只需要跳到下一個非空格的字符繼續(xù)循環(huán)就好
//檢查是否有一個左括號:
if(char==='('){
//如果有,我們會存一個類型為`paren`的新標記到數(shù)組,并將值設(shè)置為一個左括號。
tokens.push({
type:'paren',
value:'(',
});
//`current`自增
current++;
//然后繼續(xù)進入下一次循環(huán)。
continue;
}
//接下去檢查右括號,像上面一樣
if(char===')'){
tokens.push({
type:'paren',
value:')',
});
current++;
continue;
}
//接下去我們檢查空格,這對于我們來說就是為了知道字符的分割,但是并不需要存儲為標記。
//所以我們來檢查是否有空格的存在,如果存在,就繼續(xù)下一次循環(huán),做除了存儲到標記數(shù)組之外的其他操作即可
letWHITESPACE=/s/;
if(WHITESPACE.test(char)){
current++;
continue;
}
字符串和數(shù)字因為具有各自不同的含義,所以處理上面相對復雜一些。先從數(shù)字來入手,因為數(shù)字的長度不固定,所以要確保獲取到全部的數(shù)字字符串呢,就要經(jīng)過遍歷,從遇到第一個數(shù)字開始直到遇到一個不是數(shù)字的字符結(jié)束,并且要把這個數(shù)字存起來。
//(add123456)
//^^^^^^
//只有兩個單獨的標記
//
//因此,當我們遇到序列中的第一個數(shù)字時,我們就開始了
letNUMBERS=/[0-9]/;
if(NUMBERS.test(char)){
//我們將創(chuàng)建一個`value`字符串,并把字符推送給他
letvalue='';
//然后我們將遍歷序列中的每個字符,直到遇到一個不是數(shù)字的字符
//將每個作為數(shù)字的字符推到我們的`value`并隨著我們?nèi)ピ黾觍current`
//這樣我們就能拿到一個完整的數(shù)字字符串,例如上面的123和456,而不是單獨的123456
while(NUMBERS.test(char)){
value+=char;
char=input[++current];
}
//接著我們把數(shù)字放到標記數(shù)組中,用數(shù)字類型來描述區(qū)分它
tokens.push({type:'number',value});
//繼續(xù)外層的下一次循環(huán)
continue;
}
為了更適用于現(xiàn)實場景,這里支持字符串的運算,例如 (concat "foo" "bar")
這種形式的運算,那就要對 "
內(nèi)部的字符串再做一下解析,過程和數(shù)字類似,也需要遍歷,然后獲取全部的字符串內(nèi)容之后再存起來:
//從檢查開頭的雙引號開始:
if(char==='"'){
//保留一個`value`變量來構(gòu)建我們的字符串標記。
letvalue='';
//我們將跳過編輯中開頭的雙引號
char=input[++current];
//然后我們將遍歷每個字符,直到我們到達另一個雙引號
while(char!=='"'){
value+=char;
char=input[++current];
}
//跳過相對應閉合的雙引號.
char=input[++current];
//把我們的字符串標記添加到標記數(shù)組中
tokens.push({type:'string',value});
continue;
}
最后一種標記的類型是名稱。這是一個字母序列而不是數(shù)字,這是我們 lisp
語法中的函數(shù)名稱:
//(add24)
//^^^
//名稱標記
//
letLETTERS=/[a-z]/i;
if(LETTERS.test(char)){
letvalue='';
//同樣,我們遍歷所有,并將它們完整的存到`value`變量中
while(LETTERS.test(char)){
value+=char;
char=input[++current];
}
//并把這種名稱類型的標記存到標記數(shù)組中,繼續(xù)循環(huán)
tokens.push({type:'name',value});
continue;
}
以上我們就能獲得一個 tokens
數(shù)組了,下一步就是構(gòu)建一個抽象語法樹(AST)可能看起來像這樣:
![42523d36-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVOAYK97AANu8AGW8ck336.png)
{
type:'Program',
body:[{
type:'CallExpression',
name:'add',
params:[{
type:'NumberLiteral',
value:'2',
},{
type:'CallExpression',
name:'subtract',
params:[{
type:'NumberLiteral',
value:'4',
},{
type:'NumberLiteral',
value:'2',
}]
}]
}]
}
代碼思路:
同樣我們也需要有一個光標/指針來幫我們辨認當前操作的對象是誰,然后預先創(chuàng)建我們的 AST 樹,他有一個根節(jié)點叫做 Program
:
letcurrent=0;
letast={
type:'Program',
body:[],
};
再來看一眼我們之前獲得的 tokens
數(shù)組:
[
{type:'paren',value:'('},
{type:'name',value:'add'},
{type:'number',value:'2'},
{type:'paren',value:'('},
{type:'name',value:'subtract'},
{type:'number',value:'4'},
{type:'number',value:'2'},
{type:'paren',value:')'},
{type:'paren',value:')'},
]
你會發(fā)現(xiàn)對于 (add 2 (subtract 4 2))
這種具有嵌套關(guān)系的字符串,這個數(shù)組非?!氨馄健币矡o法明顯的表達嵌套關(guān)系,而我們的 AST 結(jié)構(gòu)就能夠很清晰的表達嵌套的關(guān)系。對于上面的數(shù)組來說,我們需要遍歷每一個標記,找出其中是 CallExpression
的 params
,直到遇到右括號結(jié)束,所以遞歸是最好的方法,所以我們創(chuàng)建一個叫 walk
的遞歸方法,這個方法返回一個 node
節(jié)點,并存入我們的 ast.body
的數(shù)組中:
functionwalk(){
//在walk函數(shù)里面,我們首先獲取`current`標記
lettoken=tokens[current];
}
while(current
下面就來實現(xiàn)我們的 walk
方法。我們希望這個方法可以正確解析 tokens
數(shù)組里的信息,首先就是要針對不同的類型 type
作區(qū)分:
首先先操作“值”,因為它是不會作為父節(jié)點的所以也是最簡單的。在上面我們已經(jīng)了解了值可能是數(shù)字 (subtract 4 2)
也可能是字符串 (concat "foo" "bar")
,只要把值和類型匹配上就好:
//首先先檢查一下是否有`number`標簽.
if(token.type==='number'){
//如果找到一個,就增加`current`.
current++;
//然后我們就能返回一個新的叫做`NumberLiteral`的AST節(jié)點,并賦值
return{
type:'NumberLiteral',
value:token.value,
};
}
//對于字符串來說,也是和上面數(shù)字一樣的操作。新增一個`StringLiteral`節(jié)點
if(token.type==='string'){
current++;
return{
type:'StringLiteral',
value:token.value,
};
}
接下去我們要尋找調(diào)用的表達式(CallExpressions)。每匹配一個左括號,就能在下一個得到表達式的名字,在沒有遇到右括號之前都經(jīng)過遞歸把樹狀結(jié)構(gòu)豐富起來,直到遇到右括號停止遞歸,直到循環(huán)結(jié)束。從代碼上看更加直觀:
if(
token.type==='paren'&&
token.value==='('
){
//我們將增加`current`來跳過這個插入語,因為在AST樹中我們并不關(guān)心這個括號
token=tokens[++current];
//我們創(chuàng)建一個類型為“CallExpression”的基本節(jié)點,并把當前標記的值設(shè)置到name字段上
//因為左括號的下一個標記就是這個函數(shù)的名字
letnode={
type:'CallExpression',
name:token.value,
params:[],
};
//繼續(xù)增加`current`來跳過這個名稱標記
token=tokens[++current];
//現(xiàn)在我們要遍歷每一個標記,找出其中是`CallExpression`的`params`,直到遇到右括號
//我們將依賴嵌套的`walk`函數(shù)來增加我們的`current`變量來超過任何嵌套的`CallExpression`
//所以我們創(chuàng)建一個`while`循環(huán)持續(xù)到遇到一個`type`是'paren'并且`value`是右括號的標記
while(
(token.type!=='paren')||
(token.type==='paren'&&token.value!==')')
){
//我們把這個節(jié)點存到我們的`node.params`中去
node.params.push(walk());
token=tokens[current];
}
//我們最后一次增加`current`變量來跳過右括號
current++;
//返回node節(jié)點
returnnode;
}
3.2 轉(zhuǎn)換
編譯器的下一個階段是轉(zhuǎn)換。要做的就是獲取 AST 之后再對其進行更改。它可以用相同的語言操作 AST,也可以將其翻譯成一種全新的語言。
那如何轉(zhuǎn)換 AST 呢?
你可能會注意到我們的 AST 中的元素看起來非常相似。這些元素都有 type 屬性,它們被稱為 AST 結(jié)點。這些節(jié)點含有若干屬性,可以用于描述 AST 的部分信息。
//我們可以有一個“NumberLiteral”的節(jié)點:
{
type:'NumberLiteral',
value:'2',
}
//或者可能是“CallExpression”的一個節(jié)點:
{
type:'CallExpression',
name:'subtract',
params:[...嵌套節(jié)點放在這里...],
}
對于轉(zhuǎn)換 AST 無非就是通過新增、刪除、替換屬性來操作節(jié)點,或者也可以新增節(jié)點、刪除節(jié)點,甚至我們可以在原有的 AST 結(jié)構(gòu)保持不變的狀態(tài)下創(chuàng)建一個基于它的全新的 AST。
由于我們的目標是一種新的語言,所以我們將要專注于創(chuàng)造一個完全新的 AST 來配合這個特定的語言。
為了能夠訪問所有這些節(jié)點,我們需要遍歷它們,使用的是深度遍歷的方法。對于我們在上面獲取的那個 AST 遍歷流程應該是這樣的:
![428e4434-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVOAbx4KAAH881xq5A8871.png)
如果我們直接操作這個 AST 而不是創(chuàng)造一個單獨的 AST,我們很有可能會在這里引入各種抽象。但是僅僅訪問樹中的每個節(jié)點對于我們來說想做和能做的事情已經(jīng)很多了。
(使用訪問(visiting)這個詞是因為這是一種模式,代表在對象結(jié)構(gòu)內(nèi)對元素進行操作。)
所以我們現(xiàn)在創(chuàng)建一個訪問者對象(visitor),這個對象具有接受不同節(jié)點類型的方法:
varvisitor={
NumberLiteral(){},
CallExpression(){},
};
當我們遍歷 AST 的時候,如果遇到了匹配 type
的結(jié)點,我們可以調(diào)用 visitor
中的方法。
一般情況下為了讓這些方法可用性更好,我們會把父結(jié)點也作為參數(shù)傳入。
varvisitor={
NumberLiteral(node,parent){},
CallExpression(node,parent){},
};
當然啦,對于深度遍歷的話我們都知道,往下遍歷到最深的自節(jié)點的時候還需要“往回走”,也就是我們所說的“退出”當前節(jié)點。你也可以這樣理解:向下走“進入”節(jié)點,向上走“退出”節(jié)點。
![42b08ca6-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVOAFSGCAALt-0MZCLc844.png)
![42beb83a-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVOAaeuMAANH5XLn5Is854.png)
![42ee557c-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVOAOZIJAAOb2qJ0DnI706.png)
為了支持這點,我們的“訪問者”的最終形式應該像是這樣:
varvisitor={
Program:{
enter(node,parent){},
exit(node,parent){},
},
NumberLiteral:{
enter(node,parent){},
exit(node,parent){},
},
CallExpression:{
enter(node,parent){},
exit(node,parent){},
},
...
};
遍歷
首先我們定義了一個接收一個 AST 和一個訪問者的遍歷器函數(shù)(traverser)。需要根據(jù)每個節(jié)點的類型來調(diào)用不同的訪問者的方法,所以我們定義一個 traverseNode
的方法,傳入當前的節(jié)點和它的父節(jié)點,從根節(jié)點開始,根節(jié)點沒有父節(jié)點,所以傳入 null
即可。
functiontraverser(ast,visitor){
// traverseNode 函數(shù)將接受兩個參數(shù):node 節(jié)點和他的 parent 節(jié)點
//這樣他就可以將兩者都傳遞給我們的訪問者方法(visitor)
functiontraverseNode(node,parent){
//我們首先從匹配`type`開始,來檢測訪問者方法是否存在。訪問者方法就是(enter 和 exit)
letmethods=visitor[node.type];
//如果這個節(jié)點類型有`enter`方法,我們將調(diào)用這個函數(shù),并且傳入當前節(jié)點和他的父節(jié)點
if(methods&&methods.enter){
methods.enter(node,parent);
}
//接下去我們將按當前節(jié)點類型來進行拆分,以便于對子節(jié)點數(shù)組進行遍歷,處理到每一個子節(jié)點
switch(node.type){
//首先從最高的`Program`層開始。因為 Program 節(jié)點有一個名叫 body 的屬性,里面包含了節(jié)點數(shù)組
//我們調(diào)用`traverseArray`來向下遍歷它們
//
//請記住,`traverseArray`會依次調(diào)用`traverseNode`,所以這棵樹將會被遞歸遍歷
case'Program':
traverseArray(node.body,node);
break;
//接下去我們對`CallExpression`做相同的事情,然后遍歷`params`屬性
case'CallExpression':
traverseArray(node.params,node);
break;
//對于`NumberLiteral`和`StringLiteral`的情況,由于沒有子節(jié)點,所以直接break即可
case'NumberLiteral':
case'StringLiteral':
break;
//接著,如果我們沒有匹配到上面的節(jié)點類型,就拋出一個異常錯誤
default:
thrownewTypeError(node.type);
}
//如果這個節(jié)點類型里面有一個`exit`方法,我們就調(diào)用它,并且傳入當前節(jié)點和他的父節(jié)點
if(methods&&methods.exit){
methods.exit(node,parent);
}
}
//調(diào)用`traverseNode`來啟動遍歷,傳入之前的AST樹,由于AST樹最開始
//的點沒有父節(jié)點,所以我們直接傳入null就好
traverseNode(ast,null);
}
因為 Program
和 CallExpression
兩種類型可能會含有子節(jié)點,所以對這些可能存在的子節(jié)點數(shù)組需要做進一步的處理,所以創(chuàng)建了一個叫 traverseArray
的方法來進行迭代。
//traverseArray函數(shù)來迭代數(shù)組,并且調(diào)用traverseNode函數(shù)
functiontraverseArray(array,parent){
array.forEach(child=>{
traverseNode(child,parent);
});
}
轉(zhuǎn)換
下一步就是把之前的 AST 樹進一步進行轉(zhuǎn)換變成我們所期望的那樣變成 JavaScript 的 AST 樹:
![431acbd4-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVOACNZYAAMQLn6uSTM851.png)
如果你對 JS 的 AST 的語法解析不是很熟悉的話,可以借助在線工具網(wǎng)站來幫助你知道大致要轉(zhuǎn)換成什么樣子的 AST 樹,就可以在其他更復雜的場景進行應用啦~
![43435aae-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVOAeHv-AAHIy5EC4S8971.png)
我們創(chuàng)建一個像之前的 AST 樹一樣的新的 AST 樹,也有一個Program
節(jié)點:
functiontransformer(ast){
letnewAst={
type:'Program',
body:[],
};
//這里有個 hack 技巧:這個上下文(context)屬性只是用來對比新舊 ast 的
//通常你會有比這個更好的抽象方法,但是為了我們的目標能實現(xiàn),這個方法相對簡單些
ast._context=newAst.body;
//在這里調(diào)用遍歷器函數(shù)并傳入我們的舊的AST樹和訪問者方法(visitor)
traverser(ast,{...}};
//在轉(zhuǎn)換器方法的最后,我們就能返回我們剛創(chuàng)建的新的AST樹了
returnnewAst;
}
那我們再來完善我們的 visitor
對象,對于不同類型的節(jié)點,可以定義它的 enter
和 exit
方法(這里因為只要訪問到節(jié)點并進行處理就可以了,所以用不到退出節(jié)點的方法:exit
):
{
//第一個訪問者方法是NumberLiteral
NumberLiteral:{
enter(node,parent){
//我們將創(chuàng)建一個也叫做`NumberLiteral`的新節(jié)點,并放到父節(jié)點的上下文中去
parent._context.push({
type:'NumberLiteral',
value:node.value,
});
},
},
//接下去是`StringLiteral`
StringLiteral:{
enter(node,parent){
parent._context.push({
type:'StringLiteral',
value:node.value,
});
},
},
CallExpression:{...}
}
對于 CallExpression
會相對比較復雜一點,因為它可能含有嵌套的內(nèi)容。
CallExpression:{
enter(node,parent){
//首先我們創(chuàng)建一個叫`CallExpression`的節(jié)點,它帶有表示嵌套的標識符“Identifier”
letexpression={
type:'CallExpression',
callee:{
type:'Identifier',
name:node.name,
},
arguments:[],
};
//下面我們在原來的`CallExpression`節(jié)點上定義一個新的 context,
//它是 expression 中 arguments 這個數(shù)組的引用,我們可以向其中放入?yún)?shù)。
node._context=expression.arguments;
//之后我們將檢查父節(jié)點是否是`CallExpression`類型
//如果不是的話
if(parent.type!=='CallExpression'){
//我們將用`ExpressionStatement`來包裹`CallExpression`節(jié)點
//這么做是因為單獨存在的`CallExpressions`在 JavaScript 中也可以被當做是聲明語句。
//
//比如`vara=foo()`與`foo()`,后者既可以當作表達式給某個變量賦值,
//也可以作為一個獨立的語句存在
expression={
type:'ExpressionStatement',
expression:expression,
};
}
//最后我們把我們的`CallExpression`(可能有包裹)放到父節(jié)點的上下文中去
parent._context.push(expression);
},
}
3.3 代碼生成
編譯器的最后一個階段是代碼生成,這個階段做的事情有時候會和轉(zhuǎn)換(transformation)重疊,但是代碼生成最主要的部分還是根據(jù) AST 來輸出代碼。代碼生成有幾種不同的工作方式,有些編譯器將會重用之前生成的 token,有些會創(chuàng)建獨立的代碼表示,以便于線性地輸出代碼。但是接下來我們還是著重于使用之前生成好的 AST。
根據(jù)前面的這幾步驟,我們已經(jīng)得到了我們新的 AST 樹:
![435ed5a4-92da-11ed-bfe3-dac502259ad0.png](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVSAW7POAACILhQrAN8085.png)
接下來將調(diào)用代碼生成器將遞歸的調(diào)用自己來打印樹的每一個節(jié)點,最后輸出一個字符串。
functioncodeGenerator(node){
//還是按照節(jié)點的類型來進行分解操作
switch(node.type){
//如果我們有`Program`節(jié)點,我們將映射`body`中的每個節(jié)點
//并且通過代碼生成器來運行他們,用換行符將他們連接起來
case'Program':
returnnode.body.map(codeGenerator)
.join('
');
//對于`ExpressionStatement`,我們將在嵌套表達式上調(diào)用代碼生成器,并添加一個分號
case'ExpressionStatement':
return(
codeGenerator(node.expression)+
';'//<
);
//對于`CallExpression`我們將打印`callee`,新增一個左括號
//然后映射每一個`arguments`數(shù)組的節(jié)點,并用代碼生成器執(zhí)行,每一個節(jié)點運行完之后加上逗號
//最后增加一個右括號
case'CallExpression':
return(
codeGenerator(node.callee)+
'('+
node.arguments.map(codeGenerator)
.join(',')+
')'
);
//對于`Identifier`直接返回`node`的名字就好.
case'Identifier':
returnnode.name;
//對于`NumberLiteral`直接返回`node`的值就好.
case'NumberLiteral':
returnnode.value;
//對于`StringLiteral`,在`node`的值的周圍添加雙引號.
case'StringLiteral':
return'"'+node.value+'"';
//如果沒有匹配到節(jié)點的類型,就拋出異常
default:
thrownewTypeError(node.type);
}
}
經(jīng)過代碼生成之后我們就得到了這樣的 JS 字符串:add(2, subtract(4, 2));
也就代表我們的編譯過程是成功的!
四、結(jié)語
以上就是編寫一個 LISP 到 JS 編譯器的全過程,逐行中文注釋的完整代碼地址:
https://github.com/521xueweihan/OneFile/blob/main/src/javascript/the-super-tiny-compiler.js
那么,今天學到的東西哪里會用到呢?眾所周知的 Vue 和 React 雖然寫法上有所區(qū)別,但是“殊途同歸”都是通過 AST 轉(zhuǎn)化的前端框架。這中間最重要的就是轉(zhuǎn)換 AST,它是非常“強大”且應用廣泛,比較常見的使用場景:
- IDE 的錯誤提示、代碼高亮,還可以幫助實現(xiàn)代碼自動補全等功能
- 常見的 Webpack 和 rollup 打包(壓縮)
AST 被廣泛應用在編譯器、IDE 和代碼優(yōu)化壓縮上,以及前端框架 Vue、React 等等。雖然我們并不會常常與 AST 直接打交道,但它總是無時無刻不陪伴著我們。
當然啦!看完文章不一定算真正了解了,所有學習過程都離不開動手實踐,或許實踐過程中你也會有不一樣的理解。實踐方法十分簡單:只需打開瀏覽器的“開發(fā)者模式” ——> 進入控制臺(console)——> 復制/粘貼代碼,就可以直接運行看到結(jié)果了!
![437c6754-92da-11ed-bfe3-dac502259ad0.gif](https://file1.elecfans.com//web2/M00/9F/7D/wKgaomToHVSAMd5CAAdpzre8ywg130.gif)
以上就是本文的所有內(nèi)容 本文只能算粗略帶大家了解一下編譯器迷你的樣子,如果有不同的見解,歡迎評論區(qū)留言互動,共同進步呀!
審核編輯 :李倩
-
二進制
+關(guān)注
關(guān)注
2文章
801瀏覽量
41790 -
匯編語言
+關(guān)注
關(guān)注
14文章
410瀏覽量
35995 -
編譯器
+關(guān)注
關(guān)注
1文章
1643瀏覽量
49345
原文標題:寫一個編譯器
文章出處:【微信號:cxuangoodjob,微信公眾號:程序員cxuan】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論