基于编译原理的计算器设计与实现.doc

《基于编译原理的计算器设计与实现.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于编译原理的计算器设计与实现首先看一下这个计算器的功能：CALC>seta=1;b=2CALC>setc=3CALC>calc(10+pow(b,c))*sqrt(4)-135.0CALC>exit如上所示，这个计算器的功能非常简单：1.用set命令设置上下文中的变量。2.用calc命令计算一个表达式的值。3.用exit命令退出计算器。我们把编译的重点放在calc命令后面的计算表达式的解析，其它的部分我们可以简单处理（如set命令可以这样简单处理：先按分号分隔得到多个赋值处理，再按等号分隔就可以在上下文中设置变量了，并不需

2、要复杂的编译过程）。如上的演示例子中，我们使用编译技术处理的部分是(10+pow(b,c))*sqrt(4)-1，其它部分我们只使用简单的文本处理。麻雀虽小，但五脏俱全，这个计算器包含编译技术中最必要的部分。虽然这次我们只是实现了一个计算器，但所使用的技术足以实现一个简单的脚本语言的解释器了。这个计算器分为如下几个部分：词法分析：把表达式的文本，解析成词法元素列表(tokenList)。语法分析：把tokenList解析成语法树(syntaxTree)。语义分析：把语法树转成汇编语言的代码(asm)汇编器：把汇编代码翻译为机

3、器码（字节码）。虚拟机：执行字节码。一般的编译步聚中不包含“汇编器”和“虚拟机”，而这里之所以包含这两个部分是因为：通常编译器会直接由中间代码生成机器码，而不是生成汇编代码，而这里我之所以要生成汇编代码的原因是“调试的时候汇编的可读性很好”，如果直接生成目标代码，则会非常难用肉眼来阅读。自己实现虚拟机的原因是：现有的机器（包括物理机和虚拟机以及模拟器）的指令虽然也很丰富，但似乎都没有直接计算“乘方”或“开方”的指令，自已实现虚拟机可以任意设计计算指令，这样可以降低整个程序的复杂度。因汇编器与虚拟机并不是编译原理的部分，所以下

4、文中并不会描述其实现细节，但因为计算器代码编译后的目标代码就是汇编代码，所以需要把汇编指令做一下说明（以下把这个汇编语言简称为ASM）。ASM指令介绍指令助记符操作数指命说明storenumber把number放入栈顶add从栈顶取出两个数相加，并把结果压回栈中sub从栈顶取出一个数做为被减数，再取一个做为减数，相减之后的结果入栈mul从栈顶取出两个数相乘，并把结果入栈div从栈顶取出一个数做为除法的分子，再取出一个做为除法的分母，相除的结果入栈pow从栈顶取出一个数做为底，再取出一个做为幂，计算结果入栈sqrt从栈顶取出一

5、个数，把这个数开平方后的结果入栈print在控制台打印栈顶的数字这个虚拟机是基于栈来设计的，所有的计算指令的操作数都从栈中取，store命令向栈顶添加数据。print指令用于打印当前栈顶的数据，在我们编译的汇编代码要做到：正确计算出结果，且计算完成之后的结果要刚好在栈顶，这样最后调用一个print指令即可以控制台看到计算结果。ASM举例：例1，如果我们要计算1-2*3，则我们写出的汇编代码如下（行号是为下文解释代码方便而放上去的，不是代码的一部分）：点击(此处)折叠或打开store3store2mulstore1subpri

6、nt对这段代码的说明如下：前两行向栈顶添加两个数字，先压入3再压入2，这样栈顶的数字是2，第二个数字是3。第三行mul会从栈顶弹出两个数字（2和3）计算乘法，并把结果（6）再压入栈中，此时栈中只有一个数字6。第四行向栈顶压入一个数字1，此时栈顶为1，第二个数字是6。第五行sub指令从栈顶取出两个数字，第一个数字1做为被减数，第二个数字6做为减数，即计算1-6，并把结果压入栈中，此时栈中只有一个数字-5。最后一行print指令不对栈做写操作，只读取栈顶的数字，并打印出来。在这里，我们用到两个运算，mul和sub，这两个运算都是

7、二元运算，因我在设计指令的时候，先取出来的数字是第一个操作数，所以先压入的应该是第二个操作数，这也是为什么代码中先压入的是3，之后是2，最后才是1。例2，如果我们要计算(10+pow(2,3))*sqrt(4)-1，则我们写出的汇编代码如下（行号是为下文解释代码方便而放上去的，不是代码的一部分）：点击(此处)折叠或打开store1store4sqrtstore3store2powstore10addmulsubprint对这段代码的说明如下：这段代码稍有点复杂，但有前一段代码的经验，我们可以看到，所有的操作数的先后顺序是从右

8、向左store的，所以store指令的顺序是固定下来的，剩下的关键是操作指令应该放在哪里。操作指令也是有一个规律的，即：当前栈顶的数据刚刚好满足某运算时，则操作指令就放在哪里，如：store1的时候没有任何操作的操作数都在栈中。store4的时候，刚刚好sqrt的操作数都在栈中，则此时加入