《基于编译原理的计算器设计与实现.doc》由会员分享，可在线阅读，更多相关《基于编译原理的计算器设计与实现.doc（12页珍藏版）》请在金锄头文库上搜索。
1、基于编译原理的计算器设计与实现 首先看一下这个计算器的功能：CALC set a = 1; b = 2CALC set c = 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、虚拟机”，而这里之所以包含这两个部分是因为：通常编译器会直接由中间代码生成机器码，而不是生成汇编代码，而这里我之所以要生成汇编代码的原因是“调试的时候汇编的可读性很好”，如果直接生成目标代码，则会非常难用肉眼来阅读。 自己实现虚拟机的原因是：现有的机器（包括物理机和虚拟机以及模拟器）的指令虽然也很丰富，但似乎都没有直接计算“乘方”或“开方”的指令，自已实现虚拟机可以任意设计计算指令，这样可以降低整个程序的复杂度。 因汇编器与虚拟机并不是编译原理的部分，所以下文中并不会描述其实现细节，但因为计算器代码编译后的目标代码就是汇编代码，所以需要把汇编指令做一下说明（以下把这个汇编语言简称为ASM）。A
4、SM指令介绍指令助记符 操作数 指命说明 storenumber把number放入栈顶add从栈顶取出两个数相加，并把结果压回栈中sub从栈顶取出一个数做为被减数，再取一个做为减数，相减之后的结果入栈mul从栈顶取出两个数相乘，并把结果入栈div从栈顶取出一个数做为除法的分子，再取出一个做为除法的分母，相除的结果入栈pow从栈顶取出一个数做为底，再取出一个做为幂，计算结果入栈sqrt从栈顶取出一个数，把这个数开平方后的结果入栈print在控制台打印栈顶的数字这个虚拟机是基于栈来设计的，所有的计算指令的操作数都从栈中取，store命令向栈顶添加数据。print指令用于打印当前栈顶的数据，在我们编
5、译的汇编代码要做到：正确计算出结果，且计算完成之后的结果要刚好在栈顶，这样最后调用一个print指令即可以控制台看到计算结果。ASM举例：例1，如果我们要计算1-2*3，则我们写出的汇编代码如下（行号是为下文解释代码方便而放上去的，不是代码的一部分）：点击(此处)折叠或打开 store 3store 2mulstore 1sub print 对这段代码的说明如下：前两行向栈顶添加两个数字，先压入3再压入2，这样栈顶的数字是2，第二个数字是3。 第三行mul会从栈顶弹出两个数字（2和3）计算乘法，并把结果（6）再压入栈中，此时栈中只有一个数字6。 第四行向栈顶压入一个数字1，此时栈顶为1，第二个
6、数字是6。 第五行sub指令从栈顶取出两个数字，第一个数字1做为被减数，第二个数字6做为减数，即计算1-6，并把结果压入栈中，此时栈中只有一个数字-5。 最后一行print指令不对栈做写操作，只读取栈顶的数字，并打印出来。 在这里，我们用到两个运算，mul和sub，这两个运算都是二元运算，因我在设计指令的时候，先取出来的数字是第一个操作数，所以先压入的应该是第二个操作数，这也是为什么代码中先压入的是3，之后是2，最后才是1。 例2，如果我们要计算(10 + pow(2, 3) * sqrt(4) - 1，则我们写出的汇编代码如下（行号是为下文解释代码方便而放上去的，不是代码的一部分）：点击(此
7、处)折叠或打开 store 1store 4sqrtstore 3store 2powstore 10addmulsubprint 对这段代码的说明如下：这段代码稍有点复杂，但有前一段代码的经验，我们可以看到，所有的操作数的先后顺序是从右向左store的，所以store指令的顺序是固定下来的，剩下的关键是操作指令应该放在哪里。 操作指令也是有一个规律的，即：当前栈顶的数据刚刚好满足某运算时，则操作指令就放在哪里，如： store 1的时候没有任何操作的操作数都在栈中。 store 4的时候，刚刚好sqrt的操作数都在栈中，则此时加入sqrt指令。 store 3 store 2时，刚刚好可以计
8、算pow。 store 10之后，就可以计算加法了，所以此时加入add指令。 add计算完成之后，再加上之前已计算完的sqrt指令，则此时乘法的所有操作数都在栈中了，则此时加入mul指令。 最后减操作也可以计算了，则加上sub指令。 所有计算完成之后打印出结果。 在这个例子中，我所说的“规律”其实就是“后缀表达式”。我们平常写的算术表达式是“中缀”的，即符号在操作数中间，如1 + 2，的 + 在1和2中间，转为后缀形式即为1 2 +这里因为我对于参数顺序的设计是与“正常”顺序相反的，所以1 + 2对于这个汇编器来说，其后缀形式就应该为2 1 +大家是可以按照这个规律，相对简单的实现这个计算器只
9、要做好词法分析就可以按照后缀表达式的规律直接由tokenList生成汇编代码了但我们的目的是用这个计算器的例子来讲编译，所以还是按步就班来讲。词法分析词法分析的目的是把一段文本分解成词法元素列表，例如(10 + pow(2, 3) * sqrt(4) - 1，做词法分析之后会分解成如下几个词法元素： （10+pow(2,3)*sqrt(4)-1这里只是做了一次文本处理在处理之前，我们手里有的东西就是一串字符组成的字符串，在处理之后，我们按照一定的“规则”分解为多个单词。算法是多种多样的，有创造力的程序员会想出各种办法来处理这个单词分解的问题。在编译原理中，普遍的方式是用如下一个状态转换图来实现
10、的在图中，“椭圆形”的是状态，状态与状态之间有一条有方向的线，这个线代表从一个状态到另一个状态的路径，在这条线上面有一个花括号代表从前一个状态到达 后一个状态的输入（为方便表示，0-9表示从0到9十个数字，a-z表示从a到z二十六个字母等），如从START状态开始，输入一个数字1，就会到达 INT状态。图中蓝色的状态是终结状态，如果从START状态经过若干输入后到达终结状态，则这些输入的字符可合并为词法的合法单词这里需要额外说明一点：在对输入进行匹配状态时采用贪婪方式，即：尽量输入更多的字符。在识别到一个合法的词法单元之后，状态回到START继续识别下一个元素，直到没有新的元素为止。这个状态转
11、换图在编译原理中有一个专有名词称呼它“确定有限状态自动机”，英文简称DFA。这里“确定”的意思是每一个状态经过一个输入字符可以确定只有 一条路径到达另一个状态，“有限”的意思是，状态的个数是有限的。对于一个复杂语言的状态数量是这个状态机的几个数量级的大小。但我们现在的计算器只需要 这几个状态就够了。通常的DFA会由工具读取正则方法描述而生成的，而不是直接手工构造，但对我们现在设计的计算器来说，其DFA非常小，手工构造是很方便的，所以就不用工具了。另外，如果使用工具的话，我这篇文章也不会使用现有的工具，而是自己实现一个工具。下面举个例子：我们有一个表达式12.3 + abc，下面我来描述一下DF
12、A的运行过程：定义一个变量s，来表示当前状态机所在的状态（初始时s = START）。 输入第一个字符1，此时START状态可接受这个输入1，到达INT状态，则变量s赋值为INT状态，此时可看到INT状态的颜色是蓝色表示当前可识别为一个合法的词法元素，但因为我们的规则是贪婪匹配，所以我们还要看看是否还能够匹配更多的字符。 输入第二个字符2，此时INT状态也可以接受这人输入，并到达INT状态（转了一个圈又回到原来的状态），此时变量s赋值为INT状态。 再输入第三个字符 . ，此时INT状态可接受 . 到达NUMBER状态，此时变量s赋值为NUMBER状态。 此时我们再向前看一个字符 + ，此时的
13、状态NUMBER无法接受这个字符了，同时我们可在看到NUMBER状态的颜色是蓝色的，表示当前状态可识别一个合法的词法元素，即：从 START开始到当前我们一共经历的输入为12.3，则这个单词做为第一个合法的词法元素。 第一个词法元素识别成功之后，变量s要回到START状态，并继续输入 + ，此时从START状态可到达ADD状态，且ADD状态并不允许接受任何输入，同时ADD状态的颜色也是蓝色的，则我们又识别出第二个词法元素 + 。 在识别到第二个词法元素之后，变更s要回到START状态，并继续输入a，此时START状态可由a指向的路径到达ID状态，此时s赋值为新的状态ID。 现在的情况与识别NU
14、MBER的情况类似，当前的状态也是终结状态，但按贪婪匹配的原则还要继续看看是否可以匹配到新的输入。 后面的b和c都在ID一个状态里转圈，我就不在赘述了，这样我们就识别到了最后一个词法元素abc了。 用如上过程的方法可以识别任何正确的算术表达式，但还有几点需要特别说明： 如何识别错误：目前我见过的语言规范都在描述如何正确的编译一个语言，但没有一个规范有描述如何报错的，所以我们目前能做的是只要按正常的走法走不通了，那就是错了，就要报错，并尽可能提供详细的错误信息。 对空白的识别：我在DFA中并没有画识别空白的部分，原因是对于计算器程序来说，空白完全没有用处，所以我只是在代码中直接忽略这个输入，以免
15、状态机无法 识别空白，同时在识别到词法元素之后，去掉单词前后的空白。对于某些语言来说，空白是有意义的，需要做为词法元素识别出来，不能忽略掉。 对于词法元素的表示：通常我们会用一个类型Token来表示一个词法元素，Token中有两个属性，一个用于表示这个Token的类型，另一个用于表示内 容，只有数字与标识符才需要使用Token类型的内容属性，其它的类型因为同一类型只有一种表示的可能，所以就不需要再把内容保存下来了（如ADD的内容 一定是+）。 关于标识符：DFA中的ID状态用于识别标识符，这里的标识符包括自定义的变量，也包括函数名。在DFA的设计过程中，我们可以选择把普通标识符与保留字 做为不同的状态，也可以用使用同一个状态。我们现在的设计就使用了一个ID状态表示所有的标识符，而在识别到一个ID之后，我们在看是否是一个保留字，这 样在返回Token对象时设置不同的类型。 对于INT和NUMBER：这个计算器的所有计算都使用的是double类型的数字，所在虽然我们的词法可以识别到INT，但我们定义Token的类型 时，就只定义一个NUMBER类型，INT或NUMBER状态确定的单词都返回NU
