请注意，本文编写于 1074 天前，最后修改于 1074 天前，其中某些信息可能已经过时。

不知不觉已经写了两年代码了，每过一阵子回头看看原来的代码，都觉得有不少值得改进的地方，这真是一件高兴的事。
原来我从来不会关心编译原理这种东西，感觉离自己很远，但做项目的过程中，操作了一些 AST，杂七杂八的接触过一些相关的知识，又发现了一个很好的教程，就跟着写了一遍，颇有收获。
在此把大概的步骤和思路记下来。

教程： Create Your Own Compiler
代码： https://github.com/Mereithhh/simple-compiler

目标

我们的目标是用 js 写一个编译器，把 lisp 编译成 js 代码。

可以编译成下面的 js 代码：

用起来可能是这样的：

const compiler = require("./compiler");
const input = "(add 123 ( sub 4 3))"
const output = compiler(input);
// add(123, sub(4, 3));
const add = (a,b) => a + b;
const sub = (a, b) => a - b;
const result = eval(output)
console.log(result)
// 124

概述

要实现这样一个编译器，大概要 4 步：

• 词法分析
• 语法分析
• AST转换
• 代码生成

我们一步一步来。

词法分析

这步的目的是解析我们传入代码字符串中的有效单词，并给他们分类。我们的输入是：

这步完成后，就会输出这样的数组：

[
  {
    "type": "paren",
    "value": "("
  },
  {
    "type": "name",
    "value": "add"
  },
  {
    "type": "number",
    "value": "123"
  },
  {
    "type": "paren",
    "value": "("
  },
  {
    "type": "name",
    "value": "sub"
  },
  {
    "type": "number",
    "value": "4"
  },
  {
    "type": "number",
    "value": "3"
  },
  {
    "type": "paren",
    "value": ")"
  },
  {
    "type": "paren",
    "value": ")"
  }
]

要想实现这样的效果，我们只需要简单从头到尾捋一遍我们的输入，根据不同的情况判断就好了，大概是这样的：

const PATTERNS = [
  "(",
  ")"
]
const NUMBER = /[0-9]/;
const LETTER = /[a-zA-Z]/;
const SPACE = /\s/;

module.exports = function tokenizer(input) {
  const tokens = [];
  let current = 0;
  while (current < input.length) {
    let char = input[current];
    if (PATTERNS.includes(char)) {
      tokens.push({
        type: "paren",
        value: char,
      });
      current++;
      continue;
    }
    if (NUMBER.test(char)) {
      let value = "";
      while (NUMBER.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({
        type: "number",
        value,
      });
      continue;
    }

    if (LETTER.test(char)) {
      let value = "";
      while (LETTER.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({
        type: "name",
        value,
      });
      continue;
    }

    if (SPACE.test(char)) {
      current++;
      continue;
    }


    throw new Error(`unknow charactor: ${char}`)
  }
  return tokens;
}

语法分析

语法分析是把我们的上一步获得的词组，重新组合成树状的结构，也就是 AST。 处理好之后，会得到这样的树：

{
  "type": "Program",
  "body": [
    {
      "type": "CallExpression",
      "name": "add",
      "params": [
        {
          "type": "NumberLiteral",
          "value": "123"
        },
        {
          "type": "CallExpression",
          "name": "sub",
          "params": [
            {
              "type": "NumberLiteral",
              "value": "4"
            },
            {
              "type": "NumberLiteral",
              "value": "3"
            }
          ]
        }
      ]
    }
  ]
}

这一步实现的核心思路是递归，定义一个当前下标的变量，和一个递归执行的函数。 在递归执行的函数里分别处理不同类型的数据，如果遇到了符号类型的数据，那就递归调用这个函数。不废话直接上代码：

module.exports = function parser(tokens) {
  let current = 0;
  // walk 函数每次运行完，都增加一个指针，以被下一次 walk
  function walk() {
    let token = tokens[current];
    if (token.type === 'number') {
      current++;
      return {
        type: 'NumberLiteral',
        value: token.value,
      }
    }

    if (token.type === 'paren' && token.value === '(') {
      // 下一个 token 才是函数名称
      token = tokens[++current];
      const expression = {
        type: "CallExpression",
        name: token.value,
        params: []
      }
      token = tokens[++current];
      while (token.value !== ")") {
        expression.params.push(walk())
        token = tokens[current]
      }
      current++;
      return expression;
    }


    throw new TypeError(`Unknow token: ${token.type}`)
  }

  const ast = {
    type: 'Program',
    body: [walk()],
  };

  return ast;
}

AST转换

上一步我们得到了 lisp 语言得 AST 树，现在我们要把这个树转换成 js 的 AST 树。
核心思路是遍历整个树，在遍历过程中针对每一种节点类型，使用不同的函数转化成另一种树，并且要定义一个位置变量，来把转换后的节点插入到新树中适合的位置。代码如下：

const traverse = require("./traverse");

module.exports = function transformer(originalAST) {
  const jsAST = {
    type: 'Program',
    body: [],
  };

  let position = jsAST.body;

  traverse(originalAST, {
    NumberLiteral(node) {
      position.push({
        type: "NumericLiteral",
        value: node.value,
      })
    },
    CallExpression(node, parent) {
      let expression = {
        type: "CallExpression",
        callee: {
          type: "Identifier",
          name: node.name
        },
        arguments: []
      };
      const prevPosition = position;
      position = expression.arguments;
      if (parent.type !== "CallExpression") {
        expression = {
          type: "ExpressionStatement",
          expression,
        };
      };
      prevPosition.push(expression)
    }
  })

  return jsAST;
}

其中遍历函数的实现如下：

module.exports = function traverse(ast, visitors) {
  function walkNode(node, parent) {
    const method = visitors[node.type];
    if (method) method(node, parent);
    if (node.type === "Program") walkNodes(node.body, node);
    else if (node.type === "CallExpression") walkNodes(node.params, node);
  }

  function walkNodes(nodes, parent) {
    nodes.forEach(node => walkNode(node, parent))
  }
  walkNode(ast, null)
}

代码生成

这步很简单，只要把我们需要的 jsAST 生成成相应的代码就好了，因为我们的编译器支持的语法非常简单（简陋），所以代码也很简洁🫤

module.exports = function generateCode(node) {
  if (node.type === "NumericLiteral") {
    return node.value;
  }
  if (node.type === "Identifier") {
    return node.name;
  }
  if (node.type === "CallExpression") {
    // name(arg1, arg2, arg3)
    return `${generateCode(node.callee)}(${node.arguments.map(generateCode).join(", ")})`
  }
  if (node.type === "ExpressionStatement") {
    return `${generateCode(node.expression)};`
  }
  if (node.type === "Program") {
    return node.body.map(generateCode).join("\n")
  }
}

总结

跟着教程走下来，发现编译器（入门）并没有我想的那么复杂，写一个最基础的编译器并不需要多高深的算法，代码也没有多难懂。 简洁的代码又非常巧妙，很少的代码实现了需要的功能。 其中递归是个很重要的应用，合理的利用递归可以写出有些“魔力”的代码。

实际上在平时的开发中，我发现“抽象”是一种非常重要的能力，一个会合理抽象的程序员，可以用很少的代码完成很强的功能，同时具有很强的扩展性和鲁棒性。

之前我看过“计算机程序的构造与解释”这门网课，结合今天的代码又有了些新的思考，很推荐这门课，有空我应该会再看一遍👀