不知道你是不是和我一樣，看到“編譯器”三個(gè)字的時(shí)候，就感覺(jué)非常高大上，同時(shí)心底會(huì)升起一絲絲“害怕”！

我始終認(rèn)為編譯器是很復(fù)雜...很復(fù)雜的東西，不是我這種小白能懂的。而且一想到要學(xué)習(xí)編譯器的知識(shí)，腦海里就浮現(xiàn)出那種 500 頁(yè)起的厚書(shū)。

一直到我發(fā)現(xiàn) the-super-tiny-compiler 這個(gè)寶藏級(jí)的開(kāi)源項(xiàng)目，它是一個(gè)僅 1000 行左右的迷你編譯器，其中注釋占了代碼量的 80%，實(shí)際代碼只有 200 行！麻雀雖小但五臟俱全，完整地實(shí)現(xiàn)了編譯器所需基本功能，通過(guò) 代碼+注釋+講解 讓你通過(guò)一個(gè)開(kāi)源項(xiàng)目入門(mén)編譯器。

地址：https://github.com/jamiebuilds/the-super-tiny-compiler

中文：https://github.com/521xueweihan/OneFile/blob/main/src/javascript/the-super-tiny-compiler.js

下面我將從介紹 什么是編譯器 開(kāi)始，使用上述項(xiàng)目作為示例代碼，更加細(xì)致地講解編譯的過(guò)程，把編譯器入門(mén)的門(mén)檻再往下砍一砍。如果你之前沒(méi)有接觸過(guò)編譯器相關(guān)的知識(shí)，那這篇文章可以讓你對(duì)編譯器所做的事情，以及原理有一個(gè)初步的認(rèn)識(shí)！

準(zhǔn)備好變強(qiáng)了嗎？那我們開(kāi)始吧！

一、什么是編譯器

從概念上簡(jiǎn)單講：

編譯器就是將“一種語(yǔ)言（通常為高級(jí)語(yǔ)言）”翻譯為“另一種語(yǔ)言（通常為低級(jí)語(yǔ)言）”的程序。

對(duì)于現(xiàn)代程序員來(lái)說(shuō)我們最熟悉的 JavaScript、Java 這些都屬于高級(jí)語(yǔ)言，也就是便于我們編程者編寫(xiě)、閱讀、理解、維護(hù)的語(yǔ)言，而低級(jí)語(yǔ)言就是計(jì)算機(jī)能直接解讀、運(yùn)行的語(yǔ)言。

編譯器也可以理解成是這兩種語(yǔ)言之間的“橋梁”。編譯器存在的原因是因?yàn)橛?jì)算機(jī) CPU 執(zhí)行數(shù)百萬(wàn)個(gè)微小的操作，因?yàn)檫@些操作實(shí)在是太“微小”，你肯定不愿意手動(dòng)去編寫(xiě)它們，于是就有了二進(jìn)制的出現(xiàn)，二進(jìn)制代碼也被理解成為機(jī)器代碼。很顯然，二進(jìn)制看上去并不好理解，而且編寫(xiě)二進(jìn)制代碼很麻煩，因此 CPU 架構(gòu)支持把二進(jìn)制操作映射作為一種更容易閱讀的語(yǔ)言——匯編語(yǔ)言。

雖然匯編語(yǔ)言非常低級(jí)，但是它可以轉(zhuǎn)換為二進(jìn)制代碼，這種轉(zhuǎn)換主要靠的是“匯編器”。因?yàn)閰R編語(yǔ)言仍然非常低級(jí)，對(duì)于追求高效的程序員來(lái)說(shuō)是無(wú)法忍受的，所以又出現(xiàn)了更高級(jí)的語(yǔ)言，這也是大部分程序員使用且熟悉的編程語(yǔ)言，這些抽象的編程語(yǔ)言雖然不能直接轉(zhuǎn)化成機(jī)器操作，但是它比匯編語(yǔ)言更好理解且更能夠被高效的使用。所以我們需要的其實(shí)就是能理解這些復(fù)雜語(yǔ)言并正確地轉(zhuǎn)換成低級(jí)代碼的工具——編譯器。

我覺(jué)得對(duì)于初學(xué)者來(lái)說(shuō)到這里有個(gè)大致的了解就可以了。因?yàn)榻酉氯ヒ治龅倪@個(gè)例子非常簡(jiǎn)單但是能覆蓋大多數(shù)場(chǎng)景，你會(huì)從最真實(shí)最直接的角度來(lái)直面這個(gè)“大敵”——編譯器。

二、“迷你”編譯器

下面我們就用 the-super-tiny-compiler 為示例代碼，帶大家來(lái)簡(jiǎn)單了解一下編譯器。

不同編譯器之間的不同階段可能存在差別，但基本都離不開(kāi)這三個(gè)主要組成部分：解析、轉(zhuǎn)換和代碼生成。

其實(shí)這個(gè)“迷你”編譯器開(kāi)源項(xiàng)目的目的就是這些：

• 證明現(xiàn)實(shí)世界的編譯器主要做的是什么

• 做一些足夠復(fù)雜的事情來(lái)證明構(gòu)建編譯器的合理性

• 用最簡(jiǎn)單的代碼來(lái)解釋編譯器的主要功能，使新手不會(huì)望而卻步

以上就解釋了這個(gè)開(kāi)源項(xiàng)目存在的意義了，所以如果你對(duì)編譯器有很濃厚的興趣希望一學(xué)到底的，那肯定還是離不開(kāi)大量的閱讀和鉆研啦，但是如果你希望對(duì)編譯器的功能有所了解，那這篇文章就別錯(cuò)過(guò)啦！

現(xiàn)在我們就要對(duì)這個(gè)項(xiàng)目本身進(jìn)行進(jìn)一步的學(xué)習(xí)了，有些背景需要提前了解一下。這個(gè)項(xiàng)目主要是把 LISP 語(yǔ)言編譯成我們熟悉的 JavaScript 語(yǔ)言。

那為什么要用 LISP 語(yǔ)言呢？

LISP 是具有悠久歷史的計(jì)算機(jī)編程語(yǔ)言家族，有獨(dú)特和完全用括號(hào)的前綴符號(hào)表示法。起源于 1958 年，是現(xiàn)今第二悠久仍廣泛使用的高端編程語(yǔ)言。

首先 LISP 語(yǔ)言和我們熟悉的 C 語(yǔ)言和 JavaScript 語(yǔ)言很不一樣，雖然其他的語(yǔ)言也有強(qiáng)大的編譯器，但是相對(duì)于 LISP 語(yǔ)言要復(fù)雜得多。LISP 語(yǔ)言是一種超級(jí)簡(jiǎn)單的解析語(yǔ)法，并且很容易被翻譯成其他語(yǔ)法，像這樣：

所以到這里你應(yīng)該知道我們要干什么了吧？那讓我們?cè)偕钊氲亓私庖幌戮唧w要怎么進(jìn)行“翻譯”（編譯）吧！

三、編譯過(guò)程

前面我們已經(jīng)提過(guò)，大部分的編譯器都主要是在做三件事：

1. 解析
2. 轉(zhuǎn)換
3. 代碼生成

下面我們將分解 the-super-tiny-compiler 的代碼，然后進(jìn)行逐行解讀。

讓我們一起跟著代碼，弄清楚上述三個(gè)階段具體做了哪些事情～

3.1 解析

解析通常分為兩個(gè)階段：詞法分析和句法分析

1. 詞法分析：獲取原始代碼并通過(guò)一種稱(chēng)為標(biāo)記器（或詞法分析器 Tokenizer）的東西將其拆分為一種稱(chēng)為標(biāo)記（Token）的東西。標(biāo)記是一個(gè)數(shù)組，它描述了一個(gè)獨(dú)立的語(yǔ)法片段。這些片段可以是數(shù)字、標(biāo)簽、標(biāo)點(diǎn)符號(hào)、運(yùn)算符等等。

2. 語(yǔ)法分析：獲取之前生成的標(biāo)記（Token），并把它們轉(zhuǎn)換成一種抽象的表示，這種抽象的表示描述了代碼語(yǔ)句中的每一個(gè)片段以及它們之間的關(guān)系。這被稱(chēng)為中間表示（intermediate representation）或抽象語(yǔ)法樹(shù)（Abstract Syntax Tree， 縮寫(xiě)為AST）。AST 是一個(gè)深度嵌套的對(duì)象，用一種更容易處理的方式代表了代碼本身，也能給我們更多信息。

比如下面這個(gè)語(yǔ)法:

(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:')'},
]

代碼思路：

因?yàn)槲覀冃枰ソ馕鲎址?，就需要有一個(gè)像指針/光標(biāo)來(lái)幫我們辨認(rèn)目前解析的位置是哪里，所以會(huì)有一個(gè) current 的變量，從 0 開(kāi)始。而我們最終的目的是獲取一個(gè) token 數(shù)組，所以也先初始化一個(gè)空數(shù)組 tokens。

//`current`變量就像一個(gè)指光標(biāo)一樣讓我們可以在代碼中追蹤我們的位置
letcurrent=0;

//`tokens`數(shù)組用來(lái)存我們的標(biāo)記
lettokens=[];

既然要解析字符串，自然少不了遍歷啦！這里就用一個(gè) while 循環(huán)來(lái)解析我們當(dāng)前的字符串。

//在循環(huán)里面我們可以將`current`變量增加為我們想要的值
while(current//我們還將在`input`中存儲(chǔ)`current`字符
letchar=input[current];
}

如何獲取字符串里面的單個(gè)字符呢？答案是用像數(shù)組那樣的中括號(hào)來(lái)獲?。?/span>

varchar=str[0]

這里新增一個(gè)知識(shí)點(diǎn)來(lái)咯！在 JavaScript 中 String 類(lèi)的實(shí)例，是一個(gè)類(lèi)數(shù)組，從下面這個(gè)例子可以看出來(lái)：

可能之前你會(huì)用 charAt 來(lái)獲取字符串的單個(gè)字符，因?yàn)樗窃?String 類(lèi)型上的一個(gè)方法：

這兩個(gè)方法都可以實(shí)現(xiàn)你想要的效果，但是也存在差別。下標(biāo)不存在時(shí) str[index] 會(huì)返回 undefined，而 str.charAt(index) 則會(huì)返回 ""(空字符串）：

隨著光標(biāo)的移動(dòng)和字符串中字符的獲取，我們就可以來(lái)逐步解析當(dāng)前字符串了。

那解析也可以從這幾個(gè)方面來(lái)考慮，以 (add 2 (subtract 4 2)) 這個(gè)為例，我們會(huì)遇到這些：( 左括號(hào)、字符串、空格、數(shù)字、) 右括號(hào)。對(duì)于不同的類(lèi)型，就要用不同的 if 條件判斷分別處理：

• 左右括號(hào)匹配代表一個(gè)整體，找到對(duì)應(yīng)的括號(hào)只要做上標(biāo)記就好
• 空格代表有字符分割，不需要放到我們的 token 數(shù)組里，只需要跳到下一個(gè)非空格的字符繼續(xù)循環(huán)就好

//檢查是否有一個(gè)左括號(hào):
if(char==='('){

//如果有，我們會(huì)存一個(gè)類(lèi)型為`paren`的新標(biāo)記到數(shù)組，并將值設(shè)置為一個(gè)左括號(hào)。
tokens.push({
type:'paren',
value:'(',
});

//`current`自增
current++;

//然后繼續(xù)進(jìn)入下一次循環(huán)。
continue;
}

//接下去檢查右括號(hào)，像上面一樣
if(char===')'){
tokens.push({
type:'paren',
value:')',
});
current++;
continue;
}

//接下去我們檢查空格，這對(duì)于我們來(lái)說(shuō)就是為了知道字符的分割，但是并不需要存儲(chǔ)為標(biāo)記。

//所以我們來(lái)檢查是否有空格的存在，如果存在，就繼續(xù)下一次循環(huán)，做除了存儲(chǔ)到標(biāo)記數(shù)組之外的其他操作即可
letWHITESPACE=/s/;
if(WHITESPACE.test(char)){
current++;
continue;
}

字符串和數(shù)字因?yàn)榫哂懈髯圆煌暮x，所以處理上面相對(duì)復(fù)雜一些。先從數(shù)字來(lái)入手，因?yàn)閿?shù)字的長(zhǎng)度不固定，所以要確保獲取到全部的數(shù)字字符串呢，就要經(jīng)過(guò)遍歷，從遇到第一個(gè)數(shù)字開(kāi)始直到遇到一個(gè)不是數(shù)字的字符結(jié)束，并且要把這個(gè)數(shù)字存起來(lái)。

//(add123456)
//^^^^^^
//只有兩個(gè)單獨(dú)的標(biāo)記
//
//因此，當(dāng)我們遇到序列中的第一個(gè)數(shù)字時(shí)，我們就開(kāi)始了
letNUMBERS=/[0-9]/;
if(NUMBERS.test(char)){

//我們將創(chuàng)建一個(gè)`value`字符串，并把字符推送給他
letvalue='';

//然后我們將遍歷序列中的每個(gè)字符，直到遇到一個(gè)不是數(shù)字的字符
//將每個(gè)作為數(shù)字的字符推到我們的`value`并隨著我們?nèi)ピ黾觍current`
//這樣我們就能拿到一個(gè)完整的數(shù)字字符串，例如上面的123和456，而不是單獨(dú)的123456
while(NUMBERS.test(char)){
value+=char;
char=input[++current];
}

//接著我們把數(shù)字放到標(biāo)記數(shù)組中，用數(shù)字類(lèi)型來(lái)描述區(qū)分它
tokens.push({type:'number',value});

//繼續(xù)外層的下一次循環(huán)
continue;
}

為了更適用于現(xiàn)實(shí)場(chǎng)景，這里支持字符串的運(yùn)算，例如 (concat "foo" "bar") 這種形式的運(yùn)算，那就要對(duì) " 內(nèi)部的字符串再做一下解析，過(guò)程和數(shù)字類(lèi)似，也需要遍歷，然后獲取全部的字符串內(nèi)容之后再存起來(lái)：

//從檢查開(kāi)頭的雙引號(hào)開(kāi)始:
if(char==='"'){
//保留一個(gè)`value`變量來(lái)構(gòu)建我們的字符串標(biāo)記。
letvalue='';

//我們將跳過(guò)編輯中開(kāi)頭的雙引號(hào)
char=input[++current];

//然后我們將遍歷每個(gè)字符，直到我們到達(dá)另一個(gè)雙引號(hào)
while(char!=='"'){
value+=char;
char=input[++current];
}

//跳過(guò)相對(duì)應(yīng)閉合的雙引號(hào).
char=input[++current];

//把我們的字符串標(biāo)記添加到標(biāo)記數(shù)組中
tokens.push({type:'string',value});

continue;
}

最后一種標(biāo)記的類(lèi)型是名稱(chēng)。這是一個(gè)字母序列而不是數(shù)字，這是我們 lisp 語(yǔ)法中的函數(shù)名稱(chēng)：

//(add24)
//^^^
//名稱(chēng)標(biāo)記
//
letLETTERS=/[a-z]/i;
if(LETTERS.test(char)){
letvalue='';

//同樣，我們遍歷所有，并將它們完整的存到`value`變量中
while(LETTERS.test(char)){
value+=char;
char=input[++current];
}

//并把這種名稱(chēng)類(lèi)型的標(biāo)記存到標(biāo)記數(shù)組中，繼續(xù)循環(huán)
tokens.push({type:'name',value});

continue;
}

以上我們就能獲得一個(gè) tokens 數(shù)組了，下一步就是構(gòu)建一個(gè)抽象語(yǔ)法樹(shù)（AST）可能看起來(lái)像這樣：

{
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',
}]
}]
}]
}

代碼思路：

同樣我們也需要有一個(gè)光標(biāo)/指針來(lái)幫我們辨認(rèn)當(dāng)前操作的對(duì)象是誰(shuí)，然后預(yù)先創(chuàng)建我們的 AST 樹(shù)，他有一個(gè)根節(jié)點(diǎn)叫做 Program：

letcurrent=0;

letast={
type:'Program',
body:[],
};

再來(lái)看一眼我們之前獲得的 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:')'},
]

你會(huì)發(fā)現(xiàn)對(duì)于 (add 2 (subtract 4 2)) 這種具有嵌套關(guān)系的字符串，這個(gè)數(shù)組非?！氨馄健币矡o(wú)法明顯的表達(dá)嵌套關(guān)系，而我們的 AST 結(jié)構(gòu)就能夠很清晰的表達(dá)嵌套的關(guān)系。對(duì)于上面的數(shù)組來(lái)說(shuō)，我們需要遍歷每一個(gè)標(biāo)記，找出其中是 CallExpression 的 params，直到遇到右括號(hào)結(jié)束，所以遞歸是最好的方法，所以我們創(chuàng)建一個(gè)叫 walk 的遞歸方法，這個(gè)方法返回一個(gè) node 節(jié)點(diǎn)，并存入我們的 ast.body 的數(shù)組中：

functionwalk(){
//在walk函數(shù)里面，我們首先獲取`current`標(biāo)記
lettoken=tokens[current];
}

while(current

下面就來(lái)實(shí)現(xiàn)我們的 walk 方法。我們希望這個(gè)方法可以正確解析 tokens 數(shù)組里的信息，首先就是要針對(duì)不同的類(lèi)型 type 作區(qū)分：

首先先操作“值”，因?yàn)樗遣粫?huì)作為父節(jié)點(diǎn)的所以也是最簡(jiǎn)單的。在上面我們已經(jīng)了解了值可能是數(shù)字 (subtract 4 2) 也可能是字符串 (concat "foo" "bar")，只要把值和類(lèi)型匹配上就好：

//首先先檢查一下是否有`number`標(biāo)簽.
if(token.type==='number'){

//如果找到一個(gè),就增加`current`.
current++;

//然后我們就能返回一個(gè)新的叫做`NumberLiteral`的AST節(jié)點(diǎn)，并賦值
return{
type:'NumberLiteral',
value:token.value,
};
}

//對(duì)于字符串來(lái)說(shuō)，也是和上面數(shù)字一樣的操作。新增一個(gè)`StringLiteral`節(jié)點(diǎn)
if(token.type==='string'){
current++;

return{
type:'StringLiteral',
value:token.value,
};
}

接下去我們要尋找調(diào)用的表達(dá)式（CallExpressions）。每匹配一個(gè)左括號(hào)，就能在下一個(gè)得到表達(dá)式的名字，在沒(méi)有遇到右括號(hào)之前都經(jīng)過(guò)遞歸把樹(shù)狀結(jié)構(gòu)豐富起來(lái)，直到遇到右括號(hào)停止遞歸，直到循環(huán)結(jié)束。從代碼上看更加直觀：

if(
token.type==='paren'&&
token.value==='('
){

//我們將增加`current`來(lái)跳過(guò)這個(gè)插入語(yǔ)，因?yàn)樵贏ST樹(shù)中我們并不關(guān)心這個(gè)括號(hào)
token=tokens[++current];

//我們創(chuàng)建一個(gè)類(lèi)型為“CallExpression”的基本節(jié)點(diǎn)，并把當(dāng)前標(biāo)記的值設(shè)置到name字段上
//因?yàn)樽罄ㄌ?hào)的下一個(gè)標(biāo)記就是這個(gè)函數(shù)的名字
letnode={
type:'CallExpression',
name:token.value,
params:[],
};

//繼續(xù)增加`current`來(lái)跳過(guò)這個(gè)名稱(chēng)標(biāo)記
token=tokens[++current];

//現(xiàn)在我們要遍歷每一個(gè)標(biāo)記，找出其中是`CallExpression`的`params`，直到遇到右括號(hào)
//我們將依賴(lài)嵌套的`walk`函數(shù)來(lái)增加我們的`current`變量來(lái)超過(guò)任何嵌套的`CallExpression`
//所以我們創(chuàng)建一個(gè)`while`循環(huán)持續(xù)到遇到一個(gè)`type`是'paren'并且`value`是右括號(hào)的標(biāo)記
while(
(token.type!=='paren')||
(token.type==='paren'&&token.value!==')')
){
//我們把這個(gè)節(jié)點(diǎn)存到我們的`node.params`中去
node.params.push(walk());
token=tokens[current];
}

//我們最后一次增加`current`變量來(lái)跳過(guò)右括號(hào)
current++;

//返回node節(jié)點(diǎn)
returnnode;
}

3.2 轉(zhuǎn)換

編譯器的下一個(gè)階段是轉(zhuǎn)換。要做的就是獲取 AST 之后再對(duì)其進(jìn)行更改。它可以用相同的語(yǔ)言操作 AST，也可以將其翻譯成一種全新的語(yǔ)言。

那如何轉(zhuǎn)換 AST 呢？

你可能會(huì)注意到我們的 AST 中的元素看起來(lái)非常相似。這些元素都有 type 屬性，它們被稱(chēng)為 AST 結(jié)點(diǎn)。這些節(jié)點(diǎn)含有若干屬性，可以用于描述 AST 的部分信息。

//我們可以有一個(gè)“NumberLiteral”的節(jié)點(diǎn)：
{
type:'NumberLiteral',
value:'2',
}

//或者可能是“CallExpression”的一個(gè)節(jié)點(diǎn)：
{
type:'CallExpression',
name:'subtract',
params:[...嵌套節(jié)點(diǎn)放在這里...],
}

對(duì)于轉(zhuǎn)換 AST 無(wú)非就是通過(guò)新增、刪除、替換屬性來(lái)操作節(jié)點(diǎn)，或者也可以新增節(jié)點(diǎn)、刪除節(jié)點(diǎn)，甚至我們可以在原有的 AST 結(jié)構(gòu)保持不變的狀態(tài)下創(chuàng)建一個(gè)基于它的全新的 AST。

由于我們的目標(biāo)是一種新的語(yǔ)言，所以我們將要專(zhuān)注于創(chuàng)造一個(gè)完全新的 AST 來(lái)配合這個(gè)特定的語(yǔ)言。

為了能夠訪(fǎng)問(wèn)所有這些節(jié)點(diǎn)，我們需要遍歷它們，使用的是深度遍歷的方法。對(duì)于我們?cè)谏厦娅@取的那個(gè) AST 遍歷流程應(yīng)該是這樣的：

如果我們直接操作這個(gè) AST 而不是創(chuàng)造一個(gè)單獨(dú)的 AST，我們很有可能會(huì)在這里引入各種抽象。但是僅僅訪(fǎng)問(wèn)樹(shù)中的每個(gè)節(jié)點(diǎn)對(duì)于我們來(lái)說(shuō)想做和能做的事情已經(jīng)很多了。

（使用訪(fǎng)問(wèn)（visiting）這個(gè)詞是因?yàn)檫@是一種模式，代表在對(duì)象結(jié)構(gòu)內(nèi)對(duì)元素進(jìn)行操作。）

所以我們現(xiàn)在創(chuàng)建一個(gè)訪(fǎng)問(wèn)者對(duì)象（visitor），這個(gè)對(duì)象具有接受不同節(jié)點(diǎn)類(lèi)型的方法：

varvisitor={
NumberLiteral(){},
CallExpression(){},
};

當(dāng)我們遍歷 AST 的時(shí)候，如果遇到了匹配 type 的結(jié)點(diǎn)，我們可以調(diào)用 visitor 中的方法。

一般情況下為了讓這些方法可用性更好，我們會(huì)把父結(jié)點(diǎn)也作為參數(shù)傳入。

varvisitor={
NumberLiteral(node,parent){},
CallExpression(node,parent){},
};

當(dāng)然啦，對(duì)于深度遍歷的話(huà)我們都知道，往下遍歷到最深的自節(jié)點(diǎn)的時(shí)候還需要“往回走”，也就是我們所說(shuō)的“退出”當(dāng)前節(jié)點(diǎn)。你也可以這樣理解：向下走“進(jìn)入”節(jié)點(diǎn)，向上走“退出”節(jié)點(diǎn)。

為了支持這點(diǎn)，我們的“訪(fǎng)問(wèn)者”的最終形式應(yīng)該像是這樣：

varvisitor={
Program:{
enter(node,parent){},
exit(node,parent){},
},
NumberLiteral:{
enter(node,parent){},
exit(node,parent){},
},
CallExpression:{
enter(node,parent){},
exit(node,parent){},
},
...
};

遍歷

首先我們定義了一個(gè)接收一個(gè) AST 和一個(gè)訪(fǎng)問(wèn)者的遍歷器函數(shù)（traverser）。需要根據(jù)每個(gè)節(jié)點(diǎn)的類(lèi)型來(lái)調(diào)用不同的訪(fǎng)問(wèn)者的方法，所以我們定義一個(gè) traverseNode 的方法，傳入當(dāng)前的節(jié)點(diǎn)和它的父節(jié)點(diǎn)，從根節(jié)點(diǎn)開(kāi)始，根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)，所以傳入 null 即可。

functiontraverser(ast,visitor){
// traverseNode 函數(shù)將接受兩個(gè)參數(shù)：node 節(jié)點(diǎn)和他的 parent 節(jié)點(diǎn)
//這樣他就可以將兩者都傳遞給我們的訪(fǎng)問(wèn)者方法（visitor）
functiontraverseNode(node,parent){

//我們首先從匹配`type`開(kāi)始，來(lái)檢測(cè)訪(fǎng)問(wèn)者方法是否存在。訪(fǎng)問(wèn)者方法就是（enter 和 exit）
letmethods=visitor[node.type];

//如果這個(gè)節(jié)點(diǎn)類(lèi)型有`enter`方法，我們將調(diào)用這個(gè)函數(shù)，并且傳入當(dāng)前節(jié)點(diǎn)和他的父節(jié)點(diǎn)
if(methods&&methods.enter){
methods.enter(node,parent);
}

//接下去我們將按當(dāng)前節(jié)點(diǎn)類(lèi)型來(lái)進(jìn)行拆分，以便于對(duì)子節(jié)點(diǎn)數(shù)組進(jìn)行遍歷，處理到每一個(gè)子節(jié)點(diǎn)
switch(node.type){
//首先從最高的`Program`層開(kāi)始。因?yàn)?Program 節(jié)點(diǎn)有一個(gè)名叫 body 的屬性，里面包含了節(jié)點(diǎn)數(shù)組
//我們調(diào)用`traverseArray`來(lái)向下遍歷它們
//
//請(qǐng)記住，`traverseArray`會(huì)依次調(diào)用`traverseNode`，所以這棵樹(shù)將會(huì)被遞歸遍歷
case'Program':
traverseArray(node.body,node);
break;

//接下去我們對(duì)`CallExpression`做相同的事情，然后遍歷`params`屬性
case'CallExpression':
traverseArray(node.params,node);
break;

//對(duì)于`NumberLiteral`和`StringLiteral`的情況，由于沒(méi)有子節(jié)點(diǎn)，所以直接break即可
case'NumberLiteral':
case'StringLiteral':
break;

//接著，如果我們沒(méi)有匹配到上面的節(jié)點(diǎn)類(lèi)型，就拋出一個(gè)異常錯(cuò)誤
default:
thrownewTypeError(node.type);
}

//如果這個(gè)節(jié)點(diǎn)類(lèi)型里面有一個(gè)`exit`方法，我們就調(diào)用它，并且傳入當(dāng)前節(jié)點(diǎn)和他的父節(jié)點(diǎn)
if(methods&&methods.exit){
methods.exit(node,parent);
}
}

//調(diào)用`traverseNode`來(lái)啟動(dòng)遍歷，傳入之前的AST樹(shù)，由于AST樹(shù)最開(kāi)始
//的點(diǎn)沒(méi)有父節(jié)點(diǎn)，所以我們直接傳入null就好
traverseNode(ast,null);
}

因?yàn)?Program 和 CallExpression 兩種類(lèi)型可能會(huì)含有子節(jié)點(diǎn)，所以對(duì)這些可能存在的子節(jié)點(diǎn)數(shù)組需要做進(jìn)一步的處理，所以創(chuàng)建了一個(gè)叫 traverseArray 的方法來(lái)進(jìn)行迭代。

//traverseArray函數(shù)來(lái)迭代數(shù)組，并且調(diào)用traverseNode函數(shù)
functiontraverseArray(array,parent){
array.forEach(child=>{
traverseNode(child,parent);
});
}

轉(zhuǎn)換

下一步就是把之前的 AST 樹(shù)進(jìn)一步進(jìn)行轉(zhuǎn)換變成我們所期望的那樣變成 JavaScript 的 AST 樹(shù)：

如果你對(duì) JS 的 AST 的語(yǔ)法解析不是很熟悉的話(huà)，可以借助在線(xiàn)工具網(wǎng)站來(lái)幫助你知道大致要轉(zhuǎn)換成什么樣子的 AST 樹(shù)，就可以在其他更復(fù)雜的場(chǎng)景進(jìn)行應(yīng)用啦～

我們創(chuàng)建一個(gè)像之前的 AST 樹(shù)一樣的新的 AST 樹(shù)，也有一個(gè)Program 節(jié)點(diǎn)：

functiontransformer(ast){

letnewAst={
type:'Program',
body:[],
};

//這里有個(gè) hack 技巧：這個(gè)上下文（context）屬性只是用來(lái)對(duì)比新舊 ast 的
//通常你會(huì)有比這個(gè)更好的抽象方法，但是為了我們的目標(biāo)能實(shí)現(xiàn)，這個(gè)方法相對(duì)簡(jiǎn)單些
ast._context=newAst.body;

//在這里調(diào)用遍歷器函數(shù)并傳入我們的舊的AST樹(shù)和訪(fǎng)問(wèn)者方法(visitor)
traverser(ast,{...}};

//在轉(zhuǎn)換器方法的最后，我們就能返回我們剛創(chuàng)建的新的AST樹(shù)了
returnnewAst;
}

那我們?cè)賮?lái)完善我們的 visitor對(duì)象，對(duì)于不同類(lèi)型的節(jié)點(diǎn)，可以定義它的 enter 和 exit 方法（這里因?yàn)橹灰L(fǎng)問(wèn)到節(jié)點(diǎn)并進(jìn)行處理就可以了，所以用不到退出節(jié)點(diǎn)的方法：exit）：

{
//第一個(gè)訪(fǎng)問(wèn)者方法是NumberLiteral
NumberLiteral:{
enter(node,parent){
//我們將創(chuàng)建一個(gè)也叫做`NumberLiteral`的新節(jié)點(diǎn)，并放到父節(jié)點(diǎn)的上下文中去
parent._context.push({
type:'NumberLiteral',
value:node.value,
});
},
},

//接下去是`StringLiteral`
StringLiteral:{
enter(node,parent){
parent._context.push({
type:'StringLiteral',
value:node.value,
});
},
},

CallExpression:{...}
}

對(duì)于 CallExpression 會(huì)相對(duì)比較復(fù)雜一點(diǎn)，因?yàn)樗赡芎星短椎膬?nèi)容。

CallExpression:{
enter(node,parent){

//首先我們創(chuàng)建一個(gè)叫`CallExpression`的節(jié)點(diǎn)，它帶有表示嵌套的標(biāo)識(shí)符“Identifier”
letexpression={
type:'CallExpression',
callee:{
type:'Identifier',
name:node.name,
},
arguments:[],
};

//下面我們?cè)谠瓉?lái)的`CallExpression`節(jié)點(diǎn)上定義一個(gè)新的 context，
//它是 expression 中 arguments 這個(gè)數(shù)組的引用，我們可以向其中放入?yún)?shù)。
node._context=expression.arguments;

//之后我們將檢查父節(jié)點(diǎn)是否是`CallExpression`類(lèi)型
//如果不是的話(huà)
if(parent.type!=='CallExpression'){

//我們將用`ExpressionStatement`來(lái)包裹`CallExpression`節(jié)點(diǎn)
//這么做是因?yàn)閱为?dú)存在的`CallExpressions`在 JavaScript 中也可以被當(dāng)做是聲明語(yǔ)句。
//
//比如`vara=foo()`與`foo()`，后者既可以當(dāng)作表達(dá)式給某個(gè)變量賦值，
//也可以作為一個(gè)獨(dú)立的語(yǔ)句存在
expression={
type:'ExpressionStatement',
expression:expression,
};
}

//最后我們把我們的`CallExpression`(可能有包裹)放到父節(jié)點(diǎn)的上下文中去
parent._context.push(expression);
},
}

3.3 代碼生成

編譯器的最后一個(gè)階段是代碼生成，這個(gè)階段做的事情有時(shí)候會(huì)和轉(zhuǎn)換（transformation）重疊，但是代碼生成最主要的部分還是根據(jù) AST 來(lái)輸出代碼。代碼生成有幾種不同的工作方式，有些編譯器將會(huì)重用之前生成的 token，有些會(huì)創(chuàng)建獨(dú)立的代碼表示，以便于線(xiàn)性地輸出代碼。但是接下來(lái)我們還是著重于使用之前生成好的 AST。

根據(jù)前面的這幾步驟，我們已經(jīng)得到了我們新的 AST 樹(shù)：

接下來(lái)將調(diào)用代碼生成器將遞歸的調(diào)用自己來(lái)打印樹(shù)的每一個(gè)節(jié)點(diǎn)，最后輸出一個(gè)字符串。

functioncodeGenerator(node){

//還是按照節(jié)點(diǎn)的類(lèi)型來(lái)進(jìn)行分解操作
switch(node.type){

//如果我們有`Program`節(jié)點(diǎn)，我們將映射`body`中的每個(gè)節(jié)點(diǎn)
//并且通過(guò)代碼生成器來(lái)運(yùn)行他們，用換行符將他們連接起來(lái)
case'Program':
returnnode.body.map(codeGenerator)
.join('
');

//對(duì)于`ExpressionStatement`，我們將在嵌套表達(dá)式上調(diào)用代碼生成器，并添加一個(gè)分號(hào)
case'ExpressionStatement':
return(
codeGenerator(node.expression)+
';'//<
);

//對(duì)于`CallExpression`我們將打印`callee`,新增一個(gè)左括號(hào)
//然后映射每一個(gè)`arguments`數(shù)組的節(jié)點(diǎn)，并用代碼生成器執(zhí)行，每一個(gè)節(jié)點(diǎn)運(yùn)行完之后加上逗號(hào)
//最后增加一個(gè)右括號(hào)
case'CallExpression':
return(
codeGenerator(node.callee)+
'('+
node.arguments.map(codeGenerator)
.join(',')+
')'
);

//對(duì)于`Identifier`直接返回`node`的名字就好.
case'Identifier':
returnnode.name;

//對(duì)于`NumberLiteral`直接返回`node`的值就好.
case'NumberLiteral':
returnnode.value;

//對(duì)于`StringLiteral`，在`node`的值的周?chē)砑与p引號(hào).
case'StringLiteral':
return'"'+node.value+'"';

//如果沒(méi)有匹配到節(jié)點(diǎn)的類(lèi)型，就拋出異常
default:
thrownewTypeError(node.type);
}
}

經(jīng)過(guò)代碼生成之后我們就得到了這樣的 JS 字符串：add(2, subtract(4, 2)); 也就代表我們的編譯過(guò)程是成功的！

四、結(jié)語(yǔ)

以上就是編寫(xiě)一個(gè) LISP 到 JS 編譯器的全過(guò)程，逐行中文注釋的完整代碼地址：

https://github.com/521xueweihan/OneFile/blob/main/src/javascript/the-super-tiny-compiler.js

那么，今天學(xué)到的東西哪里會(huì)用到呢？眾所周知的 Vue 和 React 雖然寫(xiě)法上有所區(qū)別，但是“殊途同歸”都是通過(guò) AST 轉(zhuǎn)化的前端框架。這中間最重要的就是轉(zhuǎn)換 AST，它是非常“強(qiáng)大”且應(yīng)用廣泛，比較常見(jiàn)的使用場(chǎng)景：

• IDE 的錯(cuò)誤提示、代碼高亮，還可以幫助實(shí)現(xiàn)代碼自動(dòng)補(bǔ)全等功能
• 常見(jiàn)的 Webpack 和 rollup 打包（壓縮）

AST 被廣泛應(yīng)用在編譯器、IDE 和代碼優(yōu)化壓縮上，以及前端框架 Vue、React 等等。雖然我們并不會(huì)常常與 AST 直接打交道，但它總是無(wú)時(shí)無(wú)刻不陪伴著我們。

當(dāng)然啦！看完文章不一定算真正了解了，所有學(xué)習(xí)過(guò)程都離不開(kāi)動(dòng)手實(shí)踐，或許實(shí)踐過(guò)程中你也會(huì)有不一樣的理解。實(shí)踐方法十分簡(jiǎn)單：只需打開(kāi)瀏覽器的“開(kāi)發(fā)者模式” ——> 進(jìn)入控制臺(tái)（console）——> 復(fù)制/粘貼代碼，就可以直接運(yùn)行看到結(jié)果了！

以上就是本文的所有內(nèi)容 本文只能算粗略帶大家了解一下編譯器迷你的樣子，如果有不同的見(jiàn)解，歡迎評(píng)論區(qū)留言互動(dòng)，共同進(jìn)步呀！