loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

基于栈的虚拟机的实现

上次的编译原理练习中,生成的目标代码是别人写的一个基于寄存器的简单虚拟机。这

回这个简单的基于栈的虚拟机,纯碎是为了弥补上回的练习不足。

基于寄存器(register based)的虚拟机和基于栈(stack based)的虚拟机主要的不同在于

对指令运算的中间值的保存方式。这些中间值包括各种运算的结果值,传给各个指令的参

数等等。前者一般会设置几个寄存器,如累加寄存器;后者则没有寄存器,只有一个用来

保存这些值的栈。例如,这里我实现的SM(stack based machine)中的ADD指令:

ADD:从栈中依次弹出两个数a和b,然后将b+a压栈(b是左操作数)。基于这样一个方

式,SM中大部分指令都不需要操作数,其操作数都直接从栈顶取。因为这个虚拟机仅仅是

用于上回设计的简单语言的运行,即没有函数、只有数字类型、有if和while。在这回练习中

我甚至把逻辑运算符给阉割了,只保留了大于小于之类的关系运算符。以下是该语言计算阶

乘的例子:

read x;
if( x > 0 )
{
fac = 1;
while( x > 0 )
{
  fac = fac * x;
  x = x - 1;
}
write fac;
}
else
{
write 0;
}

基本上同《编译原理与实践》里的例子一样,这样省得我去琢磨语言文法。

不过,SM中还是有一个寄存器,即指令指针寄存器(pc),永远指向将要执行的指令。在实现中,

所有指令都被保存一个数组里,所以pc就是一个指向数组索引的整数值。

SM中有一个简单的内存,只用于保存程序中的全局变量(只有全局变量)。同样,这个虚拟的

内存也被简单地用一个数组来实现,所以,指令中的所有地址,都是数组索引值。

SM的代码文件直接就是指令序列的二进制表示。在这个二进制文件中,内容依次为:操作码(1

字节),操作数(4字节,如果有的话),操作码,操作数,。。。SM读取这样的文件,将这些

指令放进指令数组,然后逐条解释执行,直到遇到空指令。

代码中的test是上面简单提到的编程语言的编译程序,该程序将源代码编译为SM可执行的二进制

文件(sm后缀)。为了方便调试,SM本身可以根据命令行参数输出二进制文件对应的反汇编代码,

这可以方便我调试编译程序的代码生成是否正常工作。同时,当初为了测试SM的正确性,还写了

个简单的汇编程序(sasm),可以把SM的汇编代码转换为二进制文件。

这回我特地在文法中间插入action丢给yacc处理,在赋值语句中一切正常。但是在if中yacc依然

提示警告,看起来应该跟if中的悬挂else二义性有关系。不过通过添加空的文法符号,居然解决了。

不清楚为什么上回死活有问题,诡异了。

 

下载SM

posted on 2010-04-15 19:56 Kevin Lynx 阅读(7606) 评论(0)  编辑 收藏 引用 所属分类: 编译原理


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理