The Super Tiny Compiler

前言

想要对编程技术提高一个维度，编译原理是绕不过的坎；它是 TypeScript、Babel、ESLint、Stylus、Vue、React、Marked 等开源前端框架的理论基石之一；了解编译原理能够对所接触的框架有更充分的认识。但是学习编译原理是一个比较复杂而又繁琐的过程，于是在 GitHub 上搜到了一个超级无敌小的编译器！它小到如果把所有注释删去的话，大概只剩 200 行左右的代码，麻小脏全，作者的注释也是超详细，当入门教程是非常不错的。

渔：https://git.io/compiler

我们将会用它将 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))

即输入 (add 2 2)，要求输出 add(2, 2)。虽然这并不包含 lisp 或者 C 的全部语法，但它足以向我们展示现代编译器很多要点。

设计

大多数编译器可以分成三个阶段：

1. 解析（Parsing）：将原始代码转换为一种更加抽象的表示（即 AST）。
2. 转换（Transformation）：将对这个抽象的表示做一些处理，让它能做到编译器期望它做到的事情。
3. 代码生成（Code Generation）：接收处理之后的代码表示，然后把它转换成新的代码。

解析（Parsing）

解析一般分成两个阶段：

1. 词法分析（Lexical Analysis）：接收原始代码，然后转换成一系列 Token（词法单元） ，这个过程由词法分析器（ Tokenizer 或者 Lexer）中完成的。Token 是一个数组，由代码语句的碎片组成。它们可以是数字、标签、标点符号、运算符，或者其它任何东西。

2. 语法分析（Syntactic Analysis）：把 Token 转换成一种抽象的表示，这种抽象的表示描述了代码语句中的每一个片段以及它们之间的关系。这被称为中间表示（intermediate representation）或抽象语法树（Abstract Syntax Tree， 缩写为 AST）。AST 是个深层嵌套的对象，易于处理并且携带着语法结构信息，例如：

JavaScript

// 代码语句（字符串）
(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: ')'        }
]

// Token 转换的抽象语法树（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 的部分信息。

JavaScript

// 比如下面是一个字面量 “NumberLiteral” 结点：
{
  type: 'NumberLiteral',
  value: '2'
}
// 又比如下面是一个表达式 “CallExpression” 结点：
{
  type: 'CallExpression',
  name: 'subtract',
  params: [...nested nodes go here...]
}

当转换 AST 的时候我们可以添加、移动、替代这些结点，也可以根据现有的 AST 生成一个全新的 AST；既然我们编译器的目标是把输入的代码转换为一种新的语言，所以我们将会着重于产生一个针对新语言的全新的 AST。

遍历（Traversal）

为了能处理所有的结点，所以需要遍历它们，使用的是深度优先遍历。

JavaScript

{
  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 的遍历流程是这样的：

1. Program - 从 AST 的顶部结点开始
2. CallExpression (add) - Program 的第一个子元素
3. NumberLiteral (2) - CallExpression (add) 的第一个子元素
4. CallExpression (subtract) - CallExpression (add) 的第二个子元素
5. NumberLiteral (4) - CallExpression (subtract) 的第一个子元素
6. NumberLiteral (2) - CallExpression (subtract) 的第二个子元素

如果直接在 AST 内部操作，而不是产生一个新的 AST，那么就要在这里介绍所有种类的抽象，但是目前访问（visiting）所有结点的方法已经足够了。使用“访问（visiting）”这个词的是因为这是一种模式，代表在对象结构内对元素进行操作。

访问者（Visitors）

我们最基础的想法是创建一个“访问者（visitor）”对象，这个对象中包含一些方法，可以接收不同的结点。

JavaScript

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

当遍历 AST 的时候，如果遇到了匹配 type 的结点，可以调用 visitor 中的方法。一般情况下为了让这些方法可用性更好，会把父结点也作为参数传入。

代码生成（Code Generation）

编译器的最后一个阶段是代码生成，这个阶段做的事情有时候会和转换（transformation）重叠，但是代码生成最主要的部分还是根据 AST 来输出代码。

代码生成有几种不同的工作方式，有些编译器将会重用之前生成的 token，有些会创建独立的代码表示，以便于线性地输出代码。但是接下来还是着重于使用之前生成好的 AST。

代码生成器需要知道如何“打印”AST 中所有类型的结点，然后它会递归地调用自身，直到所有代码都被打印到一个很长的字符串中。

好了！这就是编译器中所有的部分了。

当然不是说所有的编译器都像我说的这样。不同的编译器有不同的目的，所以也可能需要不同的步骤。

但你现在应该对编译器到底是个什么东西有个大概的认识了，接下来才是重点。

实现

词法分析器

JavaScript

// 从接收一个字符串开始
function tokenizer(input) {

  // 当前正在处理的字符索引
  let current = 0;

  // 输出结果集合，存放词法单元
  let tokens = [];

  // 首先创建一个 `while` 循环， `current` 变量会在循环中自增。
  // 由于 token 数组的长度是任意的，所以可能要在单个循环中多次增加 `current` 
  while (current < input.length) {

    // 在这里储存了 `input` 中的当前字符
    let 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 来说不那么重要。暂且搁置它。
    // 
    // 所以只是简单地检查是不是空格，如果是，那么直接进入下一个循环。
    const WHITESPACE = /\s/;
    if (WHITESPACE.test(char)) {
      current++;
      continue;
    }

    // 下一个 token 的类型是数字。它和之前的 token 不同，因为数字可以由多个数字字符组成，
    // 但是只能把它们识别为一个 token。
    // 
    //   (add 123 456)
    //        ^^^ ^^^
    //        Only two separate tokens
    //        这里只有两个 token
    //        
    // 当遇到一个数字字符时，将会从这里开始。
    const NUMBERS = /[0-9]/;
    if (NUMBERS.test(char)) {

      // 创建一个 `value` 字符串，用于 push 字符。
      let 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
    //
    const LETTERS = /[a-z]/i;
    if (LETTERS.test(char)) {
      let 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;
}

语法分析器

JavaScript

// 现在定义 parser 函数，接受 `tokens` 数组
function parser(tokens) {

  // 再次声明一个 `current` 变量作为指针。
  let current = 0;

  // 但是这次使用递归而不是 `while` 循环，所以定义一个 `walk` 函数。
  function walk() {

    // walk 函数里，从当前 token 开始
    let 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` 的结点。
  const 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 中对应类型的处理函数。把访问节点的操作提出来作为 visitor 层，遍历过程中按词法单元类型调用对应的 enter/exit 方法即可，算是个小技巧。

JavaScript

traverse(ast, {
  Program(node, parent) {
    enter(node, parent) {
      // ...
    },
    exit(node, parent) {
      // ...
    }
  },
  CallExpression(node, parent) {
    enter(node, parent) {
      // ...
    },
    exit(node, parent) {
      // ...
    }
  },
  NumberLiteral(node, parent) {
    enter(node, parent) {
      // ...
    },
    exit(node, parent) {
      // ...
    }
  }
});

所以定义一个遍历器，它有两个参数，AST 和 vistor。在它的里面又定义了两个函数…

JavaScript

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` 的处理函数。
    let methods = visitor[node.type];

    // 如果有，把 `node` 和 `parent` 都传入其中。
    if (methods && methods.enter) {
      methods.enter(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);
    }
     // 通知 visitor 我们要离开 node 了
    if (methods && methods.exit) {
      methods.exit(node, parent);
    }
  }

  // 最后对 AST 调用 `traverseNode`，开始遍历。注意 AST 并没有父结点。
  traverseNode(ast, null);
}

转换器

目的：接收之前构建好的 AST，然后把它和 visitor 传递进入遍历器中，最后得到一个新的 AST。

JavaScript

//  原始的 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'
//                                  |           }]
//                                  |         }]
//                                  |       }
//                                  |     }]
//                                  |   }

// 定义转换器函数，接收 AST 作为参数
function transformer(ast) {

  // 创建 `newAST`，它与之前的 AST 类似，有一个类型为 Program 的根节点。
  const newAst = {
    type: 'Program',
    body: []
  };

  // 下面的代码会有些奇技淫巧，在父结点上使用一个属性 `context`（上下文），这样就
  // 可以把结点放入他们父结点的 context 中。当然可能会有更好的做法，但是为了简单姑且这么做吧。
  //
  // 注意 context 是一个*引用*，从旧的 AST 到新的 AST。
  ast._context = newAst.body;

  // 把 AST 和 visitor 函数传入遍历器
  traverser(ast, {

    // 第一个 visitor 方法接收 `NumberLiterals`。
    NumberLiteral: {
      enter (node, parent) {
        // 创建一个新结点，名字叫 `NumberLiteral`，并把它放入父结点的 context 中。
        parent._context.push({
          type: 'NumberLiteral',
          value: node.value
        });
      },
    }

    // 下一个，`CallExpressions`。
    CallExpression: {
      enter (node, parent) {
        // 创建一个 `CallExpression` 结点，里面有一个嵌套的 `Identifier`。
        let 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 中的每个结点打印到一个很大的字符串中。

JavaScript

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

编译器

JavaScript

/**
 * 最后！创建 `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
};

去掉注释完整代码

JavaScript

function tokenizer(input) {
    let current = 0;
    let tokens = [];

    while (current < input.length) {
        let char = input[current];
        if (char === '(') {
            tokens.push({
                type: 'paren',
                value: '(',
            });

            current++;
            continue;
        }

        if (char === ')') {
            tokens.push({
                type: 'paren',
                value: ')',
            });
            current++;
            continue;
        }

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

        let NUMBERS = /[0-9]/;
        if (NUMBERS.test(char)) {
            let value = '';
            while (NUMBERS.test(char)) {
                value += char;
                char = input[++current];
            }

            tokens.push({ type: 'number', value });
            continue;
        }

        if (char === '"') {
            let value = '';
            char = input[++current];

            while (char !== '"') {
                value += char;
                char = input[++current];
            }

            char = input[++current];
            tokens.push({ type: 'string', value });
            continue;
        }
        let LETTERS = /[a-z]/i;
        if (LETTERS.test(char)) {
            let value = '';

            while (LETTERS.test(char)) {
                value += char;
                char = input[++current];
            }

            tokens.push({ type: 'name', value });
            continue;
        }

        throw new TypeError('I dont know what this character is: ' + char);
    }

    return tokens;
}

function parser(tokens) {
    let current = 0;

    function walk() {
        let token = tokens[current];
        if (token.type === 'number') {
            current++;
            return {
                type: 'NumberLiteral',
                value: token.value,
            };
        }

        if (token.type === 'string') {
            current++;
            return {
                type: 'StringLiteral',
                value: token.value,
            };
        }

        if (token.type === 'paren' &&token.value === '(') {
            token = tokens[++current];
            let node = {
                type: 'CallExpression',
                name: token.value,
                params: [],
            };

            token = tokens[++current];

            while (
                (token.type !== 'paren') ||
                (token.type === 'paren' && token.value !== ')')
            ) {
                node.params.push(walk());
                token = tokens[current];
            }

            current++;
            return node;
        }

        throw new TypeError(token.type);
    }

    let ast = {
        type: 'Program',
        body: [],
    };

    while (current < tokens.length) {
        ast.body.push(walk());
    }

    return ast;
}

function traverser(ast, visitor) {

    function traverseArray(array, parent) {
        array.forEach(child => {
            traverseNode(child, parent);
        });
    }

    function traverseNode(node, parent) {
        let methods = visitor[node.type];

        if (methods && methods.enter) {
            methods.enter(node, parent);
        }

        switch (node.type) {
            case 'Program':
                traverseArray(node.body, node);
                break;
            case 'CallExpression':
                traverseArray(node.params, node);
                break;
            case 'NumberLiteral':
            case 'StringLiteral':
                break;
            default:
                throw new TypeError(node.type);
        }

        if (methods && methods.exit) {
            methods.exit(node, parent);
        }
    }
    traverseNode(ast, null);
}

function transformer(ast) {
    let newAst = {
        type: 'Program',
        body: [],
    };
    ast._context = newAst.body;

    traverser(ast, {
        NumberLiteral: {
            enter(node, parent) {
                parent._context.push({
                    type: 'NumberLiteral',
                    value: node.value,
                });
            },
        },
        StringLiteral: {
            enter(node, parent) {
                parent._context.push({
                    type: 'StringLiteral',
                    value: node.value,
                });
            },
        },
        CallExpression: {
            enter(node, parent) {
                let expression = {
                    type: 'CallExpression',
                    callee: {
                        type: 'Identifier',
                        name: node.name,
                    },
                    arguments: [],
                };
                node._context = expression.arguments;
                if (parent.type !== 'CallExpression') {
                    expression = {
                        type: 'ExpressionStatement',
                        expression: expression,
                    };
                }
                parent._context.push(expression);
            },
        }
    });
    
    return newAst;
}

function codeGenerator(node) {
    switch (node.type) {
        case 'Program':
            return node.body.map(codeGenerator).join('\n');
        case 'ExpressionStatement':
            return (
                codeGenerator(node.expression) + ';'
            );
        case 'CallExpression':
            return (
                codeGenerator(node.callee) +
                '(' +
                node.arguments.map(codeGenerator)
                    .join(', ') +
                ')'
            );
        case 'Identifier':
            return node.name;
        case 'NumberLiteral':
            return node.value;
        case 'StringLiteral':
            return '"' + node.value + '"';
        default:
            throw new TypeError(node.type);
    }
}

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

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

参考：

• 前端工程师为什么要学习编译原理？
• 前端要以正确的姿势学习编译原理（上篇）
• https://github.com/starkwang/the-super-tiny-compiler-cn/
• http://www.ayqy.net/blog/the-super-tiny-compiler%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%90/