《编译原理》课程设计说明书-DO-WHILE循环语句的翻译程序设计(LR方法、输出三地址表示).doc

*理工大学编译原理课程设计说明书DO-WHILE循环语句的翻译程序设计（LR方法、输出三地址表示）1.系统描述1.1设计目的通过设计、编制、调试一个DO-WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。1.2设计内容及步骤对循环语句： DO赋值语句WHILE 表达式按给定的题目写出符合自身语法分析方法要求的文法和属性文法描述。(1)按给定的题目给出语法分析方法的思想及分析表设计。(2)按给定的题目给出中间代码序列的结构设计。(3)完成相应的词法分析、语法分析和语义分析程序设计。(4)编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。2文法的描述本程序所用的文法如下：GS:(1)S->doE;while(B)if B.true goto B.true else goto B.false;(2)B->I1 rop I2B.type=bool;B.val=I1.val rop I2.val;(3)E->I1=I2 op I3I1.val=I2.val op I3.val;(4)I->idI.val=id.val;注意：rop is < or >，op is +,-,*,/, id is any number or identifier由上可知，非终结符B表示布尔表达式，E表示赋值表达式3.语法分析方法描述及语法分析表设计3.1语法分析方法描述本实验采用LR分析方法对DO-WHILE语句进行语法分析。LR分析法是一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K>=0）符号就能惟一的确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能惟一的确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范过程。一个LR分析器由3个部分组成：总控程序，也可以称为驱动程序。对所有的LR分析器，总控程序是相同的。分析表或分析函数。不同的方法分析表将不同，同一个方法采用的LR分析器不同时，分析表也不同，分析表表又可以分为动作（ACTION）表和状态转换（GOTO）表两个部分，它们都可以用二维数组表示。分析栈，包括文法符号栈和相应的状态栈。它们均是先进后出栈。分析器的动作由栈顶状态和当前输入符号所决定。LR分析器工作过程示意图如图所示：输入串XXX#总控程序ACTION表GOTO表Sn.S1S0Xn.X1#SP输出其中SP为栈顶指针，Si为状态栈，Xi为文法符号栈。状态转换表内容按关系GOTOSi,X=Sj确定，改关系式是指当前栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。X为终结符或非终结符。ACTIONSi,a规定了栈顶状态为Sj时遇到输入符号ci应该执行的动作。动作有以下四种可能：移进：当Sj=GOTOSi，a成立，则把Sj移入到文法符号栈。其中i，j表示状态号。规约：当在栈顶形成句柄为b时，则用b归约为相应的非终结符A，即当文法中有A->b的产生式，而b的长度为r，则从状态栈和文法符号栈中自栈顶向下去掉r个符号。并把A移入文法符号栈内，再把满足Sj=GOTOSi，A的状态移进状态栈，其中Si为修改指针后的栈顶状态。接受acc：当归约到文法符号栈中只剩下文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则为分析成功。报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该分发能接受的句子。3.2语法分析表设计3.2.1构造文法的DFAI0:S->.SS->.doE;while(B)I1:S->S.I2:S->do.E;while(B)I3:S->do.E;while(B) E->.I= I op I I->.idI4:S->doE.;while(B)I5:E->I . =I op II6:I->id.I7:S->doE;.while(B)I8:E->I=.I op I I->.idI9:S->doE;.while(B)I10:E->I = I. op II11:S->doE;while.(B)I12:E->I=I op .II=.idI13:S->doE;while(.B)B->.I rop II->.idI14:E->I=I op I.I15:S->doE;while(B.)I16:B->I .rop II17:S->doE;while(B).I18:B->I rop .II19:B->IropI.I1I0I19I4I13I9I14I15I12I6I10I8I2I7I16I11I5I3I17I183.2.2然后写出LR分析表：状态ACTIONGOTODo=;While()RopOpId#SBEI0S211acc2S33S6454S75S86R4R4R4R4R4R4R4R4R4R4R4R47S98S6109S1110S1211S1312S1413S6151614R3R3R3R3R3R3R3R3R3R3R3R315S1716S1817R1R1R1R1R1R1R1R1R1R1R1R118S61919R2R2R2R2R2R2R2R2R2R2R2R24.中间代码形式的描述及中间代码序列的结构设计4.1中间代码形式的描述在本程序中作用三地址码表示中间代码三地址码的表达形式为：标号结果：=操作数1操作符操作数2常见三地址表示举例：赋值语句 t1 := a op b， a:= b条件转移 if true goto Label无条件转移 goto Label4.2中间代码序列的结构设计本程序用标号来表示程序的跳转过程，示例如下100 赋值语句101赋值语句102 条件跳转语句103 无条件转移语句5.编译系统的概要设计本编译程序的结构图如下：源程序(do-while 语句)词法分析(Lex函数)语法语义分析 （Analyze函数）代码生成程序程序输出说明：源程序（do-while语句）通过控制台输入。然后通过 Lex函数对输入的源程序进行分析后，将分析结果以二元组的方式输出到控制台。接下来通过调用语法语义分析函数来完成对分析得到的单词进行文法句子的识别，并用进行语法制导翻译，完成属性文法定义规定的相关语义动作。本编译程序最后完成的三地址码输出是通过中间文件间接输出到控制台上的。在执行Analyze函数的过程中，同时运用ofstream文件流将三地址码输出到一个ASCII码的txt类型文件中，最后从该文件中读出最终处理的三地址码输出至控制台。6.详细的算法描述（流程图或伪代码）6.1词法分析词法分析程序要做的工作是：从源程序的第一个字符开始，顺序读字符，一次读一个，根据所读进的字符识别各类单词，同时去掉源程序中的空白和注释。词法分析检查的错误主要是挑出源程序中出现的非法符号。下面为本程序中所用来进行词法分析的伪代码：输入字符；If(字符是字母)查找关键词表；If(是关键字do或者while)识别关键词;Else 判断为标识符；Else if(字符是数字)获取整个数;Else if(运算符)If(是算术运算符)识别算术运算符 ；Else 识别为关系运算符;Else 标识为其他类型以下附部分源码:int Lex(char InStr208,int InStrLen)/0关键字，1标识符2数字3界符4算符5其他char strsrcBUFFURSIZE,strdst8,ch;int strcount=0,strLength,i=0;cout<<"Please input the do-while statement:"<<endl;gets(strsrc);strLength=strlen(strsrc);cout<<endl<<" Lexical Analyse:"<<endl;while(strcount<strLength)while(strsrcstrcount=' ') strcount+; ch=strsrcstrcount;if(Alpha(ch) i=0; do strdsti+=strsrcstrcount+;while(Alpha(strsrcstrcount)|Digit(strsrcstrcount)&&(strcount<strLength); strdsti='0'if(!strcmp(strdst,"while")cout<<setw(10)<<"(0,"<<strdst<<")"<<endl;else cout<<setw(10)<<"(1,"<<strdst<<")"<<endl;for(int k=0;strdstk!='0'k+)InStrInStrLenk=strdstk;InStrInStrLen+k='0' else if(Digit(ch)i=0; do strdsti+=strsrcstrcount+;while(Digit(strsrcstrcount)&&(strcount<strLength); strdsti='0' cout<<setw(10)<<"(2,"<<strdst<<")"<<endl;for(int k=0;strdstk!='0'k+)InStrInStrLenk=strdstk;InStrInStrLen+k='0' else if(Oper(ch)i=0;strdsti=ch;strdsti+1='0'if(!strcmp(strdst,"")|!strcmp(strdst,"(")|!strcmp(strdst,")")|!strcmp(strdst,"")|!strcmp(strdst,"")cout<<setw(10)<<"(3,"<<ch<<")"<<endl;else cout<<setw(10)<<"(4,"<<ch<<")"<<endl;for(int k=0;strdstk!='0'k+)InStrInStrLenk=strdstk;InStrInStrLen+k='0'strcount+;elsecout<<setw(10)<<"(5,"<<ch<<")"<<endl;isillegal=1; cout<<"isillegal="<<isillegal<<endl; cout<<"not while statement "<<endl;break;strcount+;InStrInStrLen+0='#'cout<<"inputed string"<<endl; for(int j=0;j<InStrLen;j+)cout<<" "<<InStrj;cout<<"grammer analysis"<<'n'return InStrLen;6.2语法分析流程图如下，具本处理过程，请参见本文档3.1小节输入串XXX#总控程序ACTION表GOTO表Sn.S1S0Xn.X1#SP输出此处附上语法语义分析函数void Analyze(State state) int row=0,col=0,numchange=0;cout<<" Procedure"<<endl;cout.setf(ios:left);cout<<"step"<<" "<<setw(20)<<"STATESTACK"<<setw(20)<<"SYMBOLSTACK"<<setw(20)<<"INPUT"<<setw(8)<<"ACTION"<<setw(6)<<"GOTO"<<endl;strcpy(next,state.InStrstate.CurInstr);ropOrOp(next);row=state.stkStatestate.CurState;col=Index(next);numchange=tablerowcol;ofstream outfile("do_while.txt");while(strcmp(state.stkSymbolstate.CurSymbol,"S")!=0&&numchange!=20)if(numchange=0)isillegal=1;break;numchange=Action(state,numchange,outfile);if(isillegal=0)cout<<setw(4)<<step+<<" "state.showState();cout<<setw(8)<<"acc"<<endl;cout<<"processing semantic analysis"<<endl;system("PAUSE");关键的状态转移函数ACTION和GOTOint Action(State &state,int actionnum,ofstream &outfile) int row=0,col=0,numchange=0;int choice=0;int ct=100;int m=0;if(actionnum>=1&&actionnum<=18)choice=1;else choice =actionnum;switch(choice)case 0:isillegal=1; cout<<"isillegal="<<isillegal<<endl;break;case 1:/移进项目cout<<setw(4)<<step+<<" "state.showState();cout<<setw(8)<<actionnum<<endl;state.CurState+;state.stkStatestate.CurState=actionnum; state.CurSymbol+; strcpy(state.stkSymbolstate.CurSymbol,state.InStrstate.CurInstr);state.CurInstr+;strcpy(next,state.InStrstate.CurInstr);ropOrOp(next);row=state.stkStatestate.CurState;col=Index(next);numchange=tablerowcol;break;case 20:/接收cout<<setw(4)<<step+<<" "state.showState();cout<<setw(8)<<"acc"<<endl;break;case 21:/r1 S->while(B)E;cout<<setw(4)<<step+<<" "state.showState();cout<<setw(8)<<actionnum;for(int i=9;i>0;i-)state.stkStatestate.CurState-=0; for(i=9-1;i>=0;i-)strcpy(Bi,state.stkSymbolstate.CurSymbol);strcpy(state.stkSymbolstate.CurSymbol-,"");outfile<<"B.false: "<<'n'state.CurSymbol+;strcpy(state.stkSymbolstate.CurSymbol,"S"); /B->IropIstrcpy(next,state.stkSymbolstate.CurSymbol);ropOrOp(next);row=state.stkStatestate.CurState;col=Index(next);numchange=tablerowcol;numchange=Goto(state,numchange);break;case 22:/r2 B->IropIcnt=0;cout<<setw(4)<<step+<<" "state.showState();cout<<setw(8)<<actionnum;for(int i=3;i>0;i-)state.stkStatestate.CurState-=0; for(i=3-1;i>=0;i-)strcpy(Bi,state.stkSymbolstate.CurSymbol);strcpy(state.stkSymbolstate.CurSymbol-,"");outfile<<"102 t1:="<<I0<<B1<<I1<<endl;outfile<<"103 if t1.val=true"<<" goto 100"<<endl;outfile<<"104 goto 105"<<endl;state.CurSymbol+;strcpy(state.stkSymbolstate.CurSymbol,"B"); /归约B->IropIstrcpy(next,state.stkSymbolstate.CurSymbol);ropOrOp(next);row=state.stkStatestate.CurState;col=Index(next);numchange=tablerowcol;numchange=Goto(state,numchange);break;case 23:/r3 E->I=IopI cnt=0;cout<<setw(4)<<step+<<" "state.showState();cout<<setw(8)<<actionnum;for(int i=5;i>0;i-)state.stkStatestate.CurState-=0; for(i=5-1;i>=0;i-)strcpy(Ei,state.stkSymbolstate.CurSymbol);strcpy(state.stkSymbolstate.CurSymbol-,"");outfile<<"100 "<<"t1:="<<I1<<E3<<I2<<endl;outfile<<"101 "<<I0<<":=t1"<<endl;state.CurSymbol+;strcpy(state.stkSymbolstate.CurSymbol,"E"); strcpy(next,state.stkSymbolstate.CurSymbol);ropOrOp(next);row=state.stkStatestate.CurState;col=Index(next);numchange=tablerowcol;numchange=Goto(state,numchange);break;case 24:/r4归约 I->idcout<<setw(4)<<step+<<" "state.showState();cout<<setw(8)<<actionnum;state.stkStatestate.CurState-=0;strcpy(Icnt+,state.stkSymbolstate.CurSymbol);/I.value=id.valuestrcpy(state.stkSymbolstate.CurSymbol,"I"); /归约I->idstrcpy(next,state.stkSymbolstate.CurSymbol);ropOrOp(next);row=state.stkStatestate.CurState;col=Index(next);numchange=tablerowcol;numchange=Goto(state,numchange);break;return numchange;int Goto(State &state,int gotonum) int row=0,col=0,numchange=0;cout<<setw(6)<<gotonum<<endl;state.CurState+;state.stkStatestate.CurState=gotonum;strcpy(next,state.InStrstate.CurInstr);ropOrOp(next);row=state.stkStatestate.CurState;col=Index(next);return tablerowcol;7.软件的测试方法和测试结果(1)运行程序，显示如下程序界面(2)按照提示输入合法的do-while语句Doa=b+c;while(a<b)(3)按enter确定输入完毕，得到词法分析结果,显示如下：并且最后一行提示了经过词法分析后合法的待输入串在栈中的存储情况。(4)继续确定，可以看见输入的句子的按LR方法的详细处理过程。结果显示如下：由此可以看见在用LR方法识别d0-while句子的时候，状态栈，符号栈以及待输入串的详细变化情况。（说明, 其中21，22，23，24分别表示用第1、2、3、4个产生式进行归约。）(5)继续执行程序，最终出现语义分析结果8.研制报告8.1研制过程本次实验是对do-while语句运用LR分析法进行语法分析，分析的过程中要求运用属性文法和语法制导翻译的相关知识来有效完成对一个合法的do-while语的语义分析。做实验如果有一个比较详细的安排和计划，就会使实验进程井井有条。在实验之始，按照实验说明书的要求，对实验进行了模块划分。首先大致分为三个部分，包括词法分析，语法分析和语义分析。因为以前做过词法分析和语法分析的相关实验，所以这部分比较容易。于是精力大部分放在第三个部分语义分析上。首先，根据自己拟定文法，构造出正确的LR分析表，文法虽然只有四个产生式，但经过分析，却产生了多达20个状态。完成了LR分析，接着是确定给定文法的属性文法，以便在语法制导翻译中，根据所给的语义动作，有效完成三地址码的输出。确定了程序的基本结构和流程，接下来就是编制程序了。模块化的功能函数降低了编制程序的难度，经过不断修改和调试程序，终于成功完成了该实验。8.2设计评价本次实验设计能有效识别合法的do-while 语句。根据给定的文法,只要是形如 doE;while(B)的句子（其中E为赋值表达式，B为布尔表达式），都可以正确得出其LR分析的详细过程，并且做出有效的三地址输出。在本次实验中，对于数据结构有特殊的要求，需要用到具有先进后出性质的栈结构，但是为了方便本次实验的处理，采用一维数组来模拟栈结构。同时，将状态栈，符号栈，和待输入串放在一个类中，以便可以声明对象直接进行处理。虽然本次实验成功完成了对do-while语句的语法制导翻译过程，但是还是存在一些缺点。比如，在词法分析过程中，没有对错误的语句输入进行判断，因此只有输入正确的 do-while语句，才能完成程序执行。8.3心得与体会通过这次为期一周的实验，完成了对do-while语句的翻译过程。这次实验对这半年来所学习的编译原理的相关知识进行了有效应用，尤其是对比较抽象的词法分析，语法分析，语义分析，语法制导翻译等有了更深层次的理解。正因为理论联系实践，我才对编译原理这门课程有了更好的掌握。虽然实验成功了很有成就感，但也发现了自己的一些不足。比如对一些基础知识的理解还不够透彻，对所学的算法还不能够熟练应用。不管这次实验中有多少跌跌撞撞，但终归是受益匪浅。学习就是不断进步的过程，经过这次的课程设计，我的编程能力和逻辑分析能力得到了锻炼。9.参考文献1张素琴、吕映芝、蒋维杜、戴桂兰等编译原理（第二版）清华大学出版社2005年2月参考书：1何炎祥编译原理（第二版）华中科技大学出版社2005年8月2胡伦骏编译原理（第2版）电子工业出版社2005年2月3胡元义等编译原理实践教程西安电子科技大学出版社2002年1月4钱能著,C程序设计教程,北京：清华大学出版社，2002.7第 17 页 共 17 页