布尔表达式的LR翻译器--中间代码为四元式.docx

学号：课程设计题目布尔表达式的LR翻译器学院计算机科学与技术学院专业软件工程班级软件1102姓名李帅奇指导教师何九周2023年1月2日课程设计任务书学生姓名：李帅奇专业班级:软件1102指导教师：何九周工作单位:计算机科学与技术学院题目：布尔表达式的LR翻译器初始条件：程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据编译原理课程所讲授的算法进行设计。要求完成的主要任务：（包括课程设计工作量及其技术要求，说明书撰写等具体要求）1 .明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的根本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按时、独立完成课程设计任务。2 .主要功能包括：利用LR分析法编制、调试其语法及语义分析程序，生成的中间代码为四元式。编制好分析程序后计假设干用例，上机测试并通过所设计的分析程序。（参考教材P181182）进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用出错处理程序。3 .设计报告：要求层次清楚、整洁标准、不得相互抄袭。正文字数不少于0.3万字。包含内容：课程设计的题目。目录。正文：包括引言、需求分析、总体设计及开发工具的选择，设计原那么1给出语法分析方法及中间代码形式的描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。结束语。参考文献。附录：软件清单（或者附盘）。时间安排:消化资料、系统调查、形式描述系统分析、总体设计、实施方案撰写课程设计报告书指导教师签名：2023年1月2日系主任（或责任教师）签名:2023年1月2日目录2需求分析33总体设计及开发工具的选择43设计分析43.2 设计原理5词法分析5语法分析5中间代码生成53.3 开发工具64设计原那么65数据结构与模块说明75.1 ACTION表和GOTO表75.2 存储符号和产生式的数组85.3 状态栈和符号栈86算法设计136.1 词法分析算法描述13词法分析流程图13词法分析算法136.2 语法分析算法代码描述14语法分析算法流程图14语法分析算法146.3 中间代码的生成177软件调试198软件的测试方法和结果209有关技术的讨论20IO收获与体会2011参考文献21本科生课程设计成绩评定表21布尔表达式的LR翻译器1引言编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和根本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。所谓LR(K)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相对于某一产生式左左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作(是移进还是按某一产生式进行归约等)。2需求分析有如下的布尔表达式文法：BBandTITTTorFFFnotFtrueIfalse(B)iropi利用LR分析法编制、调试其语法及语义分析程序，生成的中间代码为四元式。编制好分析程序后计假设干用例，上机测试并通过所设计的分析程序。布尔表达式的LR分析分为扩展文法，构造识别活动前缀的DFA图，判断有误冲突,假设有冲突，那么消除冲突和构造LR分析表等步骤。首先要拓广文法：非二义性文法如下：(0)B'B(1) BBandT(2) BT(3) TTorF(4) TF(5) FnotF(6) F(B)(7) Ftrue(8) Ffalse(9) Firopi 构造识别活动前缀的DFA图 判断有无冲突LR(O)分析时有移进一规约冲突，但冲突可以由SLR(1)分析解决。 构造LR分析表状态SiACIONGOTOandornottruefalse()irop#BTFOS4S5S6S7S81231S9R2ACC2R2SlOR2R23R4R4R4R44S4S5S6S7S8115R7R7R7R76R8R8R8R87S4S5S6S7S812238S139S4S5S6S7S814310S4S5S6S7S81511R5R5R5R512S9S1613R3S1714RlSlORlRl15R3R3R3R316R6R6R6R617R9R9R9R93总体设计及开发工具的选择3.1设计分析编译器设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。编译程序的输出结果为中间代码即逆波兰式。整个编译程序分为三局部：词法分析局部、语法分析处理及逆波兰式生成局部、输出显示局部。编译程序需要在单词级别上来分析和翻译源程序，所以首先要识别出单词，而词法分析局部的任务是：从左至右扫描源程序的字符串，按照词法规那么（正那么文法规那么）识别出一个个正确的单词，并转换成该单词相应的二元式种别码、属性值）交给语法分析使用。因此，词法分析是编译的根底。执行词法分析的程序称为词法分析器。语法分析是编译程序的核心局部,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。语法分析中主要以二元式作为输入局部,所以输出显示局部的任务是将二元式通过LR分析表对语法分析处理过程进行控制，使逆波兰式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。3.2设计原理词法分析词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即根本保存字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。程序语言的单词符号一般分为五种：关键字(保存字/根本字)、标识符、常数、运算符、界限符。词法分析的功能是输入源程序，输出单词符号。词法分析的单词符号常常表示成二元式(单词种别码，单词符号的属性值)。词法分析器的设计方法有如下四个步骤：1、写出该语言的词法规那么。2、把词法规那么转换为相应的状态转换图。3、把各转换图的初态连在一起，构成识别该语言的自动机。4、设计扫描器；把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。扫描器从初态出发，当识别一个单词后便进入终态，送出二元式语法分析语法分析是编译程序的核心局部,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作.法分析的方法有多种多样，常用的方法有递归子程序方法、运算符优先数法、状态矩阵法、LL(K)方法和LR(K)方法。归纳起来，大体上可分为两大类，即自顶向下分析方法和自底向上分析方法.Syntax进行语法分析。对于语法分析，这里采用LR(I)分析法，判断程序是否满足规定的结构.构造LR(I)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR(K)分析方法是严格的从左向右扫描，和自底向上的语法分析方法。中间代码生成进入编译程序的第三阶段：中间代码产生阶段。为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。常用的几种中间语言有：逆波兰式、四元式、三元式、树表示。本课程设计主要实现逆波兰式的生成。逆波兰式定义：将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。3.3开发工具Windows环境下使用VisualC+6.04设计原那么算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。严格说来，一个算法必须满足以下五个重要特性： 有穷性：对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。 确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。 可行性：算法中的所有操作都必须足够根本，都可以通过己经实现的根本操作运算有限次实现之。 有输入：作为算法加工对象的量值，通常表达为算法中的一组变量。但有些算法的字面上可以没有输入，实际上己被嵌入算法之中。 有输出：它是一组与“输入有确定关系的量值，是算法进行信息加工后得到的结果,这种确定关系即为算法的功能。在设计算法时，通常应考虑以下原那么：首先说设计的算法必须是“正确的，其次应有很好的“可读性，还必须具有“健壮性，最后应考虑所设计的算法具有“高效率与低存储量。所谓算法是正确的，除了应该满足算法说明中写明的“功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。算法的效率指的是算法的执行时间，算法的存储量指的是算法执行过程中所需最大存储空间。算法是程序设计的另一个不可缺的要素，因此在讨论数据结构的同时免不了要讨论相应的算法。这里有两重意思，即算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。确定性表现在对算法中每一步的描述都没有二义性，只要输入相同，初始状态相同，那么无论执行多少遍，所得结果都应该相同。5数据结构与模块说明5.1 ACTION表和GOTO表在程序中，我们使用两个二维数组存储SLR分析表，并初始化，初始化SLR表，其中action表中：100表示acc,除了100以外整数表示移进状态；负数表示用对应产生式进行规约。intaction1810=0,0,4,5,6,7,0,8,0,0),/09,0,0,0,0,0,-2,0,0,100,l-2,10,0,0,0,0,-2,0,0,-2)2-4,-4,0,0,0,0,-4,0,0,-4,30,0,4,5,6,7,0,8,0,0),4-7,-7,0,0,0,0,-7,0,0,-7)5-8,-8,0,0,0,0,-8,0,0,-860,0,4,5,6,7,0,8,0,0),70,0,0,0,0,0,0,0,13,0,80,0,4,5,6,7,0,8,0,0),90,0,4,5,6,7,0,8,0,0,10-5,-5,0,0,0,0,-5,0,0,-5119,0,0,0,0,0,16,0,0,0,120,0,0,0,0,0,0,17,0,0,13-1,10,0,0,0,0,-1,0,0,-114-3,-3,0,0,0,0,-3,0,0,-315-6,-6,0,0,0,0,-6,0,0,-616-9,-9,0,0,0,0,-9,0,0,-9);/17intgotol183=1,2,3,0,0,0,0,0,0,0,0,0,0,0,11,0 ,0 ,0,0 ,0(0 ,0 ,15,0 ,00 ,0 ,0,0,0 ,0,0 ,0 ,0);,0,12,2,3,0,0,0,0,14,3,0,0,0,0,0,0,0,0,0,0),5.2 存储符号和产生式的数组用三个数组来存储和符号以及产生式相关的信息：endls数组存储终结符、noends数组存储非终结符、PrOdUCtS数组存储产生式信息。终结符集合stringendls10=,and',or',not",true',false,(,V,)'"i",''rop,"F);非终结符集合stringnoends3=,B",T'',"F"产生式集合stringproducts10=,'B'7,BandT",uT',"TorF,"F","notF","(B),"true",false,iropi,);5.3 状态栈和符号栈我们用类来模拟状态栈和符号栈。这是状态栈：classstatestack(private:int*base;栈底指针int*top;/栈顶指针intsize;栈内元素个数intStaCkSize;栈的大小public:statestack()size=O;stacksize=20;base=newintstacksize;top=base;)intgetTop()/获取栈顶的元素。(if(base=top)(return-1;)else(return*(top-l);)boolstatePush(intelem)元素入栈(+size;(*top)=elem;+top;returntrue;)voidstatePop(inttime)/元素出栈(for(inti=0;i<time;i+)-top;-size;)voidPrintState()输出栈内的所有元素(stringstr=,;int*pre;for(pre=base;pre<top;pre+)(if(*pre>9)(charchl=(*prel0)+48;charch2=(*pre%10)+48;str+=ch1;str+=ch2;)else(charch=*pre+48;str+=ch;)cout<<setw(15)«setiosflags(ios_base:left)«str;)；这是符号栈：classsymbolstackprivate:string*base;string*top;intsize;intstacksize;public:symbolstack()(size=0;stacksize=20;base=newstringstacksize;top=base;)stringgetTop()获取栈顶的元素。(if(base=top)(return")else(return*(top-l);)元素入栈boolsymbo!Push(stringelem)(+size;*top=elem;+top;returntrue;)元素出栈voidsymbolPop(inttime)(for(inti=0;i<time;i+)(-top;size;)输出栈内的所有元素voidprintSymbol()(stringstr=,;string*pre;for(pre=base;pre<top;pre+)(str+=*pre;)cout<<setw(l5)«setiosflags(ios_base:left)«str;)）；6算法设计6.1 词法分析算法描述词法分析流程图词法分析算法用该函数将布尔表达式分开，并存储在vector中。/将字符串按空格分开,并存入vector中。vector<string>separatestrEX(stringstr)(vector<string>vec;intpos=0;for(inti=O;i<str.size();+i)(if(isspace(stri)如果当前字符是空格(vec.push_back(str.substr(pos,i-pos);复制起始位置为pos且长度为i-pos的字符串。pos=i+1;)vec.push-back(str.substr(pos,str.size()-pos);returnvec;)6.2 语法分析算法代码描述语法分析算法流程图语法分析算法用actionGoto函数对每个符号进行分析：voidactionGoto(stringstr,stringstrl)(intX=State.getTop();/当前栈顶状态inty=strtolnt(str);当前将要输入的字符if(actionxy>0&&judgeSymbol(Str)&&(str!="#")移进(printflnfoEX(step,state,symbol,str1J移入"+str);state.statePush(actionxy);SymboLsymbolPush(str);+step;)if(actionxy<0&&judgeSymbol(Str)规约(intz=-actionxy;/用-actionxy对应的产生式规约stringIenStr=ProdUCtS口;生成需要规约的产生式intn=calculatenum(IenStr);计算产生式的长度，进行规约intc=chooseNoEnds(z);stringCh=noendsc;生成规约后的非终结符CreateforChief(nJenstr,ch);生成四元式PrintfInfbEX(SteP,state,symbol,strl,"规约"+noends©+"-"+ProdUCtSz);state.statePop(n);symbol.symbolPop(n);intm=state.getTop();获取规约后的栈顶状态if(gotolmc>0)intg=gotolmc;state.statePush(g);symbol.symbolPush(ch);)+step;actionGoto(str,strl);)if(actionxy=100)<fe<fc(str=',r,)(PrintfInfoEX(SteP,state,symbol,strl,"分析完成");)如下是StrtoInt函数的代码：/将终结符和非终结符转换为action和gotol表中对应的列号intstrtolnt(stringstr)(if(str=',and")returnO;if(str=,or)return1;if(str=nnot)return2;if(str=ntrue")return3;if(str=nfalse)return4;if(str=,'(,)return5;if(str=,)M)return6;if(str="i“)return7;if(str="ropn)return8;if(str=',r')return9;if(str="B")return0;if(str=',T)return1;if(str=*,Fu)return2;)如下是judgeSymbol函数的代码：判断字符是终结符还是非终结符booljudgeSymbol(stringstr)(for(inti=0;i<10;i+)if(endlsi=str)returntrue;)returnfalse;)如下是ChooseNoEnds函数的代码:根据产生式选择非终结符intchooseNoEnds(intnum)if(num=lnum=2)return0;选择“Bif(num=3num=4)return1;/选择叮return2;选择“F)如下是Calculatenum函数的代码:/计算字符串中元素的个数intcalculatenum(stringstr)(intnum=0;for(inti=O;i<str.size();+i)(if(isgraph(stri)continue;else(+num;)+num;returnnum;)6.3 中间代码的生成该函数负责生成中间代码：生成四元式voidCreatefbrchief(intnum,stringIenstr,stringch)vector<string>Strs=SeparatestrEX(Ienstr);vector<string>:iteratoriter=strs.begin();stringstr=,;Stringll=V;string12=);string13=",”；if(num=l)(string10="=h;stringarg1=*iter;str=ll+10+13+arg1+13+"J,+13+ch+12;)if(num=2)(stringop=*iter;stringarg1=*(iter+1);str=l1+op+13+argl+13+J,+13+ch+12;)if(num=3)(stringarg1=*iter;stringop=*(iter+l);stringarg2=*(iter+2);if(argl='()(string10=m=h;str=ll+10+13+op+13+,J'+13+ch+12;)else(str=l1+op+13+argl+13+arg2+13+ch+12;)fors.push_back(str);)输出四元式voidprintForsInfb()(PrintlnfO("中间代码四元式为")；vector<string>:iteratorit=fors.begin();for(it;it<fors.end();it+)(cout<<*it<<endl;)7软件调试在整个编译器设计过程中，遇到了很多意想不到的困难，其主要原因是对各个局部要实现的功能考虑不够周全。通过反复查找资料，以及向同学请教，才得以完成。在布尔表达式翻译器的设计过程中，在语法分析器设计过程中，程序相当复杂，需要利用到大量的编译原理，以及数据结构中的相关算法。其中在分析表的构造时遇到了非常大的困难，对输入字符串的移进和归约冲突得不到很好的处理，造成了调试的困难。经过我的努力，通过屡次调试，最终构造出来分析表并调试成功。在调试的过程中，出现了如下的问题：因为函数较多，所以在编程的过程中，屡次将函数名写错。因为在分析和翻译的过程中，关系较为复杂，所以屡次搞混关系。 ACTIoN表计算错误。 进栈和出栈的元素关系弄错了。当然，错误不止这些，但从这次课设，我觉得自己在某些方面仍有所欠缺，从现在开始，我会继续呢里，在今后的学习中，必须多编写程序，使逻辑思维和动手能力有所提高，努力学好编程。8软件的测试方法和结果 输入字符串为：iropi# 输入字符串为：trueorfalseand(iropi)#如果有疑问请联系QQ：1968872434(漫画小生)源码下载地址：。漫画小生的个人主页：。谢谢大家来访。9有关技术的讨论总的来说本次课设根本上实现了相应的功能，但仍存在一定的问题，需要进一步的思考，由于时间限制和本人能力这方面，做的不是很完美，没有实现程序自动的求解FRlST集和FOLLOW集，在输出预测分析表的时候没有把对应的非终结符列输入进去，那样的话预测分析表会更加的直观和美观，此局部功能还有待改良。如果以后能把此次课设程序的输出用MFC界面做出来就更好了。10收获与体会编译原理是计算机专业的一门重要课程，正如教材第一章的引论所述，“编译程序是现代计算机系统的根本组成局部之一”。”一个编译程序就是一个语言翻译程序，语言翻译程序把一种语言(源语言)书写的程序翻译成另一种语言(目标语言)的等价程序。通过这一学期的学习，我觉得编译原理是一门理论性很强的课程，从文法和语言的概念到LL(I)文法和LR(O)文法的分析，几乎都是对具体问题的抽象。因而，我们需要更多的时间来理解、掌握相关的知识，当然在这一过程中也存在很多问题，比方我们后期学习具体文法的分析方法时，对于文法的概念不够清晰，影响了上课的效率，知道老师再次给我们讲解了文法等根底的知识点，我们才慢慢掌握后面所学的LL（I）文法等，也发现了知识点之间的关联。我觉得，对计算机语言世界的知识积累，像滚雪球一样越滚越大。这个逐渐递进，逐渐解决问题的过程对我来说是收获很大的。整个过程好似踏着前人研究编译理论的路线，不断感觉他们遇到的问题，更重要的是他们解决问题的思路。只有专注于本质，才能有所进步。11参考文献1编译原理（第二版）吕映芝、张素琴、蒋维杜清华大学出版社2程序设计语言编译原理（第3版）主编：陈火旺、刘春林等国防工业出版社3编译原理与技术（第二版）主编：陈意云中国科学技术大学出版社本科生课程设计成绩评定表班级：软件1102姓名：李帅奇学号:序号评分工程总分值实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的标准性106设计验收10总得分/等级评语:注：最终成绩以五级分制记。优90-100分）、良（80-89分）、中（70-79分）、及格160-69分）、60分以下为不及格指导教师签名：2023年1月日