目录
长夜过，最难熬的破晓一定会赴约刚好。 最向往的时光，是一如既往，就好。
自从我打 OI 以来，【集训队互测 2015】未来程序·改 就是我的梦中情题。它需要实现一个 C++ 子集的解释器。当年我的知识水平还远远不足以 A 掉它，只能望题兴叹。
大三上学期时学习了 CSI311: Principles of Programming Languages，了解了一些编译原理的知识。这让我重新燃起了对它的想法，然而当时仍感无从下手，加上事务繁多继而搁置了。前一段时间闲下来了，就想着挑战一下，用实现一个完整编译器的思路去 A 掉这道题。
然而我还是 too young too simple，实现编译器后端实在是有点难，为了正反馈考虑，我暂时选择实现了一个解释器。因此这篇博客也只是上篇。
qwqVictor/future-program。
简介
虽然比较复杂，但我仍然选择使用 C++ 来实现（主要是当时有一个可能的暑期实习会用到 C++）。目前整个程序的设计分为以下几个部分：
- 常量：包括运算符、符号定义，关键字定义，预定义的运算符等。
- 编译器前端： a. 词法分析器：其中包含了一个 tokenizer（分词器），对 token 进行分析，形成词素 b. 语法分析器：对词法分析器输出的词素流进行分析，形成 AST（抽象语法树）
- 解释器运行时：管理程序的执行栈、内存和 IO，解释执行 AST。
为了实现简洁，我没有考虑出现畸形程序的情况，没有做语义分析。
在接下来的例子中，我们使用 B2092 开关灯 的 AC 代码作为例子展示。
#include<cstdio>
#include<iostream>
using namespace std;
int lights[5001];
int main() {
int n, i, j;
cin >> n;
for (i = 2; i <= n; i = i + 1)
for (j = 1; i * j <= n; j = j + 1)
lights[i * j] = !lights[i * j];
for (i = 1; i <= n; i = i + 1)
if (lights[i] == 0) {
cout << i;
putchar(32);
}
}
编译器前端
编译器前端是实现它的重头戏，主要分为词法分析和语法分析两部分。
词法分析
词法分析实现在 LexicalAnalyzer 类中。
在编程语言中，我们可以把词素分为：关键字 (keyword)、符号 (symbol)、运算符 (operator)、字面量常量 (literial/constant) 和标识符 (identifier)，其中标识符包括变量和函数。
我的词法分析进行了两次分析 (2Pass)，来解决一些二义性。
分词
根据这个 C++ 子集的文法定义，在 LexicalAnalyzer::Tokenizer 类中我采用了一套简单的规则来分词：
- 首先，每次取 token 时过滤掉开头的空白字符
- 判断 token 是否为 symbol 或 operator 的组成部分开始： a. 如果以 symbol/operator 开始，且字符串加入下一个字符后无法构成 symbol/operator，结束 b. 如果不以 symbol/operator 开始，且当前字符为 symbol/operator 的部分，则结束 c. 其中，所有多于一个字符的 symbol/operator，除了 ‘||’ 和 ‘&&’ 的首字符均为一个合法的 symbol/operator
1Pass
分词后，我们得到了一个 token 流。
LexicalAnalyzer::parseToken() 第一次分析初步分类 token 形成的词素，识别出关键字、标识符和大部分符号、标识符。并对标识符离散化，即使用数字 id 代替字符串名称来存储标识符，节省空间。
然而这次解析后，仍然存在一些二义性，比如：
(和)可能代表函数声明、函数调用、if for while 等控制语句的括号或者表达式中的括号。{和}可能表示函数体的开始和结束，也可能表示语句块的开始和结束;可能表示 for 循环中的条件分隔符，也可能是语句分隔符+和-可能表示一元运算符的正/负号，也可能表示二元运算符的加/减号
2Pass
为了解决这些二义性，我们引入了第二次解析，LexicalAnalyzer::resolveLexemeTypes() 进行了 2Pass。
2Pass 的过程中，会根据当前的情境来解决二义性，例如：
- 使用栈记录小括号和花括号，从而判断其含义
- 记录上一次的控制字符，判断
(和)以及;的含义 - 记录是否在 int 定义内，进一步判断是变量定义还是函数声明，从而判断
(和)、{和}的含义 - 根据相邻词素，判断
+和-的含义。 a. 如果左侧的词素是 symbol/operator，且不是)、]，则必为正负含义，否则为加减
总结
在初始阶段，我们还需要去除固定的三行，以及导入预定义的标识符等等。注意，这里我们将 cin、cout 和 endl 作为三个内建对象处理，而不是关键字。
对于例子中的代码，它得到的词素列表如下：
词素列表
0: { type:Keyword,value:Int }
1: { type:Identifier,value:lights }
2: { type:Symbol,value:ArrayAccessDefBegin }
3: { type:IntConstant,value:5001 }
4: { type:Symbol,value:ArrayAccessDefEnd }
5: { type:Symbol,value:StatementSeparator }
6: { type:Keyword,value:Int }
7: { type:Identifier,value:main }
8: { type:Symbol,value:FunctionCallDefBegin }
9: { type:Symbol,value:FunctionCallDefEnd }
10: { type:Symbol,value:FunctionBodyBegin }
11: { type:Keyword,value:Int }
12: { type:Identifier,value:n }
13: { type:Symbol,value:CommaSeparator }
14: { type:Identifier,value:i }
15: { type:Symbol,value:CommaSeparator }
16: { type:Identifier,value:j }
17: { type:Symbol,value:StatementSeparator }
18: { type:Identifier,value:cin }
19: { type:Operator,value:CinTo }
20: { type:Identifier,value:n }
21: { type:Symbol,value:StatementSeparator }
22: { type:Keyword,value:For }
23: { type:Symbol,value:ControlBlockStatementBegin }
24: { type:Identifier,value:i }
25: { type:Operator,value:Assign }
26: { type:IntConstant,value:2 }
27: { type:Symbol,value:ConditionSeparator }
28: { type:Identifier,value:i }
29: { type:Operator,value:LessEqual }
30: { type:Identifier,value:n }
31: { type:Symbol,value:ConditionSeparator }
32: { type:Identifier,value:i }
33: { type:Operator,value:Assign }
34: { type:Identifier,value:i }
35: { type:Operator,value:Plus }
36: { type:IntConstant,value:1 }
37: { type:Symbol,value:ControlBlockStatementEnd }
38: { type:Keyword,value:For }
39: { type:Symbol,value:ControlBlockStatementBegin }
40: { type:Identifier,value:j }
41: { type:Operator,value:Assign }
42: { type:IntConstant,value:1 }
43: { type:Symbol,value:ConditionSeparator }
44: { type:Identifier,value:i }
45: { type:Operator,value:Multiply }
46: { type:Identifier,value:j }
47: { type:Operator,value:LessEqual }
48: { type:Identifier,value:n }
49: { type:Symbol,value:ConditionSeparator }
50: { type:Identifier,value:j }
51: { type:Operator,value:Assign }
52: { type:Identifier,value:j }
53: { type:Operator,value:Plus }
54: { type:IntConstant,value:1 }
55: { type:Symbol,value:ControlBlockStatementEnd }
56: { type:Identifier,value:lights }
57: { type:Symbol,value:ArrayAccessDefBegin }
58: { type:Identifier,value:i }
59: { type:Operator,value:Multiply }
60: { type:Identifier,value:j }
61: { type:Symbol,value:ArrayAccessDefEnd }
62: { type:Operator,value:Assign }
63: { type:Operator,value:Not }
64: { type:Identifier,value:lights }
65: { type:Symbol,value:ArrayAccessDefBegin }
66: { type:Identifier,value:i }
67: { type:Operator,value:Multiply }
68: { type:Identifier,value:j }
69: { type:Symbol,value:ArrayAccessDefEnd }
70: { type:Symbol,value:StatementSeparator }
71: { type:Keyword,value:For }
72: { type:Symbol,value:ControlBlockStatementBegin }
73: { type:Identifier,value:i }
74: { type:Operator,value:Assign }
75: { type:IntConstant,value:1 }
76: { type:Symbol,value:ConditionSeparator }
77: { type:Identifier,value:i }
78: { type:Operator,value:LessEqual }
79: { type:Identifier,value:n }
80: { type:Symbol,value:ConditionSeparator }
81: { type:Identifier,value:i }
82: { type:Operator,value:Assign }
83: { type:Identifier,value:i }
84: { type:Operator,value:Plus }
85: { type:IntConstant,value:1 }
86: { type:Symbol,value:ControlBlockStatementEnd }
87: { type:Keyword,value:If }
88: { type:Symbol,value:ControlBlockStatementBegin }
89: { type:Identifier,value:lights }
90: { type:Symbol,value:ArrayAccessDefBegin }
91: { type:Identifier,value:i }
92: { type:Symbol,value:ArrayAccessDefEnd }
93: { type:Operator,value:Equal }
94: { type:IntConstant,value:0 }
95: { type:Symbol,value:ControlBlockStatementEnd }
96: { type:Symbol,value:BlockBegin }
97: { type:Identifier,value:cout }
98: { type:Operator,value:CoutFrom }
99: { type:Identifier,value:i }
100: { type:Symbol,value:StatementSeparator }
101: { type:Identifier,value:putchar }
102: { type:Symbol,value:FunctionCallDefBegin }
103: { type:IntConstant,value:32 }
104: { type:Symbol,value:FunctionCallDefEnd }
105: { type:Symbol,value:StatementSeparator }
106: { type:Symbol,value:BlockEnd }
107: { type:Symbol,value:FunctionBodyEnd }
语法分析
语法分析负责解析上一步词法分析形成的词素流，生成抽象语法树。在这一部分，LLVM 的一篇教程 My First Language Frontend with LLVM Tutorial 给了我许多帮助。
SyntaxAnalyzer 类实现了语法分析。
结构设计
抽象语法树是程序代码的等价表示形式，因此它是一棵树状结构。其中节点可能有许多类型，且树状结构要持有许多节点的引用。这里我使用了虚函数来提供统一的获取节点类型的方法（手动实现反射.jpg），通过智能指针管理引用。
SyntaxAnalyzer::BaseASTNode 是所有 AST 节点类的基类，总计有以下几种 AST 节点：
BaseASTNode, // 基类
IdentifierASTNode, // 标识符（变量
IntConstantASTNode, // 整数常量
BinaryExpressionASTNode, // 表达式（一元/二元）
FunctionCallASTNode, // 函数调用
BlockASTNode, // 代码块
IfStatementASTNode, // If 语句
WhileStatementASTNode, // While 语句
ForStatementASTNode, // For 语句
ReturnStatementASTNode // 函数返回
作用域
变量总是需要有作用域的。C/C++ 为词法作用域，一个代码块构成了一个作用域，这里我们实现了链式查找，每个代码块创建一个当前作用域，在当前作用域无法找到变量的情况下则向上递归查找，直到查找到全局作用域。具体实现参考 SyntaxAnalyzer::Scope
变量管理
为了后续实现方便，变量本身的声明不再在 AST 中体现。 相反地，在解析变量声明时，我们将变量分为栈变量和静态变量，并计算它的偏移量。调用变量时直接从栈帧或全局内存中偏移。
关于数组，为了方便解引用，我们还额外记录了数组每一维度的偏移量。
具体实现参考 SyntaxAnalyzer::declarationAnalyze()。
函数
在这个编程语言中，函数默认返回值为 int 类型。则函数的组成部分有函数名称、函数参数和函数体。
我们的实现中，函数还会记录它的栈空间大小。
函数在 SyntaxAnalyzer::Function 类中描述。在 SyntaxAnalyzer::functionAnalyze() 函数中实现了对函数本身的解析。
语句解析
语句解析主要分为两个部分，解析变量定义、表达式和语句块，其中我们将赋值操作视为一个表达式。
对于变量定义的解析，我们需要同时记录栈空间大小和语句块的变量大小。
我们需要重点处理的是语句块。对于 For、While 等只需要按部就班解析即可，而 If 语句需要注意，我们需要记录上一个 If 的信息，用于 Else 进行匹配。Else-If 结构我们可以直接视为 else { if (xxx) } 的结构处理。
SyntaxAnalyzer::statementsAnalyze() 函数实现了语句的解析。
表达式解析
表达式求值是一个老生常谈的问题。
我们使用一个栈和一个线性表构建符号栈和后缀表达式来实现中缀表达式的解析，其中符号栈保存 AST 节点（对于未确定左右节点的二元表达式，其左右节点均为 nullptr；一元运算符 !、+ 和 - 只有右节点）。具体方法如下：
- 如果当前的词素是变量、常量，直接推入后缀表达式
- 如果当前词素是左括号，将其压入符号栈
- 如果当前词素是右括号，不断弹出符号栈中的运算符直到遇见对应的左括号，将除了左括号的运算符依次推入后缀表达式
- 如果当前词素是其他运算符： a. 符号栈非空时，按左结合原则，从符号栈中弹出优先级相同或更高的运算符，对于赋值运算符它是右结合的，所以相同优先级不弹出。还需要特殊处理一元运算符。 b. 每次弹出运算符时，将弹出的运算符推入后缀表达式。 c. 最后将当前运算符压入符号栈
- 遇到函数调用时，递归解析函数参数中的每一个表达式。然后生成一个函数调用 AST 节点推入后缀表达式
- 遇到数组解引用时，递归解析每一维度并生成乘以对应偏移量相加的右节点，然后将数组作为左节点生成一个数组解引用二元表达式 AST 节点
- 最后将符号栈的剩余内容弹出推入后缀表达式
后缀表达式生成后，复用符号栈，判断未初始化的运算表达式节点基于后缀表达式生成 AST 即可。
SyntaxAnalyzer::expressionAnalyze() 函数实现了表达式解析。
总结
全局解析时，我们需要主动触发的只有 int 开头的解析，可以根据紧随 int 的标识符后面是不是 FunctionCallDefBegin 即左括号来判断调用 functionAnalyze 还是 declarationAnalyze。
Debug 代码中包含一个调试用的输出，它可以将代码形成的 AST 以 JSON 形式输出。对于例子中的代码，它形成的 AST 如下：
AST 形式
{
"main": {
"id": 1,
"name": "main",
"stackSize": 3,
"ast": {
"type": "BlockASTNode",
"stmts": [
{
"type": "BinaryExpressionASTNode",
"op": "CinTo",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "BuiltinObject",
"id": 2,
"name": "cin",
"baseOffset": 0,
"size": 0,
"static": 1
}
},
"right": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 7,
"name": "n",
"baseOffset": 0,
"size": 1,
"static": 0
}
}
},
{
"type": "ForStatementASTNode",
"init": {
"type": "BinaryExpressionASTNode",
"op": "Assign",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "IntConstantASTNode",
"value": 2
}
},
"condition": {
"type": "BinaryExpressionASTNode",
"op": "LessEqual",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 7,
"name": "n",
"baseOffset": 0,
"size": 1,
"static": 0
}
}
},
"iter": {
"type": "BinaryExpressionASTNode",
"op": "Assign",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "BinaryExpressionASTNode",
"op": "Plus",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "IntConstantASTNode",
"value": 1
}
}
},
"loop": {
"type": "ForStatementASTNode",
"init": {
"type": "BinaryExpressionASTNode",
"op": "Assign",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 9,
"name": "j",
"baseOffset": 2,
"size": 1,
"static": 0
}
},
"right": {
"type": "IntConstantASTNode",
"value": 1
}
},
"condition": {
"type": "BinaryExpressionASTNode",
"op": "LessEqual",
"left": {
"type": "BinaryExpressionASTNode",
"op": "Multiply",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 9,
"name": "j",
"baseOffset": 2,
"size": 1,
"static": 0
}
}
},
"right": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 7,
"name": "n",
"baseOffset": 0,
"size": 1,
"static": 0
}
}
},
"iter": {
"type": "BinaryExpressionASTNode",
"op": "Assign",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 9,
"name": "j",
"baseOffset": 2,
"size": 1,
"static": 0
}
},
"right": {
"type": "BinaryExpressionASTNode",
"op": "Plus",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 9,
"name": "j",
"baseOffset": 2,
"size": 1,
"static": 0
}
},
"right": {
"type": "IntConstantASTNode",
"value": 1
}
}
},
"loop": {
"type": "BinaryExpressionASTNode",
"op": "Assign",
"left": {
"type": "BinaryExpressionASTNode",
"op": "ArrayMemoryDereference",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "IntegerArray",
"id": 6,
"name": "lights",
"dimensions": [
5001
],
"baseOffset": 1,
"size": 5001,
"static": 1
}
},
"right": {
"type": "BinaryExpressionASTNode",
"op": "Multiply",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 9,
"name": "j",
"baseOffset": 2,
"size": 1,
"static": 0
}
}
}
},
"right": {
"type": "BinaryExpressionASTNode",
"op": "Not",
"left": null,
"right": {
"type": "BinaryExpressionASTNode",
"op": "ArrayMemoryDereference",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "IntegerArray",
"id": 6,
"name": "lights",
"dimensions": [
5001
],
"baseOffset": 1,
"size": 5001,
"static": 1
}
},
"right": {
"type": "BinaryExpressionASTNode",
"op": "Multiply",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 9,
"name": "j",
"baseOffset": 2,
"size": 1,
"static": 0
}
}
}
}
}
}
}
},
{
"type": "ForStatementASTNode",
"init": {
"type": "BinaryExpressionASTNode",
"op": "Assign",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "IntConstantASTNode",
"value": 1
}
},
"condition": {
"type": "BinaryExpressionASTNode",
"op": "LessEqual",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 7,
"name": "n",
"baseOffset": 0,
"size": 1,
"static": 0
}
}
},
"iter": {
"type": "BinaryExpressionASTNode",
"op": "Assign",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "BinaryExpressionASTNode",
"op": "Plus",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
},
"right": {
"type": "IntConstantASTNode",
"value": 1
}
}
},
"loop": {
"type": "IfStatementASTNode",
"condition": {
"type": "BinaryExpressionASTNode",
"op": "Equal",
"left": {
"type": "BinaryExpressionASTNode",
"op": "ArrayMemoryDereference",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "IntegerArray",
"id": 6,
"name": "lights",
"dimensions": [
5001
],
"baseOffset": 1,
"size": 5001,
"static": 1
}
},
"right": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
}
},
"right": {
"type": "IntConstantASTNode",
"value": 0
}
},
"truthy": {
"type": "BlockASTNode",
"stmts": [
{
"type": "BinaryExpressionASTNode",
"op": "CoutFrom",
"left": {
"type": "IdentifierASTNode",
"identifier": {
"type": "BuiltinObject",
"id": 3,
"name": "cout",
"baseOffset": 0,
"size": 0,
"static": 1
}
},
"right": {
"type": "IdentifierASTNode",
"identifier": {
"type": "Integer",
"id": 8,
"name": "i",
"baseOffset": 1,
"size": 1,
"static": 0
}
}
},
{
"type": "FunctionCallASTNode",
"function": "putchar",
"funcId": 5,
"arguments": [
{
"type": "IntConstantASTNode",
"value": 32
}
]
}
]
},
"falsy": null
}
},
{
"type": "ReturnStatementASTNode",
"expr": null
}
]
}
},
"putchar": {
"id": 5,
"name": "putchar",
"stackSize": 0,
"ast": null
}
}
解释器运行时
我们的运行时实现本质上是实现了一个堆栈管理器和 AST 遍历器。
Runtime 类实现了解释器运行时。
内存分配
我们将内存分为两个部分：静态存储区和栈区。静态存储区使用一个 std::vector<int> 存储，栈区使用 std::stack<std::vector<int>> 存储。并且使用了一个 std::stack<int> 来存储栈顶指针（esp），用于作用域销毁时的变量回收。
特别地，我们需要函数的最大栈空间来预留和清理 vector 内存。
AST 执行
在实现 AST 执行时，我们需要确定两种值：
- 左值：可获取内存地址 (referenceable) 的值。它可以出现在赋值操作的左侧，或者
CinTo操作的右侧。 - 右值：不可获取内存地址的值，例如函数的返回值或表达式的计算结果，它只能作为数值使用。
因此，我们实现了一个判断函数和两个求值函数。Runtime::referenceable() 判断一个 AST 节点是否是左值。Runtime::pointerEval() 和 Runtime::eval() 分别用于取得左值的指针或执行 AST 节点获取右值。
只有两种 AST 节点可以作为左值：变量的 IdentifierASTNode 或者运算符为 ArrayMemoryDereference 的二元运算符表达式。
对于需要使用左值的场景，Runtime::pointerEval() 会返回一个 std::pair<bool, uint32_t>，分别表示变量是否是静态变量，以及它的内存地址。
Runtime::eval() 会根据 AST 的类型执行不同的动作，并最终返回一个返回值。
对于函数调用，我们会将一个新的栈帧压入 stackFrames，同时压入新的 esp，然后进入该函数的执行流。
总结
《未来程序·改》可以说是燃起我对编译原理的最初兴趣的一道题了。
实际上我买编译原理可能是因为2021 cspj的表达式树那道题。
虽然是简单的后缀表达式，但是给我带来了极大的震撼。
太厉害啦！（╯>皿<）╯