基于编译原理的计算器设计与实现.doc
《基于编译原理的计算器设计与实现.doc》由会员分享,可在线阅读,更多相关《基于编译原理的计算器设计与实现.doc(19页珍藏版)》请在咨信网上搜索。
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)。
4、ASM指令介绍指令助记符 操作数 指命说明 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,下面我来描述一下D
12、FA的运营过程:定义一个变量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。 现在的情况与辨认N
14、UMBER的情况类似,当前的状态也是终结状态,但按贪婪匹配的原则还要继续看看是否可以匹配到新的输入。 后面的b和c都在ID一个状态里转圈,我就不在赘述了,这样我们就辨认到了最后一个词法元素abc了。 用如上过程的方法可以辨认任何对的的算术表达式,但尚有几点需要特别说明: 如何辨认错误:目前我见过的语言规范都在描述如何对的的编译一个语言,但没有一个规范有描述如何报错的,所以我们目前能做的是只要按正常的走法走不通了,那就是错了,就要报错,并尽也许提供具体的错误信息。 对空白的辨认:我在DFA中并没有画辨认空白的部分,因素是对于计算器程序来说,空白完全没有用处,所以我只是在代码中直接忽略这个输入,以
15、免状态机无法 辨认空白,同时在辨认到词法元素之后,去掉单词前后的空白。对于某些语言来说,空白是故意义的,需要做为词法元素辨认出来,不能忽略掉。 对于词法元素的表达:通常我们会用一个类型Token来表达一个词法元素,Token中有两个属性,一个用于表达这个Token的类型,另一个用于表达内 容,只有数字与标记符才需要使用Token类型的内容属性,其它的类型由于同一类型只有一种表达的也许,所以就不需要再把内容保存下来了(如ADD的内容 一定是+)。 关于标记符:DFA中的ID状态用于辨认标记符,这里的标记符涉及自定义的变量,也涉及函数名。在DFA的设计过程中,我们可以选择把普通标记符与保存字 做为
16、不同的状态,也可以用使用同一个状态。我们现在的设计就使用了一个ID状态表达所有的标记符,而在辨认到一个ID之后,我们在看是否是一个保存字,这 样在返回Token对象时设立不同的类型。 对于INT和NUMBER:这个计算器的所有计算都使用的是double类型的数字,所在虽然我们的词法可以辨认到INT,但我们定义Token的类型 时,就只定义一个NUMBER类型,INT或NUMBER状态拟定的单词都返回NUMBER这个类型的Token对象。 前面的逻辑中有一个贪婪批配的原则,这个原则在某些语言的词法中会有一些特例不合用,例如在C+和JAVA中都有一个运算符“”,这个运算符代表右移,但在C+11 标
17、准中可以写出这样的代码std:vectorstd:vector,在JDK5及以上版本也可以这样写 ListList,这里假如按贪婪批配就错了。所以必须在词法分析中加入上下文的判断才干决定是按两 个来辨认还是按一个来辨认上下文的判断是语法分析的部分了,但对于复杂的词法结构在没有一个统一的词法解析算法可以解决的情 况下就得借助更高级的方法了。 现在剩下的就是写代码了。 假如我把代码贴在这里就太长了,不太合适。所以下面我只描述一下描述DFA的思绪: 思绪一:直接静态代码来描述,类似这样的方式把状态机的每个途径都描述出来:IF S = START AND c = 1 THEN S = INT . EL
18、SIF .,这样就可以输入运营了。 思绪二:表格驱动式的,例如列出下面的表格即可知道哪个状态通过哪个输入之后到达哪个新的状态了下表的左标题是当前的状态,上标题是在当前状态上的输入,表格中的内容是通过途径到达的状态。 思绪三:结合前两个思绪先写一个代码生成工具,工具读取“思绪二”中表格中的内容,并生成“思绪一”中的静态代码。0-9 . _a-zA-Z + - * / ( ) , START INT POINT ID ADD SUB MUL DIV LBT RBT COMMA INT INT NUMBER POINT NUMBER NUMBER NUMBER ID ID ID ADD SUB MU
19、L DIV LBT RBT COMMA 下面举一下DFA返回的Token对象的类型:NUM,FUN,VAR,ADD,SUB,MUL,DIV,LBT,RBT,COMMA这里前三个与DFA的状态名不同:NUM代表INT状态和NUMBER状态两个状态辨认出的词法元素。 FUN和VAR都是ID状态辨认出的元素,假如这个ID是一个函数名,则Token为FUN类型,否则即为VAR类型。 其它类型与DFA的状态是一一相应的。 最后说一下DFA的接口:假设DFA有一个方法叫做parse,则这个方法的参数只有一个字符串用于传入表达式即可。假如我们写的DFA是用于解析长文本的(而不仅仅是解析这个简短的算术表达式)
20、,则可以考虑参数为输入流。 parse方法的返回可以考虑返回一个Token的游标,游标供语法分析程序调用;也可以考虑解析完所有的词法元素返回一个Token的列表。由于目前比较通用的语法分析算法只需要向前看一个Token对象,所以游标就足够了。 由于语法分析程序有也许会把已读出来的Token放回去,下次再用,所以游 标可考虑加一个putBack方法也可以考虑不实现这个方法,而由语法分析程序自己缓存当前用不到的词法元素假如DFA返回的是list就简朴一 些,语法分析器可以前后前后移动offset即可。 DFA返回list的方式实现虽然简朴一点,但对于要解析的数据非常大的情况就不合用了特别数据是从网
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 编译 原理 计算器 设计 实现
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。