ISK-OJ 首页 题库 比赛 评测 排名 讨论 帮助 返回比赛
登录 注册

E. 调用栈

内存限制：512 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
转到题库 提交记录 返回比赛

题目描述

我们知道，大部分计算机程序都可以被分为若干具有特定参数、可以互相调用的子程序。

当一个子程序调用另一个子程序时，前者需要将调用参数传递给后者，同时还需要将自己的局部数据（寄存器上下文、局部变量等）妥善存放，保证在后者返回时前者可以继续执行原本的任务。

调用栈（下简称为「栈」）是计算机程序用于存放子程序信息的内存空间。

我们知道栈是一种后进先出的数据结构，因而特别适合用于维护嵌套结构的信息——后进（内层）的元素先出（结束），且子结构和栈中已有内容不会相互影响。

因此，计算机程序利用调用栈的方式也类似：

  • 首先规定每个子程序在栈上占据一段空间，我们称作它们的栈帧。
  • 主程序（初始子程序）刚开始时，栈是空的，该子程序的栈帧当然也是空的。
  • 程序可以往栈中压入内容，这时栈会增长（我们规定栈往内存中的高地址（或者往右/往上/往前）增长，那么也就是栈顶往右移动），程序的栈帧也同步增长（栈帧的右边界即为栈顶）。
  • 调用一个新的子程序时，将子程序的所有参数压入栈中，然后将栈的控制权交给该子程序——该子程序的栈帧从现在的栈顶开始（并和栈的变化同步），而调用者的栈帧冻结（其后的栈变化不影响该栈帧）到该子程序退出为止。
  • 子程序退出时，弹出子程序栈帧和参数，将栈的控制权交还给调用它的子程序——栈顶后退到后者的栈帧边界，并在其后和它同步变化。

容易发现，栈的性质保证了：

  • 在子程序的整个生命周期中，调用者的栈帧不会被破坏。
  • 在子程序结束后，栈将恢复成调用子程序之前的样子。
  • 任何子程序在自己上下文运行时，自己的栈帧总是在栈顶，因此对栈的操作即是对自己栈帧的操作。
  • 在任何时刻，栈都是由从主程序到当前子程序调用链上的各个子程序栈帧从左往右排列而成的。

本题的任务是模拟一个具有调用栈的抽象计算机的运行。

该计算机支持注册一个主程序（无参数）和若干有特定参数的子程序。

为了简化，我们只允许两种类型的参数，即数字 int 和字符串 str。其中数字范围和 C++ 中的 int 一样，字符串长度为 3，且仅由英文小写字母构成。

主程序不需要声明，子程序的声明是 函数名(参数列表)，比如：

some_subroutine(int, str, int)

调用的时候遵守一样的格式 some_subroutine(5, arg, 10)。

特殊地，子程序可以有不定参数，例如 va_subroutine(...)，这表示可以有不定个数的参数，每个参数都可以是两个合法的类型之一，比如这样调用它：

va_subroutine(5, arg, 6, 9, arg)

混合不定参数和固定参数也是可以的，但要保证不定参数出现在参数列表的最后，例如 mix_subroutine(int, ...)，

不定参数对应的个数可以是零个，比如这些是合法的调用：

va_subroutine()
mix_subroutine(5)

当然，主程序和子程序的主体部分是由若干指令组成的，每个子程序的指令从 开始按顺序编号，计算机默认从主程序的 号指令开始运行。

接下来我们一边梳理该计算机（或其上的程序）具有的功能，一边说明该计算机支持的各个指令类型。

首先，该计算机具有一个单字节暂存器，程序可以操作/输出暂存器的值：

  • 加（ADD BYTE），把暂存器的值加上某个字节，BYTE 格式如 0x0a。
  • 设置（SET BYTE），把暂存器的值设置为某个字节，BYTE 格式如 0x0a。
  • 回显（ECHO），按十六进制格式（如 0x0a）输出暂存器的值。

其次，该计算机具有一个大小为 字节的栈空间，按字节从 到 编址。该计算机内部还维护该栈的栈顶位置（初始为 0，表示栈为空，栈顶为 x 表示栈空间为 [0, x)），可以通过指令来以字节为单位压栈和弹栈：

  • 弹出（POP），弹出栈顶到暂存器中。
  • 写入（PUSH），往当前栈压入暂存器上的字节。

和上文所述类似，该计算机能够维护所有还未结束的子程序栈帧范围，因此支持如下指令：

  • 加载（LOAD），把暂存器中值对应的位置读入暂存器。
  • 读取（READ POSITION），读取栈上的某个位置到暂存器中。
  • 写入（WRITE POSITION），将暂存器中的内容写入栈帧的某个位置（不能写到别的栈帧上）。
  • 打印（PRINT POSITION），从某个位置开始打印字符串，遇到 \0 停止。

以上的位置，都是相对于栈帧而言的，例如 READ 0 表示读取当前子程序栈帧的第一个字节到暂存器中。

另外，暂存器在表示位置时视为一个有符号整数。

我们说过栈在任意时刻都是从主程序到当前子程序的调用链上各个子程序栈帧的排列，因此该计算机支持在通过遍历栈上的所有栈帧输出调用链：

  • 栈追踪（STACKTRACE），在 verbose 模式下输出栈追踪信息，否则什么也不做。

栈追踪信息是表示调用链信息的特定格式，我们后续再谈及。

另外，该计算机支持分支和跳转：

  • 跳转（JUMP OFFSET），跳转到程序的 BYTE 号行，行号从 开始计数。
  • 条件（B COMMAND），如果暂存器的值为零，就执行某指令。

该计算机还能够在任何时刻终止运行：

  • 终止（TERMINATE），无论如何，终止程序运行并输出 TERMINATED，并在换行后输出栈追踪信息。

显然该计算机还需要支持子程序间的调用和子程序的退出，于是：

  • 调用（CALL CALL_BODY），根据 CALL_BODY 执行函数调用。
  • 退出（LEAVE），退出当前的子程序，回收当前子程序栈帧，特别地，如果执行这条指令的是主程序，则等同于执行 TERMINATE。

注意在调用时需要压入子程序参数，我们按照从后往前的顺序压入子程序的所有参数。

对于两种参数，压入的方法是：

  • 整数参数按照 int 四字节小端压入栈，比如一个整数 0xff50fc50，按照 0x50，0xfc，0x50，0xff 的顺序压栈。
  • 字符串参数按照阅读顺序压栈（三字节），并在最后添加一个 0x00，共计四个字节。

当然程序可能会出现异常，异常包括：

  • 非法访问（ILLEGAL_ACCESS），读取、写入或打印字符串时，访问了非法的位置，比如 WRITE 写到了其他栈帧上，READ 读取到了超出栈边界的位置。
  • 帧溢出（FRAME_OVERFLOW），在栈帧为空时执行 POP。
  • 栈溢出（STACK_OVERFLOW），使用的栈空间总量超过了上限（可能由 PUSH 或 CALL 导致），或者在栈为空时 POP（其实这是不可能发生的，因为它必然和上个错误同时发生，但我们规定优先触发上一个异常）。
  • 参数错误（BAD_PARAM），调用函数的参数不符合参数列表。
  • 无法显示（NOT_PRINTABLE），PRINT 指令处理到了一个无法打印的字符。

请不要执行将要触发异常的指令。特别地，如果 PRINT 指令读取越界，请把它越界以前的字符正常打印出来。

在发生异常之后，请在打出异常名之后（需要在末尾换行）结束程序运行，并输出栈追踪信息。

作为一个玩具程序，我们不希望模拟器执行太多条指令，因此，模拟器将把它执行的第 条指令自动替换成 TERMINATE 以结束程序。

同样地，我们也不希望模拟器递归太多层，因此，模拟器将把第 层函数（main 是第 层）的 call 指令替换成 TERMINATE 以结束程序。

最后，我们来说说栈追踪信息，我们针对一个范例来说明：

========STACKTRACE:
reg: 0xa5
=========
main()
5> CALL calladd(5)
frame_range [0, 4)
stack_frame:
05 00 00 00             ....
=========
calladd(5)
0> CALL printparams(3, cal, lad, dxx)
frame_range [4, 20)
stack_frame:
64 78 78 00 6c 61 64 00 dxx.lad.
63 61 6c 00 03 00 00 00 cal.....
=========
printparams(3, 0x006c6163, 0x0064616c, 0x00787864)
0> STACKTRACE
frame_range [20, 20)
stack_frame:
=========END
  • 首先第一行是 ========STACKTRACE:，然后紧随第二行输出暂存器的值。
  • 接下来从主程序开始到当前子程序，输出每个子程序的调用参数、运行到的指令和栈帧信息，以 ========= 作为开头：
    • 第一行输出调用该程序所用的调用体，但对于不定参数，由于不能确定参数类型（虽然本题中可以，但我们假装不能），所以统一按照 int 转十六进制输出。
    • 第二行输出 num> 子程序此时正在运行的指令，其中 num 是该指令在子程序的编号。注意异常发生时，认为子程序正在执行该指令。此外，被替换为 TERMINATE 的指令在这里需要显示为原指令。
    • 第三行输出子程序的栈帧范围。
    • 第四行开始，输出子程序的栈帧信息，每八个字节为一行，先以空格为分割输出每个字节的十六进制值，然后输出这八个字节按照 ASCII 编码的字符（如果是不可显示字符，就输出 .，注意 （空格，0x32）是可显示字符。），注意不满八个字节的情形要将输出的字符起始和满八个字节的情形对齐。
  • 最后输出 ========END。

事实上这个追踪信息已经构成了这个抽象计算机目前运行状态的快照。

到这里我们已经介绍完了该计算机的全部功能，接下来我们将给出所有主程序，子程序的信息和计算机的栈大小，以及它是否处于 verbose 模式，你的任务是模拟它的运行。

输入格式

第一行一个数，表示计算机是否处于 verbose 模式。

第二行三个整数 ，分别表示子程序数量，栈空间的总大小和主程序的指令条数。

接下来 行，按顺序给出了主程序的指令，一行一条。

接下来是 个子程序的信息，第 个子程序的信息如下：

第一行是子程序的声明。

第二行一个整数 ，表示子程序的指令条数。

接下来 行，按顺序给出了该子程序的指令，一行一条。

输出格式

按照题意输出。

样例

样例输入0

0
1 4096 11
CALL printparams(7, goo, dby, epr, obl, ems, olv, ing)
SET 0x7e
PUSH
SET 0x20
PUSH
SET 0x20
PUSH
SET 0x00
PUSH
CALL printparams(8, goo, dby, epr, obl, ems, olv, ing)
LEAVE
printparams(int, ...)
33
STACKTRACE
READ -4
PUSH
SET 0xfc
PUSH
READ 0
B JUMP 22
ADD 0xff
WRITE 0
READ 1
ADD 0xfc
WRITE 1
ADD 0x00
LOAD
PUSH
READ 1
ADD 0x01
ADD 0x00
LOAD
PUSH
READ 1
ADD 0x02
ADD 0x00
LOAD
PUSH
ADD 0x00
READ 0
JUMP -21
SET 0x00
PUSH
PRINT 2
STACKTRACE
LEAVE

样例输出0

goodbyeproblemsolving
goodbyeproblemsolving~  
TERMINATED
========STACKTRACE:
reg: 0x00
=========
main()
10> LEAVE
frame_range [0, 4)
stack_frame:
7e 20 20 00             ~  .
=========END

样例输入1

0
0 4096 16
SET 0x50
PUSH
SET 0xfe
PUSH
STACKTRACE
READ 0
ADD 0x01
WRITE 0
READ 1
ADD 0xff
WRITE 1
B JUMP 2
JUMP -8
ECHO
STACKTRACE
LEAVE

样例输出1

0x00
TERMINATED
========STACKTRACE:
reg: 0x00
=========
main()
15> LEAVE
frame_range [0, 2)
stack_frame:
4e 00                   N.
=========END

数据范围与提示

对于全部数据，保证 。

保证输入的任何一行长度不超过 。

保证输出总长度小于 。

保证子程序声明是合法的。

保证每次跳转都是合法的。

保证不会调用不存在的子程序。

保证子程序调用是符合语法的且不出现多余空格，且每个逗号后固定有一个空格，保证每个参数一定是两种类型之一的合法取值。

保证每个子程序的最后一条指令一定是 LEAVE。

样例解释：简单的加法程序，0x50 + 0xfe = 0x4e。

其他样例详见附加文件。

ISK-OJ Powered by SYZOJ.