使用JavaScript语言实现迷你版本的编译器(二)-语法分析
使用JavaScript语言实现迷你版本的编译器(二)-语法分析
上一篇文章主要介绍了如何将源代码转换为一系列的 tokens 。 本篇将开始讲解如何将这些 **tokens ** 转换为抽象语法树。
1. 概念讲解
1.1 什么是语法分析?
语法分析 ( Parsing) 是编译过程中的一个阶段, 它接受词法分析阶段生成的 tokens,并将他们组织成语法结构。 这种结构通常表示为一个树,即抽象语法树 AST (Abstract Syntax Tree)。 抽象语法树是源代码的层级表示,展示了代码的各个部分如何组合在一起。
1.2 关键术语
- Token,中文直译过来就是令牌的意思。 它是词法解析的产出物,代表了源代码中最小的有意义的单元,比如数字、字符串、括号等等。
- AST ,抽象语法树, 是代码的树形结构表示方法,可以展示代码各部分语法关联关系。每个节点代表代码中的一构造,比如一个数字、一个字符串,或者一个函数调用。
1.3 使用图来说明 AST
为了更好地理解 AST,我们可以将其可视化。考虑以下的数学表达式:
(add 2 (subtract 4 2))
对应的 AST 可以用一棵树来表示,其中每个节点都是一个操作或值:
CallExpression (add)
/ \
NumberLiteral (2) CallExpression (subtract)
/ \
NumberLiteral (4) NumberLiteral (2)
这个树状结构清晰地表明了代码的逻辑结构:一个add
函数调用包含了两个参数,其中一个参数是数字2
,另一个是 subtract
函数调用的结果。
1.4 从 tokens 到 AST 的结构变化
下面展示了从 tokens 到 AST 的结构变化
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: ')' },
]
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 主要反映了 Lisp 语言源代码的结构:一个 add 函数的调用,包括两个参数,一个是数字2, 另一个是 subtract 的函数调用。
2. 实现语法分析器
2.1 逻辑梳理
在转换前,让我们先理清楚逻辑。 我们的目标肯定是要先遍历 tokens 数组,将遇到的每一个 token 先转化成 AST 节点。当我们遇到函数调用时,例如包括括号和函数名,我们需要特别注意,这里面可能会包含嵌套的表达式,处理的时候我们需要使用递归的方法去处理。
首先我们将创建一个 walk()
函数,它的主要职责为处理单个 token ,并返回相应的 AST 节点, 函数的大体逻辑如下:
- 碰到 number 类型 token ,转为 AST NumberLiteral 节点,并将token的值作为节点的值。
- 碰到 string 类型 token ,转换为 AST StringLiteral 节点,并将token的值作为节点的值。
- 碰到 parenthesis 类型并且是 ( ,说明这是一个函数调用的开始。 这里需要创建一个 CallExpression 的节点,同时使用递归去处理函数参数。
- 遇到未知的 token 类型,直接抛出一个错误。
这个过程有点像小时候搭积木一样,我们逐个检查每一个 token ,并决定如何将它们组成更大的结构。
2.2 编写代码
按照上面梳理的逻辑,我们开始逐步实现这个函数。
function parser(tokens) {
// 这个函数主要将 tokens 转换为 ast 语法
let currentIndex = 0; // 跟踪 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;
}
这段代码实现了我们之前描述的逻辑,定义了一个 walk()
方法来递归构建抽象语法树。 parser()
方法初始化了 AST 并且填充了 body 属性,最后返回完整的抽象语法树。
这里需要注意的是,我们假设方法的入参是完全正确的,并没有使用额外的逻辑去判断是否有语法错误或者其他的异常情况。
3. 代码测试
在 test.js
函数中添加如下代码:
const {
parser,
} = require('./tiny-js-compiler');
const assert = require('assert');
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'
}]
}]
}]
};
assert.deepStrictEqual(parser(tokens), ast, 'Parser should turn `tokens` array into `ast`');
console.log('Test case Passed!');
执行运行命令:
node test.js
如果看到 Test case Passed!
则说明测试通过,编写的 parser()
函数达到了我们想要的效果。
4. 结语
下一章节我们将进行抽象语法树的转换。