WHILE循环语句的翻译程序设计(递归下降法-输出四元式)

武汉理工大学《数据结构》课内实践报告学号：0121210340314课内实践报告课程名称编译原理设计题目WHILE循环语句的翻译程序设计(递归下降法，输出四元式)学院计算机科学与技术专业班级计算机1203班姓名闵丹枫指导教师林泓2014年12月8日武汉理工大学《数据结构》课内实践报告武汉理工大学《数据结构》课内实践报告1课程设计任务书学生姓名：闵丹枫专业班级：计算机1203班指导教师：林泓工作单位：计算机科学与技术学院题目:WHILE循环语句的翻译程序设计（递归下降法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）写出符合给定的语法分析方法的文法及属性文法。（2）完成题目要求的中间代码四元式的描述。（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1系统描述（问题域描述）；2文法及属性文法的描述；3语法分析方法描述及语法分析表设计；4按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5编译系统的概要设计；6详细的算法描述（流程图或伪代码）；7软件的测试方法和测试结果；8研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名：2014年9月1日系主任（或责任教师）签名：2014年月日武汉理工大学《数据结构》课内实践报告2WHILE循环语句的翻译程序设计（递归下降法、输出四元式）一．系统描述1.1问题描述设计一个WHILE〈布尔表达式〉DO〈赋值语句〉循环语句的词法﹑语法及语义分析程序，语法分析选择递归下降法，采用用语法制导翻译输出中间代码四元式。1.2主要任务设计一个能识别while循环语句的文法，消除左递归，使文法符合LL(1)文法。利用递归下降法编写一个集词法分析，语法分析和语义分析为一体的程序。该程序首先可以检查输入语句是否符合词法要求，若符合则继续识别输入的语句是否符合while语句的文法，若符合则进行语义分析，输出用四地址代码表示的中间代码。二．文法及属性文法的描述2.1文法的描述扩充巴科斯-瑙尔范式（EBNF）：while语句::=while(条件语句)do{赋值语句}条件语句::=表达式条件运算符表达式表达式::=表达式+表达式2|表达式-表达式2|表达式2表达式2::=表达式2*表达式3|表达式2/表达式3|表达式3表达式3::=(表达式)|标识符|数字赋值语句::=标识符=表达式；根据以上写出来的While循环语句的文法表示如下：1.S-while(A)do{B}2.A-CDC3.D-|=||=|=4.C-C+E|C-E|E5.E-E*F|E/F|E6.F-(C)|i|n武汉理工大学《数据结构》课内实践报告3对以上文法消除左递归，最后得到的文法为：1.S-while(A)do{B}2.A-CDC3.D-|=||=|=4.C-EG5.G-+EG|-EG|ε6.E-FH7.H-*FH|/FH|ε8.F-(C)|i|n9.B-i=C；2.1属性文法的描述(1)任一非终结符B都不是左递归的，否则会产生死循环。(2)对A的任意两个右部βi,βj,有：first(βi)∩first(βj)=φ，First(βi)表βi所能导出串的第一个符号的集合。显然，每个βi的first(βi)是互不相同的，否则则无法判断应执行哪个ζ(βi)。产生式语义规则S--while(A)do{B}{S.first:=newtemp;S.second:=newtemp;A.true:=newtemp;emit（A.false:=S.second;S1.second:=S.first;S.place:=(S.begin,‘:’)||B.place||printf(S.true,‘:’)||S1.place||printf(‘goto’,S.begin)||printf(B.false,‘:’)||printf(‘gotoLnext’);）}A--CDC{A.place:=newpemt;emit(A.place':='C1.placeD.placeC2.place)}.D--{D.place:=newtemp;Emit(D.Place':=''')}.D--{D.place:=newtemp;Emit(D.Place':=''')}.D--={D.place:=newtemp;Emit(D.Place':=''=')}.D--={D.place:=newtemp;Emit(D.Place':=''=')}.D--={D.place:=newtemp;Emit(D.Place':=''=')}武汉理工大学《数据结构》课内实践报告4C--EG{C.Place:=newtemp;Emit(C.Place':='E.PlaceG.place)}G-+EG{G.Place:=newtemp;Emit(G1.Place':=''+'E.PlaceG2.place)}G--EG{G.Place:=newtemp;Emit(G1.Place':=''-'E.PlaceG2.place)}G-ε{G.Place:=newtemp;Emit(G.Place':='''}H-*FH{H.Place:=newtemp;Emit(H1.Place':=''*'F.PlaceH2.place)}H-/FH{H.Place:=newtemp;Emit(H1.Place':=''+'F.PlaceH2.place)}H-ε{G.Place:=newtemp;Emit(H1.Place':=''+'E.PlaceH2.place)}F-(C){F.Place:=C.Place}B-i=C;{p:=lookup(i.name)Ifp!=nilthenEmit(p':='C.PlaceElseerror)}三．语法分析方法描述3．1语法分析方法描述递归下降法是一种比较简单直观，易于构造的语法分析方法。他要求文法满足LL（1）文法，他的设计思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的单词（或串），当某非终结符的产生式有多个候选时，能够按LL（1）形式可唯一地确定选择某个候选进行推导。它的优点是简单直观，易于构造，很多编译系统所实现缺点是对文法要求很高，由于递归调用多，影响分析器的效率。递归下降程序是由一组子程序组成，每个子程序对应于一个非终结(S,A,B,C,D,E,F,G,H)。每个子程序处理相应句型中相对于此非终结符号的产生式。在定义文法时，是递归定义的，所以这些子程序也是递归的。当一个子程序调用另一个子程序时，原子程序顺序执行语句，即总是先执行被调用的子程序，然后再执行后继的程序。程序中9个子程序，其中S是开始符号，也是递归下降分析的入口，通过调用词法分析器进行单词分析，并通过word=l.Yufa_Queue.front()来得到当前所分析到的单词，然后在递归语法分析中根据这个单武汉理工大学《数据结构》课内实践报告5词分析下一步要执行的子程序。其中要注意的是，当子程序G()和H()中出现匹配的是空字符串时，不做单词处理，该所取得的单词，应该为下一个匹配产生做准备。3．2递归下降法实现的原理设A是一个非终结符：A→β1A→β2┊A→βn则写∈first(β1)thenζ(β1)elseifchar∈first(β2)thenζ(β2)else…ifchar∈first(βn)thenζ(βn)elseERROR其中ζ(βi)表示调用处理符号串βi的子程序。对A的任一右部i设为：βi=y1y2…yn则定义ζ(βi)beginζ(y1);ζ(y2);…;ζ(yn)end其中yj可分为下列两种情况（j=1,…,n):1)yj∈VT,则ζ(yj)ifchar≠yjthenERRORelseREAD(char)2)yj∈VN,则ζ(yj)表示调用关于yj的递归子程序。四．中间代码形式的描述及中间代码序列的结构设计4.1四元式形式中间代码为四元式，按照要求，要输出四元式一个四元式是一个带有四个域的记录结构，这四个域分别称为op﹑arg1﹑arg2及result。域op包含一个代表运算符的内部码。语句whileabdoa=a+b的四元式输出:1(,a,b,3)2(j,_,_,6)3(+,a,b,n)4(=,n,_,a)5(j,_,_,1)6武汉理工大学《数据结构》课内实践报告6五．编译系统的概要设计5.1全局程序的概要设计递归下降分析技术就是通过对每个非终结符编写一个子程序来实现它的操作，然后通过递归的调用来实现对输入字符串的分析，这其中还包括对输入字符串的词法分析。在词法分析的时，得到的字符单词要和关键字比较，看是否是关键字，根据比较结果进行返回相应的单词类型。单词类型主要包括界限符，关键字，常量，标识符，运算符等，每种符号都是一种类型。在语法分析程序中，根据词法得到的结果，进行判断是否是当前需要的单词类型，如果不是就说明输入字符串不能由该文法推导出来；如果是当前需要的类型，就相应得做该单词类型分支程序。根据文法可以得到这个递归下降程序可以分析while语句，在文法的开始符号S开始进行递归调用，因此这个文法的递归中就要考虑到调用以及递归。在递归子程序中，在嵌套调用其他子程序时都是有一定条件的，当满足这个条件的时候该程序可以按照满足的条件执行下去，当没有满足程序中的条件时就会显示语法错误。5.2词法分析词法分析程序的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号的中间程序。词法分析检查的错误主要是挑出源程序中出现的非法符号。所谓非法符号是指不是程序设计语言中允许出现的符号，就像自然语句中的错字。5.3递归下降翻译器的设计对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数，函数的返回值为A的综合属性，A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号，非3：终结符和语义动作分别做以下工作。1.对于带有综合属性x的终结符X，把x的值存入为X，x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。2.对于每个非终结符号B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,…，bk)3.对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对应属性的每一次引用。5.4语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语武汉理工大学《数据结构》课内实践报告7义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。