WHILE循环语句的翻译程序设计(递归下降法,输出四元式)_百度文库

1、学 号： 0121210340314课内实践报告课程名称编译原理设计题目WHILE循环语句的翻译程序设计(递归下降法，输出四元式学 院计算机科学与技术专业班级计算机1203班姓 名闵丹枫指导教师林 泓2014年12月8日课程设计任务书学生姓名： 闵丹枫 专业班级： 计算机1203班 指导教师： 林 泓 工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（递归下降法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说

2、明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码四元式的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本

3、设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2014年 9月 1日系主任（或责任教师）签名： 2014年 月 日WHILE循环语句的翻译程序设计（递归下降法、输出四元式）一 系统描述1.1问题描述设计一个WHILE布尔表达式DO赋值语句循环语句的词法语法及语义分析程序，语法分析选择递归下降法，采用用语法制导翻译输出中间代码四

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

5、= <表达式> + <表达式2> | <表达式> - <表达式2> | <表达式2> <表达式2>:=<表达式2> * <表达式3> |<表达式2> / <表达式3> | <表达式3><表达式3>:=(<表达式> | <标识符>|<数字><赋值语句>:=<标识符>=<表达式>；根据以上写出来的While循环语句的文法表示如下：1. S -> while (A do B2. A

6、 -> 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

7、| n 9. B->i=C；2.1 属性文法的描述(1任一非终结符B都不是左递归的，否则会产生死循环。(2对A的任意两个右部i , j ,有：first(ifirst(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.p

8、lace |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':='

9、'<'.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.placeG

10、->+EG G.Place:=newtemp;Emit(G1.Place':=''+'E.Place G2.placeG->-EG G.Place:=newtemp;Emit(G1.Place':=''-'E.Place G2.placeG-> G.Place:=newtemp;Emit(G.Place':='''H->*FH H.Place:=newtemp;Emit(H1.Place':=''*'F.Place H2.placeH

11、-> / FHH.Place:=newtemp;Emit(H1.Place':=''+'F.Place H2.placeH->G.Place:=newtemp;Emit(H1.Place':=''+'E.Place H2.placeF->(C F.Place:=C.PlaceB->i=C;p:=lookup(If p!=nil thenEmit(p':='C.PlaceElse error三 语法分析方法描述31 语法分析方法描述递归下降法是一种比较简单直观，易于构造的

12、语法分析方法。他要求文法满足LL（1）文法，他的设计思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的单词（或串），当某非终结符的产生式有多个候选时，能够按LL（1）形式可唯一地确定选择某个候选进行推导。它的优点是简单直观，易于构造，很多编译系统所实现缺点是对文法要求很高，由于递归调用多，影响分析器的效率。32 递归下降法实现的原理设A是一个非终结符：A1 A2An则写 (A if charfirst(1 then(1 else if charfirst(2 then (2 elseif charfirst(n then (nelse ERROR其中(i表示调

13、用处理符号串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(char2 yjVN,则(yj表示调用关于yj的递归子程序。四中间代码形式的描述及中间代码序列的结构设计4.1四元式形式中间代码为四元式，按照要求，要输出四元式一个四元式是一个带有四个域的记录结构，这四个域分别称为oparg1arg2及result。域op包含一个代表运算符的内部码。语句while aa+b的四元式输出:1 ( <,

14、a , b , 3 2 ( j , _ , _ ,6 3 ( + , a , b , n 4 ( = , n , _ , a 5 ( j , _ , _ , 16五 编译系统的概要设计5.1全局程序的概要设计递归下降分析技术就是通过对每个非终结符编写一个子程序来实现它的操作，然后通过递归的调用来实现对输入字符串的分析，这其中还包括对输入字符串的词法分析。在词法分析的时，得到的字符单词要和关键字比较，看是否是关键字，根据比较结果进行返回相应的单词类型。单词类型主要包括界限符，关键字，常量，标识符，运算符等，每种符号都是一种类型。在语法分析程序中，根据词法得到的结果，进行判断是否是当前需要的单词类

15、型，如果不是就说明输入字符串不能由该文法推导出来；如果是当前需要的类型，就相应得做该单词类型分支程序。根据文法可以得到这个递归下降程序可以分析while语句，在文法的开始符号S开始进行递归调用，因此这个文法的递归中就要考虑到调用以及递归。在递归子程序中，在嵌套调用其他子程序时都是有一定条件的，当满足这个条件的时候该程序可以按照满足的条件执行下去，当没有满足程序中的条件时就会显示语法错误。5.2词法分析词法分析程序的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号的中间程序。词法分析检查的错误主要是挑出源程序中出现的非法符号。所谓非法符号是指

16、不是程序设计语言中允许出现的符号，就像自然语句中的错字。5.3递归下降翻译器的设计对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数，函数的返回值为A的综合属性，A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号，非3：终结符和语义动作分别做以下工作。1. 对于带有综合属性x的终结符X，把x的值存入为X，x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。2. 对于每个非终结符号B，产生一个右边带

17、有函数调用的赋值语句c=B(b1,b2,，bk3. 对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对应属性的每一次引用。5.4语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接

18、保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。六 详细的算法描述S(W(EF(D(G(R(T(方法和变量的定义#define MAX 100int m = 0, sum = 0;/sum用于计算运算符的个数 m用于标记输入表达式中字符的个数char JG = 'A'char strMAX; /用于存赋值表达式int token = 0; /左括号的标志int sign = 0;char whi5 = 'w', 'h', 'i'

19、;, '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; /对赋值语句进行乘除处理便于输出四元式 vo

20、id jiajianchuli(int j, int m; /对赋值语句进行加减处理四元式void siyuanshi(; /用于处理赋值语句输出四元式void anlyse(string tempchar *wh = new char5;int s_length = temp.size( + 1;char *str = new chars_length;for (; sign < 5; sign+whsign = tempsign;if (Judge_W(whif (tempsign = '('sign+;Do_E(temp;做W（）：bool Judge_W(char

21、 *ch bool flag = true;for (int i = 0; i < 5; i+if (chi != whiiflag = false;cout << "while关键字输入错误！" << endl;break;return flag;做E（）：void Do_E(string temp /E -> aFbif (tempsign >= 'a' && tempsign <= 'z' | (tempsign > 'A' && te

22、mpsign <= '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 = '

23、=' | 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

24、 << tempf_sign + 1 << "," < f_sign - 1 << "," << temp f_sign + 2 << ",sign" << endl ; sign = sign + 2;sign+;if (tempsign = '' && tempsign+1 = ''sign = sign + 2;Do_G(temp;else if (tempf_sign + 1 >= 'a&

25、#39; && 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+;i

26、f (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 != '' &

27、amp;& sign < lench = 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(intJG-;strpc = str

28、m - 1 = JG;c-;JG = (char(intJG+;sign+;cout << str << endl;siyuanshi(;if (tempsign != '' cout << "前缺少 “;”" << endl;if (temptemp.size(-1 != '' cout << "缺少“”" << endl;对赋值语句进行四元式输出：void change(int eint f = e + 2;char ch = strf;if (c

29、h >= 'A'&&ch <= 'Z'for (int l = 0; l if (strl = chstrl = JG;if (stre >= 'A'&&stre <= 'Z'for (int i = 0; i i + if (stri = strestri = JG;void chengchuchuli(int i, int mi+;for (; i <= m - 1; i+/处理乘除运算if (stri = '*' | stri = '/&#

30、39;cout << "(" << stri << " " << stri - 1 << " " << stri + 1 << " " << JG << "" << endl;change(i - 1;stri - 1 = stri = stri + 1 = JG;sum-;JG = (char(intJG+;void jiajianchuli(int j, int mj+;f

31、or (; j <= m - 1; j+/处理加减运算if (strj = '+' | strj = '-'cout << "(" << strj << " " << strj - 1 << " " << strj + 1 << " " << JG << "" << endl;change(j - 1;strj - 1 = strj = s

32、trj + 1 = JG;sum-;JG = (char(intJG+;void siyuanshi(for (int i = 0; i <= m - 1; i+/处理乘除运算if (stri = '*' | stri = '/'cout << "(" << stri << " " << stri - 1 << " " << stri + 1 << " " << JG <<

33、; "" << endl;change(i - 1;stri - 1 = stri = stri + 1 = JG;sum-;JG = (char(intJG+;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(intJG+;for (int k = 0; k <= m - 1; k+/处理赋值运算if (strk = '='JG = (char(int-JG;cout << "(