點擊上方「CSDN」，選擇「置頂公眾號」
關鍵時刻，第一時間送達！
作者丨Minko Gechev
譯者丨夜風輕揚
譯者註：即使對於專業程式設計師來說，構造一個編譯器也是頗具挑戰性的任務，本文將會引導你抽絲剝繭，一探究竟！
我已經寫了幾篇與程式語言開發相關的文章，這讓我非常興奮！例如，在「關於 Angular 2 和 TypeScript 項目中的靜態代碼分析」[1]中，我研究了編譯器前端的基本知識，解釋了詞法分析、語法分析和抽象語法樹等各個階段。
最近我發表了「開發靜態類型程式語言[2] 」。本文展示了一個簡單的、靜態類型的函數式程式語言，它是受到了lambda微積分的啟發。我將編譯器開發的前端部分外包給了解析器生成器，並將注意力放在用於類型檢查的模塊的後端，以及用於代碼生成的模塊。
為什麼我需要這個？
你可能想「為什麼我需要知道如何開發編譯器?」，有幾個重要的原因:
你將更好地理解所使用的程式語言是如何工作的。這將使你能夠藉助該語言開發出更高效的程序。
經常的，為了不同的目的，你不得不重用下面所述的模塊(例如，對配置文件進行解析、對網絡消息進行解析等等)。
創建一個DSL。在你的項目中創建一個特定領域的語言可能非常方便，以便簡化任務，否則，使用通用程式語言，解決同樣問題，你可能需要花費更多的時間。
我們要討論的範圍是什麼？
在這篇博文中，我們將介紹從端到端的基礎知識。我們將用25行JavaScript代碼開發一個非常簡單的編譯器！我們的編譯器將會包含:
詞法分析模塊
語法分析模塊
解析器將基於EBNF語法
我們將使用遞歸下行解析算法來開發解析器
代碼生成器
我們將要探討的語言對於開發有實際意義的軟體程序並不是特別有用，但是它可以很容易地擴展成一個。
整個實現可以在我的GitHub介紹[3]中找到。
引入一種簡單的前綴語言
下面是我們語言中的一個示例表達式的樣子:
mul 3 sub 2 sum 1 3 4
在本文的最後，我們將能經過任何編譯器的典型階段，將這些表達式轉換為JavaScript語句。
為簡單起見，我們需要遵循一些規則:
我們只有函數:mul，sub，sum，div。
每個字符串標記都被空格隔開。
我們只支持自然數。
為了探究上述表達式背後的語義，我們定義一些JavaScript函數:
const mul = (...operands) => operands.reduce((a, c) => a * c, 1);
const sub = (...operands) => operands.reduce((a, c) => a - c);
const sum = (...operands) => operands.reduce((a, c) => a + c, 0);
mul接受多個操作數，並通過 =>操作符傳遞。函數只是將它們相乘，例如mul(2、3、4)==24。sub分別減去傳遞的參數,sum則是計算參數的總和。
上述的表達式可以轉換為下列的JavaScript表達式：
mul(3, sub(2, sum(1, 3, 4)))
或者
3 * (2 - (1 + 3 + 4))
現在，在我們了解了語義之後，讓我們從編譯器的前端開始吧！
注意：類似的前綴表達式可以通過基於堆棧的算法進行簡單的評估，但是在這種情況下，我們將關注概念而不是實現。
開發編譯器的前端
任何編譯器的前端通常都有詞法分析模塊[4]和語法分析模塊[5]。在這一節中，我們將在幾行JavaScript代碼中構建兩個模塊！
開發一個詞法分析器
詞法分析階段負責將程序的輸入字符串(或字符流)劃分為稱為標記的小塊。標記通常包含關於它們類型的信息(如果它們是數字、操作符、關鍵字、標識符等)、它們所代表程序的子串以及它們在程序中的位置。該位置通常用於報告用戶友好的錯誤，以防出現無效的語法結構。
例如下列的JavaScript程序:
if (foo) {
bar();
}
一個示例的JavaScript詞彙分析器將生成輸出:
[
{
lexeme: 'if',
type: 'keyword',
position: {
row: 0,
col: 0
}
},
{
lexeme: '(',
type: 'open_paran',
position: {
row: 0,
col: 3
}
},
{
lexeme: 'foo',
type: 'identifier',
position: {
row: 0,
col: 4
}
},
...
]
我們將保持我們的詞法分析器儘可能簡單。事實上，我們可以通過一條 JavaScript語句實現它：
const lex = str => str.split(' ').map(s => s.trim()).filter(s => s.length);
在這裡，我們使用單一的空格來劃分字符串，然後將產生的子串映射成修理版本並且過濾掉空串。
針對一個表達式調用lexer將產生一個字符串數組:
lex('mul 3 sub 2 sum 1 3 4')
// ["mul", "3", "sub", "2", "sum", "1", "3", "4"]
這完全實現了我們的目標！
現在讓我們進入語法分析的階段！
開發一個語法分析器
語法分析器(通常稱為解析器)是一個編譯器的模塊，該編譯器從一個標記列表(或流)中生成一個抽象語法樹6。在這個過程中，語法分析器會對無效程序產生語法錯誤。
通常，解析器是基於語法[7]實現的。以下是我們語言的語法:
digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
num = digit+
op = sum | sub | mul | div
expr = num | op expr+
語法中包含有數字，這些數字組合在一起可以形成數字(num)；有4個操作；一個表達式可以是一個數字，或者是操作，後面跟著一個或多個表達式。我們將把語法中的個體定義(例如num和op)作為規則。
這就是所謂的EBNF 語法[6]。稍微看一下語法，試著去理解它，然後完全忘記它！在解釋解析器之後，我們將回到語法，你將看到所有東西是如何連接在一起的！
如前所述，解析器是一種工具，它將標記的列錶轉換為AST。
例如，對於我們的表達式:
mul 3 sub 2 sum 1 3 4
解析器將根據上面的語法生成下面的AST:
讓我們來研究一下這個算法吧！
const Op = Symbol('op');
const Num = Symbol('num');
const parse = tokens => {
let c = 0;
const peek = () => tokens[c];
const consume = () => tokens[c++];
const parseNum = () => ({ val: parseInt(consume()), type: Num });
const parseOp = () => {
const node = { val: consume(), type: Op, expr: [] };
while (peek()) node.expr.push(parseExpr());
return node;
};
const parseExpr = () => /\d/.test(peek()) ? parseNum() : parseOp();
return parseExpr();
};
壞消息是，有很多事情正在發生。好消息是，這是編譯器中最複雜的部分！
讓我們把代碼分成各個部分，然後一步步查看每一個步驟。
節點類型
const Op = Symbol('op');
const Num = Symbol('num');
首先，我們定義了在AST中將要使用的不同節點類型，我們只需要數字和操作。例如，數字節點42將會是這樣的:
{
type: Num,
val: 42
}
運算符sum，應用到2、 3、 4，將會是這樣的:
{
type: Op,
val: 'sum',
expr: [{
type: Num,
va: 2
}, {
type: Num,
va: 3
}, {
type: Num,
va: 4
}]
}
這是多麼簡單啊！
語法分析器
在聲明了節點類型之後，我們定義了一個名為parse的函數，該函數接受一個稱為標記的參數。在它的內部，我們定義了另外五個函數:
peek-返回與標記元素關聯的本地變量c 的當前值。
consum-返回與c本地變量和增量c的當前值相關聯的標記元素。
parseNum-獲取當前的標記(即調用peek())，將其解析為一個自然數字，並返回一個新的數字標記。
parseOp-我們會稍微研究一下。
parseExpr - 檢查當前標記與正則表達式/\d/（即是一個數字）是否匹配，如果成功則調用parseNum，否則返回parseOp。
解析操作
parseOp可能是上面解析器中最複雜的函數。這是因為存在循環和間接遞歸的情況。這裡是它再一次的定義為了可以逐行對進行解釋：
const parseOp = () => {
const node = { val: consume(), type: Op, expr: [] };
while (peek()) node.expr.push(parseExpr());
return node;
};
當peek()的返回值不是數值時， parseExpr會調用parseOp，我們知道這是一個運算符，所以我們創建一個新的操作節點。注意，我們不會執行任何進一步的驗證，但是，在實際的程式語言中，我們希望這樣做，如果遇到一個未知的標記時，會報告語法錯誤。
無論如何，在節點聲明中，我們將「子表達式」的列表設置為空列表(也就是[])，把操作名設置為peek()的值，把節點類型設置為Op。隨後，通過將當前解析的表達式推到給定節點的子表達式列表中，我們循環遍歷所有標記。最後，我們返回該節點。
牢記 while (peek()) node.expr.push(parseExpr());執行一個間接遞歸。我們得到如下表達式：
sum sum 2
這將會：
首先，調用parseExpr，結果會發現當期的標記（就是tokens[0]）不是一個數（是sum），所以它會調用 parseOp。
在parseOp創建一個操作節點後，並且由於調用consume()，c值增加。
下一步，parseOp將會遍歷節點，對於tokens[c]，這裡c對於1，將會調用parseExpr。
parseExpr會發現當前的節點不是一個數，所以會調用 parseOp。
parseOp會創建另外一個操作節點並且將c加1，並對所有的標記再來一次循環。
parseOp 將會調用parseExpr，這時 c 不等於 2了。
tokens[2] 是 「2」，parseExpr將會調用 parseNum，創立一個數值節點, 並將 c 變量加1。
parseNum將會返回數節點並且推入到表達式數組的最後一個操作節點中，該節點通過最新一次的 parseOp 調用生成。
最後一次的 parseOp調用將會返回操作節點，因為 peek()將會返回undefined（ parseNum將 c加到 3，tokens[3] === undefined）。
最後一次parseOp調用返回的節點將會返回給最外層的parseOp調用該調用也會返回操作節點。
最後，parseExpr 將會返回根操作節點。
產生的AST如下所示：
{
type: "Op",
val: "sum",
expr: [{
type: "Op",
val: "sum",
expr: [{
type: "Num",
val: 2
}]
}]
}
最後一步是遍歷這棵樹並生成JavaScript！
遞歸下降解析
現在，讓我們將單獨的函數與上面定義的語法聯繫起來，看看為什麼語法有意義。讓我們來看看EBNF語法的規則:
digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
num = digit+
op = sum | sub | mul | div
expr = num | op expr+
現在它們更清晰一些了？expr看起來很像parseExpr，這裡我們或者解析出一個數或者是一個操作。類似的，op expr+看起來很像parseOp和num類似parseNum。實際上，解析器常常直接從語法中生成解析器，因為它們都與遞歸下降解析算法[8]有直接的聯繫。
事實上，我們剛剛開發了一個簡單的遞歸下降解析器！我們的解析器非常簡單(我們語法中只有4個產生式規則)，但是你可以想像一個真實的程式語言的解析器是多麼複雜。
相較於編寫真正的解析器，觀察其簡化模型，開發一種語言的語法是非常方便的。解析器包含大量細節(例如，你的開發語言的許多語法結構)，這與極其簡化和簡約的語法形成了鮮明的對比。
開發編譯器
在本文的這一部分中，我們將遍歷語言的AST並生成JavaScript。整個編譯器只有7行JavaScript代碼(字面上的！)
const transpile = ast => {
const opMap = { sum: '+', mul: '*', sub: '-', div: '/' };
const transpileNode = ast => ast.type === Num ? transpileNum(ast) : transpileOp(ast);
const transpileNum = ast => ast.val;
const transpileOp = ast => `(${ast.expr.map(transpileNode).join(' ' + opMap[ast.val] + ' ')})`;
return transpileNode(ast);
};
讓我們來逐行探究一下實現的細節。
首先，我們定義了一個函數稱為transpile。它接受由解析器生成的AST作為參數。然後在opMap中，我們第一了數據操作和語言中操作的映射。基本上，sum 映射為+，mul映射為*，等等。
下一步，我們定義函數transpileNode，該函數接受AST節點。如果節點是是一個數，我們調用transpileNum函數，否則，調用transpileOp。
最後，我們定義兩個函數，來處理單個節點的轉譯：
- transpileNum - 把一個數轉換成JavaScript 中的數 (簡單的直接返回這個數)。
- 將操作轉換為JavaScript算術運算。注意這裡有一個間接的遞歸(transpileOp->transpileNode->transpileOp)。對於每個操作節點，我們都希望首先轉換其子表達式。我們通過調用 transpileNode 函數來做到這一點。
在transpile函數體的最後一行，我們返回transpileNode的結果，形成這棵樹的根節點。
將一切都結合在一起
以下是我們如何將所有部分連接在一起的方法:
const program = 'mul 3 sub 2 sum 1 3 4';
transpile(parse(lex(program)));
// (3 * (2 - (1 + 3 + 4)))
我們調用 lex(program)，生成標記列表，此後我們將這些標記傳遞給 parse函數，生成抽象語法樹（AST），最後，我們將AST轉譯成JavaScript！
結論
本文詳細介紹了一種非常簡單的編譯器(或transpile)的開發，將前綴表達式編譯為JavaScript。雖然這只是解釋了編譯器開發的一些基本知識，但是我們介紹了一些非常重要的概念:
詞法分析
語法分析
原始碼生成
EBNF語法
遞歸下降解析
如果你有興趣做進一步的閱讀，我向你推薦：
開發靜態類型化程式語言
構造一個簡單的解釋器
編譯器：準則、技術和工具（第二版）
類型和程式語言
參考文獻
Static Code Analysis of Angular 2 and TypeScript Projects - https://mgv.io/ng-static-analysis.
Developing Statically Typed Programming Language - https://mgv.io/typed-lambda
Tiny Compiler - https://mgv.io/tiny-compiler
Lexical Analysis - https://mgv.io/wiki-lex
Syntax Analysis - https://mgv.io/wiki-parser
Abstract Syntax Tree - https://mgv.io/wiki-case-ast
EBNF grammar - https://mgv.io/wiki-ebnf
Recursive Descent Parsing - https://mgv.io/wiki-recursive-descent-parser