WHILE循环语句的翻译程序设计(递归下降法、输出三地址表示).docx

武汉理工大学编译原理课程设计课程设计任务书学生姓名： 赵旭林 专业班级： 计算机0801班 指导教师： 陈天煌 工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码三地址表示的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2010年 11月 13日系主任（或责任教师）签名： 2010年 11月 13日编译原理课程设计WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）1、系统要求及描述1.1 实验要求1目的通过设计、编制、调试一个WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。2设计内容及要求 对循环语句： WHILE表达式DO赋值语句（1） 按给定的题目写出符合自身语法分析方法要求的文法和属性文法描述。（2） 按给定的题目给出语法分析方法的思想及分析表设计。（3） 按给定的题目给出中间代码序列的结构设计。（4） 完成相应的词法分析、语法分析和语义分析程序设计。（5） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。1.2 递归下降法原理递归子程序法是一种确定的自顶向下的语法分析方法。它的主要原理是，对每个非终极符按其产生式结构构造相应语法分析子程序， 每个过程的功能是识别由该非终结符推出的串， 当某非终结符的产生式有多个候选项时， 能够按LL(1)的形式可唯一确定某个候选式进行推导。其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。缺点：对文法要求高，必须满足LL(1)文法， 如果某个产生式的推导不满足LL（1）而满足LL(2)时， 也可采用多向前扫描一个符号的办法。另一个缺点是： 由于递归调用过多， 所以速度慢，占用空间多。1.3 三地址码具体形式三地码形式如下： X:= y op z条件语句while(A) do B翻译成： Begin：1. if A goto 32. goto exit3. do B4. goto beginexit2、系统设计及说明2.1 系统设计及流程图2.1.1 文法设计while语句文法设计为：S - while (A) S | i=E;A - B op B | BOp - & | | B - E relop E relop - | = | E+E | E-E | E*E | E/E | (E) | i | n由于文法左递归， 而递归下降法的基本要求是文法必须是LL(1)文法，不能有左递归， 所以将文法消除左递归得：S - while (A) S | i=E;A - B | B op BOp - & | |B - E relop Erelop - = | | = | = | (E)F | iF | nFF - +EF | -EF | *EF | /EF | 2.1.2 属性文法设计产生式属性文法S - while (B) S1S.begin:=newlabel;S.next:=newlabel;B.true:=newlabel;B.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin, :) | B.code |gen(S.true, :) | S1.code | gen(goto,S.begin) | gen(B.false, :) | gen(goto Lnext);B - E1 relop E2B.place:=newlabel;B.code:=E1.code | relop.code |E2.code |gen(B.place := , E1.place , relop. place , E2.place);relop - relop.place:=newlabel;relop.code:=gen();E - (E1)FE.place:=newlabel;E.code:=E1.code | F.code |gen(E.place := ,(, E1.place , ), F.place);E - iFE.palce:=newlabel;E.code:=i.code | F.code | gen(E.palce := ,i.place , F.place);E - nFE.place:=newlabel;E.code:=n.code | F.code | gen(E.place := , n.place , F.place);F - +EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= + , E.place , F1.place);F - -EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= - , E.place , F1.place);F - *EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= * , E.place , F1.place);F - /EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= / , E.place , F1.place);F - F.place:=newlabel;F.code:=gen(F.code:= );2.1.3 系统流程图2.2 伪代码设计及分析 2.2.1 数据结构说明源文件为source.txt，词法分析结果存放在lex.txt，三地址码存放在syntax.txt中。每个文件都有相对应的输入输出流来实现文件中数据的读取与保存。结构体word用在词法分析中，用于保存单词的属性值和类型。KeyWord数组用于保存关键字，对应有一个函数iskeyword()判断是否是关键字。2.2.2 词法分析设计与实现 在程序中，词法分析的部分是直接用实验一的程序。但要注意的问题是，由于在做实验一的时候没有考虑到代码重用问题，所以整个程序显得比较凌乱，和课程设计要求不太符合，所以在重用代码的时候修改了一下，使之更加符合课程设计程序的整体要求。2.2.3 语法分析设计与实现由于递归下降法是一种自顶向下的语法分析方法，所以在判断给出的句子语法是否正确时是用文法的开始符号推导出句子，如果推导成功，那么给定的句子语法正确，如果不成功，那么说明有语法错误。每个非终结符的伪代码设计如下：1. S的子程序的伪代码：int S() 取单词；if (str是while关键字) 取下一次单词；if (str = ()调用非终结符A的子程序；取下一次单词；if (str = ) 调用A()的子程序；elsewhile后面应该有(, 返回; else if (str 是变量) 取单词； if (是=) 调用E()的子程序；取单词； if (不是;)出错，结尾应该是; 2. A的子程序伪代码：int A()调用B()的子程序；取单词；if(是&或者|) 代表用的推导式为：S - B op B;调用B()的子程序；;else if (后一个单词时变量或者是界符) 代表用的推导式为：S - B3. B的子程序伪代码：int B()调用E的子程序;取单词；if(是运算符) 调用E的子程序；else 出错返回；4. E的子程序伪代码：int E()取单词；if(是() 调用E的子程序； 取单词；if(是) 匹配，返回正确；else 括号不匹配，出错返回；else if (是变量) 用的推导式为：E - iF，调用F()子程序；else if (是数字) 用的推导式为：E - iF，调用F()子程序；else 出错处理；5. F子程序为伪代码：int F()取单词；if(是+) 用的推导式为：F - +EF; E(); F();else if (是-) 用的推导式为：F - -EF; E(); F();else if (是*) 用的推导式为：F - *EF; E(); F();else if (是/) 用的推导式为：F - /EF; E(); F();else if (是变量或者界符)用的推导式为：F - ;else 出错返回;2.2.4 语义分析设计与实现除了能正确地画出语法图并化简，求出FIRST,FOLLW集外，在实现过程中还要想方设法保证输出的产生式规则（三地址代码）严格按照自顶向下、从左至右的顺序进行，为了达到这一要求，需要在每次调用与某个语法变量相应的处理程序时，一进入过程就输出该规则（生成相应的三地址代码），而在有些情况下，为了正确地选择匹配的规则（生成相应的三地址代码）必须连续向前看若干的符号（token），这时应分析过的符号暂时用栈保存起来。3、调试过程及实验结果分析3.1 调试过程1. 要特别注意产生式F-，因为它代表的产生式不退出任何符号，所以不能像其他产生式一样直接判断。如果是得话 A - B | B op B2. 因为在lex文件中第一排是文字说明， 所以不能直接在getstr取出单词， 因此又定义了一个新的函数， 将单词取出放在一个新的文件_lex.txt中3. 注意每个子程序的返回值，如果正确返回1，出错返回0，而且在出错前应该提示错误的信息， 比如说刚开始匹配while后面的单词时，如果不是“）”， 应该提示“while 后面缺 “）”。”然后返回， 不能再继续处理后面的内容。3. 刚开始用文件流从文件中读取信息时候，发现再第一个文件流读取完文件并且关闭的时候，再次打开文件读取， 发现读取出来的数据为空。上网查阅资料发现，用文件输入流打开第一个文件，然后对文件内容处理，当结束使用该输入流时，流被设置了eof或者fail， eof为end of file(文件结束符)，fail为可恢复错误状态。例如：fin.open(file1);while(fin temp)/do some thing跳出循环，即是遇到输入错误或者文件结束符。此时流状态被设置为eofbit或者failbit。而fin.close()只关闭该流对文件的关联，并不清除错误状态，而必须使用fin.clear()清楚流里面的结束或者错误状态。3.2 实验结果在调试完程序之后，查看实验结果。1. 正确输入：图表 1 符合文法要求输入2. 词法分析的结果：图表 2 词法分析结果在词法分析的结果中，行号代表单词出现在文件中的第几行，属性代表单词是关键字（1）、运算符（2）、变量（4、常数（0）、界符（3）。3. 分析过程：图表 3分析过程3：输出三地址码：图表 4 三地址码4： 输入错误的情况：图表 5 输入错误5： 输入错误情况下的分析： 结果分析：根据实验结果可以发现，程序能对输入串进行词法分析，并且在词法分析的基础上进行语法分析，能判断给定的串是否符合文法要求，并且能明确给出推导过程。在输入串不符合文法要求的时候，能给出错误提示，然后退出系统。4、设计心得与改进方案4.1 心得体会1. 课程设计较以往的课程设计来说难了很多，因为老师布置题目下来的时间比较早，因此有了较为充分的时间进行程序设计和编写工作，但总的来说时间还是很紧，程序还有许多需要改进的地方，也让我明白了做事情不能拖，一旦有了任务需要抓紧时间完成，不能等到最后临时抱佛脚。2. 由于编译原理这门课有很强的理论性，而且在书本中讲的也大多是都是理论方面的知识，因此在做具体实践的过程中需要查阅大量的资料，这就对我们的信息检索能力提出了很大的要求，如何在更短的时间内获取更多有用的信息并且学会利用不同的渠道(比如说搜索引擎，或者学校提供的数据库)来查找需要的资料成了我们必须要掌握的基本技能之一，这是我觉的与其他课程设计相比区别最大的一个地方，也是我收获最大的一部分。3. 因为这次的题目比较大，而以往写的程序都是很短的一部分。而这次整个程序一共有一千多行，所以在编写程序之前应该构建好系统的框架，明确每个部分的功能，并且设计好每一个子程序的伪代码，这样会使编写代码的是很逻辑更加清晰，而且可读性更强。4. 因为这次的程序用到了以前的实验结果，但由于都是用面向过程写的，所以感觉在代码重用方面比较麻烦，修改了很多地方才能使之正常运行。这也是我懂得了在平时的编程过程中应该养成良好的习惯，增强代码的健壮性，方便代码重用。5. 这次课程设计使