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

学号：课程设计题目WHILE循环语句的翻译程序设计（递归下降法、输出四元式）学院计算机科学与技术专业计算机科学与技术班级计算机班姓名指导教师2012年1月6日武汉理工大学《编译原理》课程设计说明书1目录1．问题描述......................................................31.1问题描述.............................................................31.2主要任务.............................................................31.3测试数据.............................................................32文法及属性文法的描述...........................................32.1文法的描述...........................................................32.2while-do循环语句的文法..............................................42.3递归文法的优化.......................................................42.4属性文法的描述.......................................................53．语法分析方法描述..............................................63.1程序设计对文法的要求.................................................63.2语法分析的思想.......................................................73.3递归下降文法实现原理.................................................73.4中间代码形式.........................................................84简要的分析与概要设计...........................................84．1全局程序的概要设计..................................................84.2词法分析.............................................................94.3递归下降翻译器的设计.................................................94.4语法制导翻译........................................................105详细的算法描述................................................105.1算法描述............................................................105.2运行结果............................................................146.研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）.156.1研制过程............................................................156.2本设计的评价、特点..................................................166.3感受和体会..........................................................166.4对程序改进的想法....................................................17武汉理工大学《编译原理》课程设计说明书2课程设计任务书学生姓名：专业班级：计算机班指导教师：工作单位：计算机科学与技术学院题目:WHILE循环语句的翻译程序设计（递归下降法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）写出符合给定的语法分析方法的文法及属性文法。（2）完成题目要求的中间代码四元式的描述。（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1系统描述（问题域描述）；2文法及属性文法的描述；3语法分析方法描述及语法分析表设计；4按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5编译系统的概要设计；6详细的算法描述（流程图或伪代码）；7软件的测试方法和测试结果；8研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名：2012年1月6日系主任（或责任教师）签名：2012年1月6日武汉理工大学《编译原理》课程设计说明书3课程设计报告书1．问题描述1.1问题描述设计一个WHILE〈布尔表达式〉DO〈赋值语句〉循环语句的词法﹑语法及语义分析程序，语法分析选择递归下降法，采用用语法制导翻译输出中间代码四元式。1.2主要任务通过设计、编制、调试一个WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。首先写出一个能识别while循环语句的文法，通过消除左递归使它符合LL(1)即递归下降法的要求，然后按照这个文法编写一个集词法分析，语法分析和语义分析为一体的程序，该程序首先可以检查输入语句是否符合词法要求，若符合则继续识别输入的语句是否符合while语句的文法，若符合则进行语义分析，输出用四地址代码表示的中间代码。1.3测试数据编写好源代码后，进行调试，主要调试数据有：新建一个文本，输入一个while循环语句的内容，保存；打开该文件，进行词法、语法的分析，给出分析结果。2文法及属性文法的描述2.1文法的描述用扩充巴科斯-瑙尔范式（EBNF）给出的while循环语句的文法描述，如下：while语句::=while(条件语句)do{赋值语句}条件语句::=表达式条件运算符表达式条件运算符::=||=|=|=武汉理工大学《编译原理》课程设计说明书4表达式::=表达式+表达式2|表达式-表达式2|表达式2表达式2::=表达式2*表达式3|表达式2/表达式3|表达式3表达式3::=(表达式)|标识符|数字赋值语句::=标识符=表达式；2.2while-do循环语句的文法产生式为S-whileEdoA，为便于语法制导翻译将其改写如下：文法G(s)如下：S--WEDG（意思是whileEdoG）G--c=RR--dTe|dT--+|-|*|/E--aFbF--|==|2.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因为此while循环语句的翻译程序设计用的是递归下降法，而递归下降法对文法的要求是文法要满足是LL（1）文法，故文法中不能包含左递归，对上述的文法进行消除左递归之后，得到如下的递归文法:1.S-while(A)do{B}2.A-CDC武汉理工大学《编译原理》课程设计说明书53.D-|=||=|=4.C-EG5.G-+EG|-EG|ε6.E-FH7.H-*FH|/FH|ε8.F-(C)|i|n9.B-i=C；2.4属性文法的描述(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':=''=')}C--EG{C.Place:=newtemp;Emit(C.Place':='E.PlaceG.place)}G-+EG{G.Place:=newtemp;武汉理工大学《编译原理》课程设计说明书6Emit(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．语法分析方法描述3.1程序设计对文法的要求递归下降法是一种比较简单直观，易于构造的语法分析方法。他要求文法满足LL（1）文法，他的设计思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的单词（或串），当某非终结符的产生式有多个候选时，能够按LL（