该CMM解释器包含共包含了前端的词法分析、语法分析和语义分析,IR的语法树的解析,中间代码以及后端虚拟机对中间表示的解释执行,另外还有Debug功能。
该解释器主要支持int
、double
、bool
、string
类型,以及if-else
、while
、break
、continue
语句,支持read
输入和write
输出。
首先感谢Moskize91,我主要参考了他的部分代码和结构。
前端主要由词法分析Lexer
和语法语义分析Parser
构成,由Lexer
将通过有限状态机将文件中的字符逐个读入,当状态发送改变时,说明前一个状态对应的Token
已经构造完毕,传递给Parser
,然后Parser
通过递归下降子程序对Token
进行递归处理,直至将其转换为终结符。
前端的执行是先调用Parser
的,所以当Parser
开始执行的时候,它会向Lexer
请求Token
,然后Lexer
才开始从文件中陆续读取字符并将其解析成Token
返回,所以对于前端的执行,代码只需被扫描一遍即可。Parser
最终将所有Token
转换为一颗语法树,并返回语法树的根节点。
Token
中除了对应的字符串外,还存储着对应的位置信息,所以若在解析时出现语法错误,Lexer
或Parser
会抛出异常并停止解析。
语法树的解析工作由CodeCreater
来完成,它同样通过递归下降的方式根据语法树的生成结构遍历语法树。整套代码的所有信息都存储在Context
类中,它是代码块对应的上下文。由于该解释器只支持判断语句与循环语句,所以所有代码整体是在一个大的代码块中,共享一个Context
。
Context
主要包含了以下几个类:
CodeChunk
:该类主要用来按顺序存储中间代码。VariablePool
:变量池,用来为中间代码分配变量。临时变量会被回收,在代码中被定义的局部变量不会被回收。VariableRecorder
:用来记录变量与变量名之间的对应关系已经变量的类型信息,每一个代码块都有一个,最终形成树形结构,但是子节点可以访问父节点,父节点并不能访问子节点。PositionPlaceholder
:该类用于填充转跳语句的操作数,因为产生转跳语句时并不知道其转跳目标的位置,所以需要占位。JumpStack
:记录当前的循环体,并指定相关的continue
与break
转跳位置信息。
所有的变量类型都会被推迟到运行时来判断,所以在中间代码生成时采用一种延迟绑定的策略,在运行时解释中间代码时再将变量类型绑定到相应的操作数上。
中间代码主要是在三元式的加了一点微小的改动,主要包括:
public enum Command {
Mov,
Add, Sub, Mul, Div, Mod, Opposite,
Not, And, Or,
Gt, Gte, Lt, Lte, Equal, NotEqual,
Jmp, JmpUnless,
Write, Read,
NewArray, Get, Set
}
Mov
:变量的赋值。Jmp
:直接转跳语句。JmpUnless
:当特定条件不成立时进行转跳,跳到目标位置的下一行。Write
:将对应变量的值输出。Read
:输入信息为特定变量赋值。NewArray
:定义一个数组。Get
:从数组中取出一个对应索引的元素。Set
:给数组中指定索引的元素赋值。
Set
与Get
是对于数组的操作,比较特殊,它们有三个操作数。
IntermediateCodeCreator
为中间代码生成提供了接口,它调用CodeCreator
并返回一个产生的中间代码序列。在返回中间代码序列之前,该类会将所有的转跳语句的占位符替换为对应的行数。
int i = 0;
while (i < 10) {
write(i);
i += 1;
}
Mov 1, _, _ << 0
Mov 0, 1, _
Mov 1, 0, _
Mov 2, _, _ << 10
Lt 1, 2, _
JmpUnless 11, 1, _
Mov 2, 0, _
Write 2, _, _
Mov 1, _, _ << 1
Add 0, 1, _
Jmp 2, _, _
中间代码存在很大的冗余,优化的话以后有时间再做吧。
后端是一个简单的虚拟机,虚拟机读入文件,启动语法分析并转化成中间代码序列,然后将中间代码转交给Runtime
类,由Runtime
类来按序解释中间代码。
中间代码的解释执行是由Interpreter
类来完成的,该类维持一个静态的HashMap
,其中key
为中间代码的命令,而value
为命令所对应的lambda
函数。lambda
函数的返回值为下一条指令的位置,在解释时从第0个中间代码开始,通过中间代码命令取出对应函数并执行,得到下一条指令,找到没有指令可执行为止。
若在解释时遇到两个变量类型不一致的问题,解释器会提升变量的类型,如果此时还不一致,那么就抛出错误。
在解释执行中间代码时,解释器会将所有遇到的临时变量和局部变量转换为Value
类型并存储在DataChunk
中。
所有变量的类型信息都是在运行时出现,所有对于类型错误,数组的错误操作等都是在运行时才会被发现。在解释时,如果遇到错误,打印错误信息并退出。
int i = 0;
while (i < 10) {
write(i);
i += 1;
}
解释器加入了Debug
模式,在该模式中,Debug
类会从词法分析中获取源代码,在中间代码生成过程中建立源代码与中间代码的映射关系,并记录相关代码的作用域以方便查询变量信息。在中间代码执行前,虚拟机会将执行权限与相关的参数传给Debug
类,由Debug
类来负责执行。
Debug
对中间代码的解释执行并无两样,只是它存储了许多调试信息,并按照需要解释命令。具体命令如下:
l/list [inter]
:打印源代码,当命令后跟inter
时打印中间代码。r/run
:运行程序,直到遇到断点或程序结束;若程序已经结束,则重新开始运行。c/continue
:运行程序,直到遇到断点或程序结束。b/break [inter] line
:在源代码的对应行上加入断点,当命令中含有inter
时在中间代码上加断点。n/next [inter]
:运行下一行代码,当命令中含有inter
时运行下一行中间代码。p/print id
:打印变量信息,若id
为正整数,则打印中间代码中的操作数所对应的变量。d/delete [inter] line
:删除对应行上的断点。info break [inter]
:输出断点信息。q/quit
:退出程序。