简易编译器实现
前言
该编译器实现的功能是将Lisp语言中的函数调用语法编译为c语言中的函数调用语法。本人对 JavaScript 语言更熟悉，所以代码使用 JavaScript 实现。
下面是我的编译器要做的事情：
要求输入任意一段 Lisp 语言中的函数调用语法文本，最终输出 c 语言的函数调用语法。
本编译器主要包含三个阶段：
- 解析
- 转换
- 代码生成
下面会依次说明我对每个过程理解和最终代码的实现。
解析阶段
在解析阶段又分为两个阶段：词法分析和语法分析。
词法分析
将源代码通过 tokenizer 分解为 tokens，这里的 tokens 是一个数组，数组的每一项称为一个 token，它的结构如下：
const token = {type: "paren", value: "("};
type 属性是用来描述源代码中的每一个字符类型，value 属性就是该字符的取值。
对于下面这个 Lisp 语句：
(add 2 (subtract 4 2))
它经过词法分析后，tokens 的结构如下：
语法分析
在语法分析阶段，利用词法分析得到的 tokens 数组，将其转换为 AST 抽象语法树，这个抽象语法树作用就是将之前 tokens 数组中毫无联系的 token，联系起来，抽象的描述了整个语句的语法和作用。
上面的 tokens 经过语法分析后会得到如下结构的抽象语法树：
转换阶段
在该阶段要做的事情就是操作来自解析阶段得到的 AST 抽象语法树，这一步我认为是编译过程中的核心阶段，你可以在该阶段做任何事情。比如增、删、替换 AST 中的某些节点，或者根据原来的 AST 生成一颗新的 AST。
对于 JS 来说，由于某些浏览器的兼容性，你会利用一些插件将 ES6+ 的语句转换为 ES5 的语句，就需要将得到的抽象语法树中表示 ES6+ 语法的那部分节点转换为符合 ES5 语法的节点。 而本编译器的目的是将 Lisp 函数调用的语法转换为 C 语言的函数调用的语法，因此，我们需要根据原来的 AST 抽象语法树来创建一颗新的符合 C 语言的抽象语法树。
想要转换抽象语法树，就需要知道如何遍历抽象语法树，这里使用深度优先遍历下面抽象语法树。
- 到达 Program 节点，这是抽象语法树的根节点
- 到达 CallExpression (add) 节点，这是根节点的左孩子节点
- 到达 NumberLiteral (2) 节点，这是 CallExpression (add) 的第一个参数
- 到达 CallExpress (subtract) 节点，这是根节点的右孩子节点
- 到达 NumberLiteral (4) 节点，这是 CallExpress (subtract) 的第一个参数
- 到达 NumberLiteral (2) 节点，这是 CallExpress (subtract) 的第二个参数
代码生成阶段
该阶段的作用是将新的 AST 转换为目标源码。
代码实现
tokenizer
该函数的作用是根据输入的源码文本生成 tokens
// 接收输入的字符串源码
function tokenizer(input) {
// 用于表示当前扫描到 input 的哪个下标了
let current = 0;
// 存放 token 的数组
let tokens = [];
// 使用 current 扫描 input
while (current < input.length) {
// 当前扫描到字符
let char = input[current];
// 判断当前字符是否为圆括号
if (char === '(') {
// 将该字符描述成一个 token，类型为 paren 表示为圆括号类型，取值为 (
tokens.push({
type: 'paren',
value: '(',
});
// current 指针后移
current++;
// 进入下一次循环
continue;
}
// 同理，这里用来检查当前扫描到的字符是否为闭合的圆括号
if (char === ')') {
tokens.push({
type: 'paren',
value: ')',
});
current++;
continue;
}
// 这里用来跳过源代码文本中的空格
let WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
// 当扫描到一个数字时，这里要将一个完整的数当作一个 token
// 比如 add 100 200，这里的 100 和 200 当作两个 token
// 所以内部要使用一个循环
let NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {
// 记录完整的数
let value = '';
// 只要当前扫描到的是数字，那么 current 就后移
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}
// 最后将完整的数字 token 存放到 tokens 中，类型为 number，取值为 value
tokens.push({ type: 'number', value });
// 进入下一次循环
continue;
}
// 如果扫描到了引号，说明遇到字符串了，我们要将完整的字符串当作一个 token
// 因此内部也要使用一个循环
if (char === '"') {
// 记录完整字符串的值
let value = '';
// 跳过遇到的第一个引号
char = input[++current];
// 记录两个引号之间的字符串值
while (char !== '"') {
value += char;
char = input[++current];
}
// 跳过遇到的第二个引号
char = input[++current];
// 将完整的字符串当作 token 存入 tokens 中，类型为 string
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];
}
// 将完整的标识符名称当作 token 存放到 tokens 中，类型为 name
tokens.push({ type: 'name', value });
continue;
}
// 这里用来识别输入到未知字符，抛出异常
throw new TypeError('I dont know what this character is: ' + char);
}
// 当整个输入的源码文本扫描完毕后，返回 tokens 数组
return tokens;
}
parser
该函数的作用是根据 tokens 生成抽象语法树 AST
// 参数为 tokens
function parser(tokens) {
// 使用 current 指针来扫描数组
let current = 0;
// 由于要构建树结构，所以这里使用递归
function walk() {
// 从 tokens 中取出一个 token
let token = tokens[current];
// 如果 token 的类型是 number
if (token.type === 'number') {
// 扫描数组的指针后移
current++;
// 返回 Numberliteral 类型的 AST 节点
return {
type: 'NumberLiteral',
value: token.value,
};
}
// 同理，如果 token 是 string 类型，则返回 StringLiteral 类型的 AST 节点
if (token.type === 'string') {
current++;
return {
type: 'StringLiteral',
value: token.value,
};
}
// 如果 token 是一个左圆括号
if (
token.type === 'paren' &&
token.value === '('
) {
// 跳过该 token，在 Lisp 语法中，左圆括号就是表示有函数调用（本编辑器只实现函数调用语法的编译）
// 所以左圆括号的下一个 token 就是该函数的标识符
token = tokens[++current];
// 创建一个 CallExpression 类型的节点，name 表示标识符即为函数名称，params
let node = {
type: 'CallExpression',
name: token.value,
params: [],
};
// 取到下一个 token，此时该 token 可能是一个 number 类型的 token，也可能是一个左括号
token = tokens[++current];
// 接下来开始遍历后面的 token，直到 current 遇到右括号，目的是获取函数调用时所有的参数
// 但是很可能出现一种情况就是参数也可能是一个函数调用表达式，这时就要使用递归了
//
// 比如下面这个 Lisp 语法的函数调用
// (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: ')' }, <<< 右括号
// ]
//
// 现在开始递归调用 walk 函数，来递增 current
// 使用 while 循环递归，直到 token 是一个右括号
// 如果当前 token 的类型不是一个括号，或者是括号，但不是右括号
//
while (
(token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// 递归调用 walk 函数，它的返回值是一个 AST 节点，作为 CallExpression node 节点的参数
node.params.push(walk());
// 更新 token
token = tokens[current];
}
// 递增 current，跳过右括号
current++;
// 返回该节点
return node;
}
// 执行到此行代码，说明扫描到了无法识别的 token，直接抛出异常
throw new TypeError(token.type);
}
// 初始化 AST，默认根节点类型为 Program
let ast = {
type: 'Program',
body: [],
};
// 下面就可以来调用 walk 函数生成 AST 了，这里使用 while 循环的原因是，本编译器支持多个函数平行调用
// (add 2 2)
// (subtract 4 2)
//
while (current < tokens.length) {
ast.body.push(walk());
}
// 最后返回 AST
return ast;
}
traverser
该函数用于遍历 AST
/**
* 这里使用了一个 visitor 对象用来访问 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) {
* // ...
* },
* },
* });
*/
// 接收 ast 和 visitor
function traverser(ast, visitor) {
// 该函数用来遍历一个数组，遍历过程中会调用 traverseNode 函数
// 因为 AST 中某些节点的属性是数组类型的，比如根节点 body 属性，函数调用式中的 params 属性
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent);
});
}
// 该函数可以接收一个节点和其父节点，这两个参数可以传递给 visitor 内部的方法
function traverseNode(node, parent) {
// 获取 visitor 内部对应于 node.type 的方法
let methods = visitor[node.type];
// 如果该方法存在，并且具有 enter 属性，我们就调用 enter，传入 node 和 parent
if (methods && methods.enter) {
methods.enter(node, parent);
}
// 根据当前节点类型传入不同的参数进行遍历
switch (node.type) {
// 当前节点是根节点，则遍历 node.body 数组
case 'Program':
traverseArray(node.body, node);
break;
// 当前节点是函数调用式，则遍历 node.params 数组
case 'CallExpression':
traverseArray(node.params, node);
break;
// 如果节点是数字或者字符串类型，那么不用递归遍历
case 'NumberLiteral':
case 'StringLiteral':
break;
// 无法识别节点类型，抛出异常
default:
throw new TypeError(node.type);
}
// 如果该方法存在，并且具有 exit 属性，我们就调用 exit，传入 node 和 parent
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
// 最后传入 AST 根节点和 null，因为根节点是没有父节点的，所以为 null
traverseNode(ast, null);
}
transformer
该函数用于转换 AST
/**
* 将之前构造的 ast 传入到 traverser 函数中，利用 visitor 在遍历 ast 的过程中创建一个新的 ast
*
* ----------------------------------------------------------------------------
* 原始 AST | 转换后的 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'
* | }]
* | }
* | }
* | }]
* | }
* ----------------------------------------------------------------------------
*/
function transformer(ast) {
// 初始化新的 ast
let newAst = {
type: 'Program',
body: [],
};
// 给旧的 ast 绑定一个 _context 属性指向新的 ast 的 body
ast._context = newAst.body;
// 调用 traverser，传入旧的 ast
traverser(ast, {
// 遍历过程中遇到 NumberLiteral 类型节点，我们就对应的放入一个新节点到到新的 ast 中
NumberLiteral: {
enter(node, parent) {
parent._context.push({
type: 'NumberLiteral',
value: node.value,
});
},
},
// 同理，遇到 StringLiteral 类型节点，也进行相同操作
StringLiteral: {
enter(node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value,
});
},
},
// 接下来，如果遇到函数调用式
CallExpression: {
enter(node, parent) {
// 这里就修改为符合 C 语言语法的函数调用式
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name,
},
arguments: [],
};
node._context = expression.arguments;
if (parent.type !== 'CallExpression') {
expression = {
type: 'ExpressionStatement',
expression: expression,
};
}
parent._context.push(expression);
},
}
});
// 最后返回这个新的 ast
return newAst;
}
codeGenerator
该函数的作用是将传入的 ast 转换为源代码字符串
// 由于是树结构，因此会递归调用该函数
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(', ') +
')'
);
// 标识符节点
case 'Identifier':
return node.name;
// 数字节点
case 'NumberLiteral':
return node.value;
// 字符串节点
case 'StringLiteral':
return '"' + node.value + '"';
// 无法识别的节点则抛出异常
default:
throw new TypeError(node.type);
}
}
compiler
组合编译器的各个阶段功能函数
function compiler(input) {
let tokens = tokenizer(input);
let ast = parser(tokens);
let newAst = transformer(ast);
let output = codeGenerator(newAst);
return output;
}