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

-课内实践报告学 号： 0121210340314课程名称 编译原理设计题目WHILE循环语句的翻译程序设计(递归下降法，输出四元式)学 院 计算机科学与技术专业班级计算机1203班姓 名 闵丹枫指导教师林 泓2014年12月 8日第 31 页-课程设计任务书学生姓名： 闵丹枫 专业班级： 计算机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年 月 日 WHILE循环语句的翻译程序设计（递归下降法、输出四元式）一 系统描述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 B2. A -> CDC3. D -> > | = | < | >= |<=4. C -> C+E | C-E | E5. E -> E*F | E/F | E6. F -> (C) | i | n对以上文法消除左递归，最后得到的文法为：1. S->while (A) do B 2. A->CDC3. D-> > | = | < | >= | <= 4. C->EG 5. G->+EG | -EG | 6. E->FH 7. H->*FH | / FH | 8. F->(C) | i | n 9. 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(goto Lnext);）A->CDCA.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:=newtemp ;Emit(D.Place':=''>=').D-> <= D.place:=newtemp ;Emit(D.Place':=''<=')C->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-> / FHH.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.PlaceB->i=C;p:=lookup(i.name)If p!=nil thenEmit(p':='C.PlaceElse error)三 语法分析方法描述31 语法分析方法描述 递归下降法是一种比较简单直观，易于构造的语法分析方法。他要求文法满足LL（1）文法，他的设计思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的单词（或串），当某非终结符的产生式有多个候选时，能够按LL（1）形式可唯一地确定选择某个候选进行推导。它的优点是简单直观，易于构造，很多编译系统所实现缺点是对文法要求很高，由于递归调用多，影响分析器的效率。递归下降程序是由一组子程序组成，每个子程序对应于一个非终结(S,A,B,C,D,E,F,G,H)。每个子程序处理相应句型中相对于此非终结符号的产生式。在定义文法时，是递归定义的，所以这些子程序也是递归的。当一个子程序调用另一个子程序时，原子程序顺序执行语句，即总是先执行被调用的子程序，然后再执行后继的程序。程序中9个子程序，其中S 是开始符号，也是递归下降分析的入口，通过调用词法分析器进行单词分析，并通过word=l.Yufa_Queue.front()来得到当前所分析到的单词，然后在递归语法分析中根据这个单词分析下一步要执行的子程序。其中要注意的是，当子程序G()和H()中出现匹配的是空字符串时，不做单词处理，该所取得的单词，应该为下一个匹配产生做准备。32 递归下降法实现的原理设A是一个非终结符：A1 A2 An则写 (A) Û if charfirst(1 ) then(1 ) else if charfirst(2 ) then (2 ) else if charfirst(n ) then (n) else ERROR其中(i)表示调用处理符号串i的子程序。对A的任一右部i 设为： i = y1 y2 yn则定义( i) Û begin(y1);(y2);(yn) end其中yj可分为下列两种情况（j=1,n):1) yjVT,则 ( yj) Û if char yj then ERROR else READ(char)2) yjVN,则(yj)表示调用关于yj的递归子程序。四中间代码形式的描述及中间代码序列的结构设计4.1四元式形式 中间代码为四元式，按照要求，要输出四元式一个四元式是一个带有四个域的记录结构，这四个域分别称为oparg1arg2及result。域op包含一个代表运算符的内部码。语句while a<b do a=a+b的四元式输出:1 ( <, a , b , 3 ) 2 ( j , _ , _ ,6 ) 3 ( + , a , b , n ) 4 ( = , n , _ , a ) 5 ( j , _ , _ , 1) 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语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。六 详细的算法描述S()àW()àEàF()àD()àG()àR()àT()方法和变量的定义int m = 0, sum = 0;/sum用于计算运算符的个数 m用于标记输入表达式中字符的个数char JG = 'A'char strMAX; /用于存赋值表达式int token = 0; /左括号的标志int sign = 0;char whi5 = 'w', 'h', 'i', 'l', 'e' ; /检查关键字whilestring getsentence(); /获取表达式void anlyse(string temp); /while语句递归分析bool Judge_W(char *ch); /判断whilevoid Do_E(string temp); /Evoid Do_F(string temp); /F void Do_G(string temp); / Gvoid change(int e); /用于更改计算后数组中的值void chengchuchuli(int i, int m); /对赋值语句进行乘除处理便于输出四元式 void jiajianchuli(int j, int m); /对赋值语句进行加减处理四元式void siyuanshi(); /用于处理赋值语句输出四元式void anlyse(string temp)char *wh = new char5;int s_length = temp.size() + 1;char *str = new chars_length;for (; sign < 5; sign+)whsign = tempsign;if (Judge_W(wh)if (tempsign = '(')sign+;Do_E(temp);做W（）：bool Judge_W(char *ch) bool flag = true;for (int i = 0; i < 5; i+)if (chi != whii)flag = false;cout << "while关键字输入错误！" << endl;break;return flag;做E（）：void Do_E(string temp) /E -> aFbif (tempsign >= 'a' && tempsign <= 'z') | (tempsign > 'A' && tempsign <= 'Z')cout << "(" ;sign+;Do_F(temp);elsecout << "（）中含有非法字符！" << endl;做F（） F -> < | = | > | <= | >=void Do_F(string temp) /F -> < | = | > | <= | >=int f_sign = sign;if (tempf_sign = '<' | tempf_sign = '=' | tempf_sign = '>')if (tempf_sign + 1 = '=')cout << tempf_sign + 1<<","if (tempf_sign + 2 >= 'a' && tempf_sign + 2 <= 'z') | (tempf_sign + 2 > 'A' && tempf_sign + 2 <= 'Z')cout << tempf_sign << tempf_sign + 1 << "," <<tempf_sign - 1 << "," << tempf_sign + 2 << ",sign)" << endl;sign = sign + 2;sign+;if (tempsign = ')' && tempsign+1 = '')sign = sign + 2;Do_G(temp);else if (tempf_sign + 1 >= 'a' && tempf_sign + 1 <= 'z') | (tempf_sign + 1 > 'A' && tempf_sign + 1 <= 'Z')cout << tempf_sign << "," << tempf_sign - 1 << "," << tempf_sign + 1 << ",sign)" << endl;sign+;sign+;if (tempsign = ')' && tempsign + 1 = '' )sign = sign + 2;Do_G(temp);elsecout << "()中存在符号错误" << endl;做Do_G G-> c=Rvoid Do_G(string temp) /G-> c=R 赋值表达式int pMAX;int len = temp.size() + 1;char ch = 'a'int c = -1, q = 0;while (tempsign != '' && sign < len)ch = tempsign;strm+ = ch;if (ch = '=' | ch = '+' | ch = '-' | ch = '*' | ch = '/') sum+;else if (ch = '(')p+c = m - 1;else if (ch = ')')q = m - 1;chengchuchuli(pc, q);/从左括号处理到又括号jiajianchuli(pc, q);JG = (char)(int)JG-;strpc = strm - 1 = JG;c-;JG = (char)(int)JG+;sign+;cout << str << endl;siyuanshi();if (tempsign != '') cout << "前缺少 “;”" << endl;if (temptemp.size()-1 != '') cout << "缺少“”" << endl;对赋值语句进行四元式输出：void change(int e)int f = e + 2;char ch = strf;if (ch >= 'A'&&ch <= 'Z')for (int l = 0; l<m + 10; l+)if (strl = ch)strl = JG;if (stre >= 'A'&&stre <= 'Z')for (int i = 0; i<m; i+)if (stri = stre)stri = JG;void chengchuchuli(int i, int m)i+;for (; i <= m - 1; i+)/处理乘除运算if (stri = '*' | stri = '/')cout << "(" << stri << " " << stri - 1 << " " << stri + 1 << " " << JG << ")" << endl;change(i - 1);stri - 1 = stri = stri + 1 = JG;sum-;JG = (char)(int)JG+;void jiajianchuli(int j, int m)j+;for (; j <= m - 1; j+)/处理加减运算if (strj = '+' | strj = '-')cout << "(" << strj << " " << strj - 1 << " " << strj + 1 << " " << JG << ")" << endl;change(j - 1);strj - 1 = strj = strj + 1 = JG;sum-;JG = (char)(int)JG+;void siyuanshi()for (int i = 0; i <= m - 1; i+)/处理乘除运算if (stri = '*' | stri = '/')cout << "(" << stri << " " << stri - 1 << " " << stri + 1 << " " << JG << ")" << endl;change(i - 1);stri - 1 = stri = stri + 1 = JG;sum-;JG = (char)(int)JG+;for (int j = 0; j <= m - 1; j+)/处理加减运算if (strj = '+' | strj = '-')cout << "(" << strj << " " << strj - 1 << " " << strj + 1 << " " << JG << ")" << endl;change(j - 1);strj - 1 = strj = strj + 1 = JG;sum-;JG = (char)(int)JG+;for (int k = 0; k <= m - 1; k+)/处理赋值运算if (strk = '=')JG = (char)(int)-JG;cout << "(" << strk << " " << strk + 1 << " " << " " << " " << strk - 1 << ")" << endl;sum-;change(k + 1);strk - 1 = JG;七 软件的测试方法和测试结果输入 while（a>b）z=x+y;测试结果如下：输入while(a>b)z=x+y*c; 测试结果如下输入wh(a>b)z=y; 结果为：输入while(a>b)z=z+y 结果为：八 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）8.1研制过程在做本次实验之前我对LL(1)文法的构成,递归下降原理不是很了解,在查阅了相关资料后,对此有了深入了解。将词法分析，语法分析，中间语言翻译结合到一起。 8.2 设计的评价、特点、不足设计的程序基本上实现了用递归下降分析法实现了while语句的翻译，并能够用四元式将其输出，使人一目了然。程序还能够准确提示词法和语法错误。同时程序运行时简单明了，易于使用。8.3收获和体会深入了解计算机语言编译和运行的过程，对编译原理有了深刻的认识，掌握了递归下降法，熟练地使用四元式中间代码，明白了对于编写程序，解题的思路为重要。在编写程序之前，如果没有比较清晰的思路，根本不可能编出好的程序。就算马马虎虎的编出来，程序的逻辑性、健壮性、完善性、合理性也不会很强。在编程之前，我们应反复研究题目要求，对题目涉及的情况进行比较充分的分析，以便编写出更加符合题意的程序；其次要充分考虑各种临界情况，对一些错误的输入进行处理。因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，逐块的写好算法，最后再将所有的模块有机的联系起来，组成一个完整的程序。在成功通过编译的情况下，对程序运行的结果进行系统的分析，检验其正确性，如果有错误，应立即去分析源程序的逻辑错误，直到得到正确的结果。九 参考文献编译原理第2版 清华大学出版社 张素琴等著本科生课程设计成绩评定表班级：计算机1203 姓名：闵丹枫 学号：0121210340314序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：201 年月日