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

学 号： 课 程 设 计题 目 WHILE 循环语句的翻译程序设计（递归下降法、输出四元式）学 院 计算机科学与技术专 业 计算机科学与技术班 级 计算机班姓 名指导教师2012 年 1 月 6 日武汉理工大学《编译原理》课程设计说明书1目 录1．问题描述 ......................................................31.1 问题描述 .............................................................31.2 主要任务 .............................................................31.3 测试数据 .............................................................32文法及属性文法的描述 ............................................42.1 文法的描述 ...........................................................42.2 while-do 循环语句的文法 ..............................................42.3 递归文法的优化 .......................................................42.4 属性文法的描述 .......................................................53．语法分析方法描述 ..............................................63.1 程序设计对文法的要求 .................................................63.2 语法分析的思想 .......................................................73.3 递归下降文法实现原理 .................................................73.4 中间代码形式 .........................................................84简要的分析与概要设计 ............................................94．1 全局程序的概要设计 ..................................................94.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 () do{ }武汉理工大学《编译原理》课程设计说明书4::= ::= > | = | ::= + | - | ::= * | / | ::=() | |::==；2.2 while-do循环语句的文法产生式为 S-> while E do A，为便于语法制导翻译将其改写如下：文法 G(s)如下：SWEDG （意思是 while E do G）Gc=RRdTe|dT+|-|*|/EaFbF >|==| while (A) do {B}2.A -> CDC3.D -> > | = | = | C+E | C-E | E5.E -> E*F | E/F | E6.F -> (C) | i | n因为此 while 循环语句的翻译程序设计用的是递归下降法，而递归下降法对文法的要求是文法要满足是 LL（1）文法，故文法中不能包含左递归，对上述的文法进行消除左递归之后，得到如下的递归文法:武汉理工大学《编译原理》课程设计说明书51.S->while (A) do {B} 2.A->CDC3.D-> > | = | = | EG 5.G->+EG | -EG | ε 6.E->FH 7.H->*FH | / FH | ε8.F->(C) | i | n 9.B->i=C；2.4属性文法的描述(1)、任一非终结符 B 都不是左递归的，否则会产生死循环。

2)、对 A 的任意两个右部 βi , βj ,有：first(βi)∩first(βj)=φ， First(βi)表 βi 所能导出串的第一个符号的集合显然，每个 βi 的 first(βi)是互不相同的，否则则无法判断应执行哪个 ζ(βi )产生式 语义规则Swhile (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(‘goto Lnext’);）}ACDC {A.place:=newpemt;emit(A.place':='C1.place D.place C2.place)}.D > {D.place:=newtemp ;Emit(D.Place':=''>')}.D = {D.place:=newtemp ;Emit(D.Place':=''=')}.D >= {D.place:=newtemp ;武汉理工大学《编译原理》课程设计说明书6Emit(D.Place':=''>=')}.D EG {C.Place:=newtemp;Emit(C.Place':='E.Place G.place)}G->+EG {G.Place:=newtemp;Emit(G1.Place':=''+'E.Place G2.place)}G->-EG {G.Place:=newtemp;Emit(G1.Place':=''-'E.Place G2.place)}G->ε {G.Place:=newtemp;Emit(G.Place':='''}H->*FH {H.Place:=newtemp;Emit(H1.Place':=''*'F.Place H2.place)}H-> / FH {H.Place:=newtemp;Emit(H1.Place':=''+'F.Place H2.place)}H->ε {G.Place:=newtemp;Emit(H1.Place':=''+'E.Place H2.place)}F->(C) {F.Place:=C.Place}B。