摘要：手把手教你實(shí)現(xiàn)一個(gè)簡(jiǎn)單的編譯器概述今天我們將學(xué)習(xí)開(kāi)發(fā)一個(gè)編譯器，但是呢，這個(gè)編譯器并不是說(shuō)什么都能都編譯，它只是一個(gè)超級(jí)小的編譯器，主要用于說(shuō)明編譯器的一些基本的原理。這被稱(chēng)為中間表示或抽象語(yǔ)法樹(shù)。

今天我們將學(xué)習(xí)開(kāi)發(fā)一個(gè)編譯器，但是呢，這個(gè)編譯器并不是說(shuō)什么都能都編譯，它只是一個(gè)超級(jí)小的編譯器，主要用于說(shuō)明編譯器的一些基本的原理。

我們這個(gè)編譯器可以將類(lèi)似于lisp語(yǔ)言的函數(shù)調(diào)用編譯成類(lèi)似于C語(yǔ)言的函數(shù)調(diào)用。如果你對(duì)lisp語(yǔ)言和C語(yǔ)言這兩者都不熟悉，沒(méi)關(guān)系，什么語(yǔ)言其實(shí)無(wú)所謂，但接下來(lái)還是會(huì)給你一個(gè)快速的介紹。

如果我們有兩個(gè)函數(shù)分別是add和subtract,如果用它們來(lái)計(jì)算下面的表達(dá)式：

2 + 2
4 - 2
2 + （4 - 2）

那么在lisp語(yǔ)言中它可能長(zhǎng)這樣子：

(add 2 2) // 2 + 2
(subtract 4 2) // 4 - 2
(add 2 (subtract 4 2)) // 2 + （4 - 2）

而在C語(yǔ)言中它長(zhǎng)這個(gè)樣子：

add(2, 2)
subtract(4, 2)
add(2, subtract(4, 2))

相當(dāng)簡(jiǎn)單吧？

好吧，這是因?yàn)檫@僅僅只是我們這個(gè)編譯器所需要處理的情形。 這既不是list語(yǔ)言的完整語(yǔ)法，也不是C語(yǔ)言的完整語(yǔ)法。 但這點(diǎn)語(yǔ)法已經(jīng)足以用來(lái)演示現(xiàn)代編譯器所做的大部分工作。

大部分編譯器所做的工作都可以分解為三個(gè)主要的步鄹： 解析、轉(zhuǎn)換和代碼生成。

解析。 解析就是將原始代碼轉(zhuǎn)換成代碼的抽象表示。

轉(zhuǎn)換。 轉(zhuǎn)換就是以這個(gè)抽象表示為基礎(chǔ)，做編譯器想做的任何事情。

代碼生成。 代碼生成就是將轉(zhuǎn)換后的抽象表示變成新的代碼。

解析通常分為兩個(gè)階段：詞法分析和句法分析。

詞法分析。 詞法分析通常是使用一個(gè)標(biāo)記器(或詞法分析器)將原始代碼拆分成叫做標(biāo)記的東西。而標(biāo)記是一些微小的對(duì)象組成的數(shù)組，它們通常用來(lái)描述一些孤立的語(yǔ)法片段，它們可以是數(shù)字、標(biāo)簽、標(biāo)點(diǎn)符號(hào)、操作符等等。

語(yǔ)法分析。 語(yǔ)法分析將詞法分析得到的標(biāo)記重新格式化為用于描述語(yǔ)法的每個(gè)部分及其相互關(guān)系的表示。 這被稱(chēng)為中間表示或抽象語(yǔ)法樹(shù)(AST)。抽象語(yǔ)法樹(shù)(簡(jiǎn)稱(chēng)AST)是一個(gè)深度嵌套的對(duì)象，用于以一種既好用又能提供很多信息的形式表式代碼。

對(duì)于下面的語(yǔ)法：

(add 2 (subtract 4 2))

標(biāo)記可能長(zhǎng)下面這個(gè)樣子：

[
      { 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: ")"        },
]

然后它對(duì)應(yīng)的抽象語(yǔ)法樹(shù)(AST)可能長(zhǎng)下面這個(gè)樣子：

{
  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)換。 同樣，這不過(guò)就是將最后一步的抽象語(yǔ)法樹(shù)(AST)拿過(guò)來(lái)對(duì)它做一定的改變。這種改變多種多樣，可以是在同一種語(yǔ)言中進(jìn)行改變，也可以直接將抽象語(yǔ)法樹(shù)轉(zhuǎn)換成另外一種完全不同的新語(yǔ)言。

讓我們來(lái)看看我們將如何轉(zhuǎn)換一個(gè)抽象語(yǔ)法樹(shù)(AST)。

你可能已經(jīng)注意到，我們的抽象語(yǔ)法樹(shù)里面有一些非常類(lèi)似的元素。 這些元素對(duì)象有一個(gè)type屬性。 這每一個(gè)對(duì)象元素都被稱(chēng)為一個(gè)AST節(jié)點(diǎn)。 這些節(jié)點(diǎn)上定義的屬性用于描述AST樹(shù)上的一個(gè)獨(dú)立部分。

我們可以為數(shù)字字面量(NumberLiteral)建立一個(gè)節(jié)點(diǎn):

{
  type: "NumberLiteral",
  value: "2",
}

或者是為調(diào)用表達(dá)式(CallExpression)創(chuàng)建一個(gè)節(jié)點(diǎn)：

{
  type: "CallExpression",
  name: "subtract",
  params: [...nested nodes go here...],
}

當(dāng)轉(zhuǎn)換AST樹(shù)的時(shí)候，我們可能需要對(duì)它進(jìn)行add、remove、replace等操作。 我們可以增加新節(jié)點(diǎn)，刪除節(jié)點(diǎn)或者我們完全可以將AST樹(shù)擱一邊不理，然后基于它創(chuàng)建一個(gè)全新的AST。

由于我們這個(gè)編譯器的目標(biāo)是將lisp語(yǔ)言轉(zhuǎn)換成C語(yǔ)言，所以我們會(huì)聚焦創(chuàng)建一個(gè)專(zhuān)門(mén)用于目標(biāo)語(yǔ)言(在這里是C語(yǔ)言)的全新AST。

為了瀏覽所有這些節(jié)點(diǎn)，我們需要能夠遍歷它們。 這個(gè)遍歷過(guò)程是對(duì)AST的每個(gè)節(jié)點(diǎn)進(jìn)行深度優(yōu)先訪問(wè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"
      }]
    }]
  }]
}

所以對(duì)于上面的AST，我們需要像這樣走：

Program - 從AST樹(shù)的頂層開(kāi)始。

CallExpression (add) - 移動(dòng)到Program的body屬性的第一個(gè)元素。

NumberLiteral (2) - 移動(dòng)到CallExpression(add)的第一個(gè)參數(shù)。

CallExpression (subtract) - 移動(dòng)到CallExpression(add)的第二個(gè)參數(shù)。

NumberLiteral (4) - 移動(dòng)到CallExpression(subtract)的第一個(gè)參數(shù)。

NumberLiteral (2) - 移動(dòng)到CallExpression(subtract)的第二個(gè)參數(shù)。

如果我們直接操作這個(gè)AST而不是創(chuàng)建一個(gè)多帶帶的AST，我們可能需要在這里引入各種抽象概念。 但是我們正在嘗試做的事情，只需要訪問(wèn)樹(shù)中的每個(gè)節(jié)點(diǎn)就足夠了。

使用“訪問(wèn)”這個(gè)詞的原因是因?yàn)檫@個(gè)詞能夠很好的表達(dá)如何在對(duì)象結(jié)構(gòu)上操作元素。

這里最基本的思路就是我們創(chuàng)建一個(gè)訪問(wèn)者對(duì)象，這個(gè)對(duì)象擁有一些方法，這些方法可以接受不同的節(jié)點(diǎn)類(lèi)型。

比如下面這樣：

var visitor = {
  NumberLiteral() {},
  CallExpression() {},
};

當(dāng)我們遍歷AST的時(shí)候，一旦我們碰到一個(gè)與指定類(lèi)型相匹配的節(jié)點(diǎn)，我們就會(huì)調(diào)用訪問(wèn)者對(duì)象上的方法。

為了讓這個(gè)函數(shù)比較好用，我們給它傳遞了該節(jié)點(diǎn)以及它的父節(jié)點(diǎn)：

var visitor = {
  NumberLiteral(node, parent) {},
  CallExpression(node, parent) {},
};

然而，這里也會(huì)有可能出現(xiàn)在退出時(shí)調(diào)用東西。 想象一下我們前面提到的樹(shù)結(jié)構(gòu)：

    - Program
      - CallExpression
        - NumberLiteral
        - CallExpression
          - NumberLiteral
          - NumberLiteral

當(dāng)我們往下遍歷的時(shí)候，我們會(huì)遇到最終的分支。 當(dāng)我們?cè)L問(wèn)完所有的分支后我們退出。 所以向下遍歷樹(shù)，我們進(jìn)入節(jié)點(diǎn)，然后向上回溯的時(shí)候我們退出節(jié)點(diǎn)。

 -> Program (enter)
  -> CallExpression (enter)
    -> Number Literal (enter)
    <- Number Literal (exit)
    -> Call Expression (enter)
       -> Number Literal (enter)
       <- Number Literal (exit)
       -> Number Literal (enter)
       <- Number Literal (exit)
    <- CallExpression (exit)
  <- CallExpression (exit)
 <- Program (exit)

為了支持這種方式，我們的訪問(wèn)者對(duì)象需要改成下面這個(gè)樣子：

var visitor = {
  NumberLiteral: {
    enter(node, parent) {},
    exit(node, parent) {},
  }
};

編譯器的最后一步是代碼生成。有時(shí)候編譯器在這一步會(huì)重復(fù)做一些轉(zhuǎn)換步鄹做過(guò)的事情。 但是對(duì)代碼生成而言，它所做的大部分工作就是將我們的AST樹(shù)stringify一下輸出，也就是轉(zhuǎn)換成字符串輸出。

代碼生成有多種工作方式，有一些編譯器會(huì)重復(fù)利用前面生成的標(biāo)記，另一些編譯器會(huì)創(chuàng)建代碼的多帶帶表示，以便線性地打印節(jié)點(diǎn)，但是據(jù)我說(shuō)知，大多數(shù)編譯器的策略是使用我們剛剛創(chuàng)建的那個(gè)AST，這是我們將要關(guān)注的。

實(shí)際上，我們的代碼生成器將知道如何打印AST的所有不同節(jié)點(diǎn)類(lèi)型，并且它將遞歸地調(diào)用自己來(lái)打印嵌套節(jié)點(diǎn)，直到將所有內(nèi)容打印成一長(zhǎng)串代碼。

而就是這樣！ 這就是編譯器的所有差異部分。

現(xiàn)在不是說(shuō)每個(gè)編譯器看起來(lái)都和我在這里描述的完全一樣。 編譯器有許多不同的用途，他們可能需要比我詳細(xì)的更多的步驟。

但是現(xiàn)在您應(yīng)該對(duì)大多數(shù)編譯器的輪廓有一個(gè)總體的高層次的概念。

現(xiàn)在我已經(jīng)解釋了所有這些，你應(yīng)該可以寫(xiě)好自己的編譯器了是吧？

只是在開(kāi)玩笑的啦，我會(huì)在這里繼續(xù)提供幫助，所以我們開(kāi)始吧！

前面說(shuō)了，整個(gè)編譯器大概可以分為三步：解析、轉(zhuǎn)換、代碼生成。而解析又可以分成兩步：詞法解析和句法解析。所以一共需要四個(gè)函數(shù)就可以實(shí)現(xiàn)了。我們來(lái)分別看一下:

我們將從編譯器的第一步——解析——開(kāi)始，利用tokenizer函數(shù)進(jìn)行詞法分析。

我們將把字符串代碼拆分成由標(biāo)記組成的數(shù)組：

(add 2 (subtract 4 2))   =>   [{ type: "paren", value: "(" }, ...]

我們的tokenizer接收一個(gè)代碼字符串， 然后接下來(lái)做兩個(gè)事情：

function tokenizer(input) {

  // 一個(gè)current變量，類(lèi)似于游標(biāo)，用于跟蹤我們?cè)诖a字符串中的位置
  let current = 0;

  // 以及一個(gè)tockens數(shù)組，用于將我們分解的標(biāo)記存放其中
  let tokens = [];

  // 我們創(chuàng)建一個(gè)while循環(huán)，在這里面我們?cè)O(shè)置我們的current變量，這個(gè)變量會(huì)隨著循環(huán)的深入而不斷增加
  //
  // 這么做是因?yàn)閠ockens可能會(huì)是任意長(zhǎng)度
  while (current < input.length) {

    // 我們還會(huì)存儲(chǔ)變量current所在位置的字符
    let char = input[current];

    // 我們首先要檢查的是左括弧，這個(gè)將會(huì)在稍后用于CallExpression，但是此時(shí)我們只關(guān)心左括弧字符
    //
    // 我們檢查看看有沒(méi)有左括弧:
    if (char === "(") {

      // 如果有，則建立一個(gè)對(duì)象，其type屬性是paren，值為左括弧, 然后我們將這個(gè)對(duì)象加入tokens數(shù)組
      tokens.push({
        type: "paren",
        value: "(",
      });

      // 接著我們?cè)黾觕urrent變量，也就是移動(dòng)游標(biāo)
      current++;

      // 然后進(jìn)行下一輪循環(huán).
      continue;
    }

    // 接著我們檢查右括弧，我們按照前面的套路來(lái)做：檢查右括弧，新增一個(gè)標(biāo)記，增加current, 進(jìn)行下一輪循環(huán)
    if (char === ")") {
      tokens.push({
        type: "paren",
        value: ")",
      });
      current++;
      continue;
    }

    // 接著，我們檢查空白格。 這很有趣，因?yàn)槲覀冴P(guān)注空白格是因?yàn)樗鼘⒆址指糸_(kāi)，但是我們并不需要將空白格存為標(biāo)記,我們
    // 可以直接扔掉它，所以這里我們僅僅檢查空白格是否存在，如果它存在我們就進(jìn)入下一輪循環(huán)

    let WHITESPACE = /s/;
    if (WHITESPACE.test(char)) {
      current++;
      continue;
    }

    // 下一個(gè)類(lèi)型的標(biāo)記是數(shù)字，這和我們前面見(jiàn)到的不同，因?yàn)橐粋€(gè)數(shù)字可能是任意個(gè)字符組成，并且我們需要捕獲整個(gè)字符序列作為一個(gè)標(biāo)記
    //
    //   (add 123 456)
    //        ^^^ ^^^
    //  比如上面的就只有兩個(gè)獨(dú)立的數(shù)字標(biāo)記
    //
    // 所以當(dāng)我們遇到序列中的第一個(gè)數(shù)字的時(shí)候開(kāi)始進(jìn)一步處理.
    let NUMBERS = /[0-9]/;
    if (NUMBERS.test(char)) {

      // 我們?cè)谶@里面創(chuàng)建了一個(gè)value字符，用于拼接數(shù)字字符
      let value = "";

      // 接下來(lái)我們遍歷后面的每一個(gè)字符直到遇到一個(gè)非數(shù)字字符，將這些字符和前面的value變量拼接起來(lái), 并且改變current游標(biāo)
      while (NUMBERS.test(char)) {
        value += char;
        char = input[++current];
      }

      // 這之后我們將創(chuàng)建數(shù)字標(biāo)記并加入tokens數(shù)組
      tokens.push({ type: "number", value });

      // 然后我們繼續(xù)
      continue;
    }

    // 我們也支持字符串，字符串就是用雙引號(hào)(")包裹的一段文本，比如
    //
    //   (concat "foo" "bar")
    //            ^^^   ^^^ 字符串標(biāo)記
    //
    // 我們先檢查左雙引號(hào):
    if (char === """) {
      // 創(chuàng)建一個(gè)value變量用于保存字符串.
      let value = "";

      // 我們將忽略雙引號(hào)，因?yàn)槲覀冴P(guān)心的是雙引號(hào)包裹的文本.
      char = input[++current];

      // 然后我們遍歷后面的字符串，直到我們遇到右雙引號(hào)
      while (char !== """) {
        value += char;
        char = input[++current];
      }

      // 忽略右雙引號(hào)，同理，因?yàn)槲覀冴P(guān)心的是雙引號(hào)包裹的文本.
      char = input[++current];

      // 創(chuàng)建類(lèi)型為string的標(biāo)記，并放進(jìn)tockens數(shù)組
      tokens.push({ type: "string", value });

      continue;
    }

    // 最后一種類(lèi)型的標(biāo)記是name標(biāo)記，這是一串字符而不是數(shù)字,也就是lisp語(yǔ)法中的函數(shù)名
    //
    //   (add 2 4)
    //    ^^^
    //    name 標(biāo)記
    //
    let LETTERS = /[a-z]/i;
    if (LETTERS.test(char)) {
      let value = "";

      // 同理，我們遍歷，并將它們拼接起來(lái)
      while (LETTERS.test(char)) {
        value += char;
        char = input[++current];
      }

      // 并且創(chuàng)建一個(gè)類(lèi)型為name的標(biāo)記，存儲(chǔ)于tokens數(shù)組
      tokens.push({ type: "name", value });

      continue;
    }

    // 最后，如果我們到這里還沒(méi)有匹配一個(gè)字符, 我們將拋出一個(gè)錯(cuò)誤然后退出
    throw new TypeError("I dont know what this character is: " + char);
  }

   // 在tokenizer函數(shù)的末尾我們將tokens數(shù)組返回
  return tokens;
}

舉個(gè)例子，對(duì)于(add 123 456)這段lisp語(yǔ)言代碼，tokenizer化之后得到的結(jié)果如下：

句法解析的目標(biāo)就是將tokens數(shù)組轉(zhuǎn)換成AST。也就是下面的過(guò)程：

[{ type: "paren", value: "(" }, ...]   =>   { type: "Program", body: [...] }

所以，我們定義一個(gè)parse函數(shù)，接收我們的tokens數(shù)組作為參數(shù)：

function parser(tokens) {

  // 同樣我們維持一個(gè)current變量用作游標(biāo)
  let current = 0;

  // 但是這次我們使用遞歸而不是while循環(huán)，所以我們定義了walk函數(shù)
  function walk() {

    // 在walk函數(shù)內(nèi)部，我們首先拿到tokens數(shù)組中current索引處存放的標(biāo)記
    let token = tokens[current];

    // 我們將把每種類(lèi)型的標(biāo)記以另外一種結(jié)構(gòu)關(guān)系存儲(chǔ)，以體現(xiàn)句法關(guān)系
    // 首先從數(shù)字token開(kāi)始
    //
    // 我們檢查看有沒(méi)有數(shù)字token
    if (token.type === "number") {

      // 如果有，我們移動(dòng)游標(biāo)
      current++;

      // 并且我們會(huì)返回一個(gè)叫做“NumberLiteral”的新的AST節(jié)點(diǎn)并且將它的value屬性設(shè)置為我們標(biāo)記對(duì)象的value屬性
      return {
        type: "NumberLiteral",
        value: token.value,
      };
    }

    // 如果我們有string類(lèi)型的標(biāo)記，我們會(huì)和數(shù)字類(lèi)型類(lèi)似，創(chuàng)建一個(gè)叫做“StringLiteral”的AST節(jié)點(diǎn)
    if (token.type === "string") {
      //同樣移動(dòng)游標(biāo)
      current++;

      return {
        type: "StringLiteral",
        value: token.value,
      };
    }

    // 接下來(lái)我們查找CallExpressions. 我們是通過(guò)左括弧來(lái)開(kāi)始這個(gè)過(guò)程的
    if (
      token.type === "paren" &&
      token.value === "("
    ) {

      // 我們將忽略左括弧，因?yàn)樵贏ST里面，AST就是有句法關(guān)系的，所以我們不關(guān)心左括弧本身了
      token = tokens[++current];

      // 我們創(chuàng)建一個(gè)叫做CallExpression的基礎(chǔ)節(jié)點(diǎn)，并且將節(jié)點(diǎn)的名字設(shè)置為當(dāng)前標(biāo)記的value屬性，
      // 因?yàn)樽罄ɑ?biāo)記的下一個(gè)標(biāo)記就是函數(shù)名字
      let node = {
        type: "CallExpression",
        name: token.value,
        params: [],
      };

      // 我們移動(dòng)游標(biāo)，忽略掉name標(biāo)記，因?yàn)楹瘮?shù)名已經(jīng)存起在CallExpression中了
      token = tokens[++current];

      // 然后現(xiàn)在我們遍歷每一個(gè)標(biāo)記，找到CallExpression的參數(shù)直至遇到右括弧
      //
      // 現(xiàn)在，這里就是遞歸出場(chǎng)的地方了，為了避免陷入無(wú)限的嵌套節(jié)點(diǎn)解析，我們采用遞歸的方式來(lái)搞定這個(gè)事情
      //
      // 為了更好的解釋這個(gè)東西，我們以我們的Lisp代碼舉例，你可以看到，add的參數(shù)是一個(gè)數(shù)字以及一個(gè)嵌套的CallExpression，
      // 這個(gè)嵌套的函數(shù)調(diào)用包含它自己的數(shù)字參數(shù)
      //
      //   (add 2 (subtract 4 2))
      //
      // 你特可以從它的tokens數(shù)組中發(fā)現(xiàn)它有很多右括弧
      //
      //   [
      //     { 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: ")"        }, <<< 右括弧
      //   ]
      //
      // 我們將依賴(lài)于嵌套的walk函數(shù)來(lái)增加我們的游標(biāo)

      // 所以我們創(chuàng)建一個(gè)while循環(huán)，這個(gè)while循環(huán)將一直進(jìn)行直到遇到一個(gè)類(lèi)型是paren的標(biāo)記并且這個(gè)標(biāo)記的值是一個(gè)右括弧
      while (
        (token.type !== "paren") ||
        (token.type === "paren" && token.value !== ")")
      ) {
        // 我們將調(diào)用walk函數(shù)，這個(gè)函數(shù)將返回一個(gè)節(jié)點(diǎn), 我們將把這個(gè)返回的節(jié)點(diǎn)放到當(dāng)前節(jié)點(diǎn)的params
        // 數(shù)組中存儲(chǔ)起來(lái)，這樣嵌套關(guān)系再AST里面就體現(xiàn)出來(lái)了
        node.params.push(walk());
        token = tokens[current];
      }

      // 最后，我們需要最后一次移動(dòng)游標(biāo)用于忽略右括弧
      current++;

      // 并且返回節(jié)點(diǎn)
      return node;
    }

    // 同樣，如果我們沒(méi)有識(shí)別出標(biāo)記的類(lèi)型，我們也會(huì)拋出一個(gè)錯(cuò)誤
    throw new TypeError(token.type);
  }

  // 現(xiàn)在walk函數(shù)已經(jīng)定義好了， 我們需要定義我們的AST樹(shù)了，這個(gè)AST樹(shù)有一個(gè)“Program”根節(jié)點(diǎn)：
  let ast = {
    type: "Program",
    body: [],
  };

  // 然后我們要啟動(dòng)我們的walk函數(shù), 將AST節(jié)點(diǎn)放入根節(jié)點(diǎn)的body數(shù)組里面
  //
  // 我們?cè)谘h(huán)里面做這個(gè)是因?yàn)?，我們可能?huì)遇到連著的多個(gè)函數(shù)調(diào)用，比如說(shuō)像這樣的：
  //
  //   (add 2 2)
  //   (subtract 4 2)
  //啟動(dòng)walk
  while (current < tokens.length) {
    ast.body.push(walk());
  }

  // 在解析函數(shù)的最后，我們將返回生成的AST.
  return ast;
}

任然以前面的例子舉例，我們解析后得到的AST如下：

現(xiàn)在我們已經(jīng)有了我們的AST，我們想要一個(gè)訪問(wèn)者可以訪問(wèn)不同的節(jié)點(diǎn)，無(wú)論何時(shí)匹配到對(duì)應(yīng)的節(jié)點(diǎn)類(lèi)型的時(shí)候，我們都可以調(diào)用訪問(wèn)者上的方法。
所以我們定義一個(gè)旅行者函數(shù)，這個(gè)函數(shù)接收兩個(gè)參數(shù)，第一個(gè)參數(shù)為AST樹(shù)，第二個(gè)參數(shù)是一個(gè)訪問(wèn)者。這個(gè)訪問(wèn)者需要實(shí)現(xiàn)不同類(lèi)型的AST節(jié)點(diǎn)需要調(diào)用的一些方法：

traverse(ast, {
  Program: {
    enter(node, parent) {
      // ...
    },
    exit(node, parent) {
      // ...
    },
  },

  CallExpression: {
    enter(node, parent) {
      // ...
    },
    exit(node, parent) {
      // ...
    },
  },

  NumberLiteral: {
    enter(node, parent) {
      // ...
    },
    exit(node, parent) {
      // ...
    },
  },
});

5.2.1 、traverser函數(shù)實(shí)現(xiàn)

因此，我們的旅行者函數(shù)的實(shí)現(xiàn)如下，它接收AST和一個(gè)訪問(wèn)者作為參數(shù)，并且在里面還定義了兩個(gè)方法：

function traverser(ast, visitor) {

  // 定義一個(gè)traverseArray函數(shù)，可以是我們迭代一個(gè)數(shù)組，然后調(diào)用我們稍后定義的traverseNode函數(shù)
  function traverseArray(array, parent) {
    array.forEach(child => {
      traverseNode(child, parent);
    });
  }

  // traverseNode函數(shù)接收一個(gè)AST節(jié)點(diǎn)以及它的父節(jié)點(diǎn)，所以它也可以傳遞給我們的訪問(wèn)者函數(shù)
  function traverseNode(node, parent) {

    // 我們首先檢查訪問(wèn)者匹配類(lèi)型的方法
    let methods = visitor[node.type];

    // 如果該AST節(jié)點(diǎn)類(lèi)型存在enter方法，我們將以當(dāng)前node及其父節(jié)點(diǎn)作為參數(shù)調(diào)用該方法
    if (methods && methods.enter) {
      methods.enter(node, parent);
    }

    // 接下來(lái)我們會(huì)根據(jù)節(jié)點(diǎn)類(lèi)型來(lái)把事情劃分開(kāi)來(lái)
    switch (node.type) {

      // 首先我們從頂級(jí)節(jié)點(diǎn)Program開(kāi)始，由于該頂級(jí)節(jié)點(diǎn)有一個(gè)叫做body的屬性，這個(gè)屬性中是一個(gè)AST節(jié)點(diǎn)組成的數(shù)組
      // 我們將調(diào)用traverseArray函數(shù)來(lái)遞歸它
      //
      // (記住traverseArray函數(shù)會(huì)反過(guò)來(lái)調(diào)用traverseNode函數(shù)，所以我們讓這個(gè)AST被遞歸的訪問(wèn))
      case "Program":
        traverseArray(node.body, node);
        break;

      // 接下來(lái)我們對(duì)CallExpression節(jié)點(diǎn)做同樣的事情，并且訪問(wèn)它們的參數(shù)
      case "CallExpression":
        traverseArray(node.params, node);
        break;

      // 對(duì)于數(shù)字節(jié)點(diǎn)以及字符串節(jié)點(diǎn)，他們沒(méi)有任何的子節(jié)點(diǎn),所以我們直接break.
      case "NumberLiteral":
      case "StringLiteral":
        break;

      // 并且再一次，如果沒(méi)有識(shí)別出對(duì)應(yīng)的節(jié)點(diǎn)類(lèi)型，就拋出錯(cuò)誤
      default:
        throw new TypeError(node.type);
    }

    // 如果訪問(wèn)者上有exit方法，我們將以該節(jié)點(diǎn)和它的父節(jié)點(diǎn)作為參數(shù)調(diào)用exit方法
    if (methods && methods.exit) {
      methods.exit(node, parent);
    }
  }

  // 最后，我們啟動(dòng)traverser，這是通過(guò)調(diào)用traverseNode實(shí)現(xiàn)的，并且traverseNode第二個(gè)參數(shù)是null，因?yàn)槎?jí)節(jié)點(diǎn)本身就沒(méi)有父節(jié)點(diǎn).
  traverseNode(ast, null);
}

5.2.2 、transformer函數(shù)實(shí)現(xiàn)

前面我們已經(jīng)寫(xiě)好了traverser函數(shù)，而traverser函數(shù)對(duì)節(jié)點(diǎn)的主要操作都是通過(guò)它的第二個(gè)參數(shù)，也就是訪問(wèn)者來(lái)完成的，在上面，我們并沒(méi)有定義訪問(wèn)者的具體實(shí)現(xiàn)，只是定義了enter和exit兩個(gè)接口，實(shí)際上這兩個(gè)接口所做的事情就是轉(zhuǎn)換步鄹真正干的事情。為此我們定義transformer函數(shù)。

transformer函數(shù)接收AST，將它傳遞給traverser函數(shù)，并且transformer函數(shù)內(nèi)部還為traverser函數(shù)提供訪問(wèn)者。最終transformer函數(shù)返回一個(gè)新建的AST。

比如以前面那個(gè)例子為例，得到的AST和轉(zhuǎn)換后的AST如下：

----------------------------------------------------------------------------
Original AST                     |   Transformed 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"
                                 |           }]
                                 |         }
                                 |       }
                                 |     }]
                                 |   }
----------------------------------------------------------------------------

所以我們的transformer函數(shù)的具體實(shí)現(xiàn)如下：

function transformer(ast) {

  // 我們將創(chuàng)建一個(gè)新的AST(即newAst)，它和我們?cè)瓉?lái)的AST類(lèi)似，有一個(gè)Program根節(jié)點(diǎn)
  let newAst = {
    type: "Program",
    body: [],
  };

  // 接下來(lái)，我們會(huì)做一些取巧的操作，我們?cè)诟腹?jié)點(diǎn)上定義一個(gè)\_context屬性，
  // 我們會(huì)將節(jié)點(diǎn)放入父節(jié)點(diǎn)的\_context屬性中
  // 通常你會(huì)有更好的抽象(也許會(huì)復(fù)雜些)，但是在這里我們這樣做使得事情變得相對(duì)簡(jiǎn)單
  //
  // 你僅僅需要記住的是，context是一個(gè)從老AST到新AST的引用
  ast._context = newAst.body;

  // 我們以老ast和一個(gè)訪問(wèn)者作為參數(shù)調(diào)用traverser函數(shù)
  traverser(ast, {

    // 第一個(gè)訪問(wèn)者的屬性是用來(lái)處理NumberLiteral的
    NumberLiteral: {
      // 在enter方法中會(huì)對(duì)節(jié)點(diǎn)進(jìn)行訪問(wèn).
      enter(node, parent) {
        // 在這里面我們會(huì)創(chuàng)建一個(gè)新的AST節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)任然以NumberLiteral命名
        // 我們會(huì)將這個(gè)節(jié)點(diǎn)放入該節(jié)點(diǎn)父親的\_context屬性中
        parent._context.push({
          type: "NumberLiteral",
          value: node.value,
        });
      },
    },

    // 接下來(lái)是StringLiteral
    StringLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: "StringLiteral",
          value: node.value,
        });
      },
    },

    // 接下來(lái)是CallExpression
    CallExpression: {
      enter(node, parent) {

        // 我們創(chuàng)建一個(gè)新的節(jié)點(diǎn)CallExpression，它有一個(gè)嵌套的標(biāo)識(shí)符
        let expression = {
          type: "CallExpression",
          callee: {
            type: "Identifier",
            name: node.name,
          },
          arguments: [],
        };

        // 接下來(lái)，我們?cè)谠嫉腃allExpression節(jié)點(diǎn)上定義一個(gè)新的context用于引用
        // expression變量上的arguments屬性
        // 這樣我們可以加入?yún)?shù)
        node._context = expression.arguments;

        // 接著我們檢查父節(jié)點(diǎn)是不是一個(gè)CallExpression節(jié)點(diǎn)
        // 如果不是
        if (parent.type !== "CallExpression") {

          // 我們將用一個(gè)ExpressionStatement節(jié)點(diǎn)包裹這個(gè)CallExpression節(jié)點(diǎn)
          // 這么做是因?yàn)轫敿?jí)CallExpression節(jié)點(diǎn)實(shí)際上就是statement
          // 也就是說(shuō)，如果某個(gè)CallExpression節(jié)點(diǎn)的父節(jié)點(diǎn)不是CallExpression節(jié)點(diǎn)
          // 那么這個(gè)CallExpression節(jié)點(diǎn)應(yīng)該就是函數(shù)聲明
          expression = {
            type: "ExpressionStatement",
            expression: expression,
          };
        }

        // 最后我們將這個(gè)新的CallExpression(可能被ExpressionStatement包裹)
        // 放入parent._context
        parent._context.push(expression);
      },
    }
  });

  // 在transformer函數(shù)的最后，我們把我們剛創(chuàng)建的新AST返回
  return newAst;
}

我們同樣以前面的例子來(lái)看一下新創(chuàng)建AST長(zhǎng)什么樣子：

現(xiàn)在讓我們進(jìn)入我們的最后一個(gè)步鄹：代碼生成。我們的代碼生成函數(shù)會(huì)遞歸的調(diào)用自己用來(lái)打印它的節(jié)點(diǎn)到一個(gè)很大的字符串。也就是完成由newAST到代碼的過(guò)程：

newAst => generator   => output

5.3.1 codeGenerator的實(shí)現(xiàn)

function codeGenerator(node) {

  // 我們會(huì)根據(jù)節(jié)點(diǎn)的type類(lèi)型來(lái)將事情分別處理
  switch (node.type) {

    // 如果我們有一個(gè)Program節(jié)點(diǎn)，我們將遍歷body中的每一個(gè)節(jié)點(diǎn)并且對(duì)每一個(gè)節(jié)點(diǎn)遞調(diào)用codeGenerator
    // 函數(shù)，并且將它們的結(jié)果用一個(gè)換行符連接起來(lái)
    case "Program":
      return node.body.map(codeGenerator)
        .join("
");

    // 對(duì)于ExpressionStatement節(jié)點(diǎn)，我們將在節(jié)點(diǎn)的expression節(jié)點(diǎn)上調(diào)用
    // codeGenerator函數(shù)，然后我們會(huì)加上一個(gè)分號(hào)(即；)
    case "ExpressionStatement":
      return (
        codeGenerator(node.expression) +
        ";" // << (...because we like to code the *correct* way)
      );

    // 對(duì)于CallExpression節(jié)點(diǎn)，我們會(huì)打印callee并開(kāi)始一個(gè)做括弧
    // 我們會(huì)遍歷該節(jié)點(diǎn)的arguments屬性，然后對(duì)每個(gè)屬性調(diào)用codeGenerator方法,
    // 將他們的結(jié)果用逗號(hào)分隔，最后在后面加一個(gè)右括弧
    case "CallExpression":
      return (
        codeGenerator(node.callee) +
        "(" +
        node.arguments.map(codeGenerator)
          .join(", ") +
        ")"
      );

    // 對(duì)于標(biāo)識(shí)符，我們將返回節(jié)點(diǎn)的名字
    case "Identifier":
      return node.name;

    // 對(duì)于NumberLiteral節(jié)點(diǎn)，我們返回它的value屬性
    case "NumberLiteral":
      return node.value;

    // 對(duì)于StringLiteral節(jié)點(diǎn)，我們用引號(hào)將它的value屬性值包裹起來(lái)
    case "StringLiteral":
      return """ + node.value + """;

    // 如果沒(méi)有識(shí)別節(jié)點(diǎn)，我們將拋出錯(cuò)誤
    default:
      throw new TypeError(node.type);
  }
}

同樣以上面例子舉例，它的輸出結(jié)果如圖：

現(xiàn)在，編譯器的三大步鄹的代碼都已經(jīng)實(shí)現(xiàn)了，我們現(xiàn)在開(kāi)始實(shí)現(xiàn)編譯器，它的方式就是將三個(gè)步鄹鏈接起來(lái)，可以將這幾個(gè)步鄹描述如下：

1. input  => tokenizer   => tokens
2. tokens => parser      => ast
3. ast    => transformer => newAst
4. newAst => generator   => output

我們的編譯器代碼如下：

function compiler(input) {
  let tokens = tokenizer(input);
  let ast    = parser(tokens);
  let newAst = transformer(ast);
  let output = codeGenerator(newAst);

  // and simply return the output!
  return output;
}

最后作為一個(gè)模塊，我們希望別人去使用它，因?yàn)槲覀兊拿總€(gè)函數(shù)都是相對(duì)獨(dú)立的一個(gè)功能模塊，所以我們將這里面的每個(gè)函數(shù)都導(dǎo)出：

module.exports = {
  tokenizer,
  parser,
  traverser,
  transformer,
  codeGenerator,
  compiler,
};

更多相關(guān)和無(wú)關(guān)內(nèi)容歡迎瀏覽Github和個(gè)人博客

書(shū)把手系列還包括：手把手教你實(shí)現(xiàn)一個(gè)簡(jiǎn)單的Promise，手把手教你實(shí)現(xiàn)一個(gè)簡(jiǎn)單的MVC模式，手把手教你實(shí)現(xiàn)一個(gè)簡(jiǎn)單的MVP模式，手把手教你實(shí)現(xiàn)一個(gè)簡(jiǎn)單的MVVM模式。