不懂編譯原理？本文教你從零實現最簡編譯模型！
簡介
前兩日我偶然間在 GitHub 上發現了一個專案：the-super-tiny-compiler，官方介紹說這可能是一個最簡的編譯器。剛好之前學過「編譯原理」這門課，我的興趣一下子就上來了，簡單看了一下，這個專案是將一個 Lisp 表示式轉化為 C 的表示式的編譯器，中間涉及詞法分析、語法分析、AST 樹遍歷轉化以及最後的程式碼輸出環節，下面我就帶大家一起來簡單實現一下。
詞法分析
詞法分析也叫解析，每一個編譯器需要做的第一步都是詞法分析，具體是什麼意思呢？簡單來說就是把要進行轉化的「原始碼」拆解開，形成一個一個小部件，稱為 token。比如說如下將一個 JavaScript 語句拆解開的例子：
let name = "touryung";
大致分解就可以得到一個 token 陣列：[let, name, =, "touryung", ;]，這樣才有利於進行下一步操作。由於我們此次實現的是最簡編譯器，因此編譯器內部只實現了對小括號、空格、數位、字串、變數的識別。
整體框架
要實現詞法分析器（解析器），首先我們需要先搭出一個框架。詞法分析的整體思路就是遍歷輸入的字串，然後識別不同的 token，將它儲存到 token 陣列。
框架如下，不同部分的意思已在註釋中標出：
const WHITESPACE = /\s/; // 空格
const NUMBERS = /[0-9]/; // 數位
const LETTERS = /[a-z]/i; // 變數
function tokenizer(input) {
let current = 0; // 當前識別到的下標
let tokens = []; // token 陣列
while (current < input.length) {
// 遍歷
let char = input[current]; // 當前遍歷到的字元
// 不同的 token 識別操作
throw new TypeError(`I dont know what this character is: ${char}`);
}
return tokens;
}
搭出框架，下一步就是識別不同的 token 了。
識別括號
識別括號很簡單，當遍歷到當前字元是左右括號時，將一個描述當前 token 的物件放入 token 陣列即可。
// 識別左括號
if (char === "(") {
tokens.push({ type: "paren", value: "(" }); // 壓入描述當前 token 的物件
current++;
continue;
}
// 識別右括號
if (char === ")") {
tokens.push({ type: "paren", value: ")" });
current++;
continue;
}
識別空格
這裡需要注意，因為空格實際上對程式語言的語法來說是無關緊要的，這就是為什麼將 Javascript 程式碼壓縮之後仍然能夠正常執行。因此當我們識別到空格的時候，不需要將其放入 token 陣列進行下一步的操作。
實際上，在詞法分析這一步，類似空格、註釋、換行符這類不影響程式語法的 token 就不會送入下一步進行處理了。
因此，當我們識別到空格的時候，只需要繼續遍歷即可：
// 空格，不處理
if (WHITESPACE.test(char)) {
current++;
continue;
}
識別數位/變數/字串
我為什麼要把這三種 token 寫在一起呢？原因是從數位開始，這三種 token 的匹配邏輯都很相似，由於匹配的 token 可能不再是單個字元，因此需要在內部繼續迴圈直到匹配完整個 token 為止。
// 數位，迴圈獲取數值
if (NUMBERS.test(char)) {
let value = ""; // 匹配的數位賦初值
while (NUMBERS.test(char)) { // 遍歷，如果還能匹配就累加
value += char;
char = input[++current];
}
tokens.push({ type: "number", value }); // 壓入描述當前 token 的物件
continue;
}
// 變數，和 number 類似
if (LETTERS.test(char)) {
let value = "";
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
tokens.push({ type: "name", value });
continue;
}
// 字串，前後的 "" 需要跳過
if (char === '"') {
let value = "";
char = input[++current]; // 跳過前面的引號
while (char !== '"') { // 結束條件，匹配到末尾的引號
value += char;
char = input[++current];
}
char = input[++current]; // 跳過後面的引號
tokens.push({ type: "string", value });
continue;
}
其中需要注意，識別字串類似上面兩種，但是也有兩點不同：
- 在字串識別時需要跳過前後的引號，只匹配中間具體的值；
- 在中間進行遍歷的時候結束條件是匹配到末尾的引號。
有人可能會問，如果跳過的前後的引號以後要怎麼知道它是字串呢，這時候壓入陣列的 token 描述物件作用就出來了，它有一個 type 屬性可以指定當前 token 的型別。
小總結
至此，詞法分析的工作就做完了，其實相對來說還是很好懂的，那麼能不能直觀的觀察詞法分析輸出的 token 陣列是什麼樣子的呢？當然可以，只需要編寫一個樣例測試一下就行了，比如：
let source = "(add 2 (subtract 4 2))"; // 原始碼
let tokens = tokenizer(source);
console.log(tokens);
這是一個計算 2+(4-2) 的 Lisp 語句，將它作為輸入得到的 token 陣列如下所示：
[
{ "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": ")" }
]
這樣就完美的達到了我們開頭所說的將原始碼進行拆解的目的。
語法分析
接下來就是語法分析了，語法分析的作用是根據具體的程式語言語法來將上一步輸出的 token 陣列轉化為對應的 AST（抽象語法樹），既然涉及到樹結構，那麼這個步驟自然少不了遞迴操作。
整體框架
通用的，語法分析部分也需要先搭出一個框架。整體思路就是遍歷 token 陣列，遞迴地構建 AST 樹，框架如下：
function parser(tokens) {
let current = 0;
function walk() {
let token = tokens[current];
// 將不同的 token 轉化為 AST 節點
throw new TypeError(token.type);
}
let ast = {
// 此為 AST 樹最外層結構，是固定的
type: "Program",
body: [],
};
while (current < tokens.length) {
// 遍歷 token 陣列，構建樹結構
ast.body.push(walk());
}
return ast;
}
構建數位和字串節點
這兩種節點的構建較為簡單，直接返回描述節點的物件即可：
// 構建整數節點
if (token.type === "number") {
current++;
return {
type: "NumberLiteral",
value: token.value,
};
}
// 構建字串節點
if (token.type === "string") {
current++;
return {
type: "StringLiteral",
value: token.value,
};
}
構建函數呼叫節點
懂 Lisp 的人都知道，在 Lisp 中括號是精髓，比如函數呼叫類似於這種形式： (add 1 2)。因此我們需要以括號來進行識別，具體的程式碼如下：
if (token.type === "paren" && token.value === "(") {
// 左括號開始
token = tokens[++current]; // 跳過左括號
let node = {
// 函數呼叫節點
type: "CallExpression",
name: token.value,
params: [],
};
token = tokens[++current]; // 跳過 name
// 只要不是右括號，就遞迴收集引數節點
while (!(token.type === "paren" && token.value === ")")) {
node.params.push(walk()); // 新增引數
token = tokens[current];
}
current++; // 跳過右括號
return node;
}
這裡面需要注意的點是，某一個引數也可能是函數呼叫的結果，因此在解析引數時需要遞迴呼叫 walk 函數。
還有另外一點值得一提，那就是我們多次用到了這種程式碼結構：
if (value === "(") {
// ...
while (!value === ")") {
// ...
}
}
很明顯，這種結構就是適用於遍歷某個區間，因此我們在分析字串、括號這種配對元素時就需要使用這種結構。
小總結
就進行這樣簡單的幾個步驟，前面的 token 陣列就會被我們轉化成 AST 樹結構了，感覺還是非常的神奇，此時，我們的輸出以及程式設計瞭如下這樣：
{
"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"
}
]
}
]
}
]
}
遍歷並轉化 AST 樹
此時我們已經得到了一棵 AST 樹，編譯器之所以能夠將原始碼轉化為目的碼實際上就可以視作將源 AST 樹轉化為目標 AST 樹，要實現這種轉化過程，我們就需要對樹進行遍歷，然後對對應的節點進行操作。
遍歷樹
我們從上面可以看出，AST 樹中的 body 屬性和函數呼叫的引數實際上都是陣列型別的，因此我們首先需要定義對陣列型別的遍歷方法，很簡單，只需要遍歷陣列中的每個元素分別進行遍歷就行了：
// 存取（引數）陣列
function traverseArray(array, parent) {
array.forEach((child) => traverseNode(child, parent));
}
當遍歷到具體的節點時，我們就需要呼叫此節點型別的 enter 方法來進行存取（轉化 AST）操作，不同型別的節點 enter 方法是不一樣的。
function traverseNode(node, parent) {
let method = visitor[node.type]; // 去除當前型別的方法
if (method && method.enter) {
// 執行對應 enter 方法
method.enter(node, parent);
}
switch (
node.type // 對不同型別節點執行不同的遍歷操作
) {
case "Program":
traverseArray(node.body, node);
break;
case "CallExpression":
traverseArray(node.params, node);
break;
case "NumberLiteral":
case "StringLiteral":
break;
default:
throw new TypeError(node.type);
}
}
可能有人又要問，為什麼執行 enter 方法時第二個引數需要傳入父節點呢？這其實和後面的實際轉化部分的邏輯相關，我們就放到後面來進行解釋。
轉化 AST 樹
整體框架
一樣的，我們可以首先搭出大體的框架，具體的同型別的節點存取（轉化）方法後面再說。這裡的轉化思路就比較重要了：我們要如何在遍歷舊的 AST 樹時能將轉化後的節點加入新的 AST 樹？
這裡的實現思路大體分為以下幾步：
- 在舊的 AST 樹中加入一個
_context上下文屬性，指向新的 AST 樹的陣列節點 - 當遍歷舊 AST 陣列節點的子元素時，將轉化後的子元素放入它的父元素的
_context屬性中 - 根據 JavaScript 參照型別的特點，此時就實現了將轉化和的節點放入新 AST 樹的目的。
在圖中表示出來大概如下：
我相信這已經回答了上面執行 enter 方法時為什麼第二個引數需要傳入父節點的問題。
function transformer(ast) {
let newAst = {
// 新 AST 樹的最外層結構
type: "Program",
body: [],
};
// _context 用於遍歷舊子節點時壓入新 ast
ast._context = newAst.body;
let visitor = {
// 不同型別的節點存取（轉化）方法
};
traverser(ast, visitor); // 開始遍歷舊 AST 樹
return newAst;
}
數位和字串的轉化
{
NumberLiteral: {
enter(node, parent) {
parent._context.push({ // 壓入新 AST 樹
type: "NumberLiteral",
value: node.value,
});
},
},
StringLiteral: {
enter(node, parent) {
parent._context.push({
type: "StringLiteral",
value: node.value,
});
},
}
}
函數呼叫節點的轉化
函數呼叫節點特殊一點，由於它的引數可以視作它的子節點，因此需要將當前節點的 _context 屬性指向新 AST 樹對應的引數陣列。
還有一點特殊的是，如果當前的函數呼叫不是巢狀在別的函數呼叫中，那麼就可以再加一個 ExpressionStatement 資訊，表示當前節點是一整個語句，比如 (add 2 (subtract 4 2)) 內層的括號就不能稱作一個完整的語句，因為它是作為另一個函數的引數形式存在的。
{
CallExpression: {
enter(node, parent) {
let expression = { // 新 AST 樹的函數呼叫節點
type: "CallExpression",
callee: {
type: "Identifier",
name: node.name,
},
arguments: [],
};
node._context = expression.arguments; // 引數陣列處理
// 如果當前的函數呼叫不是巢狀在別的函數呼叫中
if (parent.type !== "CallExpression") {
expression = {
type: "ExpressionStatement",
expression: expression,
};
}
parent._context.push(expression);
},
},
}
小總結
截至目前，我們已經完成了 AST 樹的遍歷和轉化工作，這部分的工作量不小，但是也是整個編譯中最精華的部分，如果順利的話，我們現在可以得到如下轉化後的新 AST 樹：
{
"type": "Program",
"body": [
{
"type": "ExpressionStatement",
"expression": {
"type": "CallExpression",
"callee": {
"type": "Identifier",
"name": "add"
},
"arguments": [
{
"type": "NumberLiteral",
"value": "2"
},
{
"type": "CallExpression",
"callee": {
"type": "Identifier",
"name": "subtract"
},
"arguments": [
{
"type": "NumberLiteral",
"value": "4"
},
{
"type": "NumberLiteral",
"value": "2"
}
]
}
]
}
}
]
}
這就是對應 C 程式碼的 AST 樹的結構了，將它與之前 Lisp 的 AST 樹相比，還是可以看出很多不同的。
程式碼生成
最後，就是最激動人心的時刻了，生成目的碼！這一步相對輕鬆，根據上一步生成的 AST 樹，對它進行遞迴遍歷並生成最終的程式碼：
function codeGenerator(node) {
switch (node.type) {
case "Program":
return node.body.map(codeGenerator).join("\n");
case "ExpressionStatement":
return `${codeGenerator(node.expression)};`;
case "CallExpression": // 生成函數呼叫式
return `${codeGenerator(node.callee)}(${node.arguments
.map(codeGenerator)
.join(", ")})`;
case "Identifier": // 生成變數名
return node.name;
case "NumberLiteral":
return node.value; // 生成數位
case "StringLiteral":
return `"${node.value}"`; // 生成字串（別忘了兩邊的引號）
default:
throw new TypeError(node.type);
}
}
最終，我們實現了從 Lisp 的範例程式碼 (add 2 (subtract 4 2)) 到 C 語言程式碼 add(2, subtract(4, 2)) 的轉化。
大總結
本篇文章帶大家從零實現了一個編譯器最基本的功能，涉及了詞法分析、語法分析、AST 樹遍歷轉化等內容。編譯原理聽似高深（確實高深），但是基礎的部分就是那些內容，啥詞法分析語法分析的，最終都會迴歸到對字串的處理。
我研究的方向是前端，那別人可能認為平時可能都不會涉及到編譯原理的內容，但是實際上一旦深入研究的話，類似 Babel 將 ES6+ 的程式碼轉化為 ES5 之類的工作實際上都是編譯器做的工作，還有最近很火的 esbuild，只要涉及到程式碼的轉化，肯定都會涉及編譯，甚至 Vue 內部也有一個編譯器用於模板編譯。
說了這麼多，本意還是希望大家在平時的學習中要多多涉獵新領域的知識，擴充套件自己的技能面，這樣才能提高自己的技術視野和上限。
最後，推薦一個我最近在學習的最簡 Vue 模型專案，也可以在這裡面學習到 Vue 中模板編譯的原理。
（全文終）