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

tiger2005 · 2025-02-18 19:36:47 · 题解

我们首先实现一个虚拟机。

namespace VM {
const int MEM_SIZE = 1 << 22;
const int BYTE_CODE_LENGTH = 1 << 12;
i64 mem[MEM_SIZE];
i64 bytecode[BYTE_CODE_LENGTH];

int run(i64 start) {
  i64 *pc = (i64*)start, *sp = mem + MEM_SIZE, *bp = sp, ax, tmp;
  // finally execute _PSH and _EXIT by modifying pc
  *--sp = _EXIT;
  *--sp = _PSH;
  tmp = (i64)sp;
  *--sp = tmp;

  while (1) {
    i64 ins = *pc++;
    switch (ins) {
    case _LEA: ax = (i64)(bp + *pc++); break;
    case _LEAP: tmp = ax * (*pc++); ax = (*sp++) + tmp; break;
    case _IMM: ax = *pc++; break;
    case _JMP: pc = (i64*)*pc; break;
    case _JSR: *--sp = (i64)(pc + 1); pc = (i64*)(*pc); break;
    case _BZ: pc = ax ? pc + 1 : (i64*)(*pc); break;
    case _BNZ: pc = ax ? (i64*)(*pc) : pc + 1; break;
    case _ENT: *--sp = (i64)bp; bp = sp; break;
    case _ADJ: if (*pc < 0) memset(sp + *pc, 0, sizeof(i64) * -(*pc)); sp = sp + *pc++; break;
    case _LEV: sp = bp; bp = (i64*)*sp++; pc = (i64*)*sp++; break;
    case _LI: ax = *(i64*)ax; break;
    case _SI: *(i64*)*sp++ = ax; break;
    case _PSH: *--sp = ax; break;
    case _OR: ax = *sp++ || ax; break;
    case _XOR: ax = bool(*sp++) ^ bool(ax); break;
    case _AND: ax = *sp++ && ax; break;
    case _NOT: ax = !ax; break;
    case _EQ: ax = *sp++ == ax; break;
    case _NE: ax = *sp++ != ax; break;
    case _LT: ax = *sp++ < ax; break;
    case _GT: ax = *sp++ > ax; break;
    case _LE: ax = *sp++ <= ax; break;
    case _GE: ax = *sp++ >= ax; break;
    case _ADD: ax = *sp++ + ax; break;
    case _SUB: ax = *sp++ - ax; break;
    case _MUL: ax = *sp++ * ax; break;
    case _DIV: ax = *sp++ / ax; break;
    case _MOD: ax = *sp++ % ax; break;
    case _NEG: ax = -ax; break;
    case _SHL: printf("%d", (int)ax); sp++; break;
    case _SHR: *(i64*)ax = input_a[input_cur++]; sp++; break;
    case _PCHR: putchar(ax); sp++; break;
    case _EXIT: return (int)ax;
    }
  }
}
};

下面是字节码的设计。这个设计实际上使用了一些寄存器和一个栈，其中栈的低地址部分储存编译时确定的全局变量空间，而高位置部分储存函数调用信息和临时变量空间。我们需要同时在数组中储存指针和变量值，为了方便起见，这里统一使用 long long 处理这些值。这样的处理方案可能会导致一些操作符的行为出现异常，但是题目中给出的数据代码都非常正常，或者说不依赖于整形溢出之类的操作，所以不妨就假设这样处理没有问题。

为了跑动字节码，我们需要至少四个寄存器：

pc：指向当前字节码操作类型的指针，这个指针应当指向 bytecode 数组的一个位置；
sp：指向栈顶值的指针。在这个指针的帮助下，PUSH 操作等价于 *--sp = ...，而 POP 操作等价于 *sp++。需要注意的是，栈的方向是从高地址向低地址，那么指针的移动方向也需要以次为依据移动；
bp：指向栈底的指针。需要注意的是，bp 本身指向的内容并不是栈底的值，而是比栈底的值更高一个位置的值。这个值一般是上一个栈的栈底。在此基础上，我们就可以在退出函数时令 sp = bp, bp = *sp++ 快速回到函数被调用时的栈情况；
ax：临时的数值储存器。我们将会进一步讨论这个寄存器的作用。

我们观察表达式的求值部分，实际上其等价于在表达式树上以后序遍历的顺序计算每个子树的行为的过程。在平常的写法下，我们需要先把表达式子树的值压入栈中，然后调用根节点的操作进行运算。为了进一步减少对栈的操作，我们考虑如下策略：（下面的策略在双目操作符的表达式树上适用）：

计算左表达式树的值并自动储存在 ax 上；
将 ax 压入栈中；
计算右表达式树的值并自动储存在 ax 上；
这个时候操作的左值一定是栈顶的值，右值一定是 ax，调用双目操作对应的字节码，将左值弹出后与 ax 进行运算，将得到的结果继续储存在 ax 上返回。

这个方案很容易变成单目操作符的策略。而对于立即数，可以直接将对应的值加载到 ax 上。

接下来是字节码部分。

字节码	操作
`LEA x`	根据操作参数，以栈底为基址进行偏移，得到地址并储存在 `ax` 中。这个操作是为了在函数调用时准确的取到其局部变量的地址，因为在函数的规划下，每个局部变量和栈底的相对偏移是固定的。
`LEAP x`	取出栈顶值 `ax'`，并令 `ax = ax' + ax * x`。这个部分主要是为了取出数组的地址，因为数组中每个位置的地址应当是每一维参数的加权和，而权重是可以在编译期计算的。
`IMM x`	将立即数 `x` 加载到 `ax` 上。
`JMP p`	令 `pc = p`，也就是强制跳转。`p` 参数一般是以 `pc` 为基址的（因为多环境下字节码起始位置会发生变动），但是这一题中字节码储存在一个固定位置的数组中，所以可以忽略这一点。
`JSR p`	将 `pc + 1` 压入栈后令 `pc = p`。这个操作可以和下面的 `LEV` 一起，让虚拟机在函数退出时回到正确的状态下。
`BZ p`	如果 `ax` 等于 `0`，则令 `pc = p`，否则令 `pc = pc + 1`。这本质上等于以 `ax` 为参数进行选择跳转。
`BNZ p`	`BZ p` 的镜像版本。
`ENT`	进入函数主体前的工作。此时需要将 `bp` 压入栈中，然后令 `bp = sp`。
`LEV`	函数调用结束。我们在函数调用时分别调用了 `JSR` 和 `ENT`，分别将 `pc` 的下一个位置和调用前的 `bp` 压入栈内，那么只需要先令 `sp = bp`，然后分别弹出 `bp` 和 `pc` 的新值即可。
`ADJ x`	令 `sp = sp + x`。这部分等价于函数开辟或回收局部变量的空间。需要注意的是，根据题目要求，在开辟空间（`x < 0`）时，需要将这部分空间全部置零。
`LI`	令 `ax = *ax`，也就是根据地址取值。对于局部变量，需要根据 `LEA` 的结果取值，而对于全局变量只需要根据一个立即数取值。在取值前，地址都需要根据数组参数偏移。
`SI`	取出栈顶的一个地址 `p`，然后令 `*p = a`，也就是将 `ax` 写入到栈顶的一个地址中。
`PSH`	将 `ax` 压入栈中。
`EXIT`	退出程序。
其余部分	剩下的基本都是系统内置函数的 `caller` 和运算符处理了。关于运算符处理可以参考前面提到的策略。

由于字节码可能并不包含 EXIT 字节码，我们可以考虑将这个字节码写在栈上，然后模拟 JSR 事件，将指向 EXIT 的指针压入栈中。在上面的设计中，我们还将 PSH 指令写到栈上，这个指令可有可无。

在实现好执行字节码的虚拟机后，剩余的事情就是把代码转换为字节码。我们首先实现一个 Reader：

struct Reader {
  char ch;
  Reader(bool) {}
  Reader() { ch = getchar(); }
  char seek() { return ch; }
  void skip() { ch = getchar(); }
  bool eof() { return ch == EOF; }
  void read(char &c) { c = seek(); skip(); }
  char read() { char res; return read(res), res; }
} reader(false);

这个读入类需要在主函数调用 reader = Reader() 激活，这是因为我们无法保证默认的读入操作在打开读写文件之前。

然后是实现 Token 流，也就是每次从读入类读出一个 Token。我们根据输入 seek 到的字符考虑：

如果这个字符是 #，则当前行是头文件引用，直接当作注释处理就好；
如果这个字符是字母，则贪心的读入一个只包含字母、数字和下划线的字符串，这个字符串可能为名称或者保留字，需要通过匹配确定。特别的，如果匹配到的保留字是 using，则一样可以看作注释处理；
如果这个字符是数字，则贪心的读入一个数字即可；
否则，我们认为这个字符是符号的一部分，贪心匹配符号即可。

接下来就是递归处理 Token 流并得到整个字节码架构。这里有一些需要注意的点。

我们需要在每个代码块中新增一个作用域，形成作用域栈。在定义局部变量时，使用 ADJ 开辟空间，向当前作用域写入大小和偏移量等信息，在离开作用域时则需要撤销更改，同时计算好需要回收的内存，通过 ADJ 指令释放。
在调用函数时，考虑到函数作用域的条件，我们需要按顺序执行下面的操作：在原先的作用域下计算各个参数并按顺序压入栈中 \rightarrow 将作用域栈移动到另一个栈中，只保留全局变量 \rightarrow 新增作用域，由于栈形态确定，可以轻易得到每个形参对应的基址偏移量 \rightarrow 将形参绑定到作用域上，随后运行函数体 \rightarrow 在函数 LEA 之后，手动 ADJ 移出所有参数，并且将作用域移回。
本题中的控制中断语句只有 return，而没有 break 和 continue，那么只需要在计算好 return 对应的返回值之后，调用 LEA 离开函数即可。函数的返回值储存在 ax 中。
需要注意本题中的一些细节，比如变量定义时自动初始化为 0，以及函数默认返回值为 0 等。前者可以在 ADJ 实现，已经提及，而后者可以在函数体的字节码最后，在 LEA 前加入 IMM 0。
在表达式树上，每个表达式的默认返回值都是右值，而对于赋值的情况，左表达式的最后一句应当是 LI（因为在正确的代码下，这个值是一个左值），此时只需要撤销这个 LI 操作，就可以获得原始地址。这个方案同时适用于 cin。
cin 和 cout 可以看作任意参数，而对于 << 和 >> 操作符，只需要看作二元运算符，并且保留右操作数的地址或值即可。
函数只需要映射到 ENT 对应的地址。
建议在调试期间输出栈信息和寄存器信息，方便找到异常行为。这些行为包括但不限于：在一些位置忘记 POP、回收变量内存错误、基址计算错误等。

此处为最终的代码。这份代码在 37ms 的时间内执行了全部数据，最慢的数据也只是执行了 8ms。