简介

前两日我偶然间在 GitHub 上发现了一个项目:the-super-tiny-compiler,官方介绍说这可能是一个最简的编译器。刚好之前学过「编译原理」这门课,我的兴趣一下子就上来了,简单看了一下,这个项目是将一个 Lisp 表达式转化为 C 的表达式的编译器,中间涉及词法分析、语法分析、AST 树遍历转化以及最后的代码输出环节,下面我就带大家一起来简单实现一下。

词法分析

词法分析也叫解析,每一个编译器需要做的第一步都是词法分析,具体是什么意思呢?简单来说就是把要进行转化的「源代码」拆解开,形成一个一个小部件,称为 token。比如说如下将一个 JavaScript 语句拆解开的例子:

let name = "touryung";

大致分解就可以得到一个 token 数组:[let, name, =, "touryung", ;],这样才有利于进行下一步操作。由于我们此次实现的是最简编译器,因此编译器内部只实现了对小括号、空格、数字、字符串、变量的识别。

整体框架

要实现词法分析器(解析器),首先我们需要先搭出一个框架。词法分析的整体思路就是遍历输入的字符串,然后识别不同的 token,将它保存到 token 数组

框架如下,不同部分的意思已在注释中标出:

const WHITESPACE = /\s/; // 空格const NUMBERS = /[0-9]/; // 数字const LETTERS = /[a-z]/i; // 变量function tokenizer(input) {  let current = 0; // 当前识别到的下标  let tokens = []; // token 数组  while (current < input.length) {    // 遍历    let char = input[current]; // 当前遍历到的字符    // 不同的 token 识别操作    throw new TypeError(`I dont know what this character is: ${char}`);  }  return tokens;}

搭出框架,下一步就是识别不同的 token 了。

识别括号

识别括号很简单,当遍历到当前字符是左右括号时,将一个描述当前 token 的对象放入 token 数组即可。

// 识别左括号if (char === "(") {  tokens.push({ type: "paren", value: "(" }); // 压入描述当前 token 的对象  current++;  continue;}// 识别右括号if (char === ")") {  tokens.push({ type: "paren", value: ")" });  current++;  continue;}

识别空格

这里需要注意,因为空格实际上对编程语言的语法来说是无关紧要的,这就是为什么将 Javascript 代码压缩之后仍然能够正常运行。因此当我们识别到空格的时候,不需要将其放入 token 数组进行下一步的操作。

实际上,在词法分析这一步,类似空格、注释、换行符这类不影响程序语法的 token 就不会送入下一步进行处理了。

因此,当我们识别到空格的时候,只需要继续遍历即可:

// 空格,不处理if (WHITESPACE.test(char)) {  current++;  continue;}

识别数字/变量/字符串

我为什么要把这三种 token 写在一起呢?原因是从数字开始,这三种 token 的匹配逻辑都很相似,由于匹配的 token 可能不再是单个字符,因此需要在内部继续循环直到匹配完整个 token 为止。

// 数字,循环获取数值if (NUMBERS.test(char)) {  let value = ""; // 匹配的数字赋初值  while (NUMBERS.test(char)) { // 遍历,如果还能匹配就累加    value += char;    char = input[++current];  }  tokens.push({ type: "number", value }); // 压入描述当前 token 的对象  continue;}// 变量,和 number 类似if (LETTERS.test(char)) {  let value = "";  while (LETTERS.test(char)) {    value += char;    char = input[++current];  }  tokens.push({ type: "name", 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;}

其中需要注意,识别字符串类似上面两种,但是也有两点不同:

  1. 在字符串识别时需要跳过前后的引号,只匹配中间具体的值;
  2. 在中间进行遍历的时候结束条件是匹配到末尾的引号。

有人可能会问,如果跳过的前后的引号以后要怎么知道它是字符串呢,这时候压入数组的 token 描述对象作用就出来了,它有一个 type 属性可以指定当前 token 的类型。

小总结

至此,词法分析的工作就做完了,其实相对来说还是很好懂的,那么能不能直观的观察词法分析输出的 token 数组是什么样子的呢?当然可以,只需要编写一个样例测试一下就行了,比如:

let source = "(add 2 (subtract 4 2))"; // 源代码let tokens = tokenizer(source);console.log(tokens);

这是一个计算 2+(4-2) 的 Lisp 语句,将它作为输入得到的 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(抽象语法树),既然涉及到树结构,那么这个步骤自然少不了递归操作。

整体框架

通用的,语法分析部分也需要先搭出一个框架。整体思路就是遍历 token 数组,递归地构建 AST 树,框架如下:

function parser(tokens) {  let current = 0;  function walk() {    let token = tokens[current];    // 将不同的 token 转化为 AST 节点    throw new TypeError(token.type);  }  let ast = {    // 此为 AST 树最外层结构,是固定的    type: "Program",    body: [],  };  while (current < tokens.length) {    // 遍历 token 数组,构建树结构    ast.body.push(walk());  }  return ast;}

构建数字和字符串节点

这两种节点的构建较为简单,直接返回描述节点的对象即可:

// 构建整数节点if (token.type === "number") {  current++;  return {    type: "NumberLiteral",    value: token.value,  };}// 构建字符串节点if (token.type === "string") {  current++;  return {    type: "StringLiteral",    value: token.value,  };}

构建函数调用节点

懂 Lisp 的人都知道,在 Lisp 中括号是精髓,比如函数调用类似于这种形式: (add 1 2)。因此我们需要以括号来进行识别,具体的代码如下:

if (token.type === "paren" && token.value === "(") {  // 左括号开始  token = tokens[++current]; // 跳过左括号  let node = {    // 函数调用节点    type: "CallExpression",    name: token.value,    params: [],  };  token = tokens[++current]; // 跳过 name  // 只要不是右括号,就递归收集参数节点  while (!(token.type === "paren" && token.value === ")")) {    node.params.push(walk()); // 添加参数    token = tokens[current];  }  current++; // 跳过右括号  return node;}

这里面需要注意的点是,某一个参数也可能是函数调用的结果,因此在解析参数时需要递归调用 walk 函数。

还有另外一点值得一提,那就是我们多次用到了这种代码结构:

if (value === "(") {  // ...  while (!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"            }          ]        }      ]    }  ]}

遍历并转化 AST 树

此时我们已经得到了一棵 AST 树,编译器之所以能够将源代码转化为目标代码实际上就可以视作将源 AST 树转化为目标 AST 树,要实现这种转化过程,我们就需要对树进行遍历,然后对对应的节点进行操作。

遍历树

我们从上面可以看出,AST 树中的 body 属性和函数调用的参数实际上都是数组类型的,因此我们首先需要定义对数组类型的遍历方法,很简单,只需要遍历数组中的每个元素分别进行遍历就行了:

// 访问(参数)数组function traverseArray(array, parent) {  array.forEach((child) => traverseNode(child, parent));}

当遍历到具体的节点时,我们就需要调用此节点类型的 enter 方法来进行访问(转化 AST)操作,不同类型的节点 enter 方法是不一样的。

function traverseNode(node, parent) {  let method = visitor[node.type]; // 去除当前类型的方法  if (method && method.enter) {    // 执行对应 enter 方法    method.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);  }}

可能有人又要问,为什么执行 enter 方法时第二个参数需要传入父节点呢?这其实和后面的实际转化部分的逻辑相关,我们就放到后面来进行解释。

转化 AST 树整体框架

一样的,我们可以首先搭出大体的框架,具体的同类型的节点访问(转化)方法后面再说。这里的转化思路就比较重要了:我们要如何在遍历旧的 AST 树时能将转化后的节点加入新的 AST 树?

这里的实现思路大体分为以下几步:

  1. 在旧的 AST 树中加入一个 _context 上下文属性,指向新的 AST 树的数组节点
  2. 当遍历旧 AST 数组节点的子元素时,将转化后的子元素放入它的父元素的 _context 属性中
  3. 根据 JavaScript 引用类型的特点,此时就实现了将转化和的节点放入新 AST 树的目的。

在图中表示出来大概如下:

我相信这已经回答了上面执行 enter 方法时为什么第二个参数需要传入父节点的问题。

function transformer(ast) {  let newAst = {    // 新 AST 树的最外层结构    type: "Program",    body: [],  };  // _context 用于遍历旧子节点时压入新 ast  ast._context = newAst.body;  let visitor = {    // 不同类型的节点访问(转化)方法  };  traverser(ast, visitor); // 开始遍历旧 AST 树  return newAst;}

数字和字符串的转化

{  NumberLiteral: {    enter(node, parent) {      parent._context.push({ // 压入新 AST 树        type: "NumberLiteral",        value: node.value,      });    },  },  StringLiteral: {    enter(node, parent) {      parent._context.push({        type: "StringLiteral",        value: node.value,      });    },  }}

函数调用节点的转化

函数调用节点特殊一点,由于它的参数可以视作它的子节点,因此需要将当前节点的 _context 属性指向新 AST 树对应的参数数组。

还有一点特殊的是,如果当前的函数调用不是嵌套在别的函数调用中,那么就可以再加一个 ExpressionStatement 信息,表示当前节点是一整个语句,比如 (add 2 (subtract 4 2)) 内层的括号就不能称作一个完整的语句,因为它是作为另一个函数的参数形式存在的。

{  CallExpression: {    enter(node, parent) {      let expression = { // 新 AST 树的函数调用节点        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);    },  },}

小总结

截至目前,我们已经完成了 AST 树的遍历和转化工作,这部分的工作量不小,但是也是整个编译中最精华的部分,如果顺利的话,我们现在可以得到如下转化后的新 AST 树:

{  "type": "Program",  "body": [    {      "type": "ExpressionStatement",      "expression": {        "type": "CallExpression",        "callee": {          "type": "Identifier",          "name": "add"        },        "arguments": [          {            "type": "NumberLiteral",            "value": "2"          },          {            "type": "CallExpression",            "callee": {              "type": "Identifier",              "name": "subtract"            },            "arguments": [              {                "type": "NumberLiteral",                "value": "4"              },              {                "type": "NumberLiteral",                "value": "2"              }            ]          }        ]      }    }  ]}

这就是对应 C 代码的 AST 树的结构了,将它与之前 Lisp 的 AST 树相比,还是可以看出很多不同的。

代码生成

最后,就是最激动人心的时刻了,生成目标代码!这一步相对轻松,根据上一步生成的 AST 树,对它进行递归遍历并生成最终的代码:

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

最终,我们实现了从 Lisp 的示例代码 (add 2 (subtract 4 2)) 到 C 语言代码 add(2, subtract(4, 2)) 的转化。

大总结

本篇文章带大家从零实现了一个编译器最基本的功能,涉及了词法分析、语法分析、AST 树遍历转化等内容。编译原理听似高深(确实高深),但是基础的部分就是那些内容,啥词法分析语法分析的,最终都会回归到对字符串的处理。

我研究的方向是前端,那别人可能认为平时可能都不会涉及到编译原理的内容,但是实际上一旦深入研究的话,类似 Babel 将 ES6+ 的代码转化为 ES5 之类的工作实际上都是编译器做的工作,还有最近很火的 esbuild,只要涉及到代码的转化,肯定都会涉及编译,甚至 Vue 内部也有一个编译器用于模板编译。

说了这么多,本意还是希望大家在平时的学习中要多多涉猎新领域的知识,扩展自己的技能面,这样才能提高自己的技术视野和上限。

最后,推荐一个我最近在学习的最简 Vue 模型项目,也可以在这里面学习到 Vue 中模板编译的原理。

https://github.com/cuixiaorui/mini-vue

(全文终)