用 JavaScript 寫一個超小型編譯器
前幾天看到 Github 上一個非常好的編譯器 Demo：
thejameskyle/the-super-tiny-compiler: Possibly the smallest compiler ever
雖然是一個很小很小的并沒有什么卵用的編譯器，但可以向我們展示編譯器的很多東西。
昨天和今天有空， 把它翻譯了出來 ，如果可以的話，建議直接去 這里 看代碼，Github上的閱讀體驗更好：
當然也可以看下面，不過知乎編輯器對于代碼的支持真是蛋疼。。。 用客戶端APP的同學請使用『瀏覽器打開』。
/**
* 今天讓我們來寫一個編譯器，一個超級無敵小的編譯器！它小到如果把所有注釋刪去的話，大概只剩
* 200行左右的代碼。
*
* 我們將會用它將 lisp 風格的函數調用轉換為 C 風格。
*
* 如果你對這兩種風格不是很熟悉，下面是一個簡單的介紹。
*
* 假設我們有兩個函數，`add` 和 `subtract`，那么它們的寫法將會是下面這樣：
*
* LISP C
*
* 2 + 2 (add 2 2) add(2, 2)
* 4 - 2 (subtract 4 2) subtract(4, 2)
* 2 + (4 - 2) (add 2 (subtract 4 2)) add(2, subtract(4, 2))
*
* 很簡單對吧？
*
* 這個轉換就是我們將要做的事情。雖然這并不包含 LISP 或者 C 的全部語法，但它足以向我們
* 展示現代編譯器很多要點。
*
*/
/**
* 大多數編譯器可以分成三個階段：解析（Parsing），轉換（Transformation）以及代碼
* 生成（Code Generation）
*
* 1. *解析*是將最初原始的代碼轉換為一種更加抽象的表示（譯者注：即AST）。*
*
* 2. *轉換*將對這個抽象的表示做一些處理，讓它能做到編譯器期望
* 它做到的事情。
*
* 3. *代碼生成*接收處理之后的代碼表示，然后把它轉換成新的代碼。
*/
/**
* 解析（Parsing）
* -------
*
* 解析一般來說會分成兩個階段：詞法分析（Lexical Analysis）和語法分析（Syntactic Analysis）。
*
* 1. *詞法分析*接收原始代碼，然后把它分割成一些被稱為 Token 的東西，這個過程是在詞法分析
* 器（Tokenizer或者Lexer）中完成的。
*
* Token 是一個數組，由一些代碼語句的碎片組成。它們可以是數字、標簽、標點符號、運算符，
* 或者其它任何東西。
*
* 2. *語法分析* 接收之前生成的 Token，把它們轉換成一種抽象的表示，這種抽象的表示描述了代
* 碼語句中的每一個片段以及它們之間的關系。這被稱為中間表示（intermediate representation）
* 或抽象語法樹（Abstract Syntax Tree， 縮寫為AST）
*
* 抽象語法樹是一個嵌套程度很深的對象，用一種更容易處理的方式代表了代碼本身，也能給我們
* 更多信息。
*
* 比如說對于下面這一行代碼語句：
*
* (add 2 (subtract 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: ')' }
* ]
*
* 它的抽象語法樹（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'
* }]
* }]
* }]
* }
*/
/**
* 轉換（Transformation）
* --------------
*
* 編譯器的下一步就是轉換。它只是把 AST 拿過來然后對它做一些修改。它可以在同種語言下操
* 作 AST，也可以把 AST 翻譯成全新的語言。
*
* 下面我們來看看該如何轉換 AST。
*
* 你或許注意到了我們的 AST 中有很多相似的元素，這些元素都有 type 屬性，它們被稱為 AST
* 結點。這些結點含有若干屬性，可以用于描述 AST 的部分信息。
*
* 比如下面是一個“NumberLiteral”結點：
*
* {
* type: 'NumberLiteral',
* value: '2'
* }
*
* 又比如下面是一個“CallExpression”結點：
*
* {
* type: 'CallExpression',
* name: 'subtract',
* params: [...nested nodes go here...]
* }
*
* 當轉換 AST 的時候我們可以添加、移動、替代這些結點，也可以根據現有的 AST 生成一個全新
* 的 AST
*
* 既然我們編譯器的目標是把輸入的代碼轉換為一種新的語言，所以我們將會著重于產生一個針對
* 新語言的全新的 AST。
*
*
* 遍歷（Traversal）
* ---------
*
* 為了能處理所有的結點，我們需要遍歷它們，使用的是深度優先遍歷。
*
* {
* 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'
* }]
* }]
* }]
* }
*
* So for the above AST we would go:
* 對于上面的 AST 的遍歷流程是這樣的：
*
* 1. Program - 從 AST 的頂部結點開始
* 2. CallExpression (add) - Program 的第一個子元素
* 3. NumberLiteral (2) - CallExpression (add) 的第一個子元素
* 4. CallExpression (subtract) - CallExpression (add) 的第二個子元素
* 5. NumberLiteral (4) - CallExpression (subtract) 的第一個子元素
* 6. NumberLiteral (4) - CallExpression (subtract) 的第二個子元素
*
* 如果我們直接在 AST 內部操作，而不是產生一個新的 AST，那么就要在這里介紹所有種類的抽象，
* 但是目前訪問（visiting）所有結點的方法已經足夠了。
*
* 使用“訪問（visiting）”這個詞的是因為這是一種模式，代表在對象結構內對元素進行操作。
*
* 訪問者（Visitors）
* --------
*
* 我們最基礎的想法是創建一個“訪問者（visitor）”對象，這個對象中包含一些方法，可以接收不
* 同的結點。
*
* var visitor = {
* NumberLiteral() {},
* CallExpression() {}
* };
*
* 當我們遍歷 AST 的時候，如果遇到了匹配 type 的結點，我們可以調用 visitor 中的方法。
*
* 一般情況下為了讓這些方法可用性更好，我們會把父結點也作為參數傳入。
*/
/**
* 代碼生成（Code Generation）
* ---------------
*
* 編譯器的最后一個階段是代碼生成，這個階段做的事情有時候會和轉換（transformation）重疊，
* 但是代碼生成最主要的部分還是根據 AST 來輸出代碼。
*
* 代碼生成有幾種不同的工作方式，有些編譯器將會重用之前生成的 token，有些會創建獨立的代碼
* 表示，以便于線性地輸出代碼。但是接下來我們還是著重于使用之前生成好的 AST。
*
* 我們的代碼生成器需要知道如何“打印”AST 中所有類型的結點，然后它會遞歸地調用自身，直到所
* 有代碼都被打印到一個很長的字符串中。
*
*/
/**
* 好了！這就是編譯器中所有的部分了。
*
* 當然不是說所有的編譯器都像我說的這樣。不同的編譯器有不同的目的，所以也可能需要不同的步驟。
*
* 但你現在應該對編譯器到底是個什么東西有個大概的認識了。
*
* 既然我全都解釋一遍了，你應該能寫一個屬于自己的編譯器了吧？
*
* 哈哈開個玩笑，接下來才是重點 :P
*
* 所以我們開始吧...
*/
/**
* =======================================================================
* (/^▽^)/
* 詞法分析器（Tokenizer）!
* =======================================================================
*/
/**
* 我們從第一個階段開始，即詞法分析，使用的是詞法分析器（Tokenizer）。
*
* 我們只是接收代碼組成的字符串，然后把它們分割成 token 組成的數組。
*
* (add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]
*/
// 我們從接收一個字符串開始，首先設置兩個變量。
function tokenizer(input) {
// `current`變量類似指針，用于記錄我們在代碼字符串中的位置。
var current = 0;
// `tokens`數組是我們放置 token 的地方
var tokens = [];
// 首先我們創建一個 `while` 循環， `current` 變量會在循環中自增。
//
// 我們這么做的原因是，由于 token 數組的長度是任意的，所以可能要在單個循環中多次
// 增加 `current`
while (current < input.length) {
// 我們在這里儲存了 `input` 中的當前字符
var char = input[current];
// 要做的第一件事情就是檢查是不是右圓括號。這在之后將會用在 `CallExpressions` 中，
// 但是現在我們關心的只是字符本身。
//
// 檢查一下是不是一個左圓括號。
if (char === '(') {
// 如果是，那么我們 push 一個 type 為 `paren`，value 為左圓括號的對象。
tokens.push({
type: 'paren',
value: '('
});
// 自增 `current`
current++;
// 結束本次循環，進入下一次循環
continue;
}
// 然后我們檢查是不是一個右圓括號。這里做的時候和之前一樣：檢查右圓括號、加入新的 token、
// 自增 `current`，然后進入下一次循環。
if (char === ')') {
tokens.push({
type: 'paren',
value: ')'
});
current++;
continue;
}
// 繼續，我們現在檢查是不是空格。有趣的是，我們想要空格的本意是分隔字符，但這現在
// 對于我們儲存 token 來說不那么重要。我們暫且擱置它。
//
// 所以我們只是簡單地檢查是不是空格，如果是，那么我們直接進入下一個循環。
var WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
// 下一個 token 的類型是數字。它和之前的 token 不同，因為數字可以由多個數字字符組成，
// 但是我們只能把它們識別為一個 token。
//
// (add 123 456)
// ^^^ ^^^
// Only two separate tokens
// 這里只有兩個 token
//
// 當我們遇到一個數字字符時，將會從這里開始。
var NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {
// 創建一個 `value` 字符串，用于 push 字符。
var value = '';
// 然后我們循環遍歷接下來的字符，直到我們遇到的字符不再是數字字符為止，把遇到的每
// 一個數字字符 push 進 `value` 中，然后自增 `current`。
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}
// 然后我們把類型為 `number` 的 token 放入 `tokens` 數組中。
tokens.push({
type: 'number',
value: value
});
// 進入下一次循環。
continue;
}
// 最后一種類型的 token 是 `name`。它由一系列的字母組成，這在我們的 lisp 語法中
// 代表了函數。
//
// (add 2 4)
// ^^^
// Name token
//
var LETTERS = /[a-z]/i;
if (LETTERS.test(char)) {
var value = '';
// 同樣，我們用一個循環遍歷所有的字母，把它們存入 value 中。
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
// 然后添加一個類型為 `name` 的 token，然后進入下一次循環。
tokens.push({
type: 'name',
value: value
});
continue;
}
// 最后如果我們沒有匹配上任何類型的 token，那么我們拋出一個錯誤。
throw new TypeError('I dont know what this character is: ' + char);
}
// 詞法分析器的最后我們返回 tokens 數組。
return tokens;
}
/**
* =======================================================================
* ヽ/?o ? o\?
* 語法分析器（Parser）!!!
* =======================================================================
*/
/**
* 語法分析器接受 token 數組，然后把它轉化為 AST
*
* [{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }
*/
// 現在我們定義 parser 函數，接受 `tokens` 數組
function parser(tokens) {
// 我們再次聲明一個 `current` 變量作為指針。
var current = 0;
// 但是這次我們使用遞歸而不是 `while` 循環，所以我們定義一個 `walk` 函數。
function walk() {
// walk函數里，我們從當前token開始
var token = tokens[current];
// 對于不同類型的結點，對應的處理方法也不同，我們從 `number` 類型的 token 開始。
// 檢查是不是 `number` 類型
if (token.type === 'number') {
// 如果是，`current` 自增。
current++;
// 然后我們會返回一個新的 AST 結點 `NumberLiteral`，并且把它的值設為 token 的值。
return {
type: 'NumberLiteral',
value: token.value
};
}
// 接下來我們檢查是不是 CallExpressions 類型，我們從左圓括號開始。
if (
token.type === 'paren' &&
token.value === '('
) {
// 我們會自增 `current` 來跳過這個括號，因為括號在 AST 中是不重要的。
token = tokens[++current];
// 我們創建一個類型為 `CallExpression` 的根節點，然后把它的 name 屬性設置為當前
// token 的值，因為緊跟在左圓括號后面的 token 一定是調用的函數的名字。
var node = {
type: 'CallExpression',
name: token.value,
params: []
};
// 我們再次自增 `current` 變量，跳過當前的 token
token = tokens[++current];
// 現在我們循環遍歷接下來的每一個 token，直到我們遇到右圓括號，這些 token 將會
// 是 `CallExpression` 的 `params`（參數）
//
// 這也是遞歸開始的地方，我們采用遞歸的方式來解決問題，而不是去嘗試解析一個可能有無限
// 層嵌套的結點。
//
// 為了更好地解釋，我們來看看我們的 Lisp 代碼。你會注意到 `add` 函數的參數有兩個，
// 一個是數字，另一個是一個嵌套的 `CallExpression`，這個 `CallExpression` 中
// 包含了它自己的參數（兩個數字）
//
// (add 2 (subtract 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` 時，我們將會依賴嵌套的 `walk` 函數來
// 增加 `current` 變量
//
// 所以我們創建一個 `while` 循環，直到遇到類型為 `'paren'`，值為右圓括號的 token。
while (
(token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// 我們調用 `walk` 函數，它將會返回一個結點，然后我們把這個節點
// 放入 `node.params` 中。
node.params.push(walk());
token = tokens[current];
}
// 我們最后一次增加 `current`，跳過右圓括號。
current++;
// 返回結點。
return node;
}
// 同樣，如果我們遇到了一個類型未知的結點，就拋出一個錯誤。
throw new TypeError(token.type);
}
// 現在，我們創建 AST，根結點是一個類型為 `Program` 的結點。
var ast = {
type: 'Program',
body: []
};
// 現在我們開始 `walk` 函數，把結點放入 `ast.body` 中。
//
// 之所以在一個循環中處理，是因為我們的程序可能在 `CallExpressions` 后面包含連續的兩個
// 參數，而不是嵌套的。
//
// (add 2 2)
// (subtract 4 2)
//
while (current < tokens.length) {
ast.body.push(walk());
}
// 最后我們的語法分析器返回 AST
return ast;
}
/**
* =======================================================================
* ⌒(?>???<?)⌒
* 遍歷器!!!
* =======================================================================
*/
/**
* 現在我們有了 AST，我們需要一個 visitor 去遍歷所有的結點。當遇到某個類型的結點時，我們
* 需要調用 visitor 中對應類型的處理函數。
*
* traverse(ast, {
* Program(node, parent) {
* // ...
* },
*
* CallExpression(node, parent) {
* // ...
* },
*
* NumberLiteral(node, parent) {
* // ...
* }
* });
*/
// 所以我們定義一個遍歷器，它有兩個參數，AST 和 vistor。在它的里面我們又定義了兩個函數...
function traverser(ast, visitor) {
// `traverseArray` 函數允許我們對數組中的每一個元素調用 `traverseNode` 函數。
function traverseArray(array, parent) {
array.forEach(function(child) {
traverseNode(child, parent);
});
}
// `traverseNode` 函數接受一個 `node` 和它的父結點 `parent` 作為參數，這個結點會被
// 傳入到 visitor 中相應的處理函數那里。
function traverseNode(node, parent) {
// 首先我們看看 visitor 中有沒有對應 `type` 的處理函數。
var method = visitor[node.type];
// 如果有，那么我們把 `node` 和 `parent` 都傳入其中。
if (method) {
method(node, parent);
}
// 下面我們對每一個不同類型的結點分開處理。
switch (node.type) {
// 我們從頂層的 `Program` 開始，Program 結點中有一個 body 屬性，它是一個由若干
// 個結點組成的數組，所以我們對這個數組調用 `traverseArray`。
//
// （記住 `traverseArray` 會調用 `traverseNode`，所以我們會遞歸地遍歷這棵樹。）
case 'Program':
traverseArray(node.body, node);
break;
// 下面我們對 `CallExpressions` 做同樣的事情，遍歷它的 `params`。
case 'CallExpression':
traverseArray(node.params, node);
break;
// 如果是 `NumberLiterals`，那么就沒有任何子結點了，所以我們直接 break
case 'NumberLiteral':
break;
// 同樣，如果我們不能識別當前的結點，那么就拋出一個錯誤。
default:
throw new TypeError(node.type);
}
}
// 最后我們對 AST 調用 `traverseNode`，開始遍歷。注意 AST 并沒有父結點。
traverseNode(ast, null);
}
/**
* =======================================================================
* ?(??????????)?
* 轉換器!!!
* =======================================================================
*/
/**
* 下面是轉換器。轉換器接收我們在之前構建好的 AST，然后把它和 visitor 傳遞進入我們的遍歷
* 器中 ，最后得到一個新的 AST。
*
* ----------------------------------------------------------------------------
* 原始的 AST | 轉換后的 AST
* ----------------------------------------------------------------------------
* { | {
* type: 'Program', | type: 'Program',
* body: [{ | body: [{
* type: 'CallExpression', | type: 'ExpressionStatement',
* name: 'add', | expression: {
* params: [{ | type: 'CallExpression',
* type: 'NumberLiteral', | callee: {
* value: '2' | type: 'Identifier',
* }, { | name: 'add'
* type: 'CallExpression', | },
* name: 'subtract', | arguments: [{
* params: [{ | type: 'NumberLiteral',
* type: 'NumberLiteral', | value: '2'
* value: '4' | }, {
* }, { | type: 'CallExpression',
* type: 'NumberLiteral', | callee: {
* value: '2' | type: 'Identifier',
* }] | name: 'subtract'
* }] | },
* }] | arguments: [{
* } | type: 'NumberLiteral',
* | value: '4'
* ---------------------------------- | }, {
* | type: 'NumberLiteral',
* | value: '2'
* | }]
* (那一邊比較長/w\) | }]
* | }
* | }]
* | }
* ----------------------------------------------------------------------------
*/
// 定義我們的轉換器函數，接收 AST 作為參數
function transformer(ast) {
// 創建 `newAST`，它與我們之前的 AST 類似，有一個類型為 Program 的根節點。
var newAst = {
type: 'Program',
body: []
};
// 下面的代碼會有些奇技淫巧，我們在父結點上使用一個屬性 `context`（上下文），這樣我們就
// 可以把結點放入他們父結點的 context 中。當然可能會有更好的做法，但是為了簡單我們姑且
// 這么做吧。
//
// 注意 context 是一個*引用*，從舊的 AST 到新的 AST。
ast._context = newAst.body;
// 我們把 AST 和 visitor 函數傳入遍歷器
traverser(ast, {
// 第一個 visitor 方法接收 `NumberLiterals`。
NumberLiteral: function(node, parent) {
// 我們創建一個新結點，名字叫 `NumberLiteral`，并把它放入父結點的 context 中。
parent._context.push({
type: 'NumberLiteral',
value: node.value
});
},
// 下一個，`CallExpressions`。
CallExpression: function(node, parent) {
// 我們創建一個 `CallExpression` 結點，里面有一個嵌套的 `Identifier`。
var expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name
},
arguments: []
};
// 下面我們在原來的 `CallExpression` 結點上定義一個新的 context，它是 expression
// 中 arguments 這個數組的引用，我們可以向其中放入參數。
node._context = expression.arguments;
// 然后來看看父結點是不是一個 `CallExpression`，如果不是...
if (parent.type !== 'CallExpression') {
// 我們把 `CallExpression` 結點包在一個 `ExpressionStatement` 中，這么做是因為
// 單獨存在（原文為top level）的 `CallExpressions` 在 JavaScript 中也可以被當做
// 是聲明語句。
//
// 譯者注：比如 `var a = foo()` 與 `foo()`，后者既可以當作表達式給某個變量賦值，也
// 可以作為一個獨立的語句存在。
expression = {
type: 'ExpressionStatement',
expression: expression
};
}
// 最后我們把 `CallExpression`（可能是被包起來的） 放入父結點的 context 中。
parent._context.push(expression);
}
});
// 最后返回創建好的新 AST。
return newAst;
}
/**
* =======================================================================
* ヾ（〃＾?＾）??
* 代碼生成器!!!!
* =======================================================================
*/
/**
* 現在只剩最后一步啦：代碼生成器。
*
* 我們的代碼生成器會遞歸地調用它自己，把 AST 中的每個結點打印到一個很大的字符串中。
*/
function codeGenerator(node) {
// 對于不同 `type` 的結點分開處理。
switch (node.type) {
// 如果是 `Program` 結點，那么我們會遍歷它的 `body` 屬性中的每一個結點，并且遞歸地
// 對這些結點再次調用 codeGenerator，再把結果打印進入新的一行中。
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
// 對于 `ExpressionStatements`,我們對它的 expression 屬性遞歸調用，同時加入一個
// 分號。
case 'ExpressionStatement':
return (
codeGenerator(node.expression) +
';' // << (...因為我們喜歡用*正確*的方式寫代碼)
);
// 對于 `CallExpressions`，我們會打印出 `callee`，接著是一個左圓括號，然后對
// arguments 遞歸調用 codeGenerator，并且在它們之間加一個逗號，最后加上右圓括號。
case 'CallExpression':
return (
codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator)
.join(', ') +
')'
);
// 對于 `Identifiers` 我們只是返回 `node` 的 name。
case 'Identifier':
return node.name;
// 對于 `NumberLiterals` 我們只是返回 `node` 的 value
case 'NumberLiteral':
return node.value;
// 如果我們不能識別這個結點，那么拋出一個錯誤。
default:
throw new TypeError(node.type);
}
}
/**
* ============================================================================
* ( * ‘ヮ’) ”
* !!!!!!!!!!!!編譯器!!!!!!!!!!!
* ============================================================================
*/
/**
* 最后！我們創建 `compiler` 函數，它只是把上面說到的那些函數連接到一起。
*
* 1. input => tokenizer => tokens
* 2. tokens => parser => ast
* 3. ast => transformer => newAst
* 4. newAst => generator => output
*/
function compiler(input) {
var tokens = tokenizer(input);
var ast = parser(tokens);
var newAst = transformer(ast);
var output = codeGenerator(newAst);
// 然后返回輸出!
return output;
}
/**
* =======================================================================
* (??????)
* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!你做到了!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
* =======================================================================
*/
// 現在導出所有接口...
module.exports = {
tokenizer: tokenizer,
parser: parser,
transformer: transformer,
codeGenerator: codeGenerator,
compiler: compiler
};
來自：https://zhuanlan.zhihu.com/p/21830284
本文由用戶 DixieBeck 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！