前端编译原理 the-super-tiny-compiler

时隔四个月的更新#

其实后面的递归步骤只是借助 JS 的引用数据类型特性，模拟了类似 c 语言的指针功能 😐 , 就是简单的传递指针，不断生成类似链表的数据结构，填充数据，最终得到目标代码... 而已.. 已.

起初#

the-super-tiny-compiler 是 github 上的一个使用 js 编写的编译器，代码注释中称其可能是最小的编译器，可以将 lisp 风格的语言编写为 c 风格的语言

这个编译器项目可以说是麻雀虽小，五脏俱全

但是本人再阅读器源代码的时候，在生成新 ast 的过程中，对其递归过程产生了不解

所以从现在开始，要对源代码进行一下分析

编译器原理简单来说就是
词法分析
语法分析（生成 ast）
将 oldAst -> newAst
最后将产生的 newAst 生成目标语言语法进行输出
将 (add 2 (subtract 4 2)) 作为输入，得到的 ast 结构如下

const 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",
            },
          ],
        },
      ],
    },
  ],
};

得到这个结构后，执行了这样一个函数


function transformer(ast) {
  let newAst = {
    type: "Program",
    body: []
  }

  ast._context = newAst.body
}

给 ast 对象下添加了一个新属性，将该属性指向了 newAst 的 body 属性中
然后向下执行了

function transformer(ast) {
  let newAst = {
    type: "Program",
    body: []
  }

// 这里改变 ast 的属性就可以之间影响到 newAst 
  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
          }
        }

        parent._context.push(expression)
      }
    }


  })

  return newAst//返回 newAst
}

可以看到，newAst 的数据变化只执行了一个 traverser 函数就完成了，函数把刚刚的 ast 当作参数，以及根据不同类型对 newAst 中的 body 复制的行为，

这个函数的内部是这样子的

function traverser(ast, visitor) {

  function traverseArray(array, parent) {
    
  }

  function traverseNode(node, parent) {
    // 判断传入进来的 node 有没有对应的属性
    let methods = visitor[node.type]

    // 如果有 就给其父节点的 body 赋值进去
    if (methods && methods.enter) {
      methods.enter(node, parent)
    }

    // 然后再把 visiter 中不包括的属性进行单独处理 
    switch (node.type) {
      // first exec 执行最外层的 遍历 节点下的 body
      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)
    }
  }

  traverseNode(ast, null)

}

执行他的时候，主线为 traverser -> traverseNode ->
ast 作为 node 参数传入进去，这个函数的执行过程就进行了递归调用
第一次执行 methods 为 undefined 然后进入 switch 语句中
第一次的 ast type 是 Program 然后就将 ast 的 body 当作参数传递进去，然后 break; 掉
至此，函数主线已经执行完毕了
之后的执行流程则是对 ast.body 进行的一个伪递归或者叫嵌套调用，函数每次根据其传入的 tree 参数，根据表达式，参数，去判断是否生成新的 ast

值得一提的是，在生成 newAst 的时候
有类似这样的语句
node._context = expression.arguments;
将传入节点的_context 属性指向当前对象下的某个属性，达到引用的效果，这时，使用 visitor 遍历语法数的时候，不管传入的对象是什么，因为已经在上层构建好了内存地址的引用关系，所以只需要给 parent._context 属性添加只就可以了

最后的最后就是将生成的新 ast 生成我们的目标语言，这个没什么好说的，递归生成字符串就好了。

总结，看似简单的小项目，如果自己去实现，不知到要考虑多少细节，所以说，前端深入之路，任重而道远！