题解：P11738 [集训队互测 2015] 未来程序·改
normalpcer · · 题解
题意简述
要求实现一个解释器，支持 C++ 语言的一个子集。
-
需要支持变量。
- 除了
cin,cout,endl，变量类型一定为int或若干维度的int数组。 - 程序中所有的整数字面量均为十进制。
- 变量声明的时候赋予默认值
0 。不会出现声明的同时初始化变量。 - 数组每个维度的大小一定为单个十进制数。
- 除了
-
需要支持函数。
- 函数的返回值一定为
int。 - 函数的参数一定为空或者若干个
int。 - 如果没有返回语句，认为返回值是
0 。 - 似乎函数声明的同时一定会进行定义。
- 函数的返回值一定为
-
需要支持以下的整数运算：
- 算术运算：加减乘除、取模，正负号。
- 逻辑运算：与或非，异或（这里的异或似乎只会对
0 和1 进行）。没有“短路”机制。 - 比较运算：大于、小于、大于等于、小于等于、等于、不等于。
- 赋值。和 C++ 中一样，赋值语句的返回值是到左操作数的引用。复制操作为右结合。
另外，需要支持
cin、cout的左移和右移。（右操作数只会为整数） 需要正确地处理圆括号和方括号。
-
需要支持以下的控制语句：
if (stat) stat [else stat]while (stat) statfor (stat; stat; stat) stat- 上述语句的主体部分可以为单条语句，或者是花括号包裹的多条语句。
-
需要支持以下没有任何作用的语句：
#include <iostream>#include <cstdio>using namespace std;
-
需要实现函数
putchar(int)，输出给定 ASCII 码的字符。
以上整理的可能不是很全面，请以题面为准。
分析
事先声明，本人对于一些术语的认识可能并不正确，对于以下内容可能的的一些错误，请见谅。
由于这段代码在写这道题之前就已经实现了一些功能，可能会有一些冗余的设计。
我将整个解释器分为了分词（Tokenize）、解析（Parse）、解释运行（Interpret）三个阶段。
分词
首先是分词。读入的程序是一个个的字符，字符之间免不了会有一些关联。于是我们可以先把它们变成一系列 Token。
这个部分可以参考 UVA12421。
我把 Token 分为了整数、浮点数、字符串、标识符、换行符、符号这几种。因为 C++ 对于换行不敏感，所以实际上没有用到换行符。由于代码长度限制，我在后来删除了字符串和浮点数的处理。
Token 类的定义如下：
struct Token {
enum Tag {
NoneTag, IdentifierTag, SymbolTag, IntegerTag, StringTag, EndOfLineTag, FloatingPointTag
} tag = NoneTag;
std::variant<int, Identifier, Integer, String, Symbol, FloatingPointNumber> value = 0;
};std::variant 是一个类型安全的联合体，可以在被删除时自动调用正确的析构函数。尖括号中的类型用于存储各自的信息。为了方便，String，Identifier和 Symbol 的存储直接使用 std::string。
分词的流程比较容易，我们通过一个字符大概就能知道接下来的 Token 类型。
例如，读到一个字母或者下划线，就知道接下来是一个标识符；读到一个数字，就知道接下来是一个整数或者浮点数；读到一个双引号，就知道就下来是一个字符串。
我们只需要实现每一个类型的解析函数，根据第一个字符判断，调用正确类型的函数即可。
另外，我实现了一个 Scanner，可以读取字符的同时支持撤销最多两次。好像是浮点数解析的时候需要撤销两次，对于本题应该可以简单地用 std::istream 代替。
读取数字可能略微麻烦一些，但也不是特别麻烦。
static std::vector<Token> tokenize(IO::Scanner &io) {
std::vector<Token> tokens;
try {
while (true) {
char ch = io.get();
io.unget();
if (ch == '\0') {
break;
} if (ch == '\n') {
io.get();
// tokens.push_back({Token::EndOfLineTag});
} else if (isBlank(ch)) {
io.get();
} else if (ch == '"') {
String str;
io >> str;
tokens.push_back({Token::StringTag, str});
} else if (isDigit(ch)) {
Integer integer;
FloatingPointNumber fp;
bool isInteger = true;
io >> integer;
// 已经有了后缀运算符，不应视为浮点数
if (integer.suffixOperators.empty()) {
if (io.get() == '.') {
if (not isDigit(io.get())) {
// 如果后面不是紧接数字，放弃匹配小数
io.unget(), io.unget(); // 下一次读取还是获得 '.'
goto egg; // 跳到结尾，直接加入先前读入的数字
}
io.unget(); // 读到小数点，即 0.123 的形式
isInteger = false;
io >> fp;
fp.value += integer.value;
} else {
io.unget();
}
if (ch = io.get(); ch == 'e' or ch == 'E') {
// 科学计数法
if (isInteger) fp.value = integer.value;
isInteger = false;
ch = io.get();
bool expSigned = false;
if (ch == '+') ch = io.get();
else if (ch == '-') ch = io.get(), expSigned = true;
if (isDigit(ch)) {
io.unget(), io >> integer;
if (expSigned) fp.value *= std::pow(10.0, -(double)integer.value);
else fp.value *= std::pow(10, integer.value);
fp.suffixOperators = std::move(integer.suffixOperators);
} else {
compileError("Invalid decimal literal");
}
} else {
io.unget();
}
}
egg:
if (isInteger) tokens.push_back({Token::IntegerTag, integer});
else tokens.push_back({Token::FloatingPointTag, fp});
} else if (isIdentifierStart(ch)) {
Identifier identifier;
io >> identifier;
tokens.push_back({Token::IdentifierTag, identifier});
} else {
Symbol symbol;
io >> symbol;
if (symbol.value == "#") {
// 单行注释
while (io.get() != '\n');
continue; // 忽略井号
}
tokens.push_back({Token::SymbolTag, symbol});
}
}
} catch (IO::EOFError &) {}
tokens.push_back({Token::EndOfLineTag});
return tokens;
}io >> x 表示从 Scanner 中读取对应类型。这段代码同时支持识别各种数字的后缀，例如 0LL 这样的。这里实际上是把井号视为单行注释。
UVA12421 需要支持省略 .. 运算符，会再麻烦一些。
匹配符号使用“贪婪匹配”的原则，尽可能匹配更长的符号（例如 == 和 = 前者更优先）。可以使用字典树实现。
解析
我们可以把代码转化成一棵树，即抽象语法树（Abstract Syntax Tree）。
抽象语法树和表达式树类似，或者反过来说，后者是前者的子树。
我把程序中的元素分为了以下几类：
语句（Statement），语句块（Block），表达式（Expression），值（Value）。
比如，考虑以下代码：
if (a != 0 && b != 0) {
putchar(a + b);
}这是一个 if 语句，包含条件表达式和主体语句块。
里面的 putchar(a + b) 可以看成一整个表达式，把函数调用看成一种运算符。
它就可以被描述成这样：
If-Statement
Condition:
&&
!=, a, 0
!=, b, 0
Body:
[0] EvalExpr
Call
putchar
+, a, b那么如何建出这样一棵树呢？
大多数时候，我们读到一个词，就能判断出接下来是什么样子。例如上面的例子中，我们只要读到 if，就能知道会有一个圆括号，接下来读取一个表达式直到对应的右侧圆括号，再接下来读取一个语句或者语句块。
表达式解析
解析表达式似乎是一个难点。我的做法是：先转成后缀表达式，然后建表达式树。
具体来讲，后缀表达式还是通过类似常规流程的压栈来实现。不过有一些额外的细节。
我在维护运算符种类以外，还维护了一个整数，表示这个符号还有几个运算数没有访问到。
这样，比如现在遇到了符号 -，如果栈顶运算符还需要一个运算数，那么它就应该是负号，否则就是减号。这样我们就区分开了一元和二元的同一运算符。
括号和函数调用也能由此区分，如果括号之前是一个完整结果，那么括号应该被视为函数调用。特别地，如果整个表达式的外侧都是括号，这也应该是普通的括号。这可以通过最开始向栈中压入一个空操作，并将剩余操作数设为 1 来解决。
函数调用的参数，我设置了一个“逗号”运算符，它的左儿子为一个参数，右儿子为另一个逗号或者参数。例如，下面的函数调用：
f(0, 1, 2, 3);解析出的表达式树：
Call
f
Comma
0
Comma
1
Comma
2
Comma
3这样，我们就把函数调用变成了固定的二元运算符。
中括号访问，我把它看成了另外一种运算符，把这个运算符和一个中括号一同压入栈中。多维数组可以参考多维 vector，每次下标访问返回少一个维度的数组，最终获得值。
这部分代码大致是这样：
struct StackValueType {
Operator op;
int args_remains; // 剩余操作数
};
const auto &&end_condition = [&]() {
if constexpr(std::is_same_v<PredType, int>) {
return [&](std::string const &op, std::vector<StackValueType> const &ops) {
if (op == "," and (ops.empty() or ops.back().op == NoneOp)) return true;
if (op == ";" or op == "\n") return true;
return false;
};
} else {
return pred;
}
}();
auto [postfix, it] = [&]() {
const auto inf = OperatorInfo::priority_max;
std::vector<StackValueType> ops {{NoneOp, 1}}; // 运算符栈
auto it = src.begin();
// 转成后缀表达式
struct PostfixValueType {
bool symbol = false;
std::variant<Operator, ValueNode> item;
};
std::vector<PostfixValueType> postfix;
auto add = [&](Operator type, int args_remains) {
if (infoOf(type).leftAssociative) {
while (not ops.empty() and infoOf(ops.back().op).priority < infoOf(type).priority) postfix.push_back({true, {ops.back().op}}), ops.pop_back();
} else {
while (not ops.empty() and infoOf(ops.back().op).priority <= infoOf(type).priority) postfix.push_back({true, {ops.back().op}}), ops.pop_back();
}
ops.push_back({type, args_remains});
};
for (; it != src.end(); it++) {
auto &token = *it;
if (token.tag == Token::SymbolTag or token.tag == Token::EndOfLineTag) {
auto op = token.tag == Token::EndOfLineTag? "\n": std::get<Symbol>(token.value).value;
if (end_condition(op, ops)) {
it++;
break;
}
if (op == "(") {
// 函数调用
// 如果左侧是一个完整结果，视为函数调用
if (not ops.empty() and ops.back().args_remains == 0) {
add(Call, 0);
ops.push_back({FunctionArgsBracket, 1});
} else {
ops.back().args_remains--;
ops.push_back({Bracket, 1});
}
} else if (op == ")") {
while (infoOf(ops.back().op).priority != inf) {
postfix.push_back({true, ops.back().op}), ops.pop_back();
}
// 结束函数调用括号
if (ops.back().op == FunctionArgsBracket) {
bool flag = ops.back().args_remains == 1;
ops.pop_back();
// 如果没有参数，填充一个空值
if (flag) postfix.push_back({false, ValueNode{ValueNode::NoneValue, Token{Token::NoneTag}}});
} else {
// 结束常规括号
assert(ops.back().op == Bracket and ops.back().args_remains == 0);
ops.pop_back();
}
} else if (op == ",") {
while (not ops.empty() and infoOf(ops.back().op).priority < infoOf(SplitComma).priority) {
postfix.push_back({true, {ops.back().op}}), ops.pop_back();
}
ops.push_back({SplitComma, 1});
} else if (op == "[") {
add(Subscript, 0);
ops.push_back({SubscriptBracket, 1});
} else if (op == "]") {
// 中括号匹配
while (infoOf(ops.back().op).priority != inf) {
postfix.push_back({true, ops.back().op}), ops.pop_back();
}
assert(ops.back().op == SubscriptBracket);
bool flag = ops.back().args_remains == 1;
// postfix.push_back({true, ops.back().op}), ops.pop_back();
ops.pop_back();
if (flag) postfix.push_back({false, ValueNode{ValueNode::NoneValue, Token{Token::NoneTag}}});
} else if (op == "+") {
// 判断为一元或者二元
// 如果左侧为一个期待其他操作数的符号，视为一元运算符
if (not ops.empty() and ops.back().args_remains != 0) {
ops.back().args_remains--;
add(UnaryAdd, 1);
} else {
add(Add, 1);
}
} else if (op == "-") {
if (not ops.empty() and ops.back().args_remains != 0) {
ops.back().args_remains--;
add(UnarySub, 1);
} else {
add(Sub, 1);
}
}
#define JOIN_BINARY_OP(op_type, op_str) else if (op == op_str) add(op_type, 1);
JOIN_BINARY_OP(Mul, "*")
JOIN_BINARY_OP(Div, "/")
JOIN_BINARY_OP(Mod, "%")
JOIN_BINARY_OP(Less, "<")
JOIN_BINARY_OP(Greater, ">")
JOIN_BINARY_OP(LessEqual, "<=")
JOIN_BINARY_OP(GreaterEqual, ">=")
JOIN_BINARY_OP(Equal, "==")
JOIN_BINARY_OP(NotEqual, "!=")
JOIN_BINARY_OP(And, "&&")
JOIN_BINARY_OP(Or, "||")
JOIN_BINARY_OP(BitAnd, "&")
JOIN_BINARY_OP(BitOr, "|")
JOIN_BINARY_OP(BitXor, "^")
JOIN_BINARY_OP(BitShiftLeft, "<<")
JOIN_BINARY_OP(BitShiftRight, ">>")
JOIN_BINARY_OP(Assign, "=")
JOIN_BINARY_OP(MemberAccess, ".")
JOIN_BINARY_OP(Range, "..")
JOIN_BINARY_OP(ScopeResolution, "::")
#undef JOIN_BINARY_OP
else if (op == "!") {
ops.back().args_remains--;
add(Not, 1);
} else if (op == "~") {
ops.back().args_remains--;
add(BitNot, 1);
} else {
std::cerr << "Unknown symbol: " << op << endl;
throw -1;
}
} else {
// 直接压入答案
if (token.tag == Token::IdentifierTag) {
postfix.push_back({false, ValueNode{ValueNode::Identifier, token}});
} else if (token.tag == Token::IntegerTag) {
postfix.push_back({false, ValueNode{ValueNode::Integer, token}});
}
ops.back().args_remains--;
assert(ops.back().args_remains == 0);
}
}
// 清空剩余操作符
while (not ops.empty() and ops.size() != (size_t)1) {
postfix.push_back({true, ops.back().op});
ops.pop_back();
}
return std::pair{postfix, it};
}();（Range .. 运算符好像是做其他的题留下的，C++ 并没有这样的运算符）
pred 是传入的参数，用来判断什么时候结束表达式，从而更好地复用代码。传入一个整数表示使用默认判断。postfix 是生成的后缀表达式。
有了后缀表达式之后就比较好办了，这里不做阐述。
树的存储
我采用这样的方式：一个节点存储若干个指针，指向其他的节点。
例如 if 语句的条件需要一个表达式，那就添加一个成员。
ExpressionNode *condition; // 条件在这里，我们其实可以发现一个继承关系，if 语句并不在乎条件是一个运算符还是一个值，于是可以让“值节点”继承于“表达式节点”。
这里介绍一个 C++ 特性。如果类 Derived 继承于 Base，那么可以将 Derived * 和 Base * 互相转换。比如我们在表达式节点上这样定义：
struct ExpressionNode {
enum OperatorType {
None, Plus
} op;
};
struct ValueNode: public ExpressionNode {
int value;
};假如有一个值节点，我们便可以把它的指针转为 ExpressionNode 挂载到 if 语句的条件上。当真正执行条件时，可以通过 op == None 来判断出这是一个值节点，从而把这个指针转换回 ValueNode * 来求值。
另外，我选择将基类的析构函数设为虚函数（virtual），这样可以在被删除时调用正确的析构函数，避免内存泄露。
例如以下代码：
#include <iostream>
struct ExpressionNode {
enum OperatorType {
None, Plus
} op;
ExpressionNode *left = nullptr;
ExpressionNode *right = nullptr;
virtual ~ExpressionNode() {
std::cout << "~ExpressionNode" << std::endl;
delete left;
delete right;
}
};
struct ValueNode: public ExpressionNode {
int *value = nullptr;
virtual ~ValueNode() {
std::cout << "~ValueNode" << std::endl;
delete value;
}
};
int main() {
ExpressionNode *ptr = new ValueNode;
delete ptr;
}这样可以确保调用了派生类的析构函数。这段代码会依次调用 ~ValueNode 和 ~ExpressionNode。如果没有虚析构函数，则只会调用 ~ExpressionNode。
另外，类中有虚函数可以将其变为多态类，这允许我们使用 dynamic_cast 来向派生类指针转换，获得检查。（dynamic_cast<Derived *>(ptr)，如果 ptr 指向的对象实际上不是 Derived 类型，那么会返回空指针）
我的代码中有这些类型的节点，缩进表示继承关系。具体类的定义可以直接翻看代码。
Node
StatementNode 语句
ExpressionEvaluateStatementNode 表达式求值
DeclareStatementNode 声明
VariableDeclareStatementNode 变量声明
FunctionDeclareStatementNode 函数声明
RunBlockStatementNode 运行代码块
ConditionalStatementNode 有条件语句
IfStatementNode if
WhileStatementNode while
ForStatementNode for
ReturnStatementNode return
BlockNode 语句块
ExpressionNode 表达式
ValueNode 值其他
正如上文所说，大多数情况下，我们只需要读到一个关键字就能知道接下来的内容，递归解析即可。
我现在区分声明和求值的方法是，如果语句的开头连续出现了两个标识符就认为这是一个声明，否则可能是一个求值。虽然比较简陋，但是对于本题应该是足够的。如果是类型后置的语言可能要方便一些。
另外，我对于数组定义没有想到什么优雅的方法，现在是简单粗暴地存储每一维的大小。
其他的比较简单，就不再讲述了。
解释运行
一种比较高效的方式是，先“编译”为一种字节码，然后就只需要在一条链上执行字节码了。
但是我选择了偷懒，直接在抽象语法树上递归执行，这样虽然有一些额外开销，对执行效率产生影响，但是不影响通过本题。
首先需要实现的是变量的存储。我定义了如下类型：
struct Object {
enum Type {
Struct, Int, Function, String, None, Array, BuiltinFunction, BuiltinIStream, BuiltinOStream, BuiltinEndl
} type;
std::variant<
std::nullptr_t, // 没有东西
int, // int
std::shared_ptr<std::string>, // string
std::shared_ptr<Identifier>, // builtin_function
std::shared_ptr<ArrayObjectValue>, // array
AST::FunctionDeclareStatementNode * // function
> value;
};如上。我们可以把函数也看成一种变量，存储的值是它对应的代码块。
ArrayObjectValue 用来存储数组。
然后，我们需要在变量名和变量内容之间进行映射。我引入了作用域的概念，虽然这个题保证不会有重名，但是涉及到递归的时候还是需要的。（相当于不同递归层数的变量发生了重名）
可以用类似链表达方式实现多层作用域：
std::map<Identifier, Object> variables;
Scope *parent = nullptr; // 父级作用域在这一层如果找不到变量，可以到上一层查找，直到不存在更上层了。
每一次进入一个语句块都进入一层作用域，退出语句块就退出作用域即可。
接下来，我的解释器类实现了以下方法：
class Interpreter {
Program program;
std::vector<std::unique_ptr<Scope>> scopeStack; // 作用域栈
Object ret; // 上一次的返回值
bool returnFlag = false; // 正在执行 return
Interpreter(Program &&);
void run();
Object evaluateExpression(AST::ExpressionNode *); // 计算表达式
Object *evaluateLeftValueExpression(AST::ExpressionNode *); // 计算左值表达式
TypeName evaluateType(Identifier const &); // 推导类型
template <typename OutIterator>
OutIterator getFunctionArguments(AST::ExpressionNode *, OutIterator); // 提取函数参数
void runBlock(AST::BlockNode *); // 执行语句块
template <typename StatementPointer>
void runDeclarationStatement(StatementPointer); // 执行声明语句
template <typename StatementPointer>
void runStatement(StatementPointer); // 执行语句
void enterScope(); // 创建新的作用域
void leaveScope(); // 离开当前作用域
Scope *topScope(); // 获取当前作用域
};正如上文所述，我们把函数参数通过若干层逗号存储起来，getFunctionArguments 是这个的逆过程，按顺序把所有参数提取到目标迭代器中。
计算左值是为了支持 a[5] = 20 这样的数组操作。a[5] 可以作为一个左值计算，得到一个指针再对其赋值。
突然发现我并没有实现赋值语句的左值运算，可能是没有 (a = b) = c 这样奇怪的数据。
这些函数基本上递归跑就可以了。
另外，返回值采用的方法是，直接设置 ret 变量的值，然后 returnFlag 设为 true。需要注意，每一次执行语句和语句块的时候都需要检查是否需要返回。
隐式返回 0，在调用函数之后发现这次没有发生返回就直接设为 0 即可。
总结
经过部分删减的代码（主要删的 Tokenize 部分）可以见洛谷云剪贴板，Ubuntu Paste 或 Github。请注意代码长度为 84 KB，提交时可能需要略微压行。
这份代码使用 gcc 13.3.0 的编译选项 -fsanitize=address,undefined,leak 没有发现未定义行为和内存泄露。
很有意思的大模拟，也是我的第一道黑题。感觉主要难度还是在解析 AST 上，解析表达式和声明有点麻烦。这个解释器只是实现了不考虑错误、不考虑性能优化的一个很小的 C++ 子集，无论在可用性和性能上均有很大的优化空间。在编写的时候，我尝试着写出更加优雅的封装，让代码更加清晰和可复用，增加可维护性，虽然并不完美，但我自认为是一次不错的尝试。
这份代码最初还有不少细节问题，只能获得
#undef assert
#define assert(x) (void)(!!(x)||(std::exit(__LINE__),0))这样可以获取断言失败的行数（模
感谢您的阅读。