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

1、武汉理工大学数据结构课内实践报告 学 号： 0121210340314 课内实践报告 课程名称 编译原理 WHILE 循环语句的翻译程序设计 设计题目 （递归下降法，输出四元式） 学院 计算机科学与技术 专业班级 计算机1203班 姓名 闵丹枫 指导教师 林泓 2014年 12月 8 日 武汉理工大学数据结构课内实践报告 武汉理工大学数据结构课内实践报告 课程设计任务书 学生姓名：闵丹枫专业班级：计算机1203班 指导教师： 林 泓工作单位：计算机科学与技术学院 题目：WHILE循环语句的翻译程序设计（递归下降法、输出四元式） 初始条件： 理论：学完编译课程，掌握一种计算机高级语言的使用。 实

2、践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设 计。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） （1）写出符合给定的语法分析方法的文法及属性文法。 （2）完成题目要求的中间代码四元式的描述。 （3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。 （4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 （5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括： 1系统描述（问题域描述）； 2文法及属性文法的描述； 3语法分析方法描述及语法分析表设计； 4按给定的题目给出中间代码形式的描述及中间

3、代码序列的结构设计； 5编译系统的概要设计； 6详细的算法描述（流程图或伪代码）； 7软件的测试方法和测试结果； 8研制报告（研制过程，本设计的评价、特点、不足、收获与体会等） 9参考文献（按公开发表的规范书写）。 时间安排： 设计安排一周：周1、周2:完成系统分析及设计。 周3、周4:完成程序调试及测试。 周5:撰写课程设计报告。 设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。 设计报告书收取时间：设计周的次周星期一上午 10点。 21 指导教师签名: 2014年9月1日 系主任（或责任教师）签名: 2014 WHILE循环语句的翻译程序设计（递归下降法、输出四元式） 一.系

4、统描述 1.1问题描述 设计一个WHILB布尔表达式DO赋值语句循环语句的词法、语法及语义分析程序， 语法分析选择递归下降法，采用用语法制导翻译输出中间代码四元式。 1.2主要任务 设计一个能识别while循环语句的文法，消除左递归，使文法符合LL（1）文法。利用递归 下降法编写一个集词法分析，语法分析和语义分析为一体的程序。该程序首先可以检查输入 语句是否符合词法要求，若符合则继续识别输入的语句是否符合while语句的文法，若符合 则进行语义分析，输出用四地址代码表示的中间代码。 文法及属性文法的描述 2.1文法的描述 扩充巴科斯-瑙尔范式（EBNF : vwhile语句 :=while （

5、）do := := + | - | := * | / | :=（）| | :=; 根据以上写出来的While循环语句的文法表示如下： 1. S - while （A） do B 2. A - CDC 3. D - | = | = | C+E | C-E | E 5. E - E*F | E/F | E 6. F - （C） | i | n 对以上文法消除左递归，最后得到的文法为: 1. S-while (A) do B 2. A-CDC 3. D- | = | =| EG 5. G-+EG | -EG | 2.1属性文法的描述 (1)任一非终结符B都不是左递归的，否则会产生死循环。 对 A 的

6、任意两个右部 B i , B j ,有：first( B i) A first( B j)= , First( B i)表 B i所能导出串的第一个符号的集合。显然，每个B i的first( B i)是互不相同的，否则则无 法判断应执行哪个Z ( B i ) 产生式 语义规则 S-while (A) do B S.first:=n ewtemp; S.sec ond:=n ewtemp; A.true:=newtemp; emit (A.false:=S.second; S1.sec on d:=S.first; S.place:=(S.begin, ： ) | B.place |printf

7、(S.true, :) |S1.place | printf(goto ,S.begin) | printf(B.false, :) | printf( goto Ln ext );) A-CDC 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 ; Emit(D.Place:=) .D- = D.place:=newtem

8、p ; Emit(D.Place:=EG C.PIace:=n ewtemp; Emit(C.PIace:=E.PIace 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:=n ewtemp; Emit(H1.Place:=*F.Place H2.place) H- / FH H.Place:=n

9、ewtemp; 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-i=C; p:=lookup(i .n ame) If p!=nil the n Emit(p:=C.Place Else error) 三.语法分析方法描述 3. 1语法分析方法描述 递归下降法是一种比较简单直观，易于构造的语法分析方法。他要求文法满足LL( 1) 文法，他的设计思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别 由该非

10、终结符推出的单词(或串)，当某非终结符的产生式有多个候选时，能够按 LL( 1)形 式可唯一地确定选择某个候选进行推导。 它的优点是简单直观，易于构造，很多编译系统所实现 缺点是对文法要求很高，由于递归调用多，影响分析器的效率。 递归下降程序是由一组子程序组成，每个子程序对应于一个非终结(S,A,B,C,D,E,F,G,H) 每个子程序处理相应句型中相对于此非终结符号的产生式。在定义文法时，是递归定义的， 所以这些子程序也是递归的。当一个子程序调用另一个子程序时，原子程序顺序执行语句， 即总是先执行被调用的子程序，然后再执行后继的程序。程序中9个子程序，其中S是开始 符号，也是递归下降分析的入

11、口，通过调用词法分析器进行单词分析，并通过 word=I.Yufa_Queue.fro nt()来得到当前所分析到的单词，然后在递归语法分析中根据这个单 词分析下一步要执行的子程序。其中要注意的是，当子程序G()和H()中出现匹配的是空字符 串时，不做单词处理，该所取得的单词，应该为下一个匹配产生做准备。 3. 2递归下降法实现的原理 设A是一个非终结符：1 AB2 Apn 则写 Z (A) if char first( p 1 then Z ( P 1 ) else if char first( p 2tl)en Z ( P 2 ) else if char first( p n ) the

12、n Z ( P n) else ERROR 其中Z ( P i)表示调用处理符号串p i的子程序。 对A的任一右部i设为：p i = y1 y2 yn 则定义 Z ( p i) begin Z (y1); Z (y2);Z (yn) end 其中yj可分为下列两种情况(j=1,n): 1) yj VT,则 Z ( yj) if char 工 yj then ERROR else READ(char) 2) yj VN,则Z (yj)表示调用关于yj的递归子程序。 四中间代码形式的描述及中间代码序列的结构设计 4.1四元式形式 中间代码为四元式，按照要求，要输出四元式一个四元式是一个带有四个域的

13、记录结 构，这四个域分别称为op、arg1、arg2及result。域op包含一个代表运算符的内部码。语 句while ab do a=a+b 的四元式输出： 1 ( aFb 做 Do_G G- c=R dHngiil) 对赋值语句进行四元式输出: v 七. 软件的测试方法和测试结果 输入 while （ ab） z=x+y; 测试结果如下： F:VC2013whileDe bugw/hilE.exw 请输入赋值表达式: 输入while语句为:whileb 四元去 C ign 赋值语句； b)z=x+y*c;测试结果如下 i3F:VC2013whileDebijgwhi le.exe 诸输入赋

14、值表达式; 输入的Mliile语句为 | whilb 四元孟. （、亠曰尸 b -zsigrn、 赋值语口 Ex+yc I 弄 y c C+ x A B） 请按任意犍继稣 输入wh(ab)z=y;结果为: F:VC2013whileDebtigwhile.exe wlib语 y e S1111键 bSK罡 芝入元11按 目uh输四LJh请 误* 输入 while(ab)z=z+y结果为: 八. 研制报告(研制过程，本设计的评价、特点、不足、收获 与体会等) 8.1研制过程 在做本次实验之前我对 LL(1)文法的构成，递归下降原理不是很了解，在查阅了相关 资料后,对此有了深入了解。将词法分析，语

15、法分析，中间语言翻译结合到一起。 8.2设计的评价、特点、不足 设计的程序基本上实现了用递归下降分析法实现了 while语句的翻译，并能够用四元 式将其输出，使人一目了然。程序还能够准确提示词法和语法错误。 同时程序运行时简单 明了，易于使用。 8.3收获和体会 深入了解计算机语言编译和运行的过程，对编译原理有了深刻的认识，掌握了递归下降 法，熟练地使用四元式中间代码，明白了对于编写程序，解题的思路为重要。在编写程序之 前，如果没有比较清晰的思路，根本不可能编出好的程序。就算马马虎虎的编出来，程序的 逻辑性、健壮性、完善性、合理性也不会很强。在编程之前，我们应反复研究题目要求，对 题目涉及的情况进行比较充分的分析，以便编写出更加符合题意的程序；其次要充分考虑各 种临界情况，对一些错误的输入进行处理。因此在我们编程序之前一定要做好充分的准备， 首先要理清自己的思路，然后再将思路分划成几个模块，逐块的写好算法，最后再将所有的 模块有机的联系起来，组成一个完整的程序。在成功通过编译的情况下，对程序运行的结果 进行系统的分析，检验其正确性，如果有错误，应立即去分析源程序的逻辑错误，直到得到 正确的结果。 九. 参考文献 编译原理第2版清华大学出版社张素