摘要：手把手教你實現(xiàn)一個簡單的編譯器概述今天我們將學習開發(fā)一個編譯器，但是呢，這個編譯器并不是說什么都能都編譯，它只是一個超級小的編譯器，主要用于說明編譯器的一些基本的原理。這被稱為中間表示或抽象語法樹。

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

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

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

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

那么在lisp語言中它可能長這樣子：

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

而在C語言中它長這個樣子：

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

相當簡單吧？

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

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

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

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

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

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

詞法分析。 詞法分析通常是使用一個標記器(或詞法分析器)將原始代碼拆分成叫做標記的東西。而標記是一些微小的對象組成的數(shù)組，它們通常用來描述一些孤立的語法片段，它們可以是數(shù)字、標簽、標點符號、操作符等等。

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

對于下面的語法：

(add 2 (subtract 4 2))

標記可能長下面這個樣子：

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

在解析之后，編譯器的下一步鄹是轉(zhuǎn)換。 同樣，這不過就是將最后一步的抽象語法樹(AST)拿過來對它做一定的改變。這種改變多種多樣，可以是在同一種語言中進行改變，也可以直接將抽象語法樹轉(zhuǎn)換成另外一種完全不同的新語言。

讓我們來看看我們將如何轉(zhuǎn)換一個抽象語法樹(AST)。

你可能已經(jīng)注意到，我們的抽象語法樹里面有一些非常類似的元素。 這些元素對象有一個type屬性。 這每一個對象元素都被稱為一個AST節(jié)點。 這些節(jié)點上定義的屬性用于描述AST樹上的一個獨立部分。

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

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

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

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

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

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

為了瀏覽所有這些節(jié)點，我們需要能夠遍歷它們。 這個遍歷過程是對AST的每個節(jié)點進行深度優(yō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"
      }]
    }]
  }]
}

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

Program - 從AST樹的頂層開始。

CallExpression (add) - 移動到Program的body屬性的第一個元素。

NumberLiteral (2) - 移動到CallExpression(add)的第一個參數(shù)。

CallExpression (subtract) - 移動到CallExpression(add)的第二個參數(shù)。

NumberLiteral (4) - 移動到CallExpression(subtract)的第一個參數(shù)。

NumberLiteral (2) - 移動到CallExpression(subtract)的第二個參數(shù)。

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

使用“訪問”這個詞的原因是因為這個詞能夠很好的表達如何在對象結(jié)構(gòu)上操作元素。

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

比如下面這樣：

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

當我們遍歷AST的時候，一旦我們碰到一個與指定類型相匹配的節(jié)點，我們就會調(diào)用訪問者對象上的方法。

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

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

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

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

當我們往下遍歷的時候，我們會遇到最終的分支。 當我們訪問完所有的分支后我們退出。 所以向下遍歷樹，我們進入節(jié)點，然后向上回溯的時候我們退出節(jié)點。

 -> 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)

為了支持這種方式，我們的訪問者對象需要改成下面這個樣子：

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

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

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

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

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

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

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

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

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

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

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

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

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

我們的tokenizer接收一個代碼字符串， 然后接下來做兩個事情：

function tokenizer(input) {

  // 一個current變量，類似于游標，用于跟蹤我們在代碼字符串中的位置
  let current = 0;

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

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

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

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

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

      // 接著我們增加current變量，也就是移動游標
      current++;

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

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

    // 接著，我們檢查空白格。 這很有趣，因為我們關(guān)注空白格是因為它將字符串分隔開，但是我們并不需要將空白格存為標記,我們
    // 可以直接扔掉它，所以這里我們僅僅檢查空白格是否存在，如果它存在我們就進入下一輪循環(huán)

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

    // 下一個類型的標記是數(shù)字，這和我們前面見到的不同，因為一個數(shù)字可能是任意個字符組成，并且我們需要捕獲整個字符序列作為一個標記
    //
    //   (add 123 456)
    //        ^^^ ^^^
    //  比如上面的就只有兩個獨立的數(shù)字標記
    //
    // 所以當我們遇到序列中的第一個數(shù)字的時候開始進一步處理.
    let NUMBERS = /[0-9]/;
    if (NUMBERS.test(char)) {

      // 我們在這里面創(chuàng)建了一個value字符，用于拼接數(shù)字字符
      let value = "";

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

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

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

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

      // 我們將忽略雙引號，因為我們關(guān)心的是雙引號包裹的文本.
      char = input[++current];

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

      // 忽略右雙引號，同理，因為我們關(guān)心的是雙引號包裹的文本.
      char = input[++current];

      // 創(chuàng)建類型為string的標記，并放進tockens數(shù)組
      tokens.push({ type: "string", value });

      continue;
    }

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

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

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

      continue;
    }

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

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

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

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

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

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

function parser(tokens) {

  // 同樣我們維持一個current變量用作游標
  let current = 0;

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

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

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

      // 如果有，我們移動游標
      current++;

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

    // 如果我們有string類型的標記，我們會和數(shù)字類型類似，創(chuàng)建一個叫做“StringLiteral”的AST節(jié)點
    if (token.type === "string") {
      //同樣移動游標
      current++;

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

    // 接下來我們查找CallExpressions. 我們是通過左括弧來開始這個過程的
    if (
      token.type === "paren" &&
      token.value === "("
    ) {

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

      // 我們創(chuàng)建一個叫做CallExpression的基礎(chǔ)節(jié)點，并且將節(jié)點的名字設(shè)置為當前標記的value屬性，
      // 因為左括弧標記的下一個標記就是函數(shù)名字
      let node = {
        type: "CallExpression",
        name: token.value,
        params: [],
      };

      // 我們移動游標，忽略掉name標記，因為函數(shù)名已經(jīng)存起在CallExpression中了
      token = tokens[++current];

      // 然后現(xiàn)在我們遍歷每一個標記，找到CallExpression的參數(shù)直至遇到右括弧
      //
      // 現(xiàn)在，這里就是遞歸出場的地方了，為了避免陷入無限的嵌套節(jié)點解析，我們采用遞歸的方式來搞定這個事情
      //
      // 為了更好的解釋這個東西，我們以我們的Lisp代碼舉例，你可以看到，add的參數(shù)是一個數(shù)字以及一個嵌套的CallExpression，
      // 這個嵌套的函數(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: ")"        }, <<< 右括弧
      //   ]
      //
      // 我們將依賴于嵌套的walk函數(shù)來增加我們的游標

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

      // 最后，我們需要最后一次移動游標用于忽略右括弧
      current++;

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

    // 同樣，如果我們沒有識別出標記的類型，我們也會拋出一個錯誤
    throw new TypeError(token.type);
  }

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

  // 然后我們要啟動我們的walk函數(shù), 將AST節(jié)點放入根節(jié)點的body數(shù)組里面
  //
  // 我們在循環(huán)里面做這個是因為，我們可能會遇到連著的多個函數(shù)調(diào)用，比如說像這樣的：
  //
  //   (add 2 2)
  //   (subtract 4 2)
  //啟動walk
  while (current < tokens.length) {
    ast.body.push(walk());
  }

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

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

現(xiàn)在我們已經(jīng)有了我們的AST，我們想要一個訪問者可以訪問不同的節(jié)點，無論何時匹配到對應的節(jié)點類型的時候，我們都可以調(diào)用訪問者上的方法。
所以我們定義一個旅行者函數(shù)，這個函數(shù)接收兩個參數(shù)，第一個參數(shù)為AST樹，第二個參數(shù)是一個訪問者。這個訪問者需要實現(xiàn)不同類型的AST節(jié)點需要調(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ù)實現(xiàn)

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

function traverser(ast, visitor) {

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

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

    // 我們首先檢查訪問者匹配類型的方法
    let methods = visitor[node.type];

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

    // 接下來我們會根據(jù)節(jié)點類型來把事情劃分開來
    switch (node.type) {

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

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

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

      // 并且再一次，如果沒有識別出對應的節(jié)點類型，就拋出錯誤
      default:
        throw new TypeError(node.type);
    }

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

  // 最后，我們啟動traverser，這是通過調(diào)用traverseNode實現(xiàn)的，并且traverseNode第二個參數(shù)是null，因為定級節(jié)點本身就沒有父節(jié)點.
  traverseNode(ast, null);
}

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

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

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

比如以前面那個例子為例，得到的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ù)的具體實現(xiàn)如下：

function transformer(ast) {

  // 我們將創(chuàng)建一個新的AST(即newAst)，它和我們原來的AST類似，有一個Program根節(jié)點
  let newAst = {
    type: "Program",
    body: [],
  };

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

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

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

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

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

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

        // 接下來，我們在原始的CallExpression節(jié)點上定義一個新的context用于引用
        // expression變量上的arguments屬性
        // 這樣我們可以加入?yún)?shù)
        node._context = expression.arguments;

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

          // 我們將用一個ExpressionStatement節(jié)點包裹這個CallExpression節(jié)點
          // 這么做是因為頂級CallExpression節(jié)點實際上就是statement
          // 也就是說，如果某個CallExpression節(jié)點的父節(jié)點不是CallExpression節(jié)點
          // 那么這個CallExpression節(jié)點應該就是函數(shù)聲明
          expression = {
            type: "ExpressionStatement",
            expression: expression,
          };
        }

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

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

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

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

newAst => generator   => output

5.3.1 codeGenerator的實現(xiàn)

function codeGenerator(node) {

  // 我們會根據(jù)節(jié)點的type類型來將事情分別處理
  switch (node.type) {

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

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

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

    // 對于標識符，我們將返回節(jié)點的名字
    case "Identifier":
      return node.name;

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

    // 對于StringLiteral節(jié)點，我們用引號將它的value屬性值包裹起來
    case "StringLiteral":
      return """ + node.value + """;

    // 如果沒有識別節(jié)點，我們將拋出錯誤
    default:
      throw new TypeError(node.type);
  }
}

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

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

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

最后作為一個模塊，我們希望別人去使用它，因為我們的每個函數(shù)都是相對獨立的一個功能模塊，所以我們將這里面的每個函數(shù)都導出：

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

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

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