关于可以参考这篇文章。或者微信搜索订阅号'北宸南蓁'或者搜索wDxKn89。
Parsing
我们来构建一个tokenizer用于进行lexical analysis（词法分析）
设计思路
我们向tokenizer中传递需要转换的字符类型的code，并且将code通过一些分解规则，拆分为tokens数组。
(add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]复制代码 tokenizer代码实现
function tokenizer(input) { //该'current'变量用于追踪代码走到哪里，可以类比SQL中的游标(https://blog.csdn.net/DreamLLOver/article/details/51523887) let current = 0; //用于存放tokens的数组 let tokens = []; //通过判断'current'与input.length的长度来控制循环次数和对tokens的处理次数 while (current < input.length) { //取出指定游标下需要处理的code. let char = input[current]; //首先我们向要校验是否是'(',之后会被'CallExpression'使用，但是我们现在只关心这个字符是什么。 if (char === '(') { //如果满足条件，我们向token数组push一个type值为'parn',同时value为'('的token对象。 tokens.push({ type: 'paren', value: '(', }); // 更新游标的值。 current++; // 继续处理剩余的code continue; } //道理同上 if (char === ')') { tokens.push({ type: 'paren', value: ')', }); current++; continue; } //由于在代码中会存在空格/tab等制造的空格，同时我们在构建token的时候，是不必要关注空格的，因为空格本身对代码运行没有任何影响。 let WHITESPACE = /\s/; if (WHITESPACE.test(char)) { current++; continue; } //由于我们实现的是基于两个数字参数的转换，对于一些非数字会有其他匹配规则或者类似'12sdsd4'是不满足运行规则的，所以需要挑选出满足条件的数字token let NUMBERS = /[0-9]/; if (NUMBERS.test(char)) { //用于存放数字字符 let value = ''; //然后会不停的去loop code 序列 while (NUMBERS.test(char)) { value += char; char = input[++current]; } // 将'number'token存放到tokens中 tokens.push({ type: 'number', value }); continue; } //同时为了满足compiler的多样性，我们还支持String的转换，只要满足字符串被double quotes 包裹 if (char === '"') { let value = ''; // 跳过引号 char = input[++current]; //纪录String value += char; char = input[++current]; } // 跳过引号 char = input[++current]; // 添加StringToken tokens.push({ type: 'string', value }); continue; } //最后我们需要处理function name,用于标识操作动作 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; } //最后如果code没有满足条件说明，该code是一个'脏code' throw new TypeError('I dont know what this character is: ' + char); }//最后返回处理过的tokens return tokens;}复制代码 Parser的代码实现
我们已经有了tokenizer(已经将raw code格式化为tokens array)，既然烹饪材料已经有了，就需要对'材料'进行进一步加工，从而转换为AST。
[{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }复制代码 我们定义一个接收tokens数组的'parser'函数
function parser(tokens) { //与处理raw code 的方式一样，需要一个"游标"来跟踪代码的运行轨迹 let current = 0; //在处理raw code生成tokens是用的while对需要处理的char来根据不同的处理规格进行token的生成，现在我们处理token的时候，完全可以构建一个函数，这样能够使得代码更加的清晰 function walk() { //获取tokens数组对应current下标的token对象 let token = tokens[current]; //我们根据用于标识token类型的type来进行token的分类 if (token.type === 'number') { //更新游标 current++; //构建AST node结点，type是需要事先按照一定的规则进行赋值，value是token的value return { type: 'NumberLiteral', value: token.value, }; } // 处理type为string的token,用于生成满足对应type的AST node if (token.type === 'string') { current++; return { type: 'StringLiteral', value: token.value, }; } //根据案例code，我们是将LISP的函数转换为C语言的，根据LISP函数的特点，'('代表函数的开始，所以我们需要处理type为paren（括号）同时值为'('的token，用于构建一个代表函数的AST node。 if ( token.type === 'paren' && token.value === '(' ) { //这一步需要额外的注意，我们通过处理tokens用于构建对应的AST,我们只关心函数名是什么，参数是什么，而不关心'('或者')'这些不具备函数特性的东西，它们只是标识一个函数的函数开始和结束 token = tokens[++current]; //构建一个type为CallExpression Base node ,我们将raw code的函数名作为该node的name的值。同时params用于存放函数内部的参数或者是子函数的nodes. let node = { type: 'CallExpression', name: token.value, params: [], }; // 刚才如果是处理'(',在处理完之后，current还是指向函数名，所以需要将游标更新到最新 token = tokens[++current]; //由于raw code的形式是变化不定的，所以如果只是根据tokens.length来进行while处理是远远不够，也不正确的，因为可能在LISP的一个函数中可能内嵌n多个子函数。 // (add 2 (subtract 4 2)) // // 下面的代码中存在多个')',这种情况在parser的过程中是不可预知的。 // [ // { 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: ')' }, <<< )最外层的） // ] //所以，我们是不能通过简单的循环来对tokens进行AST化，但是我们可以利用walk函数，进行递归调用，来让walk来处理内嵌CallExpression的情况，只要控制好停止条件就可以。 //通过while来控制递归是否终止 while ( (token.type !== 'paren') || (token.type === 'paren' && token.value !== ')') ) { //调用walk(),将返回的node push到用于存放AST树形结构的node.params中。 node.params.push(walk()); token = tokens[current]; } //更新游标，跳出tokens的数据范围 current++; // 返回处理之后的node结点。 return node; } // 容错处理. throw new TypeError(token.type); } //构建type为Program的root node。 let ast = { type: 'Program', body: [], }; //调用walk()来处理tokens,然后将处理之后的结果存放到AST root node的body属性中。 while (current < tokens.length) { ast.body.push(walk()); } // 返回根据tokens处理过的AST对象。 return ast;}复制代码 Transformation
通过Parsing对raw code的处理，生成对应的AST。但是我们需求是对AST进行处理来生成目标AST。但是现在有一个问题，如何才能遍历这些树形结构，总不能用while来处理，同时也不能保证node信息的被按访问顺序的纪录。
所以我们需要能利用visitor(针对树形结构的游标)来构建一个访问AST同时按照访问顺序纪录一些node信息的"遍历器"。traverser的代码实现
大致思路,traverse接收ast,还有不同类型的visitor。
traverse(ast, { Program: { enter(node, parent) { // ... }, exit(node, parent) { // ... }, }, CallExpression: { enter(node, parent) { // ... }, exit(node, parent) { // ... }, }, NumberLiteral: { enter(node, parent) { // ... }, exit(node, parent) { // ... }, }, });复制代码 真实代码
function traverser(ast, visitor) { //该函数用于处理node.body/node.params，处理顶层的树结构，将child剥离出来，然后进行traverseNode处理 function traverseArray(array, parent) { array.forEach(child => { traverseNode(child, parent); }); } //接收需要被处理的'node'结点，同时将该'node'的直接parent的结点传入 function traverseNode(node, parent) { //根据被遍历的node结点的type，从visitor中获取到对应type的处理对象 let methods = visitor[node.type]; //如果该处理对象存在同时有enter方法(也就是visitor匹配了node type了)， //然后将node,node 的直接parent结点传入，进行下一步处理 if (methods && methods.enter) { methods.enter(node, parent); } //通过node type来进行不同的操作处理 switch (node.type) { //从AST的顶层入口，顶层的type为`Program`，同时树形的关联关系和逻辑都被存放在body属性中，所以我们需要对body进行traverseArray处理，由于traverseArray()内部调用traverseNode(),所以会对body内部所有的child进行递归traverseNode()处理。 case 'Program': traverseArray(node.body, node); break; //对AST中的CallExpression进行处理 case 'CallExpression': traverseArray(node.params, node); break; //由于`NumberLiteral` 和`StringLiteral`没有任何child node,所以不需要进行traverseArray()处理，直接跳过 case 'NumberLiteral': case 'StringLiteral': break; //容错处理 default: throw new TypeError(node.type); } //由于遍历AST是采用depth-first，所以需要在处理完所有child的时候，进行推出操作 if (methods && methods.exit) { methods.exit(node, parent); } } //我们通过启动traverseNode()来触发遍历操作，由于顶层的AST是不存在parent node,所以直接传入null traverseNode(ast, null);}复制代码 transformer
通过构建了traverser(),我们现在有能力可以对AST进行有目的的遍历，同时还可以保证他们直接存在的原有关联不被破坏。接下来，我们就需要利用traverser()来对AST进行有目的的改造(生成新的AST)。
原始的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
{ 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' }] } } }]}复制代码 transformer的代码实现(接收lisp ast)
function transformer(ast) { //首先先构建一个 newAst和lisp ast拥有相同的program node let newAst = { type: 'Program', body: [], }; //我们采用直接在old ast中设置一个context（或者说在每一级的parent中设置一个用于接收处理过的AST）,context 是从old ast转换为new ast的引用 ast._context = newAst.body; //调用traverser对ast在特定的visior下针对满足条件的node 结点进行处理。 traverser(ast, { // 处理type为 `NumberLiteral`的node， NumberLiteral: enter(node, parent) { //重新构建了一个type为'NumberLiteral'并push到用于纪录树的关联关系的context中。 parent._context.push({ type: 'NumberLiteral', value: node.value, }); }, }, // 构建处理 `StringLiteral` StringLiteral: { enter(node, parent) { parent._context.push({ type: 'StringLiteral', value: node.value, }); }, }, // 处理 `CallExpression`. CallExpression: { enter(node, parent) //构建一个新增了内置Identifier的node 结点 let expression = { type: 'CallExpression', callee: { type: 'Identifier', name: node.name, }, arguments: [], }; /在原始的expression node中新增一个context,用于存放函数的参数nodes node._context = expression.arguments; //判断parent node的type是否是'CallExpression'(可能会存在如下的lisp （add substricl(2,3),但是是不满足情况的，由于在ast生成的阶段只是根据type来构建，没有进行语法的校验) if (parent.type !== 'CallExpression') { //我们将`CallExpression`node 包装在ExpressionStatement中。(CallExpression在JS中保留声明) expression = { type: 'ExpressionStatement', expression: expression, }; } //将处理之后的node更新到parent的context中 parent._context.push(expression); }, } }); //返回处理之后的ast return newAst;}复制代码 Code Generator
我们采用递归调用code generator将new ast中的node字符化。 codeGenerator的代码实现
function codeGenerator(node) { // 根据type来区分不同的输出处理 switch (node.type) { //如果遇到`Program` node，将body的数组中的item通过再次调用codeGenerator来进行类输出，（可以认为是递归调用） 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); }}复制代码 代码回顾
最后我们构建了一个compiler函数。他们直接的交互顺序和方式如下：
- input(数据源) => tokenizer => tokens
- tokens => parser => ast
- ast => transformer => newAst
- newAst => generator => output(目标)
function compiler(input) { let tokens = tokenizer(input); let ast = parser(tokens); let newAst = transformer(ast); let output = codeGenerator(newAst); return output;}复制代码 我们也可以将这些方法进行导出
module.exports = { tokenizer, parser, traverser, transformer, codeGenerator, compiler,};复制代码