七的博客
使用JavaScript语言实现迷你版本的编译器(五)-项目总结
使用JavaScript语言实现迷你版本的编译器(五)-项目总结
经过前面几个章节的一步步解析、转换、生成等步骤，已经实现了一个简单的编译器。 当然并不是所有的编译器都是这样，这还只是一个 demo 项目，重点是为了让我们能快速理解编译器的基本思想。
如果接触过 babel 这个库的话，可以发现 babel 的编译流程大体上跟我们写的编译器代码很相似。 babel 的工作流程也是 code parser -> AST transform -> code generate 这几个流程。 详细的 babel 原理可以参考这篇文章： https://babeljs.io/docs/en/#babel-is-a-javascript-compiler 。
1. 编译器的核心步骤
编译器的实现大致分为如下步骤：
- 词法分析 Tokenization
- 语法分析 Parsing
- 抽象语法树转换 AST Transformer
- 目标代码生成 Code Generation
1.1 词法分析
词法分析的目的是将输入的源代码字符串分解成一系列的标记，即 tokens。这些tokens 是构成语言的基本元素，比如数字、标识符或符号。
function tokenizer(input) {
// 当前的一个遍历字符串的下标
let currentIndex = 0;
let tokens = [];
while (currentIndex < input.length) {
// 1. 处理 (
// 括号直接添加到 tokens数组即可, 类型为 parenthesis, 值为 (
let currentChar = input[currentIndex];
if (currentChar === '(') {
tokens.push({
"type": "parenthesis",
"value": "("
});
currentIndex++;
continue
}
// 2. 处理)
// 括号直接添加到 tokens数组即可, 类型为 parenthesis, 值为 )
if (currentChar === ')') {
tokens.push({
"type": "parenthesis",
"value": ")"
});
currentIndex++;
continue
}
// 3. 处理空格
// 使用正则匹配当前字符是否为空格,空格就直接跳过
let spaceReg = /\s/
if (spaceReg.test(currentChar)) {
currentIndex++;
continue
}
// 4. 处理数值
let numberReg = /[0-9]/
if (numberReg.test(currentChar)) {
let numberString = "";
// 数值使用正则去匹配,因为数值可能有多位, 所以需要在循环中再开一个循环.
// 从当前位置开始向后依次遍历,一直遍历到不是数值的那位. 同时需要注意外层循环的 currentIndex 是需要一直变化的
while (numberReg.test(currentChar)) {
numberString = numberString + currentChar;
currentIndex++;
currentChar = input[currentIndex];
}
// 添加到 tokens 数组, 类型为 number, 值为获取到的数值
tokens.push({
"type": "number",
"value": numberString
})
continue
}
// 5. 处理使用 " 包裹的字符串
// 例子: (concat "foo" "bar")
if (currentChar === '"') {
let wrapString = "";
currentIndex++;
// 从当前位置开始向后遍历,一直遍历到不是 " 的前一个位置.
// 获取2个 " 之间的字符
while (currentChar !== '"') {
wrapString = wrapString + currentChar;
currentIndex++;
currentChar = input[currentIndex];
}
// 添加到 tokens 数组, 类型为 string, 值就是字符串
tokens.push({
"type": "number",
"value": wrapString
})
}
// 6. 处理字母标识符
// 使用正则判断是否为 a-z 的字母,这是 lisp 语言的定义
// 循环往后查找为字母标识符的字符一直到结束
// 添加到 tokens 数组, 类型为 name, 值就是字符串
// 例子 (add 2 4) . add 就是 name
let letterReg = /[a-z]/
if (letterReg.test(currentChar)) {
let letterString = "";
while (letterReg.test(currentChar)) {
letterString = letterString + currentChar;
currentIndex++;
currentChar = input[currentIndex];
}
tokens.push({
"type": "name",
"value": letterString
})
continue
}
// 7. 其他类型
// 直接抛出异常错误,暂时不支持这种类型
throw new TypeError('unknown character is: ' + char);
}
return tokens;
}
1.2. 语法分析
词法分析后，我们获得了一个 tokens 列表。语法分析的任务是将这些 token 重新组合，构建成一个抽象语法树（AST）。AST 是一个树形结构，代表了代码的语法结构，它将用于后续的转换或代码生成阶段。
function parser(tokens) {
// 这个函数主要将 tokens 转换为 ast 语法
// 跟踪 token 数组中位置
let currentIndex = 0;
// 总结下步骤:
// 1. 初始化根节点
// 2. 处理数值以及字符串 Token
// 定义 walk 函数用来遍历 tokens ,同时使用递归的方式, 不再使用 while 循环
function walk() {
let token = tokens[currentIndex];
// 1. 处理 number 类型,转为 AST NumberLiteral 节点
// 假设我们有一个数字 token { type: 'number', value: '2' }，解析器会创建一个节点 { type: 'NumberLiteral', value: '2' }。
if (token.type === 'number') {
currentIndex++;
return {
"type": "NumberLiteral",
"value": token.value
}
}
// 2. 处理 string类型,转换为 AST StringLiteral 节点
if (token.type === 'string') {
currentIndex++;
return {
"type": "StringLiteral",
"value": token.value
}
}
// 3. 创建 CallExpression 节点(CallExpressions)
// 3.1 如果遇到当前的类型为 parenthesis 并且为 ( 的话,我们直到这是一个函数调用的开始
if (token.type === 'parenthesis' && token.value === '(') {
// 3.2 跳过当前的开括号
currentIndex++;
token = tokens[currentIndex];
// 定义一个 CallExpression 类型的节点, name为当前 Token 的value. 定义一个空的参数数组(params).
// 假设我们的 tokens 数组是这样的：[{ type: 'paren', value: '(' }, { type: 'name', value: 'add' }, ...]，解析器将创建一个节点 { type: 'CallExpression', name: 'add', params: [] }。
let astNode = {
"type": "CallExpression",
"name": token.value,
"params": []
}
// 3.3 跳过函数名字的 token
currentIndex++;
token = tokens[currentIndex];
// 处理参数
// 3.4 由于函数的参数可能会是复杂的表达式,包括其他函数的调用. 我们需要递归调用 walk 函数来处理每个函数
// 在 Lisp中是支持 嵌套的括号的,我们接下来将会处理这种情况
// (add 2 (subtract 4 2)) 的 token 会是下面这样
// 上面的函数调用解析器将首先为 add 创建一个 'CallExpression' 节点，并且其参数将是一个数字字面量和另一个 'CallExpression' 节点。
// 后面的节点又是一个需要递归解析的节点
// 所以我们碰到嵌套的 CallExpression 时,使用 walk 函数递归进行处理
// 直到遇到闭合括号
// 循环中将调用 walk 函数返回一个节点,我们将节点放到 node.params 中
while (
(token.type !== 'parenthesis') ||
(token.type === 'parenthesis' && token.value !== ')')
) {
// 调用 walk 函数将返回的节点加入到参数中
astNode.params.push(walk());
token = tokens[currentIndex]
}
// 跳过闭合括号
currentIndex++;
return astNode;
}
// 其他类型直接抛出异常
throw new TypeError(token.type);
}
// 创建 AST 根节点 Program
let rootNode = {
"type": "Program",
body: []
}
// 开始遍历 tokens, 将通过 walk() 函数返回的节点压入 rootNode.body 中
// 之所以要这么循环的原因是可能有连续的 CallExpression ,不仅仅是嵌套
// 如果 tokens 数组表示 (add 2 2) (subtract 4 2)，AST 的 body 将包含两个 'CallExpression' 节点。
while (currentIndex < tokens.length) {
rootNode.body.push(walk());
}
return rootNode;
}
1.3. 抽象语法树转换
在语法分析阶段之后，我们得到了一个初步的抽象语法树（AST）。这个 AST 反映了源代码的结构和语法关系。接下来的转换阶段，我们可以对这个 AST 进行各种修改，以满足特定的编译目标或优化代码。
function transformer(ast) {
// 这里传入一个 list 的 AST 节点信息
// 创建一个新的 AST 节点, 有一个类型为 Program 的节点
let newAst = {
"type": "Program",
"body": []
};
// 这里有一个技巧, 通过在旧节点上添加一个 context 属性来引用新的 AST 节点
// context 是旧 AST 到新 AST 的一个引用
ast._context = newAst.body;
// 调用遍历器, 传入 AST 以及访问者对象
traverser(ast, {
// 对于NumberLiteral和StringLiteral节点，它们被直接复制到新AST中，类型不变。
// visitor 处理 NumberLiteral 类型节点
NumberLiteral: {
enter(node, parent) {
// 创建一个新的 NumberLiteral 节点, 压入 父节点的 context 中
parent._context.push({
"type": "NumberLiteral",
value: node.value
})
}
},
// 处理 StringLiteral 类型节点
StringLiteral: {
enter(node, parent) {
parent._context.push({
"type": "StringLiteral",
"value": node.value
})
}
},
// 处理 CallExpression 类型节点
// 对于CallExpression节点，转换更复杂。每个CallExpression都被转换成一个新的CallExpression节点，但是如果它不是另一个CallExpression的子节点（即它是顶层调用），则会被包装在一个ExpressionStatement中，因为在JavaScript中，独立的函数调用需要是一个语句。
CallExpression: {
enter(node, parent) {
// 创建一个新的 CallExpression 节点,包含 Identifier
let expression = {
type: "CallExpression",
callee: {
"type": "Identifier",
"name": node.name
},
arguments: [],
}
// 在原始的 CallExpression 节点上定义新的 context , 引用 expression 的 arguments
node._context = expression.arguments;
// 如果父节点不是 CallExpression
if (parent.type !== 'CallExpression') {
// 将 CallExpression 节点包装在一个 ExpressionStatement 中
// 因为在 JavaScript 中, 顶层的 CallExpression 通常是语句
expression = {
type: "ExpressionStatement",
expression: expression
};
}
// 将可能被包装的 CallExpression 节点推入父节点的 context 中
parent._context.push(expression);
}
}
})
// 函数结束时返回新创建的 AST
return newAst;
}
function traverser(ast, visitor) {
// traverseArray 函数允许我们遍历一个数组,调用 traverseNode
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent)
})
}
// 接受一个节点以及它的父节点
function traverseNode(node, parent) {
// 尝试从 visitor 对象中找出对应类型的方法集合
let methods = visitor[node.type];
// 如果存在 enter 方法, 递归进行子节点前调用它
if (methods && methods.enter) {
methods.enter(node, parent);
}
// 根据当前的节点类型, 选择不同的遍历策略
switch (node.type) {
// Program 节点则遍历它的 body 属性中的每一个节点
case 'Program':
traverseArray(node.body, node);
break;
// CallExpression节点就直接遍历它的params属性中的每一个节点。
case 'CallExpression':
traverseArray(node.params, node);
break;
// NumberLiteral 以及 StringLiteral 没有子节点,直接不做处理
case 'NumberLiteral':
case 'StringLiteral':
break
default:
throw new TypeError(node.type);
}
// 如果存在 exit 方法, 就在完成子节点的递归后调用它
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
// 最开始调用 traverseNode 来遍历, 顶层 AST 父节点是 null
traverseNode(ast, null);
}
1.4. 目标代码生成
代码生成是编译器的最后阶段，这里将经过转换的AST转化为目标代码，这可能是另一种高级语言的代码、字节码或机器代码。
function codeGenerator(node) {
// 根据节点类型进行分别处理
switch (node.type) {
// 针对 Program 节点,我们直接遍历 body 数组中的每一个节点
// 并调用 codeGenerator 函数,通过换行符连接起来
case "Program":
return node.body.map(codeGenerator).join("\n");
// 对于表达式语句节点,我们将内嵌的表达式调用 codeGenerator 函数,生成的代码后面添加一个分号
case "ExpressionStatement":
return (
// 添加分号是因为我们需要遵守正确的代码风格
codeGenerator(node.expression) + ";"
)
// 函数调用表达式处理,添加一个左括号,然后遍历 arguments 数组对每个参数调用 codeGenerator 函数,使用逗号串联起来,再添加一个右括号
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);
}
}
2. 项目结构以及内容
项目整体结构如下：
.
├── test.js // 测试文件
└── tiny-js-compiler.js // 编译器代码文件
2.1 编译器代码
tiny-js-compiler.js 的完整文件内容如下：
function tokenizer(input) {
let currentIndex = 0;
let tokens = [];
while (currentIndex < input.length) {
// 1. 处理 (
// 括号直接添加到 tokens数组即可, 类型为 parenthesis, 值为 (
let currentChar = input[currentIndex];
if (currentChar === '(') {
tokens.push({
"type": "parenthesis",
"value": "("
});
currentIndex++;
continue
}
// 2. 处理)
// 括号直接添加到 tokens数组即可, 类型为 parenthesis, 值为 )
if (currentChar === ')') {
tokens.push({
"type": "parenthesis",
"value": ")"
});
currentIndex++;
continue
}
// 3. 处理空格
// 使用正则匹配当前字符是否为空格,空格就直接跳过
// language=JSRegexp
let spaceReg = /\s/
if (spaceReg.test(currentChar)) {
currentIndex++;
continue
}
// 4. 处理数值
// 数值使用正则去匹配,因为数值可能有多位, 所以需要在循环中再开一个循环.
// 从当前位置开始向后依次遍历,一直遍历到不是数值的那位. 同时需要注意外层循环的 currentIndex 是需要一直变化的
// 添加到 tokens 数组, 类型为 number, 值为获取到的数值
// 例子: (add 123 456) 123 456 为数值
let numberReg = /[0-9]/
if (numberReg.test(currentChar)) {
let numberString = "";
// currentIndex++;
// currentChar = input[currentIndex]
while (numberReg.test(currentChar)) {
numberString = numberString + currentChar;
currentIndex++;
currentChar = input[currentIndex];
}
tokens.push({
"type": "number",
"value": numberString
})
continue
}
// 5. 处理使用 " 包裹的字符串
// 从当前位置开始向后遍历,一直遍历到不是 " 的前一个位置.
// 获取2个 " 之间的字符
// 添加到 tokens 数组, 类型为 string, 值就是字符串
// 例子: (concat "foo" "bar")
if (currentChar === '"') {
let wrapString = "";
currentIndex++;
while (currentChar !== '"') {
wrapString = wrapString + currentChar;
currentIndex++;
currentChar = input[currentIndex];
}
tokens.push({
"type": "number",
"value": wrapString
})
}
// 6. 处理字母标识符
// 使用正则判断是否为 a-z 的字母,这是 lisp 语言的定义
// 循环往后查找为字母标识符的字符一直到结束
// 添加到 tokens 数组, 类型为 name, 值就是字符串
// 例子 (add 2 4) . add 就是 name
let letterReg = /[a-z]/
if (letterReg.test(currentChar)) {
let letterString = "";
while (letterReg.test(currentChar)) {
letterString = letterString + currentChar;
currentIndex++;
currentChar = input[currentIndex];
}
tokens.push({
"type": "name",
"value": letterString
})
continue
}
// 7. 其他类型
// 直接抛出异常错误,暂时不支持这种类型
throw new TypeError('unknown character is: ' + char);
}
return tokens;
}
function parser(tokens) {
// 这个函数主要将 tokens 转换为 ast 语法
// [{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }
// 跟踪 token 数组中位置
let currentIndex = 0;
// 总结下步骤:
// 1. 初始化根节点
// 2. 处理数值以及字符串 Token
// 定义 walk 函数用来遍历 tokens ,同时使用递归的方式, 不再使用 while 循环
function walk() {
let token = tokens[currentIndex];
// 1. 处理 number 类型,转为 AST NumberLiteral 节点
// 假设我们有一个数字 token { type: 'number', value: '2' }，解析器会创建一个节点 { type: 'NumberLiteral', value: '2' }。
if (token.type === 'number') {
currentIndex++;
return {
"type": "NumberLiteral",
"value": token.value
}
}
// 2. 处理 string类型,转换为 AST StringLiteral 节点
if (token.type === 'string') {
currentIndex++;
return {
"type": "StringLiteral",
"value": token.value
}
}
// 3. 创建 CallExpression 节点(CallExpressions)
// 3.1 如果遇到当前的类型为 parenthesis 并且为 ( 的话,我们直到这是一个函数调用的开始
if (token.type === 'parenthesis' && token.value === '(') {
// 3.2 跳过当前的开括号
currentIndex++;
token = tokens[currentIndex];
// 定义一个 CallExpression 类型的节点, name为当前 Token 的value. 定义一个空的参数数组(params).
// 假设我们的 tokens 数组是这样的：[{ type: 'paren', value: '(' }, { type: 'name', value: 'add' }, ...]，解析器将创建一个节点 { type: 'CallExpression', name: 'add', params: [] }。
let astNode = {
"type": "CallExpression",
"name": token.value,
"params": []
}
// 3.3 跳过函数名字的 token
currentIndex++;
token = tokens[currentIndex];
// 处理参数
// 3.4 由于函数的参数可能会是复杂的表达式,包括其他函数的调用. 我们需要递归调用 walk 函数来处理每个函数
// 在 Lisp中是支持 嵌套的括号的,我们接下来将会处理这种情况
// (add 2 (subtract 4 2)) 的 token 会是下面这样
// [
// { 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: ')' }, <<< Closing parenthesis
// { type: 'paren', value: ')' }, <<< Closing parenthesis
// ]
// 上面的函数调用解析器将首先为 add 创建一个 'CallExpression' 节点，并且其参数将是一个数字字面量和另一个 'CallExpression' 节点。
// 后面的节点又是一个需要递归解析的节点
// 所以我们碰到嵌套的 CallExpression 时,使用 walk 函数递归进行处理
// 直到遇到闭合括号
// 循环中将调用 walk 函数返回一个节点,我们将节点放到 node.params 中
while (
(token.type !== 'parenthesis') ||
(token.type === 'parenthesis' && token.value !== ')')
) {
// 调用 walk 函数将返回的节点加入到参数中
astNode.params.push(walk());
token = tokens[currentIndex]
}
// 跳过闭合括号
currentIndex++;
return astNode;
}
// 其他类型直接抛出异常
throw new TypeError(token.type);
}
// 创建 AST 根节点 Program
let rootNode = {
"type": "Program",
body: []
}
// 开始遍历 tokens, 将通过 walk() 函数返回的节点压入 rootNode.body 中
// 之所以要这么循环的原因是可能有连续的 CallExpression ,不仅仅是嵌套
// 如果 tokens 数组表示 (add 2 2) (subtract 4 2)，AST 的 body 将包含两个 'CallExpression' 节点。
while (currentIndex < tokens.length) {
rootNode.body.push(walk());
}
// 例子
// (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": ")" }
// ]
// 解析器开始遍历 tokens。
// 遇到第一个开括号，知道一个函数调用即将开始。
// 然后是一个名字 token "add"，创建一个 CallExpression 节点，其 name 是 "add"。
// 然后是一个数字 token "2"，这是 add 的第一个参数，创建一个 NumberLiteral 节点。
// 遇到另一个开括号，意味着有另一个函数调用作为 add 的参数，开始一个新的 CallExpression 节点，其 name 是 "subtract"。
// subtract 的参数是两个数字 "4" 和 "2"，为每个都创建一个 NumberLiteral 节点。
// 遇到闭括号，意味着 subtract 函数调用的结束。
// 又一个闭括号，意味着 add 函数调用的结束。
// {
// "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"
// }
// ]
// }
// ]
// }
// ]
// }
return rootNode;
}
function transformer(ast) {
// 这里传入一个 list 的 AST 节点信息
// 创建一个新的 AST 节点, 有一个类型为 Program 的节点
let newAst = {
"type": "Program",
"body": []
};
// 这里有一个技巧, 通过在旧节点上添加一个 context 属性来引用新的 AST 节点
// context 是旧 AST 到新 AST 的一个引用
ast._context = newAst.body;
// 调用遍历器, 传入 AST 以及访问者对象
traverser(ast, {
// 对于NumberLiteral和StringLiteral节点，它们被直接复制到新AST中，类型不变。
// visitor 处理 NumberLiteral 类型节点
NumberLiteral: {
enter(node, parent) {
// 创建一个新的 NumberLiteral 节点, 压入 父节点的 context 中
parent._context.push({
"type": "NumberLiteral",
value: node.value
})
}
},
// 处理 StringLiteral 类型节点
StringLiteral: {
enter(node, parent) {
parent._context.push({
"type": "StringLiteral",
"value": node.value
})
}
},
// 处理 CallExpression 类型节点
// 对于CallExpression节点，转换更复杂。每个CallExpression都被转换成一个新的CallExpression节点，但是如果它不是另一个CallExpression的子节点（即它是顶层调用），则会被包装在一个ExpressionStatement中，因为在JavaScript中，独立的函数调用需要是一个语句。
CallExpression: {
enter(node, parent) {
// 创建一个新的 CallExpression 节点,包含 Identifier
let expression = {
type: "CallExpression",
callee: {
"type": "Identifier",
"name": node.name
},
arguments: [],
}
// 在原始的 CallExpression 节点上定义新的 context , 引用 expression 的 arguments
node._context = expression.arguments;
// 如果父节点不是 CallExpression
if (parent.type !== 'CallExpression') {
// 将 CallExpression 节点包装在一个 ExpressionStatement 中
// 因为在 JavaScript 中, 顶层的 CallExpression 通常是语句
expression = {
type: "ExpressionStatement",
expression: expression
};
}
// 将可能被包装的 CallExpression 节点推入父节点的 context 中
parent._context.push(expression);
}
}
})
// 函数结束时返回新创建的 AST
return newAst;
}
function traverser(ast, visitor) {
// traverseArray 函数允许我们遍历一个数组,调用 traverseNode
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent)
})
}
// 接受一个节点以及它的父节点
function traverseNode(node, parent) {
// 尝试从 visitor 对象中找出对应类型的方法集合
let methods = visitor[node.type];
// 如果存在 enter 方法, 递归进行子节点前调用它
if (methods && methods.enter) {
methods.enter(node, parent);
}
// 根据当前的节点类型, 选择不同的遍历策略
switch (node.type) {
// Program 节点则遍历它的 body 属性中的每一个节点
case 'Program':
traverseArray(node.body, node);
break;
// CallExpression节点就直接遍历它的params属性中的每一个节点。
case 'CallExpression':
traverseArray(node.params, node);
break;
// NumberLiteral 以及 StringLiteral 没有子节点,直接不做处理
case 'NumberLiteral':
case 'StringLiteral':
break
default:
throw new TypeError(node.type);
}
// 如果存在 exit 方法, 就在完成子节点的递归后调用它
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
// 最开始调用 traverseNode 来遍历, 顶层 AST 父节点是 null
traverseNode(ast, null);
}
function codeGenerator(node) {
// 根据节点类型进行分别处理
switch (node.type) {
// 针对 Program 节点,我们直接遍历 body 数组中的每一个节点
// 并调用 codeGenerator 函数,通过换行符连接起来
case "Program":
return node.body.map(codeGenerator).join("\n");
// 对于表达式语句节点,我们将内嵌的表达式调用 codeGenerator 函数,生成的代码后面添加一个分号
case "ExpressionStatement":
return (
// 添加分号是因为我们需要遵守正确的代码风格
codeGenerator(node.expression) + ";"
)
// 函数调用表达式处理,添加一个左括号,然后遍历 arguments 数组对每个参数调用 codeGenerator 函数,使用逗号串联起来,再添加一个右括号
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);
}
}
function compiler(input) {
let tokens = tokenizer(input);
let ast = parser(tokens);
let newAst = transformer(ast);
return codeGenerator(newAst);
}
module.exports = {
tokenizer,
parser,
traverser,
transformer,
codeGenerator,
compiler,
};
2.2 测试用例代码
测试用例 test.js 的内容如下：
const {
tokenizer,
parser,
transformer,
codeGenerator,
compiler,
} = require('./tiny-js-compiler');
const assert = require('assert');
const input = '(add 2 (subtract 4 2))';
const output = 'add(2, subtract(4, 2));';
const tokens = [
{type: 'parenthesis', value: '('},
{type: 'name', value: 'add'},
{type: 'number', value: '2'},
{type: 'parenthesis', value: '('},
{type: 'name', value: 'subtract'},
{type: 'number', value: '4'},
{type: 'number', value: '2'},
{type: 'parenthesis', value: ')'},
{type: 'parenthesis', value: ')'}
];
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'
}]
}]
}]
};
const newAst = {
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'
}]
}]
}
}]
};
assert.deepStrictEqual(tokenizer(input), tokens, 'Tokenizer should turn `input` string into `tokens` array');
assert.deepStrictEqual(parser(tokens), ast, 'Parser should turn `tokens` array into `ast`');
assert.deepStrictEqual(transformer(ast), newAst, 'Transformer should turn `ast` into a `newAst`');
assert.deepStrictEqual(codeGenerator(newAst), output, 'Code Generator should turn `newAst` into `output` string');
assert.deepStrictEqual(compiler(input), output, 'Compiler should turn `input` into `output`');
console.log('All Passed!');
3. 测试
测试我们需要用到 node.js 运行 test.js 文件， 在命令行中执行如下命令：
node test.js
如果看到 All Passed! 则说明所有的测试用例都跑通。
4. 结语
通过这几篇文章，相信如何从零开始构建一个简单的编译器应该有了基本的理解。 虽然这只是一个基础的版本，但是现代化的编译器的基本流程跟这个是差不多的。你可以更加深入的学习编译原理的知识，然后去扩展或者改进这个迷你编译器。动手实践很重要！
你可以试着添加如下的语言特性：
支持更多的数据类型：如布尔值、null 和 undefined。
支持复杂的表达式：如二元运算符、逻辑运算符等。
支持控制流语句：如if语句、循环语句等。
每增加一个新的特性，都需要在词法分析器、语法分析器和代码生成器中相应地增加处理逻辑。
5. 参考资料
- https://github.com/jamiebuilds/the-super-tiny-compiler babel的一个作者编写的编译器例子
- https://babeljs.io/docs/#babel-is-a-javascript-compiler babel 官网的介绍