题解：P11738 [集训队互测 2015] 未来程序·改

Mrkn_chenyx12 · 2025-09-13 00:40:27 · 题解

解法构建

本题要求实现一种语法类似于 C++ 的编程语言。由于数据规模较小，最方便的方法之一是解释执行。

考虑按照以下步骤：

1. 拆分，将代码划分为若干片段，称为 Token，如 int、main、(、>=、123456。其中一种实现方式是同时标注类型，如 keyword、number。
2. 语法解析，从前往后遍历拆分后的代码，通过分辨当前位置和邻近位置的 Token 类型判断属于哪种语法，自顶向下递归构建抽象语法树（AST）用于存储信息。
3. 解析执行，自顶向下使用专用的执行器模拟执行不同类型的 AST 节点表示的逻辑。

功能分析

第一步中，考虑每次产生一个类型枚举和内容字符串组成的对。

第二步中，不妨将所有需要实现的功能分为语句和表达式，且前者包含后者。其中一种分类方式是：

• 仅属于前者的有：作用域、定义变量、定义函数、分支语句、while 循环、for 循环、返回、cin 输入、cout 输出。
• 同时属于前者和后者的有：整数常量、标识符（代表一个变量）、一元运算、二元运算、函数调用、取下标、赋值。

鉴于 cin、cout、endl 都不是整形，不会参与到其他表达式中，不妨认为 cin、cout 是普通语句而不是表达式，endl 只需要在待输出列表中添加任意能区分于其他表达式的值，比如空指针。

再次将表达式分为前缀和中缀，其中前者可以由第一个 Token 确定类型，而后者需要通过不位于开头的某个 Token 确定类型。具体地：

• 前缀有：整数常量、标识符、一元运算。
• 中缀有：二元运算、函数调用、取下标、赋值。

解析表达式时，一种常见的写法是：指定一个优先级，先读一个前缀，再不停读中缀，直到后面没有中缀或运算优先级低于（右结合则为不高于）当前优先级，并根据中缀选择合适的语法类型，将当前前缀传递给对应解析器，并将返回值作为新的前缀。读取整个表达式时，应该指定最低的优先级。

第三步中，需要实现整形和数组两种类型。要解决的问题之一是左值的实现，变量（包括数组的某一位）均为可赋值的。

我选用的写法是：将整形显式分为左值和右值，前者存储指针，后者存储值；数组压成一维并存储指针，保存每一维下标加一的偏移量，所有维均完成偏移后返回整形左值。由于本题中变量的生命周期始终跟随作用域，故可以考虑将整形左值和数组均存储于虚拟栈中。

需要注意，作用域之间并不是独立的，而是内层作用域会基于外层作用域扩充内容。

另外，函数可以保存其在 AST 中的根节点和参数列表。鉴于函数不会被存为函数指针与其他变量混用，可以单独存一张表。

实现细节

• 对于 #include 语句和 using 语句，可以直接当成注释，跳过对应行或 Token。
• for 的 init、condition、step 均可为空。如果希望强制非空，condition 应该置非零值。
• 作用域也是语句，理论上可以不跟随函数定义或控制语句，建议单独实现为一个语句类型。因此，控制语句只需要读一个语句，而无需区分是否有大括号跟随。函数体必须指定读取作用域，而不是读取一个任意类型的语句。
• 唯一可能造成歧义的语句开头是 int，可能表示定义函数或定义变量。
• 对于词法分析“分辨当前位置和邻近位置的 Token 类型”，实际上只看到当前即可满足本题需要。或者，也可以向后再看一个，实现可能会更容易。
• 可以将整体 AST 执行一遍，再取函数表中的 main 并调用，而无需在定义函数时判断函数名称是否为 main。
• 实现 ^ 运算符不要用 (left ^ right) != 0，符合题目描述的写法是 (left && !right) || (right && !left)。
• AST 是 AST，对象是对象，最好不要混用 AST 节点和对象。
• 善用 C++ 的类和继承，构建和解析 AST 会简单很多，不妨让所有类型的节点继承自同一父类。
• 智能指针是一个好用的工具！
• 为了区分类型，相较于低效地使用字符串、不可读地不起别名使用整数、冗长地定义多个整数宏或常量作为别名，不如尝试使用枚举。
• 为了处理 return，可以置一个布尔类型的解释器状态表示是否在返回。循环语句每执行完一轮、作用域语句每执行完一句都应该检查是否在返回，如是则直接退出，否则继续执行。应该先计算返回值再设置返回状态，并在函数调用后清除返回状态。

参考代码

详见 https://www.luogu.com.cn/paste/4i8pzhla。