前言
是什么
抽象语法树（AST, Abstract Syntax Tree）是编译器和解释器中常用的数据结构，它表示代码的语法结构。AST 将代码分解成可以操作的节点，每个节点表示源代码中的一个结构。
有何用
要解析自定义的脚本，就可以通过构建 AST 来分析脚本的结构及其语法。
实现
依旧以if语句为例，但是 AST 可以解析包括condition、if body、else body等内容，且可以实现嵌套if语法。
步骤
要构建一个 AST，有如下流程：
- 定义语法规则：确定代码格式的语法结构，这里以
if为例。 - 编写词法分析器（Tokenizer/Lexer）：将源代码分解为标记（tokens）。
- 编写语法分析器（Parser）：将标记序列转换为 AST。
- 操作和遍历 AST：编写函数来遍历和操作生成的 AST。
1. 语法规则
if语句的语法规则如下：
- if 关键字后跟一个条件表达式。
- 条件表达式后跟一个块语句。
- 可选的 else 关键字后跟一个块语句。
2. 词法分析器 Tokenizer
本质就是遍历源码字符串，提取关键字、字面量等；也可以正则提取tokens。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
function tokenize(input) {
const tokens = [];
let current = 0;
while (current < input.length) {
let char = input[current];
if (/\s/.test(char)) {
current++;
continue;
}
if (char === "i" && input.slice(current, current + 2) === "if") {
tokens.push({ type: "if", value: "if" });
current += 2;
continue;
}
if (char === "e" && input.slice(current, current + 4) === "else") {
tokens.push({ type: "else", value: "else" });
current += 4;
continue;
}
if (char === "(") {
tokens.push({ type: "paren", value: "(" });
current++;
continue;
}
if (char === ")") {
tokens.push({ type: "paren", value: ")" });
current++;
continue;
}
if (char === "{") {
tokens.push({ type: "brace", value: "{" });
current++;
continue;
}
if (char === "}") {
tokens.push({ type: "brace", value: "}" });
current++;
continue;
}
if (/\d/.test(char)) {
let value = "";
while (/\d/.test(char)) {
value += char;
char = input[++current];
}
tokens.push({ type: "number", value });
continue;
}
throw new TypeError("Unexpected character: " + char);
}
return tokens;
}
3. 语法分析器 Parser
对tokens遍历，并按照token类型组织遍历的具体规则，比如if后面一个token必须是(，否则报错。
考虑嵌套if，这里的if-else body/consequent对walk()进行了递归调用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
function parse(tokens) {
let current = 0;
function walk() {
let token = tokens[current];
if (token.type === "number") {
current++;
return {
type: "NumberLiteral",
value: token.value,
};
}
if (token.type === "if") {
current++;
token = tokens[current];
if (token.type !== "paren" || token.value !== "(") {
throw new TypeError("Expected ( after if");
}
current++;
const test = walk();
token = tokens[current];
if (token.type !== "paren" || token.value !== ")") {
throw new TypeError("Expected ) after condition");
}
current++;
token = tokens[current];
if (token.type !== "brace" || token.value !== "{") {
throw new TypeError("Expected { after )");
}
current++;
const consequent = [];
while (
tokens[current].type !== "brace" ||
tokens[current].value !== "}"
) {
consequent.push(walk());
}
current++;
let alternate = null;
token = tokens[current];
if (token && token.type === "else") {
current++;
token = tokens[current];
if (token.type !== "brace" || token.value !== "{") {
throw new TypeError("Expected { after else");
}
current++;
alternate = [];
while (
tokens[current].type !== "brace" ||
tokens[current].value !== "}"
) {
alternate.push(walk());
}
current++;
}
return {
type: "IfStatement",
test,
consequent,
alternate,
};
}
throw new TypeError("Unexpected token type: " + token.type);
}
const ast = {
type: "Program",
body: [],
};
while (current < tokens.length) {
ast.body.push(walk());
}
return ast;
}
4. 遍历和操作 AST
实际上有了 AST，你可以对其进行几乎任何你想要的操作了。
这里对 AST 的所有结点进行了遍历，并使用访问对象来打印遍历的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function traverse(node, visitor) {
function traverseArray(array, parent) {
array.forEach((child) => {
traverseNode(child, parent);
});
}
function traverseNode(node, parent) {
let methods = visitor[node.type];
if (methods && methods.enter) {
methods.enter(node, parent);
}
switch (node.type) {
case "NumberLiteral":
break;
case "IfStatement":
traverseNode(node.test, node);
traverseArray(node.consequent, node);
if (node.alternate) {
traverseArray(node.alternate, node);
}
break;
case "Program":
traverseArray(node.body, node);
break;
default:
throw new TypeError(node.type);
}
if (methods && methods.leave) {
methods.leave(node, parent);
}
}
traverseNode(node, null);
}
其他
在实际的游戏脚本中，需要对token细化，此外也要实现具体的if-condition条件的判断，比如之前所发布的对condition的实现。
