基于JS实现一个小型编译器

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

前言

the-super-tiny-compiler 是一个代码行数只有不到 200 行的超级小型的 compiler，但通过这个 compiler 能学习到最基础的 compile 原理，包括 babel 也是基于这样的原理来进行开发的。

仓库本身的例子是将一组 lisp 风格的函数语法编译成了 C 风格的函数语法，举例子来说:

LISP 风格	C 风格
2+2	(add 2 2)	add(2,2)
4-2	(subtract 4 2)	substract(4, 2)
2 + (4 - 2)	(add 2 (substract 4 2))	add(2, (substract(4, 2)))

这就大概是这次 compiler 需要完成的事情，可能看上去语法不是很完整，但是也能够演示现代编译器的主要部分思想了。

大多数的 Compilers 都会把编译过程分成三个主要的过程: parse、transform 以及 code generate：

parse 主要是将源码转换成一种更抽象的代码表达
transform 则是将上面抽象的表达进行任意 compiler 想进行的操作
code generate 将 transform 处理之后的代码生成一种新的代码

Parse

parse 主要分为两个步骤: 词法分析以及语法分析。

词法分析将源码根据表达切分一个个的 tokens，tokens 是一组用来描述单独语法的对象，可以是 numbers、labels、punctuation、operators 等
语法分析则是将词法分析生成的 tokens 进行重新编排得到一个叫做抽象语法树 (AST)的结构，AST 是一种易于使用且能展示完整信息的嵌套树状结构。

例如前面提到的 add 2 (subtract 4 2) 表达式被词法分析处理之后生成的 tokens 大概是:

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

Transform

transform 主要就是拿到 parse 得到的抽象语法树，并基于此做出一些修改。tranform 这个过程既可以基于当前语言的风格去修改 ast 也可以使用一种新的语言风格。

下面基于前面的 ast 结构来展示 transform 这个过程的工作流程。

可以看到，ast 里面的元素看起来都很相似，这些元素组成了 ast 的子结点，这些子结点的数据结构类型描述了代码中的一个单独的部分(例如变量、声明语句，表达式等等)。

例如上面提到的类型是 NumberLiteral 的节点:

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

或者更复杂一点的子节点类型:

{
    type: 'CallExpression',
    name: 'substract',
    params: [...nested nodes here ...],
}

在 transfrom 这个过程中，我们可以通过增/删/改来操作抽象语法树结点，或者可以直接基于当前的抽象语法树创建一个新的出来。

既然这里我们的目标是将输入的代码转换成一种新的语言风格的代码(Lisp -> C)，所以这里会创建一个针对新语言的全新 AST 出来。

因此这里我们需要明确一下修改 AST 的操作:

Traversal(遍历)

为了能处理所有的结点，我们可以用深度优先搜索对其进行遍历:

{
  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'
      }]
    }]
  }]
}

遍历流程是这样的:

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

如果直接在 ast 内部操作而不是产生一个新的 ast，可能就需要介绍所有的种类的抽象。但目前来看，访问所有结点的方法已经足够了。

访问(visiting) 这个词代表一种在对象结构内对元素进行操作的模式。

Visitors(访问)

这里我们可以创建一个 visitor 对象，这个对象包括一些方法用于接收不同的结点。

例如:

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

因此当我们遍历 ast 的时候，如果匹配到了对应 type 的结点，可以调用 visitor 中的方法来处理。

Code generate

Compiler 的最后一个阶段就是 generate, 这个阶段做的事情可能会和 transformation 重叠，但是代码生成最主要的部分还是根据 AST 来输出代码。

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

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

代码实现

以上就是 Compiler 所有的部分了，但并不是所有的 Compiler 都是这样，不同的 compiler 目的不同，所以也可能需要不同的步骤。

接下来就开始代码的编写:

词法分析器(tokenizer)

按照前面的理论分析，我们一步先进行 parser 这个阶段里面的词法分析器(tokenizer)。

这个函数接收一个字符串，然后将其分割成由 token 组成的数组:

ex:

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

因此可以编写这样的一个函数:

const tokenizer = (input) => {
  const tokens = [];
  let current = 0;
  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;
    }

    // 空格目前不需要处理
    if (/\s/.test(char)) {
      current++;
      continue;
    }

    // 处理数字
    if (/[0-9]/.test(char)) {
      let value = '';
      // 一直遍历直到遇到非数字的字符
      while (/[0-9]/.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({
        type: 'number',
        value,
      })
      continue;
    }

    // 处理字符串
    if(/[a-z]/i.test(char)) {
      let value = '';

      while(/[a-z]/i.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({
        type: 'name',
        value,
      });

      continue;
    }

    // 如果存在匹配不上的 token 就抛错
    throw new Error(`Unknown token: ${char}`);
  }
  return tokens;
}

语法分析器(parser)

词法分析器接收语法分析得到的 token 数组，然后将其转换成 AST 结构。

例如:

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

const parser = (tokens) => {
  let current = 0;
  
  const walk = () => {
    const token = tokens[current];
    // 如果是 number 类型的结点，返回一个新的 ast 节点即可
    if (token.type === 'number') {
      current++;
      return {
        type: 'NumberLiteral',
        value: token.value,
      }
    }

    // 接下来检查 CallExpression 类型，先从左圆括号开始
    if (
      token.type === 'paren' &&
      token.value === '('
    ) {
      // 跳过左圆括号
      token = tokens[++current];
      // 首先会创建一个 CallExpression 的根节点，然后 name 设置成当前的 token.value
      // 因为左圆括号后的 token 一定是函数名称
      const node = {
        type: 'CallExpression',
        name: token.value,
        params: [],
      };

      // 这里再跳一次函数名称
      token = tokens[++current];

      // 通过循环遍历接下来的每个 token，直到遇到右圆括号
      // 这些 token 会成为 `CallExpression` 的  `params`

      // 以 lisp 风格的代码来说: (add 2 (substract 4 2))
      
      while (
        token.type !== 'paren' ||
        (token.value !== ')' && token.type === 'paren')
      ) {
        node.params.push(walk());
        token = tokens[current];
      }
      current++;
      return node;
    }
    throw new Error(`Unknown token type: ${token.type}`);
  }

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

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

  return ast;
}

遍历器(visitors)

通过语法分析得到 ast 之后，接下来需要一个遍历器 (visitors) 去遍历结点。然后当遇到某个类型的结点的时候，可以调用 visitors 中对应的类型处理函数:

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

因此我们的代码可以这样写:

const traverser = (ast, visitor) => {

  // 用于对数组中的每个元素都调用 traverseNode 函数
  const traverseArray = (array, parent) => {
    array.forEach((child) => {
      traverseNode(child, parent);
    });
  }

  // 函数接收一个 node 以及其父结点作为参数
  // 这个结点会被传入到 visitor 中相应的处理函数那里
  const traverseNode = (node, parent) => {
    const method = visitor[node.type];
    if (method) {
      method(node, parent);
    }
    // 对不同的结点分开处理
    switch (node.type) {
      case 'Program':
        traverseArray(node.body, node);
        break;

      case 'CallExpression':
        traverseArray(node.params, node);
        break;
        
      // 这种情况下就没有子节点了，直接 break 出去
      case 'NumberLiteral':
        break;
      
      default:
        throw new Error(`Unknown node type: ${node.type}`);
    }
  }

  traverseNode(ast, null);
}

转换器(transformer)

转换器配合上面的遍历器来一起使用，它接收之前构建好的 ast，然后将其和 visitor 一起传入遍历器中，从而得到一个全新的 AST 出来。

原始的 AST 结构为( add 2 (subtract 4 2) ):

{
  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 结构为( add(2, subtract(4, 2)) ):

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

接下来我们可以这样编写对应的转换器代码:

const transformer = (ast) => {
  const newAst = {
    type: 'Program',
    body: [],
  }

  ast._context = newAst.body;

  traverser(ast, {
    // 处理 NumberLiteral 类型
    NumberLiteral: (node, parent) => {
      parent._context.push({
        type: 'NumberLiteral',
        value: node.value,
      });
    },

    // 处理 CallExpression 类型
    CallExpression: (node, parent) => {

      // 初始化一个 CallExpression 的新节点
      // 里面放个嵌套的 Identifier 节点
      const expression = {
        type: 'CallExpression',
        callee: {
          type: 'Identifier',
          name: node.name
        },
        arguments: [],
      };

      node._context = expression.arguments;

      // 看看父节点是不是 CallExpression
      if (parent.type !== 'CallExpression') {

        // 如果不是的话，就将 CallExpression 节点包在一个叫 `ExpressionStatement` 的语句节点里
        // 这么做是因为 top level 的 CallExpression 在 JavaScript 中也可以被当成是声明语句
        expression = {
          type: 'ExpressionStatement',
          expression,
        };
      }

      // 最后我们把 CallExpression 放入父结点的 context 中
      parent._context.push(expression);
    }
  });

  return newAst;
}

代码生成器(code generator)

代码生成器同样是个递归函数，最后会将 AST 中的每个结点打印到一个大的字符串中:

const codeGenerator = (node) => {
  switch (node.type) {
    // 如果是 Program，则会遍历 'body' 属性中的每个结点
    // 并且对这些结点进行递归 codeGenerator,再把结果打印进新的一行里面
    case 'Program':
      return node.body.map(codeGenerator).join('\n');
    
    // 对于 ExpressionStatement 对 expression 属性进行递归调用，并加个分号
    case 'ExpressionStatement':
      return `${codeGenerator(node.expression)};`;
    
    // 对于 CallExpression 对 callee 属性进行递归调用，接着加上(括号
    // 然后对 arguments 属性进行递归调用，并加上)括号
    case 'CallExpression':
      return `${codeGenerator(node.callee)}(${node.arguments.map(codeGenerator).join(', ')})`;

    // 对于 Identifier,直接返回 name
    case 'Identifier':
      return node.name;
    
    // 对于 NumberLiteral,直接返回 value
    case 'NumberLiteral':
      return node.value;
    
    default:
      throw new Error(`Unknown node type: ${node.type}`);
  }
}

编译器(Compiler)

到这一步，基本上所有的流程就已经完成了，我们可以创建一个 compiler 函数，通过调用上面的函数就可以完成整个 compiler 的工作了:

input => tokenizer => tokens
tokens => parser => ast
ast => transformer => newAst
newAst => generator => output

代码只需要以下简单几步即可:

const compiler = (input) => {
  const tokens = tokenizer(input);
  const ast = parser(tokens);
  const newAst = transformer(ast);
  
  return codeGenerator(newAst);
}

我们可以输入前面的几组测试例子，能保证得到的结果是正确的。