DO-WHILE循环语句的翻译程序设计（LR方法、输出四元式）.doc

武汉理工大学编译原理课程设计学 号： 0120910340422课 程 设 计题 目DO-WHILE循环语句的翻译程序设计（LR方法、输出四元式）学 院计算机科学与技术专 业计算机科学与技术班 级0904班姓 名曾雷指导教师林泓2012年1月5日课程设计任务书学生姓名： 曾雷 专业班级： 计算机0904班 指导教师： 林泓 工作单位：计算机科学与技术学院 题目: DO-WHILE循环语句的翻译程序设计（LR方法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码四元式的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 20 年 月 日系主任（或责任教师）签名： 20 年 月 日1、系统描述通过设计、编制、调试一个DO-WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。用语法制导完成语义分析，并将形成的中间代码以四元式的形式输出。2 、文法及属性文法的描述21 文法的描述该文法的产生式如下所示：(1)Z-doEwhile(T)(2)E-AE (3)E-A (4)A-iopA (5)A-i (6)T-iop1i 其中do、while、( 、) 、 、 、op、op1、 ； 和i均为终结符，而Z、A、T、E这些大写字母均为非终结符。op1表示比较运算符，op表示算术运算符，i表示合法标识符。22 属性文法的描述对该文法的属性文法描述如下：(1) Z-doEwhile(T) prinf( E if T goto E else goto next)(2) E-AE print(E.val = A.valE.val) (3) E-A print(E.val = A.val)(4) A-i op A print(A.Val= i.Val op A.Val) (5) A-i； print(A.Val = i.Val;.Val) (6) T-i op1 i print(T .Val= i1.Val op1 i2.Val)3 、语法分析方法描述及语法分析表设计31 语法分析表设计311 文法的DFAI0:S-ZZ-doEwhile(T)Aiop1i)T(whileAE;iiopiAiEdoZI1:S-ZI2:Z-doEwhile(T)I3:Z- doEwhile(T)E-AEE-AE-AA-iopAI5:E-AEE-AEE-AE-AA-iopAA-i;I8:E-AEI6:A-iopAA-i;I9:A-iopAA-iopAI12:A-iopAI10:A-i;I4:Z- doEwhile(T)I7:Z- doEwhile(T)I11:Z- doEwhile(T)I13:Z- doEwhile(T)T-iop1iI15:T-iop1iI18:T-iop1iI14:Z- doEwhile(T)I16:Z- doEwhile(T)I17:T-iop1i312 LR（0）分析表状态 ACTION GOTOdowhile（）iopop1;#ZEAT 0s21 1acc 2s3 3s645 4s7 5r3s6r385 6s9s10 7s11 8r2s2 9s612 10r5r5r5 11s13 12r4r4r414 13s1514 14s16 15s17 16r1 17s18 18r6312 LR（0）分析方法描述说明LR分析法的规约过程是规范推到的逆过程，所以LR分析过程是一种规范规约的过程。其分析过程为：由文法构造出该文法项目集，再根据项目集构造该文法的DFA，再判断是否有移进-规约和规约-规约冲突，若没有冲突则该文法为LR(0)的，若有冲突则该文法是SLR（1）的，最后可以构造出LR(0)分析表。然后根据LR(0)分析表进行语法分析，分析过程就是进栈和规约的过程。若能规约出开始符S，则语法正确。反之，语法错误。4 、中间代码形式的描述及中间代码序列的结构设计本系统中所采用的中间代码形式是四元式，是一种比较普遍采用的形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG2及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a：=b*c+b*d的四元式表示如下：1）（*，b，c，t1）2）（*，b，d，t2）3）（+，t1，t2，t3）4）（：=，t3，-，a）四元式对中间结果的引用必须通过给定的名字，也就是说，四元式的联系是通过临时变量实现的。本程序中所用到的四元式语句如下：1)形如（op，arg1，arg2，result）的赋值语句2)形如（jrop，B，C，L）的条件转移语句3)形如（=，arg1，-，result）的复写语句5、编译系统的概要设计5.1 词法分析词法分析程序要做的工作是：从源程序的第一个字符开始，顺序读字符，一次读一个，根据所读进的字符识别各类单词，同时去掉源程序中的空白和注释。词法分析检查的错误主要是挑出源程序中出现的非法符号。所谓非法符号是指不是程序设计语言中允许出现的符号，就像自然语句中的错字。结束符“#”界限符开始到输入流中读下一字符CharChar是什么？初始化标识符和关键字词法分析子程序字母数字运算符无符号数词法分析子程序运算符词法分析子程序界限符词法分析子程序结束流程图如下：5.2 语法分析语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。流程图如下：输入串#cic1Sp#XiSi总 控 程 序输出ACTION表GOTO表栈结束其中SP为栈顶指针，Si为状态栈，Xi为文法符号栈。状态转换表内容按关系GOTOSi,X=Sj确定，改关系式是指当前栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。X为终结符或非终结符。ACTIONSi,a规定了栈顶状态为Sj时遇到输入符号ci应该执行的动作。动作有以下四种可能：（1） 移进：当Sj=GOTOSi，a成立，则把Sj移入到文法符号栈。其中i，j表示状态号。（2） 规约：当在栈顶形成句柄为b时，则用b归约为相应的非终结符A，即当文法中有A-b的产生式，而b的长度为r，则从状态栈和文法符号栈中自栈顶向下去掉r个符号。并把A移入文法符号栈内，再把满足Sj=GOTOSi，A的状态移进状态栈，其中Si为修改指针后的栈顶状态。（3） 接受acc：当归约到文法符号栈中只剩下文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则为分析成功。（4） 报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该分发能接受的句子。5.3 语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。6、 详细的算法描述程序的核心算法LR（）void LR() int Tai50,len=1;/Tai50为状态号 int i,j,k,l,m,tmp_n=0,num=0; int X; char temp; char fuhaoN=#;/N=50，fuhao为符号 num=strlen(shuru);/输入字符串的长度 Tai0=0;cout状态 符号 输入串 endl; for(i=0;inum;)j=Tailen-1;temp=shurui;/temp为输入流的逐个符号switch(temp)case +:case -:case *:case /:case =:case %: temp=P; break;case : temp=T; break;if(temp!=P&temp!=T&temp!=d&temp!=w)if(temp=0&temp=a&temp=A&temp=Z)/将数字，字母总结为itemp=i;switch(temp) case d: k=0; break; case : k=1; break; case : k=2; break; case w: k=3; break; case (: k=4; break; case ): k=5; break;case i: k=6; break;case P: k=7; break;case T: k=8; break;case ;: k=9; break; case #: k=10; break; if(actionj.act_0k=s) Tailen+=actionj.act_1k; tmp_n=strlen(fuhao)-1; fuhao+tmp_n=shurui+; for(l=0;llen;l+)coutTail;/输出状态号 coutsetw(20)fuhao;/输出符号 coutsetw(3) ; for(l=i;lnum-1;l+)/输出输入串coutshurul; coutendl; else if(actionj.act_0k=r) X=strlen(WENactionj.act_1k)-1;/int X len-=X; for(m=len;mlen+X;m+) fuhaom=0; fuhaolen=WENactionj.act_1k0;/符号代替 switch(WENactionj.act_1k0) case Z: l=0; break; case E: l=1; break; case T: l=2; break; case A: l=3; break; len+=1; Tailen-1=actionTailen-2.gol;/到goto表中寻找，状态号代替 for(l=0;llen;l+) printf(%d,Tail);/coutTail; coutsetw(20)fuhao; cout ; for(l=i;lnum-1;l+) coutshurul; coutendl; else if(actionj.act_0k=A) cout 正确接受!n; cout-n; cout 输出四元式：！n;cout-n; return;/exit(0);else cout 出错！endl; cout-n; cout 按键退出！endl;cout-n; getch(); exit(0); 7、软件的测试方法和测试结果7.1运行正确时的情况如下：7.2从txt文件中取出do-while程序段：7.3语法分析的过程：7.4输出四元式：8、研制报告 通过本次的编译原理的课程设计，我对LR分析法有了更深入的了解，对于大多数用无二义性的上下文无关文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、即使地指出出错的位置。但是它有一个很明显的缺点：对于一个实用的高级语言程序，文法的分析器的构造工作量是相当大的。本次课程设计，我就仅仅只是用了一个简单的直接文法来构造分析表实现“do-WHILE循环语句的翻译程序设计”，因此，有许多的不足之处，希望老师见谅。 此外，在课程设计的过程中我又复习了一些C+编程的知识点，如文件的读取和存储，以及一些头文件里的函数的运用。 总结下来，此次课程设计使我获益匪浅，我既巩固了所学的编译原理的知识又巩固了自己C+的知识，除此之外还提高了自己的编程能力。我还在实践中点点滴滴的提升了自己的逻辑分析和编程以及调试程序的能力。9、参考文献教材：1张素琴、吕映芝、蒋维杜、戴桂兰等编译原理（第二版）清华大学出版社2005年2月参考书：1何炎祥编译原理（第二版）华中科技大学出版社2005年8月2胡伦骏编译原理