IR Virtual Machine

用于哈尔滨工业大学/南京大学《编译原理》实验的Web版中间代码虚拟机

虚拟机访问地址

• Github Pages镜像
• Gitee Pages镜像
• Netlify镜像

仓库地址

• Github仓库
• Gitee仓库

记得点个Star哦~😘

为什么我要做这个项目？

• 实验指导书上没有给出的中间代码语法的严格定义
  在进行编译原理实验三的过程中，当我想尝试一些中间代码的优化方式时，我时常疑惑我想要用的那些写法是否合法。比如，ARG和WRITE指令的右边能不能直接写一个解引用或取地址，例如WRITE *t1？实验指导书对IR语法的描述已经比较详尽了，可惜一些细节上仍然没有说明白。为此，我不得不逐个编写IR文件，在虚拟机程序上验证我的猜想。
• 现有虚拟机程序存在一些bug或不合理之处
  在虚拟机上进行大量的测试以后，我也发现了现有的虚拟机程序（irsim）在代码执行上的的一些bug或不合理之处。例如，RETURN指令后面是一个从未出现过的变量名时，虚拟机竟然会现场定义这个变量，不报告任何错误；IR整数变量的长度是32位，虚拟机却能正常存储超过其表示范围的值；指导书要求变量命名规范与之前相同，虚拟机却能接受62x这样的变量名。
• 现有虚拟机的交互体验尚待提高
  此外，现有虚拟机程序虽然功能完善，但我认为其交互体验仍然可以提高，在某些交互细节的处理上也有一定欠缺。比如，每次运行结束后通过模态弹框提示结果，这使得再次运行或加载新文件之前必须手动关掉该对话框；同时，若在选择文件界面取消了选择，则程序会崩溃退出。而且，要想运行虚拟机，还需进行环境配置。最后，我个人希望虚拟机可以支持全局变量的使用，虽然指导书上已经假设程序中不存在全局变量。

或许，当年虚拟机程序的作者如今已身居要职，已没有精力回过头来完善他多年前写成的程序。那么，我们为什么不使用更现代的技术，去写一个能完全兼容课本规范的、更好的IR虚拟机呢？

特点

• ✅在线运行，无需配置环境
• ✅给出了精确的IR语法定义
• ✅支持批量加载IR代码文件，可直接将多个IR文件拖入
• ✅交互界面友好，IR代码编辑器支持语法高亮、自动补全、搜索替换与可视化错误提示等多种功能
• ✅以标签页的形式切换多个虚拟机实例
• ✅支持注释，支持全局变量的定义与使用
• ✅完善的错误检查，详细的错误提示
• ✅完整展示全局变量表和调用栈中所有函数的局部变量表
• ✅可设置的运行选项：最大执行步数限制（防止无限循环/递归）；虚拟机内存大小、栈大小
• ✅良好的移动端适配
• ✅丰富的示例IR程序
• ✅IR执行性能比irsim高约200倍🚀
• ✅提供CLI命令行版本供自动化测试使用

使用方法

导入.ir文件

打开虚拟机页面后，您可以通过以下任何一种方式开始使用虚拟机： - 使用左侧菜单中的新建选项，创建一个空白的.ir文件 - 使用左侧菜单中的导入选项，导入想要运行的本地.ir文件 - 直接将本地的.ir文件拖入页面中 - 使用左侧菜单中的示例选项，在对话框中选取您感兴趣的示例IR程序

对于每个导入的.ir文件，系统都会创建一个新的虚拟机实例，您可以在页面中以标签页的形式切换这些实例。

编辑IR代码

虚拟机实例界面的左侧部分是IR代码编辑器，它使用的是与VSCode同款的Monaco Editor，支持IR代码的语法高亮、自动补全、搜索（Ctrl+F或F3）、替换（Ctrl+H）、切换注释（Ctrl+/）与可视化错误提示等多种功能。您可以在其中编辑IR代码，并且方便地发现和修正IR代码的静态检查错误。

运行IR代码

虚拟机实例界面的中间部分是虚拟机控制台。点击控制台顶部的运行按钮，虚拟机将运行IR程序；点击单步按钮，虚拟机则将一步一步执行IR程序。在单步执行过程中，点击运行按钮可以切换到连续运行模式。当执行到READ指令时，控制台中会显示输入提示消息，您完成输入后按下Enter键即可。虚拟机采用流式输入，您可以在一行中用任意空白符号分隔多组数据。程序执行结束时，控制台会输出程序main函数的返回值和运行统计信息。
新创建的虚拟机处于初始状态，此状态下可以点击运行或单步按钮开始虚拟机的运行。IR程序执行完毕后，虚拟机会处于正常退出或不正常退出状态，在这些状态下都可以直接点击运行或单步按钮，开始下一轮运行。在开始执行前，虚拟机将首先对IR程序进行静态检查，如果存在错误，则会变为IR静态分析错误状态；运行时遇到错误，虚拟机将进入运行时错误状态；运行步数超过设置的上限值，虚拟机就会进入达到步数限制状态。在这些状态下，不能继续运行虚拟机，需要点击控制台上方的重置按钮将虚拟机恢复到初始状态。
虚拟机控制台只保留最近的5000行输出结果，如果需要完整的输出，请使用本虚拟机的CLI版本（使用说明见下方对应章节）。点击清屏按钮，可以清空控制台上的所有输出。
您也可以使用快捷键代替控制台上的四个按钮进行操作，这些快捷键如下： |快捷键|功能| |-----|---| |F2|运行| |F8|单步运行| |F9|重置| |F10|清空控制台|

您必须先点击一下虚拟机控制台区域，使其成为焦点，然后才能使用这些快捷键。

修改虚拟机设置

虚拟机实例界面的右侧部分是虚拟机监视器，在其中可以设置虚拟机的执行步数上限和内存大小，也可以查看虚拟机当前的运行状态、执行步数、内存使用和变量表。
只有当虚拟机处于初始状态时，您才可以修改虚拟机的设置。如果您不希望限制虚拟机的执行步数，则可以将执行步数上限设置为0。

IR程序示例

IR虽然简单，其实无所不能。难道你不想试试左侧菜单中示例选项里那些有意思的IR程序吗~
注：示例IR程序及其cmm源代码位于仓库的public/demos目录下

虚拟机信息

• 小端序
• 机器字长：32位
• 模拟cdecl调用约定

IR语法定义

注：下方IR语法定义在《编译原理实践与指导教程》（许畅，陈嘉，朱晓瑞编著.机械工业出版社）中的描述之上，进行了进一步的精确定义，与书中的语法完全兼容，并新增了对注释语句的支持和一条全局变量声明指令。

• IR的关键字：
  Keywords -> FUNCTION | DEC | GLOBAL_DEC | LABEL | GOTO | IF | ARG | PARAM | CALL | RETURN | READ | WRITE
• 定义ID为符合C语言标准的标识符名称，且不能与IR中的关键字重名：
  ID = [a-zA-Z_$](\w$)*
• 定义Imm为一个立即数（32位有符号整数，若超过范围[-2^31, 2^31-1]，高位将被截断）：
  Imm = #(-)?(\d)+
• 定义Size为分配空间字节数（32位有符号整数，若超过范围[-2^31, 2^31-1]，高位将被截断），必须是正整数且为4的倍数：
  Size = (\d)+
• 定义Singular为一个一元值，它要么是一个立即数，或者是ID本身，或者是前置了一个解引用运算符*或取地址运算符&的ID。*ID表示以ID的值为地址的32位有符号整数，&ID表示ID的地址：
  Singular -> Imm | ID | *ID | &ID
• 定义BinaryMathOp为二元四则运算符之一：
  BinaryMathOp -> + | - | * | /
• 定义BinaryRelOp为二元关系运算符之一：
  BinaryRelOp -> == | != | < | <= | > | >=
• 定义LValue为可出现在赋值符号左侧的值：
  LValue -> ID | *ID
• 定义RValue为一个可出现在赋值符号右侧的值（除了函数调用）。第二个候选式中，各个元素之间均由至少一个空格或制表符'\t'隔开：
  RValue -> Singular | Singular BinaryMathOp Singular
• 定义CondValue为一个可出现在IF指令条件处的值。各个元素之间均由至少一个空格或制表符'\t'隔开：
  CondValue -> Singular BinaryRelOp Singular

中间代码（IR）程序是由一行或多行IR指令组成的。所有合法的IR指令的语法定义如下表所示。一行IR指令内各个元素之间均由至少一个空格或制表符'\t'隔开，每行开头和结尾可以有任意多个空格或制表符'\t'。IR程序是大小写敏感的。

IR指令语法	描述
FUNCTION ID :	定义一个名为ID的函数。IR程序中必须有一个名为main的函数作为虚拟机执行的入口
LValue := RValue	赋值；若LValue为ID且该ID未被定义过，则在赋值之前将其作为当前函数的一个局部变量进行空间分配
DEC ID Size	在栈上分配一块指定大小的连续的空间，ID代表存储在该空间最低4字节的整数。用于在函数内部声明数组或结构体，也可用于声明整数变量。其占用的内存空间初始时为随机内容
GLOBAL_DEC ID Size	在全局变量存储区分配一块指定大小的连续的空间，ID代表存储在该空间最低4字节的整数。用于声明全局整数变量、数组或结构体，这是本虚拟机新增的一条IR指令。其占用的内存空间被全部初始化为0。全局变量的作用域为整个IR程序，与声明位置无关
LABEL ID :	定义一个名为ID的标号
GOTO ID	无条件跳转，跳转目标是名为ID的标号的下一条指令
IF CondValue GOTO ID	条件跳转，若CondValue为真，则跳转目标是名为ID的标号的下一条指令；否则继续执行下一条IR指令
ARG Singular	传递一个实参。最后一个被ARG指令传递的实参将对应第一条PARAM指令读取到的形参值
PARAM ID	声明一个名为ID的函数形参
CALL ID	调用名为ID的函数并忽略返回值
LValue := CALL ID	调用名为ID的函数并存储返回值到LValue中；若LValue为ID且该ID未被定义过，则在被调用的函数返回后，将其作为当前函数的一个局部变量进行空间分配
RETURN Singular	退出当前函数并返回给定值
READ LValue	从控制台读取一个整数储存在给定变量中；若LValue为ID且该ID未被定义过，则将其作为当前函数的一个局部变量进行空间分配
WRITE Singular	向控制台输出给定整数
（空）	空行，将被忽略
;<任意内容>	注释，将被忽略

CLI版本虚拟机

本虚拟机也提供了CLI（命令行界面）版本，可在命令行中执行IR文件，并用来进行IR程序的自动化测试。CLI版虚拟机使用和Web版虚拟机相同的IR执行引擎，二者的执行逻辑完全一致。仓库内cli子目录下是虚拟机CLI版本的源代码，其中build/irvm.mjs是已经打包构建好的CLI程序，可以复制到任何目录下使用。

使用方法

首先需要安装最新版Node.js。
进入irvm.mjs所在目录，使用以下命令运行虚拟机CLI：

node irvm.mjs [-h] [-p] [-s] [-t] [-r] [-l {en,zh-cn}] irFile

• 必须参数
• irFile：要执行的IR文件路径
• 可选参数
• -h, --help：展示帮助
• -p：将输入时的提示文字打印到stdout，不提供此参数则不打印
• -s：执行结束后，将执行步数打印到stdout，便于机器解析。不提供此参数则不打印
• -t：执行结束后，将执行耗时（以毫秒为单位）打印到stdout，便于机器解析。不提供此参数则不打印
• -r：执行结束后，将main函数返回结果和统计信息以自然语言打印到stdout，便于人类阅读。不提供此参数则不打印
• -l {en,zh-cn}：CLI程序的界面语言，默认为zh-cn

CLI版本虚拟机不限制中间代码执行步数，最大内存大小为32MB，最大栈内存大小为16MB。
当IR程序正常退出（main函数返回值为0）时，node进程的返回值同样是0；否则，node进程的返回值就是main函数的返回值。如果CLI程序在执行时发生了错误，则进程不会返回0。

使用示例

• 运行IR程序，打印输入提示和人类可读的执行统计：

node irvm.mjs rand.ir -p -r

• 运行IR程序，不打印输入提示和执行统计：

node irvm.mjs rand.ir

• 运行IR程序，将stdout上的输出写入文件：

node irvm.mjs rand.ir > out.txt

• 运行IR程序，从文件读取输入，将stdout上的输出写入文件，并输出机器可读的执行步数（Windows CMD/PowerShell环境）：

type in.txt | node irvm.mjs rand.ir -s > out.txt

• 上一个示例的Linux环境命令：

cat in.txt | node irvm.mjs rand.ir -s > out.txt

CLI版虚拟机同样以流的方式读取输入，控制台或者输入文件中的各个数据之间可用任意空白符号分隔。注意输入文件中的数据数量不能少于程序将要读取的数据数量，否则CLI程序将产生错误并退出。

一些设计理念与讨论

• 全局变量相互不能重名，同一函数内的变量、形参相互不能重名，函数内的变量、形参可以但不建议和全局变量重名，不同函数内的变量、形参可以但不建议重名
  IR中的变量真的没有作用域吗？其实这样规定欠妥。如果变量真的没有作用域，那么在出现直接递归的情况下，就必须为每次调用新开辟一个局部变量表，以确保上层函数中的局部变量不会受到本层调用的影响。那么，对于复杂的间接递归的情形呢？显然，合理的做法是为每次函数调用都在栈中新建一个局部变量表。如此，IR中的变量就确实有作用域了。
  我想，归根到底，IR还不是目标代码，只是一种很接近底层的、语法简单规整的比较高级的语言。IR程序中的变量并不代表某个寄存器或某片确定的内存空间，其与C语言中的变量并没有本质区别。
• 变量、函数和标签之间可以但不建议重名
  为何？因为中间代码涉及这三者的语法没有任何交集，重名并不会引发任何歧义，只是不利于人本身对代码的阅读。
• 为何在这个虚拟机里面看到的指令执行条数比在irsim中的少？
  因为本虚拟机并不实际执行FUNCTION和LABEL指令，也不会将它们计算在执行步数内。而据本人观察，irsim不计入除了main函数外的所有FUNCTION指令，且会计入所有顺序执行到的LABEL指令。这就会使得部分中间代码在本虚拟机上显示的执行步数略少于在irsim上的。那么，到底哪一种较为合理呢？我认为，不考虑虚拟机对每条指令的具体实现，单就语义层面来看，FUNCTION和LABEL起到的都只是代码标号的作用，并不代表一次执行，因此不将它们计入执行步数是合理的。除此之外，本虚拟机的计步策略与irsim相同，可以放心地用来评估中间代码优化的成效。
• 单步执行中，被标注的那一行代表？
  代表的是下一条要被执行的指令，也就是再次点击单步执行后被执行的指令。注：irsim中，高亮的行是刚才执行完的指令，我认为自己的实现更直观，也更符合逻辑。
• 普通变量声明指令的执行逻辑？
• 对于t1 := #3这样的变量声明指令，其执行逻辑是：如果当前函数的变量表中没有名为t3的变量，那么在栈上创建它并赋值为3；否则将已存在的变量赋值为3。
• 对于DEC v 8这样的变量声明指令，其执行逻辑是：如果当前函数的变量表中没有名为v的变量，那么在栈上创建它；否则，检查之前创建变量v的IR指令的行号和当前指令的行号是否相同，如果相同，则不做任何操作，后续v将仍然指向之前创建的变量；如果不同，则报变量重复声明错误。这样就可以支持DEC指令在循环中的多次执行。
• 全局变量声明指令的执行逻辑？
  所有全局变量声明指令都在进入main函数之前执行，并计入执行步数。假如全局变量声明指令出现在了函数内部，那么在之后执行时，全局变量声明指令就会被跳过（但是根据C--语法生成的全局变量声明指令是不应该出现在一个函数内部的）。全局变量占用的内存空间被全部初始化为0。全局变量的作用域为整个IR程序，与声明位置无关。即使一行IR指令引用的全局变量是在它下面声明的，它也可以正常访问到该全局变量。
• 让我的实验三代码能生成全局变量声明指令容易吗？
  特别简单，针对ExtDef → Specifier ExtDecList SEMICOLON这条产生式生成GLOBAL_DEC指令即可。

一些脑洞操作的讨论

• IR指令中的立即数过大会怎么样？
  本虚拟机的机器字长是32位，IR变量的类型都是补码表示的32位有符号整数（使用DEC或GLOBAL_DEC指令声明的数组或结构体变量虽然可以占据更多的空间，但其变量名代表的是存储在其中最低4字节的整数）。同惯常的实现一样，当立即数或从控制台读入的整数超过范围[-2^31, 2^31-1]时，其二进制表示中超出的高位部分将被截断；考虑到JavaScript语言自身的限制，为了防止丢失精度，当立即数或从控制台读入的整数超过范围[-(2^53-1), 2^53-1]时，虚拟机将发生一个指令解码错误或运行时错误。
• 函数里没有RETURN指令会怎么样？
  本虚拟机模拟了x86的cdecl调用约定，ARG指令将参数逐个压入栈中，函数的PARAM指令从栈中逐个读取参数，RETURN指令代替调用者恢复寄存器、清理堆栈，并使eip指向返回地址。如果没有RETURN语句，虚拟机将从当前位置继续向后执行IR指令，其后果是无法预料的。当然，任何运行时错误都会被虚拟机检测到并报告。
  注意：如果虚拟机报错从地址xx处读入指令超出了指令地址空间，请首先检查定义在最下方的函数是否没有RETURN指令。
• 函数的PARAM指令和调用时的ARG指令数量不等会怎么样？
  ARG指令更多则PARAM只会读到最后压入的几个参数；PARAM指令更多则多出来的PARAM指令会读到属于调用者的栈，可能引发内存访问越界错误。
• 只有ARG而后面没有CALL会怎么样？
  会浪费一点栈空间。

一些实现细节

• 等待控制台输入是如何实现的？
  使用JavaScript的异步编程实现。虚拟机的单步执行和连续执行方法都是async异步函数，其内部运行到读取控制台输入时，将await一个等待读取控制台输入的函数。该函数返回一个Promise，用户按下Enter键后，将调用这个期约的resolve函数将其落定，此时await结束，后面原本被挂起的代码继续执行，这样就实现了等待控制台的输入。
• 虚拟机的内存模型
  虚拟机的内存被分为栈内存和全局变量内存，栈空间从内存最高地址向下增长，全局变量空间从内存最低地址向上增长。指令被单独存放在其他地方。虚拟机的所有内存都是可读可写的，有栈溢出检查和全局变量溢出检查。详细的内存模型可以在src/modules/vm/vm.ts的注释里找到。
• 较多输出时提升性能的关键
  浏览器的界面重绘是特别耗时间的。因此，不能简单地在虚拟机有一条输出的时候就更新一次界面。虚拟机使用了一个输出缓冲区，虚拟机的所有输出都被放入这个缓冲区中，由虚拟机实例的使用方来决定什么时候读取并清空缓冲区，然后将其内容更新到界面上。

虚拟机性能

本虚拟机的性能经过多轮次的精心优化，目前的性能测试结果如下：
- 测试环境 - OS: Windows 10 64-bit 22H2 - CPU: i5-11260H - 浏览器: Edge 122

运行示例IR程序中的Benchmark，本虚拟机执行步数为3000004，耗时约为92毫秒，合计约3260.9万指令/秒。
作为对比，使用irsim运行同一程序（硬件和OS环境相同，Python 3.8.19），执行步数3000006，耗时约18.5秒，合计仅约16.2万指令/秒。本虚拟机性能高于irsim约200倍。

虚拟机的逻辑结构和源代码结构

虚拟机的逻辑结构

    ----------------------------------
    |                                |
    |               MMU              |
    | (名字挺吓人的，实际上只负责内存读写) |
    |     srcs/modules/vm/mmu.ts     |
    |                                |
    ----------------------------------
                    |
    ----------------------------------   ------------------------------
    |                                |   |                            |
    |               VM               |   |            ALU             |
    |  (虚拟机主模块，执行指令、处理IO)   |---| (进行32位整数的算术和逻辑运算) |
    |     srcs/modules/vm/vm.ts      |   |   srcs/modules/vm/alu.ts   |
    |                                |   |                            |
    ----------------------------------   ------------------------------
                    |
    ----------------------------------
    |                                |
    |            Decoder             |
    |  (静态检查IR指令并解码为可执行指令) |
    |   srcs/modules/vm/decoder.ts   |
    |                                |
    ----------------------------------

主要源代码的逻辑结构

    -------  -------         -------
    | VM0 |  | VM1 |   ...   | VMn |
    -------  -------         -------
       |        |               |
    ----------------------------------------------
    |                                            |
    |   VMContainer                              |
    |   (容纳多个VM实例的容器)                      |
    |   srcs/modules/vmContainer/vmContainer.ts  |
    |                                            |
    ----------------------------------------------
        ^             |
        | 映射         | syncVmState() 进行状态同步
        v             v
    ----------------------------------------------
    |                                            |
    |   VmState.vmPageStates                     |
    |   (各VM实例的UI状态，Redux Store)            |
    |   VmState.activeVmIndex为当前标签页VM的下标   |
    |   srcs/store/reducers/vm/vm.ts             |
    |                                            |
    ----------------------------------------------

如何添加一种语言

• Step1: 进入src/locales，以您语言的缩写为文件名新建一个.ts文件。然后将en.ts的内容粘贴进去，进行各个字符串的翻译，并修改被导出的变量名。
• Step2: 打开src/locales/index.ts，在文件顶端含有Add new language import here指示的地方引入您刚才创建的模块，然后在文件下面的locales变量里有Add new language entry here指示的地方照例添加一个记录。
• Step3: 在本地进行测试，然后提交PR即可。不要在本地进行构建。完成！

How to add a new language

• Step1: Go to src/locales, and create a .ts file named by your language. Then copy the content of en.ts into your created file, do translations, and rename the exported variable.
• Step2: Open src/locales/index.ts, find Add new language import here and add an import of your previously created module. Next add an entry into locales where there's an Add new language entry here mark.
• Step3: Test your new language and create a pull request. Don't run build. That's done!

如何添加一个主题

• Step1: 进入src/themes，新建一个主题名.scss文件。然后将light.scss的内容粘贴进去，修改各个颜色，并一定要修改类选择器的名字。
• Step2: 打开src/themes/index.ts，在文件里含有Add new theme entry here指示的地方照例添加一个记录。注意记录对象的className属性一定要和刚才scss文件里类选择器的名字相同。
• Step3: 打开src/App.tsx，在文件里含有Add new theme import here指示的地方照例添加对新主题scss文件的导入。
• Step4: 在本地进行测试，然后提交PR即可。不要在本地进行构建。完成！

How to add a new theme

• Step1: Go to src/themes, and create a yourThemeName.scss file. Then copy the content of light.scss into your created file, modify colors, and DO REMEMBER to rename the class selector.
• Step2: Open src/themes/index.ts, add an entry where there's an Add new theme entry here mark. Note that the className property must match the name of your theme's class selector.
• Step3: Open src/App.tsx, add an import for the new .scss file where there's an Add new theme import here mark.
• Step4: Test your new theme and create a pull request. Don't run build. That's done!

写在后面

今天是2024年的3月25日，从我开始开发这个项目算起，已经快要过去一年了。这几天，我大幅度重构了项目的代码，把虚拟机的性能提升了将近10倍，添加了很多IR示例程序，引入了强大的Monaco编辑器组件代替原先我手写的编辑器，还做了虚拟机的CLI版本。我的编译原理课程明明早已结束，这个项目的代码也有八个多月没有更新了，最近为什么又“朝花夕拾”了呢？
——因为，从某种意义上来说，这个项目，是我大学四年来学习成长的一次总检验。
客观地说，这个项目的规模并不算大，代码量也并不多，我只花了10天左右的时间就发布了第一个版本。但是，这个项目，代表了我一直以来“保持热爱，奔赴山海”的做事风格。当意识到我可以用自己的技能解决一个问题，让一件事情变得更好的时候，我就会激动得不能自已，并且马上开展行动。去年在做编译原理实验三的时候，我萌生了弥补irsim的所有不足，做一个全新的Web版虚拟机的想法，于是就毫不犹豫地创建了这个项目。之后的十天里，我每天都迸发着“兴酣落笔摇五岳，诗成笑傲凌沧州”的激情，敲下每一行代码时，指尖都跃动着欣喜。我相信，自己一定能让同学们在验收的时候，都用上这个更好的虚拟机——我做到了。能用自己的双手创造出新的事物，给这个世界带来一点小小的改变——多么让人感到快乐与幸福呀！从高中第一次接触编程到今天，我对编程的热爱从未减退，我写每一行代码的初心也都未曾改变。
同时，这个项目的六千多行代码里，也融入着我大学四年来沉甸甸的收获。编译