【造轮子系列】面试官问：你能手写编译器将LISP表达式转换成JS语法吗？
概览： 专栏上篇文章带着大家做了一个模板引擎，主要核心思路就是通过正则匹配特定的符号，然后动态拼接成可执行函数，结合数据并在特定的作用域执行，便可输出静态的文本，虽然也对模板字符串进行了转换，但是模板引擎的实现通常比较简单，不需要特别复杂的语法分析和优化（感兴趣的小伙伴戳此链接：juejin.cn/post/720769… ）。 本篇带领大家实现一个较为复杂的编译器，通过这个编译器的实现，可以让大家了解如何编译高级编程语言的源代码，麻雀虽小五脏俱全，让我们一起看下神秘的编译器到底是什么样子的？
github上的一个编译器的项目实在是经典，所以，就用这个经典项目来讲解怎样实现一个极简的编译器:仓库
实现简单的需求：
/**
* target LISP JS
*
* 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))
*/
上面的代码，最左边是数学表达式，第二列是LISP语言风格的函数调用表示方法，最后一列是转换后的JS语法的函数调用，我们今天要做的就是将中间的LISP转换成右边的JS。通常构建编译器的流程会比较复杂，一般包括词法分析，语法分析，语义分析，中间代码生成，优化，目标代码生成，目标代码优化，目标代码链接，而我们今天要实现的只需要其中的几个关键步骤，词法分析，语法分析，语法的转换，最后目标生成，因为我们是从高级语言转为高级语言，核心是语法的转换，而优化，我们暂时也不涉及。看下图：
我们核心的步骤有四步，先是做词法分析，将代码分解成tokens，然后对tokens进行解析，解析成一个对象，称为AST（抽象语法树），然后对抽象语法树进行转换，转换成适配新语法的新的语法树，最后根据这个语法树进行最终代码的生成。简单的高级语言之间的转换基本都是这几步。
词法分析
将源代码分解成单个的单词或符号（也称为词法单元）。这些词法单元可以是关键字、标识符、操作符、常量、字符串等，说白了就一句话将源代码的全部有效语言信息提取出来。我们先看一下转换后的tokens长什么样子例如(add 2 (subtract 4 2))，转换为tokens如下所示（我们后面所有的代码都用这个表达式说明）。
const 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: ')' },
];
可以看见上面的tokens包含了表达式的所有有效信息，按照类型和值统一存放，本质上词法分析就是将源代码的所有有效信息提取出来，这样后续就直接操作这个具有统一结构的数组而不需要再去解析源代码。
实现思路：我们需要一个存放token的数组，然后循环遍历输入的代码字符串，匹配所遍历字符的类型，匹配出一个token类型，我们便将这个类型和值组装成一个对象存放在数组里面。遍历完整个字符串，所有的token也就都生成了。
代码实现具体如下：
function tokenizer(input) {
// 需要一个current指针标记遍历源代码的位置
let current = 0;
// 存储匹配到的每一个token
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;
}
// (add 123 456)
// ^^^ ^^^
//匹配数字
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;
}
// (concat "foo" "bar")
// ^^^ ^^^ string tokens
// 匹配字符串
if (char === '"') {
let value = '';
char = input[++current];
while (char !== '"') {
value += char;
char = input[++current];
}
char = input[++current];
tokens.push({ type: 'string', value });
continue;
}
// (add 2 4)
// ^^^
// 匹配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;
}
// 上面类型都没有匹配上则抛出错误
throw new TypeError('I dont know what this character is: ' + char);
}
return tokens;
}
通过遍历源代码，进行类型的判断，并获取该类型对应的值，直到整个字符串遍历结束，有的类型需要正则去匹配，值的获取可能也需要进微多一点逻辑处理，但是总体的思想，基本的原理比较简单，其实类似于状态机，不同的类型对应不同的状态，不同的状态会有不同的处理。
语法分析
我们需要对上面词法分析得到的tokens做进一步的处理，转换为具有一定语法内涵的树形结构，称为抽象语法树（AST），它将tokens映射成树中节点，节点之间的连接则表示它们之间的关系，比如嵌套、调用、参数传递等等。因此，抽象语法树提供了一种更加抽象和结构化的代码表示方式，便于后续编译器程序对代码进行分析、优化、转换等操作。
同样我们先来看下转换之后的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是一个树形嵌套结构，body体内是tokens所对应的语法节点，然后通过类似的结构嵌套起来，并标明了调用以及参数传递的关系。
实现思路：这种嵌套的树形结构，通常的实现思路都是通过递归的方式实现，我们需要遍历整个tokens，然后进行对应格式的输出，其整个功能实现的其核心在于递归的调用时机，而递归又是由嵌套结构决定的，我们知道了在什么地方嵌套，也就清楚了，需要在什么地方进行递归，答案是表达式是可以嵌套的，语法结构是左括弧下面的token是表达式，然后表达式的参数又可以包含表达式，我们也就清楚在什么地方进行递归了。
代码实现具体如下：
function parser(tokens) {
let current = 0;
// 核心逻辑，为了让大家看清楚结构，walk函数后面再实现
function walk() {}
// AST的主体结构
let ast = {
type: 'Program',
body: [],
};
// (add 2 2)
// (subtract 4 2)
// 多个表达式的时候需要循环遍历添加进body
while (current < tokens.length) {
ast.body.push(walk());
}
return ast;
}
上面是parser函数的主体结构，声明current指针进行tokens数组的标识，通过while遍历整个tokens数组，将walk后的结果添加进ast的body体内，所以parse的核心代码在于walk的实现。walk的核心就是处理token，将token转换成对应的ast节点，然后返回。代码如下：
function walk() {
// 通过current指针依次取出每一个token
let token = tokens[current];
// 处理类型为number的token
if (token.type === 'number') {
current++;
// 返回对应的ast节点格式
return {
type: 'NumberLiteral',
value: token.value,
};
}
// 处理类型为string的token
if (token.type === 'string') {
current++;
return {
type: 'StringLiteral',
value: token.value,
};
}
// 如果是左括弧，那么代表下一个token是表达式的name
if (
token.type === 'paren' &&
token.value === '('
) {
// 跳过“（”，获取下一个token
token = tokens[++current];
// 组装表达式节点
let node = {
type: 'CallExpression',
name: token.value,
params: [],
};
// 跳过name节点
token = tokens[++current];
// 如果不是括弧，或者不是左括弧，那么代表此token是上面表达式的参数
// 需要添加进node的params中
while (
(token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// 将递归的结果添加进node.params中
node.params.push(walk());
// 获取下一个token
token = tokens[current];
}
// 修正current，以供下次walk的调用，如果while条件不满足， // 则是遇见了")"，一对括弧意味着一个表达式结束，即表达式组装完成，需要返回
current++;
// 返回组装好的node
return node;
}
throw new TypeError(token.type);
}
walk函数的功能就是将token转换为AST对应的节点类型并返回。如果符合表达式参数的条件，那么递归调用walk自身去转换参数，并添加进node的parms数组中，这是这个函数的核心也是重点。
语法转换
我们得到了LISP的AST，下面我们要来进行语法转换，转换成适合JS语法的AST，照例我们看下要转换成什么样子。
----------------------------------------------------------------------------
Original AST | Transformed AST
----------------------------------------------------------------------------
{ | {
type: 'Program', | type: 'Program',
body: [{ | body: [{
type: 'CallExpression', | type: 'ExpressionStatement',
name: 'add', | expression: {
params: [{ | type: 'CallExpression',
type: 'NumberLiteral', | callee: {
value: '2' | type: 'Identifier',
}, { | name: 'add'
type: 'CallExpression', | },
name: 'subtract', | arguments: [{
params: [{ | type: 'NumberLiteral',
type: 'NumberLiteral', | value: '2'
value: '4' | }, {
}, { | type: 'CallExpression',
type: 'NumberLiteral', | callee: {
value: '2' | type: 'Identifier',
}] | name: 'subtract'
}] | },
}] | arguments: [{
} | type: 'NumberLiteral',
| value: '4'
---------------------------------- | }, {
| type: 'NumberLiteral',
| value: '2'
| }]
(sorry the other one is longer.) | }
| }
| }]
| }
----------------------------------------------------------------------------
抽象语法树的转换本质上是对象结构的变换，抛开业务，其实就是对象的变换操作。
实现思路：遍历整棵树（主要是body数组内容），每遇到一个类型的节点，就进行与之对应的转换，这样整棵树遍历完成，新的AST也就生成了，原理很简单，但是怎样编写较为优雅的代码就是实现就是这个方法的核心，所以我们要抽象一个工具方法traverser，通过它进行AST节点的遍历，然后再进行具体的转换逻辑，我们尝试使用上面提到的状态模式进行traverser的编写，将不同的节点类型封装成不同的状态，不同状态拥有自身不同的处理逻辑。
方法的调用大致如下：
traverse(ast, {
// 处理Program节点
Program: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
},
},
// 处理CallExpression节点
CallExpression: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
},
},
// 处理NumberLiteral节点
NumberLiteral: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
},
},
});
该方法第一个参数是AST，第二个参数是一个包含所有类型的状态对象，每一个状态拥有两个函数，分别对应开始和结束的处理逻辑，这样，以后还要添加其他的逻辑，便可以扩展这个对象。
我们先看一下它的整个调用的过程，这样再去编写代码会清晰很多：
-> Program (enter)
-> CallExpression (enter)
-> Number Literal (enter)
<- Number Literal (exit)
-> Call Expression (enter)
-> Number Literal (enter)
<- Number Literal (exit)
-> Number Literal (enter)
<- Number Literal (exit)
<- CallExpression (exit)
<- CallExpression (exit)
<- Program (exit)
下面我们来看具体的实现：
function traverser(ast, visitor) {
// 封装数组的遍历，AST中，body体和参数都是数组
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent);
});
}
// 核心逻辑
function traverseNode(node, parent) {
// 取出对象节点的方法
let methods = visitor[node.type];
// 如果有enter方法，先执行
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;
default:
throw new TypeError(node.type);
}
// 如果有exit方法，最后执行
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
// 开始调用，parent为null
traverseNode(ast, null);
}
}
上面的工具方法traverse，主要构建了遍历和处理的逻辑，每一个节点均有两次处理的机会，而具体不同类型节点的转换逻辑就封装在里面。接下来我们看具体的转换方法：
function transformer(ast) {
let newAst = {
type: 'Program',
body: [],
};
// 将newAst.body 挂载到老的AST，因为，遍历的时候传入的是老的AST，所以需要_context保存
// newAst.body的引用
ast._context = newAst.body;
// 调用traverse方法，核心在于每个状态的处理逻辑
// 我们只需要enter方法进行逻辑处理即可
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: [],
};
// 下一级子元素的_context引用
node._context = expression.arguments;
// 最外层表达式的格式进行特殊处理
if (parent.type !== 'CallExpression') {
expression = {
type: 'ExpressionStatement',
expression: expression,
};
}
parent._context.push(expression);
},
}
});
return newAst;
}
我们对于每一种节点类型进行了相应的处理，具体逻辑是调用工具函数traverse，进行依次遍历。这样我们新的AST就生成好了，接下来，我们就剩下最后一步了，生成最后的JS代码。
目标代码生成
在完成了前面几步之后再生成目标代码，就变的简单了，我们需要定义一个codeGenerator方法，方法的参数是AST，该方法的目的就是返回AST对应的JS表达式，大家从我这段描述应该能感受到，接下来我们又要用递归的方式处理了，判断节点不同的类型然后递归的调用，生成最终的code。代码如下：
function codeGenerator(node) {
// 节点类型的判断
switch (node.type) {
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(', ') +
')'
);
// 如果是identifier类型
case 'Identifier':
return node.name;
// 如果是数值类型类型
case 'NumberLiteral':
return node.value;
// 如果是字符串类型
case 'StringLiteral':
return '"' + node.value + '"';
default:
throw new TypeError(node.type);
}
}
至此，我们就将(add 2 (subtract 4 2))的LISP风格的函数调用转换成JS风格的函数调用add(2, subtract(4, 2))。
本篇实现了一个极简的编译器，对LISP的函数调用表达式进行了转换，核心有两点，首先要明确编译的思想和流程，其次在代码的实现上要重点理解递归的调用，递归的思想在整个编程领域及其重要而又基础，很多复杂的实现都能看到它的影子，如果大家感兴趣，后面跟大家着重讲解递归。
转载自:https://juejin.cn/post/7209917117470048312