the-super-tiny-compiler源码解析

ayqy贾杰

发布于 2019-06-12 14:53:51

1.1K0

发布于 2019-06-12 14:53:51

一.目标

通过实现编译器来支持简单的表达式转换，把Lisp风格的函数调用转换成C风格的，例如：

              LISP-style              C-style
2 + 2         (add 2 2)               add(2, 2)
4 - 2         (subtract 4 2)          subtract(4, 2)
2 + (4 - 2)   (add 2 (subtract 4 2))  add(2, subtract(4, 2))

即输入(add 2 2)，要求输出add(2, 2)

二.设计

把编译工作拆分成3部分：

解析：把代码字符串转成抽象表示
转换：把抽象表示修改成想要的样子
代码生成：把转换过的抽象表示转成新代码字符串

这里的解析包括词法分析及语法分析，由词法分析器把代码串转换成一系列词法单元（token），再由语法分析器生成能够描述语法结构（包括语法成分及其关系）的中间表示形式（Intermediate Representation）或抽象语法树（Abstract Syntax Tree）

从结构上看，词法单元是一组描述独立语法成分（比如数值，标签，标点符号，操作符等）的小对象，抽象语法树（简称AST）是个深层嵌套的对象，易于处理并且携带着语法结构信息，例如：

// 代码字符串
(add 2 (subtract 4 2))
// 词法单元
[
 { 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',
     }]
   }]
 }]
}

转换阶段要修改AST，也就是遍历上面生成的树结构，进行节点级操作（增/删/改节点）和属性级操作（增/删/改属性）。当然，也可以创建一棵新树

实现上，可以深度优先遍历，没什么特别的，逐节点处理倒是有点意思：

var visitor = {
 NumberLiteral: {
   enter(node, parent) {},
   exit(node, parent) {}
 },
 CallExpression: {
   enter(node, parent) {},
   exit(node, parent) {}
 },
 //...
};

把访问节点的操作提出来作为visitor层，遍历过程中按词法单元类型调用对应的enter/exit方法即可，算是个小技巧

改完AST，就到了最后的代码生成环节，遍历收集，把AST还原成代码串就好了

三.实现

词法分析

// 接受代码字符串input
function tokenizer(input) {
 // 当前正在处理的字符索引
 let current = 0;
 // 输出结果集合，存放词法单元
 let tokens = []; // 遍历字符串，挑出词法单元
 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;
   }   // 跳过空白字符
   let WHITESPACE = /\s/;
   if (WHITESPACE.test(char)) {
     current++;
     continue;
   }   // 匹配数值
   let NUMBERS = /[0-9]/;
   if (NUMBERS.test(char)) {
     let value = '';     // 匹配连续数字，作为数值
     while (NUMBERS.test(char)) {
       value += char;
       char = input[++current];
     }
     tokens.push({ type: 'number', value });     continue;
   }   // 匹配形如"abc"的字符串
   if (char === '"') {
     let value = '';     // 吃掉左双引号
     char = input[++current];
     // 收集两个双引号之间的所有内容，作为字符串值
     while (char !== '"') {
       value += char;
       char = input[++current];
     }
     // 吃掉右边双引号
     char = input[++current];
     tokens.push({ type: 'string', value });     continue;
   }   // 匹配函数名，要求只含大小写字母
   let LETTERS = /[a-z]/i;
   if (LETTERS.test(char)) {
     let value = '';     // 收集连续字母
     while (LETTERS.test(char)) {
       value += char;
       char = input[++current];
     }
     tokens.push({ type: 'name', value });     continue;
   }   // 无法识别的字符，报错
   throw new TypeError('I dont know what this character is: ' + char);
 } return tokens;
}

遍历代码字符串，拆出各个词素，包成词法单元的形式

语法分析

function parser(tokens) {
 // 当前正在处理的token索引
 let current = 0; // 递归遍历（因为函数调用允许嵌套），把token转成AST节点
 function walk() {
   let token = tokens[current];   // 数值
   if (token.type === 'number') {
     current++;     // 生成一个AST节点，表示数值字面量
     return {
       type: 'NumberLiteral',
       value: token.value,
     };
   }   // 字符串
   if (token.type === 'string') {
     current++;     return {
       type: 'StringLiteral',
       value: token.value,
     };
   }   // 函数调用
   if (
     token.type === 'paren' &&
     token.value === '('
   ) {
     // 丢掉左括号，取下一个token作为函数名
     token = tokens[++current];     let node = {
       type: 'CallExpression',
       name: token.value,
       params: [],
     };     // 看下一个token
     token = tokens[++current];     // 右括号之前的所有token解析完都是参数
     while (
       (token.type !== 'paren') ||
       (token.type === 'paren' && token.value !== ')')
     ) {
       node.params.push(walk());
       token = tokens[current];
     }
     // 吃掉右括号
     current++;     return node;
   }   // 无法识别的token，报错
   throw new TypeError(token.type);
 } // AST的根节点
 let ast = {
   type: 'Program',
   body: [],
 };
 // 填充ast.body，允许多条语句，所以放循环里
 while (current < tokens.length) {
   ast.body.push(walk());
 } return ast;
}

为了应对函数调用嵌套的情况，改用递归来遍历token序列

遍历

function traverser(ast, visitor) {
 // 遍历AST节点数组
 function traverseArray(array, parent) {
   array.forEach(child => {
     traverseNode(child, parent);
   });
 } function traverseNode(node, parent) {
   // 从visitor取出对应的一组方法
   let methods = visitor[node.type];
   // 通知visitor我们正在访问node
   if (methods && methods.enter) {
     methods.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;     // 无法识别的AST节点，报错
     default:
       throw new TypeError(node.type);
   }   // 通知visitor我们要离开node了
   if (methods && methods.exit) {
     methods.exit(node, parent);
   }
 } // 开始遍历
 traverseNode(ast, null);
}

递归遍历AST结构，遍历过程中通知visitor，有点切面的意思

转换

// 输入Lisp AST，输出C AST
function transformer(ast) {
 // 新AST的根节点
 let newAst = {
   type: 'Program',
   body: [],
 }; // 偷懒以简单粗暴的方式维持新旧AST的联系，方便在遍历过程中操作新AST
 ast._context = newAst.body; // 创建vistor，开始遍历
 traverser(ast, {
   // 数值和字符串，直接原样插入新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) {
       // 创建不同的AST节点
       let expression = {
         type: 'CallExpression',
         callee: {
           type: 'Identifier',
           name: node.name,
         },
         arguments: [],
       };       // 函数调用可以有孩子，建立节点对应关系，供子节点使用
       node._context = expression.arguments;       // 顶层函数调用算是语句，包装成特殊的AST节点
       if (parent.type !== 'CallExpression') {
         expression = {
           type: 'ExpressionStatement',
           expression: expression,
         };
       }       parent._context.push(expression);
     },
   }
 }); return newAst;
}

由于遍历（traverser）与修改（visitor）操作分开成了2层，不太容易在遍历旧AST节点的同时明确知道对应的新AST父节点，这里采用了简单粗暴的方式，直接通过新增_context属性让旧AST节点的父节点持有待操作的新AST节点引用，能用，但污染了旧AST

代码生成

// 递归遍历新AST，输出代码字符串
function codeGenerator(node) {
 switch (node.type) {
   // 根节点，把body里的所有内容都生成一遍，按行输出
   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 + '"';   // 无法识别的新AST节点，报错
   default:
     throw new TypeError(node.type);
 }
}

再把AST转回代码字符串，该加分号的加分号，该添括号的添括号……

流程串接

function compiler(input) {
 let tokens = tokenizer(input);
 let ast    = parser(tokens);
 let newAst = transformer(ast);
 let output = codeGenerator(newAst); return output;
}

把上面所有环节串起来，构成简单的编译器，确实只有200行的样子，试玩一下：

const input  = '(add 2 (subtract 4 2))';
let output = compiler(input);
// add(2, subtract(4, 2));
console.log(output);

四.优化

2个可优化点：

词法分析：逐字符匹配比较啰嗦，效率可接受的话，正则表达式更清晰
转换：生成新AST的方式比较脏，污染了旧AST，可以通过额外的数据结构记录新旧AST的联系，避免影响旧AST

更清晰的词法分析

比如各词素对应的正则表达式：

const REGEX = {
 PAREN: /^\(|^\)/,
 WHITESPACE: /^\s+/,
 NUMBERS: /^\d+/,
 STRING: /^"([^"]+)?"/,
 NAME: /^[a-z]+/i
};while (rest.length > 0) {
 let type, value;
 // 匹配结果，本次匹配消费掉的串长度
 let matched, span; // 匹配左括号、右括号
 if (matched = rest.match(REGEX.PAREN)) {
   type = 'paren';
 }
 //...匹配其它词素 value = value || matched[0];
 tokens.push({type, value});
 rest = rest.slice(span || matched[0].length);
}

比较清晰了，如果想要提升扩展性的话，可以把词素相关的type, value, span进一步配置化：

// 词素相关配置
const lexemes = [
 {
   regex: /^\(|^\)/,
   type: 'paren',
   value: 0,
   span: 0
 }, {
   regex: /^\d+/,
   type: 'number',
   value: 0,
   span: 0
 }, {
   regex: /^"([^"]+)?"/,
   type: 'string',
   value: 1,
   span: 0
 }, {
   regex: /^[a-z]+/i,
   type: 'name',
   value: 0,
   span: 0
 }
];

然后以统一的方式处理这些词素：

while (rest.length > 0) {
 // 跳过空白字符
 if (matched = rest.match(/^\s+/)) {
   rest = rest.slice(matched[0].length);
   continue;
 } lexemes.forEach(({regex, type : t, value: v, span: s}) => {
   if (matched) return;
   if (matched = rest.match(regex)) {
     type = t;
     value = matched[v];
     span = matched[s].length;
   }
 }); if (matched) {
   tokens.push({type, value});
   rest = rest.slice(span);
 }
 else {
   // 无法识别的字符，报错
   throw new TypeError('Unexpected character: ' + rest);
 }
}

更干净的转换

生成新树要做两件事：

节点映射
创建树结构

节点映射好办，该把新节点往哪挂是个问题。visitor与transformer实现上是独立的两层，所以需要手动记录新旧两棵树的联系，比如上面转换部分源码中的：

// 偷懒以简单粗暴的方式维持新旧AST的联系，方便在遍历过程中操作新AST
ast._context = newAst.body;
// 函数调用可以有孩子，建立节点对应关系，供子节点使用
node._context = expression.arguments;

这样就知道当前正在访问的旧节点对应的新节点应该挂到新树的哪个位置了，例如：

// 旧树中父节点身上挂着对应新树节点的孩子数组，把新节点填进去
parent._context.push({
 type: 'NumberLiteral',
 value: node.value,
});

但这样实现比较脏（污染了传入的旧树ast）。更合理的做法是以非侵入的方式记录新树中当前活跃的节点容器，由于函数调用允许嵌套，需要用栈结构来记录：

// 用额外的数据结构维持新旧AST的联系
let stack = [newAst.body];
function peak() {
 return stack[stack.length - 1];
}

并在递归遍历旧树过程中维持这种联系：

// 函数调用
CallExpression: {
 enter(node, parent) {
   // 取出活跃的新树节点容器
   let newASTHost = peak();   // 创建新树节点
   let expression = {
     type: 'CallExpression',
     callee: {
       type: 'Identifier',
       name: node.name,
     },
     arguments: [],
   };   // 函数调用可以有孩子，建立节点对应关系，供子节点使用
   stack.push(expression.arguments);   // 填充新树结构
   newASTHost.push(expression);
 },
 leave(node, parent) {
   // 参数收集结束，回到上一层
   stack.pop();
 }
}

这样就不会再污染旧树了，并且代价不很高（一个额外的数据结构stack）

五.源码

Github地址：https://github.com/ayqy/the-super-tiny-compiler

P.S.包括带详细注释的原版，以及优化之后的实现

参考资料

The Super Tiny Compiler
jamiebuilds/the-super-tiny-compiler

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-09-04，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

ide

本文分享自前端向后微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

ide

登录后参与评论

0 条评论

热度