用25行JavaScript語句實作一個簡單的編譯器

原文：Implementing a Simple Compiler on 25 Lines of JavaScript

作者：Minko Gechev

譯者：夜風輕揚

譯者注：即使對于專業程式員來說，構造一個編譯器也是頗具挑戰性的任務，本文将會引導你抽絲剝繭，一探究竟！

我已經寫了幾篇與程式設計語言開發相關的文章，這讓我非常興奮！例如，在“關于 Angular 2 和 TypeScript 項目中的靜态代碼分析”[1]中，我研究了編譯器前端的基本知識，解釋了詞法分析、文法分析和抽象文法樹等各個階段。

最近我發表了“開發靜态類型程式設計語言[2] ”。本文展示了一個簡單的、靜态類型的函數式程式設計語言，它是受到了lambda微積分的啟發。我将編譯器開發的前端部分外包給了解析器生成器，并将注意力放在用于類型檢查的子產品的後端，以及用于代碼生成的子產品。

為什麼我需要這個？

你可能想“為什麼我需要知道如何開發編譯器?”，有幾個重要的原因:

你将更好地了解所使用的程式設計語言是如何工作的。這将使你能夠借助該語言開發出更高效的程式。
經常的，為了不同的目的，你不得不重用下面所述的子產品(例如，對配置檔案進行解析、對網絡消息進行解析等等)。
建立一個DSL。在你的項目中建立一個特定領域的語言可能非常友善，以便簡化任務，否則，使用通用程式設計語言，解決同樣問題，你可能需要花費更多的時間。

我們要讨論的範圍是什麼？

在這篇博文中，我們将介紹從端到端的基礎知識。我們将用25行JavaScript代碼開發一個非常簡單的編譯器！我們的編譯器将會包含:

詞法分析子產品
文法分析子產品

解析器将基于EBNF文法

我們将使用遞歸下行解析算法來開發解析器
代碼生成器

我們将要探讨的語言對于開發有實際意義的軟體程式并不是特别有用，但是它可以很容易地擴充成一個。

整個實作可以在我的GitHub介紹[3]中找到。

用25行JavaScript語句實作一個簡單的編譯器

引入一種簡單的字首語言

下面是我們語言中的一個示例表達式的樣子:

mul  sub  sum

在本文的最後，我們将能經過任何編譯器的典型階段，将這些表達式轉換為JavaScript語句。

為簡單起見，我們需要遵循一些規則:

我們隻有函數:mul，sub，sum，div。
每個字元串标記都被空格隔開。
我們隻支援自然數。

為了探究上述表達式背後的語義，我們定義一些JavaScript函數:

const mul = (...operands) => operands.reduce((a, c) => a * c, );
const sub = (...operands) => operands.reduce((a, c) => a - c);
const sum = (...operands) => operands.reduce((a, c) => a + c, );

mul接受多個操作數，并通過 =>操作符傳遞。函數隻是将它們相乘，例如mul(2、3、4)==24。sub分别減去傳遞的參數,sum則是計算參數的總和。

上述的表達式可以轉換為下列的JavaScript表達式：

或者

3 * (2 - (1 + 3 + 4))

現在，在我們了解了語義之後，讓我們從編譯器的前端開始吧！

注意：類似的字首表達式可以通過基于堆棧的算法進行簡單的評估，但是在這種情況下，我們将關注概念而不是實作。

開發編譯器的前端

任何編譯器的前端通常都有詞法分析子產品[4]和文法分析子產品[5]。在這一節中，我們将在幾行JavaScript代碼中建構兩個子產品！

開發一個詞法分析器

詞法分析階段負責将程式的輸入字元串(或字元流)劃分為稱為标記的小塊。标記通常包含關于它們類型的資訊(如果它們是數字、操作符、關鍵字、辨別符等)、它們所代表程式的子串以及它們在程式中的位置。該位置通常用于報告使用者友好的錯誤，以防出現無效的文法結構。

例如下列的JavaScript程式:

if (foo) {
  bar();
}

一個示例的JavaScript詞彙分析器将生成輸出:

[
  {
    lexeme: 'if',
    type: 'keyword',
    position: {
      row: ,
      col: 
    }
  },
  {
    lexeme: '(',
    type: 'open_paran',
    position: {
      row: ,
      col: 
    }
  },
  {
    lexeme: 'foo',
    type: 'identifier',
    position: {
      row: ,
      col: 
    }
  },
  ...
]

我們将保持我們的詞法分析器盡可能簡單。事實上，我們可以通過一條 JavaScript語句實作它：

在這裡，我們使用單一的空格來劃分字元串，然後将産生的子串映射成修理版本并且過濾掉空串。

針對一個表達式調用lexer将産生一個字元串數組:

lex('mul 3 sub 2 sum 1 3 4')

// ["mul", "3", "sub", "2", "sum", "1", "3", "4"]

這完全實作了我們的目标！

現在讓我們進入文法分析的階段！

開發一個文法分析器

文法分析器(通常稱為解析器)是一個編譯器的子產品，該編譯器從一個标記清單(或流)中生成一個抽象文法樹6。在這個過程中，文法分析器會對無效程式産生文法錯誤。

用25行JavaScript語句實作一個簡單的編譯器

通常，解析器是基于文法[7]實作的。以下是我們語言的文法:

digit =  |  |  |  |  |  |  |  |  | 
num = digit+
op = sum | sub | mul | div
expr = num | op expr+

文法中包含有數字，這些數字組合在一起可以形成數字(num)；有4個操作；一個表達式可以是一個數字，或者是操作，後面跟着一個或多個表達式。我們将把文法中的個體定義(例如num和op)作為規則。

這就是所謂的EBNF 文法[6]。稍微看一下文法，試着去了解它，然後完全忘記它！在解釋解析器之後，我們将回到文法，你将看到所有東西是如何連接配接在一起的！

如前所述，解析器是一種工具，它将标記的清單轉換為AST。

例如，對于我們的表達式:

mul  sub  sum

解析器将根據上面的文法生成下面的AST:

用25行JavaScript語句實作一個簡單的編譯器

讓我們來研究一下這個算法吧！

const Op = Symbol('op');
const Num = Symbol('num');

const parse = tokens => {

  let c = ;

  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: 
}

運算符sum，應用到2、 3、 4，将會是這樣的:

{
  type: Op,
  val: 'sum',
  expr: [{
    type: Num,
    va: 
  }, {
    type: Num,
    va: 
  }, {
    type: Num,
    va: 
  }]
}

這是多麼簡單啊！

文法分析器

在聲明了節點類型之後，我們定義了一個名為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());執行一個間接遞歸。我們得到如下表達式：

這将會：

- 首先，調用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: 
    }]
  }]
}

最後一步是周遊這棵樹并生成JavaScript！

遞歸下降解析

現在，讓我們将單獨的函數與上面定義的文法聯系起來，看看為什麼文法有意義。讓我們來看看EBNF文法的規則:

digit =  |  |  |  |  |  |  |  |  | 
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！

用25行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

用25行JavaScript語句實作一個簡單的編譯器

為什麼我需要這個？

我們要讨論的範圍是什麼？

引入一種簡單的字首語言

開發編譯器的前端

開發一個詞法分析器

開發一個文法分析器

節點類型

文法分析器

解析操作

遞歸下降解析

開發編譯器

将一切都結合在一起

結論

參考文獻

繼續閱讀

[php]通過http post發送json資料

基于ArcEngine的道格拉斯算法的簡單實作

const和指針的交叉問題

Android系統項目腳本源碼解讀

步步為營_Android開發課[14]_使用者界面之Layout(布局)

Linux問題積累

《手把手陪您學Python》30——子產品

用swift開發儀表盤控件（二）

Linux系統——gdb調試技巧

從你的WEB世界路過之--0.初識0) 前言1) WEB基本概念2) 響應資料3. 結語

開源接口管理平台 eoLinker AMS開源版 V3.2.1更新，Mock增加允許新請求頭！

測試崗位飽和時代，月薪過萬比比皆是，你怎麼辦？（寫給未來迷茫的測試從業者）

《cuda并行程式設計》勘誤（3）

【PMBOK重點知識】第4章項目整合管理

wecenter二次開發系列（三）——多個wc架構同域網站共享cookie

32歲大齡程式員該何去何從