文章详情

登录

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

选择考试省份

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-04-02 19:55

关注

本文内容基于仓库源码进行学习

最近在研究一些构建侧的东西，在翻 babel 官网的时候看到了这样一段话:

For an awesome tutorial on compilers, check out the-super-tiny-compiler, which also explains how Babel itself works on a high level.

出于学习的心态，去翻了一下这个仓库源码，以下是笔者的一些学习的记录，希望看完之后能对你理解 babel 的工作原理有一些帮助~

前言

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

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

例如前面提到的 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'
      }]
    }]
  }]
}

遍历流程是这样的:

如果直接在 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 的工作了:

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

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

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

总结

至此一个 tiny-compiler 就被造出来了，babel 的编译流程也是基于此来完成，因为 babel 本身是个 source to source 的 compiler，整个流程也是分为 parser -> transform -> code generate 这三个步骤完成，具体可以参考 

以上就是基于JS实现一个小型编译器的详细内容，更多关于JS编译器的资料请关注编程网其它相关文章！

阅读原文内容投诉

免责声明：

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析（完整版）

    难度     813人已做
    查看

  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看

  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看

  • 2024年上半年软考高项第一、二批次真题考点汇总（完整版）

    难度     435人已做
    查看

  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机

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

前端开发2024-04-02

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

前端开发2023-06-30

基于Python3编写一个GUI翻译器

前端开发2024-04-02

基于JS编写一个看字说颜色小游戏

前端开发2024-04-02

用JavaScript实现一个编译器

前端开发JavaScript编译器2024-12-03

基于JS实现一个简单的投票demo

前端开发2024-04-02

基于vue3实现一个抽奖小项目

前端开发2023-01-28

基于原生CSS+JS实现一个标签输入框

前端开发2024-04-02

基于JS实现Android,iOS一个手势动画效果

前端开发2022-06-06

基于C#实现一个温湿度监测小工具

前端开发2023-01-12

基于原生CSS+JS怎么实现一个标签输入框

前端开发2023-06-29

基于C++实现一个日期计算器

前端开发2024-04-02

如何实现一个基于canvas的移动端图片编辑器

前端开发2023-06-09

Java基于面向对象实现一个战士小游戏

前端开发2024-04-02

基于Python+Pygame实现一个俄罗斯方块小游戏

前端开发Python库2024-11-30

基于Python+Tkinter实现一个简易计算器

前端开发2024-04-02

基于PyQt5实现一个无线网连接器

前端开发2024-04-02

基于python的Tkinter实现一个简易计算器

前端开发2022-06-04

基于JavaScript实现一个月饼音乐播放器

前端开发2024-04-02

Java基于面向对象如何实现一个战士小游戏

前端开发2023-07-02
位置：首页-资讯-前端开发
咦！没有更多了？去看看其它编程学习网 内容吧
首页课程
资料下载问答资讯