基于 js 實(shí)現(xiàn)一個(gè)小型編譯器
本文內(nèi)容基于?https://github.com/jamiebuilds/the-super-tiny-compiler?倉庫源碼進(jìn)行學(xué)習(xí)
最近在研究一些構(gòu)建側(cè)的東西，在翻 babel 官網(wǎng)的時(shí)候看到了這樣一段話:
For an awesome tutorial on compilers, check out?the-super-tiny-compiler, which also explains how Babel itself works on a high level.
出于學(xué)習(xí)的心態(tài)，去翻了一下這個(gè)倉庫源碼，以下是筆者的一些學(xué)習(xí)的記錄，希望看完之后能對你理解 babel 的工作原理有一些幫助~
前言
the-super-tiny-compiler是一個(gè)代碼行數(shù)只有不到 200 行的超級小型的 compiler，但通過這個(gè) compiler 能學(xué)習(xí)到最基礎(chǔ)的 compile 原理，包括 babel 也是基于這樣的原理來進(jìn)行開發(fā)的。
倉庫本身的例子是將一組 lisp 風(fēng)格的函數(shù)語法編譯成了 C 風(fēng)格的函數(shù)語法，舉例子來說:
| LISP 風(fēng)格 | C 風(fēng)格 | |
|---|---|---|
| 2+2 | (add 2 2) | add(2,2) |
| 4-2 | (subtract 4 2) | substract(4, 2) |
| 2 + (4 - 2) | (add 2 (substract 4 2)) | add(2, (substract(4, 2))) |
這就大概是這次 compiler 需要完成的事情，可能看上去語法不是很完整，但是也能夠演示現(xiàn)代編譯器的主要部分思想了。
大多數(shù)的 Compilers 都會把編譯過程分成三個(gè)主要的過程: parse、transform 以及 code generate：
parse 主要是將源碼轉(zhuǎn)換成一種更抽象的代碼表達(dá)
transform 則是將上面抽象的表達(dá)進(jìn)行任意 compiler 想進(jìn)行的操作
code generate 將 transform 處理之后的代碼生成一種新的代碼
Parse
parse 主要分為兩個(gè)步驟: 詞法分析以及語法分析。
詞法分析將源碼根據(jù)表達(dá)切分一個(gè)個(gè)的 tokens，tokens 是一組用來描述單獨(dú)語法的對象，可以是 numbers、labels、punctuation、operators 等
語法分析則是將詞法分析生成的 tokens 進(jìn)行重新編排得到一個(gè)叫做抽象語法樹(AST)的結(jié)構(gòu)，AST 是一種易于使用且能展示完整信息的嵌套樹狀結(jié)構(gòu)。
例如前面提到的?add 2 (subtract 4 2)表達(dá)式被詞法分析處理之后生成的 tokens 大概是:
[
{ 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: ')' }
]
語法分析處理出來的 AST 結(jié)構(gòu)為:
{
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',
}
]
}]
}]
}Transform
transform 主要就是拿到 parse 得到的抽象語法樹，并基于此做出一些修改。tranform 這個(gè)過程既可以基于當(dāng)前語言的風(fēng)格去修改 ast 也可以使用一種新的語言風(fēng)格。
下面基于前面的 ast 結(jié)構(gòu)來展示 transform 這個(gè)過程的工作流程。
可以看到，ast 里面的元素看起來都很相似，這些元素組成了 ast 的子結(jié)點(diǎn)，這些子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)類型描述了代碼中的一個(gè)單獨(dú)的部分(例如變量、聲明語句，表達(dá)式等等)。
例如上面提到的類型是?NumberLiteral的節(jié)點(diǎn):
{
type: 'NumberLiteral',
value: '2',
}
或者更復(fù)雜一點(diǎn)的子節(jié)點(diǎn)類型:
{
type: 'CallExpression',
name: 'substract',
params: [...nested nodes here ...],
}
在 transfrom 這個(gè)過程中，我們可以通過增/刪/改來操作抽象語法樹結(jié)點(diǎn)，或者可以直接基于當(dāng)前的抽象語法樹創(chuàng)建一個(gè)新的出來。
既然這里我們的目標(biāo)是將輸入的代碼轉(zhuǎn)換成一種新的語言風(fēng)格的代碼(Lisp -> C)，所以這里會創(chuàng)建一個(gè)針對新語言的全新 AST 出來。
因此這里我們需要明確一下修改 AST 的操作:
Traversal(遍歷)
為了能處理所有的結(jié)點(diǎn)，我們可以用深度優(yōu)先搜索對其進(jìn)行遍歷:
{
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'
}]
}]
}]
}
遍歷流程是這樣的:
Program - 從 AST 的頂結(jié)點(diǎn)開始
CallExpression (add) - Program 的第一個(gè)子元素
NumberLiteral (2) - CallExpression (add) 的第一個(gè)子元素
CallExpression (subtract) - CallExpression (add) 的第二個(gè)子元素
NumberLiteral (4) - CallExpression (subtract) 的第一個(gè)子元素
NumberLiteral (2) - CallExpression (subtract) 的第二個(gè)子元素
如果直接在 ast 內(nèi)部操作而不是產(chǎn)生一個(gè)新的 ast，可能就需要介紹所有的種類的抽象。但目前來看，訪問所有結(jié)點(diǎn)的方法已經(jīng)足夠了。
訪問(visiting) 這個(gè)詞代表一種在對象結(jié)構(gòu)內(nèi)對元素進(jìn)行操作的模式。
Visitors(訪問)
這里我們可以創(chuàng)建一個(gè) visitor 對象，這個(gè)對象包括一些方法用于接收不同的結(jié)點(diǎn)。
例如:
var visitor = {
NumberLiteral() {},
CallExpression() {}
};
因此當(dāng)我們遍歷 ast 的時(shí)候，如果匹配到了對應(yīng) type 的結(jié)點(diǎn)，可以調(diào)用 visitor 中的方法來處理。
Code generate
Compiler 的最后一個(gè)階段就是 generate, 這個(gè)階段做的事情可能會和 transformation 重疊，但是代碼生成最主要的部分還是根據(jù) AST 來輸出代碼。
Generate 有幾種不同的工作方式，有些 Compilers 會重用之前生成的 token，有些則會創(chuàng)建獨(dú)立的代碼表示，以便于線性輸出代碼，但接下來我們還是著重于使用之前生成好的 AST。
我們的生成器需要知道如何打印 AST 中的所有類型結(jié)點(diǎn)，然后遞歸調(diào)用自身，知道所有的代碼都被打印到一個(gè)很長的字符串中。
代碼實(shí)現(xiàn)
以上就是 Compiler 所有的部分了，但并不是所有的 Compiler 都是這樣，不同的 compiler 目的不同，所以也可能需要不同的步驟。
接下來就開始代碼的編寫:
詞法分析器(tokenizer)
按照前面的理論分析，我們一步先進(jìn)行 parser 這個(gè)階段里面的詞法分析器(tokenizer)。
這個(gè)函數(shù)接收一個(gè)字符串，然后將其分割成由 token 組成的數(shù)組:
ex:(add 2 (substract 4 2))?=>[{ type: 'paren', value: '('}, ...]
因此可以編寫這樣的一個(gè)函數(shù):
const tokenizer = (input) => {
const tokens = [];
let current = 0;
while (current < input.length) {
let char = input[current];
if (char === '(') {
tokens.push({
type: 'paren',
value: '(',
})
current++;
continue;
}
if (char === ')') {
tokens.push({
type: 'paren',
value: ')',
})
current ++;
continue;
}
// 空格目前不需要處理
if (/\s/.test(char)) {
current++;
continue;
}
// 處理數(shù)字
if (/[0-9]/.test(char)) {
let value = '';
// 一直遍歷直到遇到非數(shù)字的字符
while (/[0-9]/.test(char)) {
value += char;
char = input[++current];
}
tokens.push({
type: 'number',
value,
})
continue;
}
// 處理字符串
if(/[a-z]/i.test(char)) {
let value = '';
while(/[a-z]/i.test(char)) {
value += char;
char = input[++current];
}
tokens.push({
type: 'name',
value,
});
continue;
}
// 如果存在匹配不上的 token 就拋錯
throw new Error(`Unknown token: ${char}`);
}
return tokens;
}
語法分析器(parser)
詞法分析器接收語法分析得到的 token 數(shù)組，然后將其轉(zhuǎn)換成 AST 結(jié)構(gòu)。
例如:[{ type: 'paren', value: '(' }, ...]?=>?{ type: 'Program', body: [...] }
const parser = (tokens) => {
let current = 0;
const walk = () => {
const token = tokens[current];
// 如果是 number 類型的結(jié)點(diǎn)，返回一個(gè)新的 ast 節(jié)點(diǎn)即可
if (token.type === 'number') {
current++;
return {
type: 'NumberLiteral',
value: token.value,
}
}
// 接下來檢查 CallExpression 類型，先從左圓括號開始
if (
token.type === 'paren' &&
token.value === '('
) {
// 跳過左圓括號
token = tokens[++current];
// 首先會創(chuàng)建一個(gè) CallExpression 的根節(jié)點(diǎn)，然后 name 設(shè)置成當(dāng)前的 token.value
// 因?yàn)樽髨A括號后的 token 一定是函數(shù)名稱
const node = {
type: 'CallExpression',
name: token.value,
params: [],
};
// 這里再跳一次函數(shù)名稱
token = tokens[++current];
// 通過循環(huán)遍歷接下來的每個(gè) token，直到遇到右圓括號
// 這些 token 會成為 `CallExpression` 的 `params`
// 以 lisp 風(fēng)格的代碼來說: (add 2 (substract 4 2))
/**
* 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: ')' } <<< 右圓括號
]
遇到嵌套的 CallExpressions 的時(shí)候，會通過 walk 函數(shù)來處理
*
*/
while (
token.type !== 'paren' ||
(token.value !== ')' && token.type === 'paren')
) {
node.params.push(walk());
token = tokens[current];
}
current++;
return node;
}
throw new Error(`Unknown token type: ${token.type}`);
}
const ast = {
type: 'Program',
body: [],
}
/**
* 使用遞歸函數(shù)將結(jié)點(diǎn)處理進(jìn) ast.body 中
*/
while (current < tokens.length) {
ast.body.push(walk());
}
return ast;
}遍歷器(visitors)
通過語法分析得到 ast 之后，接下來需要一個(gè)遍歷器 (visitors) 去遍歷結(jié)點(diǎn)。然后當(dāng)遇到某個(gè)類型的結(jié)點(diǎn)的時(shí)候，可以調(diào)用 visitors 中對應(yīng)的類型處理函數(shù):
traverse(ast, {
Program(node, parent) {
// ...
},
CallExpression(node, parent) {
// ...
},
NumberLiteral(node, parent) {
// ...
},
});
因此我們的代碼可以這樣寫:
const traverser = (ast, visitor) => {
// 用于對數(shù)組中的每個(gè)元素都調(diào)用 traverseNode 函數(shù)
const traverseArray = (array, parent) => {
array.forEach((child) => {
traverseNode(child, parent);
});
}
// 函數(shù)接收一個(gè) node 以及其父結(jié)點(diǎn)作為參數(shù)
// 這個(gè)結(jié)點(diǎn)會被傳入到 visitor 中相應(yīng)的處理函數(shù)那里
const traverseNode = (node, parent) => {
const method = visitor[node.type];
if (method) {
method(node, parent);
}
// 對不同的結(jié)點(diǎn)分開處理
switch (node.type) {
case 'Program':
traverseArray(node.body, node);
break;
case 'CallExpression':
traverseArray(node.params, node);
break;
// 這種情況下就沒有子節(jié)點(diǎn)了，直接 break 出去
case 'NumberLiteral':
break;
default:
throw new Error(`Unknown node type: ${node.type}`);
}
}
traverseNode(ast, null);
}轉(zhuǎn)換器(transformer)
轉(zhuǎn)換器配合上面的遍歷器來一起使用，它接收之前構(gòu)建好的 ast，然后將其和 visitor 一起傳入遍歷器中，從而得到一個(gè)全新的 AST 出來。
原始的 AST 結(jié)構(gòu)為(add 2 (subtract 4 2)):
{
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'
}]
}]
}]
}
轉(zhuǎn)換之后生成的 AST 結(jié)構(gòu)為(add(2, subtract(4, 2))):
{
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',
}]
}]
}
}
}
接下來我們可以這樣編寫對應(yīng)的轉(zhuǎn)換器代碼:
const transformer = (ast) => {
const newAst = {
type: 'Program',
body: [],
}
ast._context = newAst.body;
traverser(ast, {
// 處理 NumberLiteral 類型
NumberLiteral: (node, parent) => {
parent._context.push({
type: 'NumberLiteral',
value: node.value,
});
},
// 處理 CallExpression 類型
CallExpression: (node, parent) => {
// 初始化一個(gè) CallExpression 的新節(jié)點(diǎn)
// 里面放個(gè)嵌套的 Identifier 節(jié)點(diǎn)
const expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name
},
arguments: [],
};
node._context = expression.arguments;
// 看看父節(jié)點(diǎn)是不是 CallExpression
if (parent.type !== 'CallExpression') {
// 如果不是的話，就將 CallExpression 節(jié)點(diǎn)包在一個(gè)叫 `ExpressionStatement` 的語句節(jié)點(diǎn)里
// 這么做是因?yàn)?top level 的 CallExpression 在 JavaScript 中也可以被當(dāng)成是聲明語句
expression = {
type: 'ExpressionStatement',
expression,
};
}
// 最后我們把 CallExpression 放入父結(jié)點(diǎn)的 context 中
parent._context.push(expression);
}
});
return newAst;
}代碼生成器(code generator)
代碼生成器同樣是個(gè)遞歸函數(shù)，最后會將 AST 中的每個(gè)結(jié)點(diǎn)打印到一個(gè)大的字符串中:
const codeGenerator = (node) => {
switch (node.type) {
// 如果是 Program，則會遍歷 'body' 屬性中的每個(gè)結(jié)點(diǎn)
// 并且對這些結(jié)點(diǎn)進(jìn)行遞歸 codeGenerator,再把結(jié)果打印進(jìn)新的一行里面
case 'Program':
return node.body.map(codeGenerator).join('\n');
// 對于 ExpressionStatement 對 expression 屬性進(jìn)行遞歸調(diào)用，并加個(gè)分號
case 'ExpressionStatement':
return `${codeGenerator(node.expression)};`;
// 對于 CallExpression 對 callee 屬性進(jìn)行遞歸調(diào)用，接著加上(括號
// 然后對 arguments 屬性進(jìn)行遞歸調(diào)用，并加上)括號
case 'CallExpression':
return `${codeGenerator(node.callee)}(${node.arguments.map(codeGenerator).join(', ')})`;
// 對于 Identifier,直接返回 name
case 'Identifier':
return node.name;
// 對于 NumberLiteral,直接返回 value
case 'NumberLiteral':
return node.value;
default:
throw new Error(`Unknown node type: ${node.type}`);
}
}編譯器(Compiler)
到這一步，基本上所有的流程就已經(jīng)完成了，我們可以創(chuàng)建一個(gè) compiler 函數(shù)，通過調(diào)用上面的函數(shù)就可以完成整個(gè) compiler 的工作了:
input => tokenizer => tokens
tokens => parser => ast
ast => transformer => newAst
newAst => generator => output
代碼只需要以下簡單幾步即可:
const compiler = (input) => {
const tokens = tokenizer(input);
const ast = parser(tokens);
const newAst = transformer(ast);
return codeGenerator(newAst);
}
我們可以輸入前面的幾組測試?yán)?，能保證得到的結(jié)果是正確的。
總結(jié)
至此一個(gè) tiny-compiler 就被造出來了，babel 的編譯流程也是基于此來完成，因?yàn)?babel 本身是個(gè) source to source 的 compiler，整個(gè)流程也是分為 parser -> transform -> code generate 這三個(gè)步驟完成，具體可以參考?https://babeljs.io/docs/en/#babel-is-a-javascript-compiler
希望本文能幫助讀者理解相關(guān)編譯工具的編譯流程。