IF-ELSE条件语句翻译程序设计(LL(1)法、输出三地址表示) 2

1、武汉理工大学编译原理课程设计说明书IF-ELSE条件语句的翻译程序设计1 问题描述 要求用LL(1)自顶向下分析方法及三地址中间代码，对IF-THEN-ELSE条件语句完成编译各阶段过程，包括词法、语法、语义等分析。2 问题分析及编译系统的概要设计 编译过程一般分为六个阶段的过程，可以由六个模块完成，它们称为词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序，此外，一个完整编译程序还必须包括“表格管理程序”和“出错处理程序”。 这次实验涉及到词法分析、语法分析、语义分析及表格管理和出错管理。其中，词法分析至少要能识别关键字“if”、“then”和“els

2、e”，标识符（即自定义变量），数字，和运算符等等；语法分析要分析程序结构的合法性，即是否为文法的句子；语义分析要能够语法制导翻译出中间代码（三地址）并将其输出；表格管理是指符号表；出错处理是指在语法分析时，所有非文法句子的错误类型处理.3 文法及属性文法的定义 3.1 文法：文法是用于描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的、易于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序.IF-ELSE条件语句的文法如下所示： 0A->EB 1.B->+EB|-EB| 2.E->F

3、T 3.T->*FT|/FT| 4.F->i|(E) 或者能够更简洁一点: 0.S->if A THEN B ELSE C 1.A->m rop n 2.B->x=m arop n 3.C->x=n arop m 4.rop->=|<|> 5.arop->+|-|*|/3.2 属性文法： 属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配备若干相关的“值”（与文法符号相关的属性）。 在一个属性文法中，对应于每个产生式Aa都有一套与之相关联的语义规则，每规则的形式为：b:=f(c1,c2,，ck)其中f是一个函数

4、，而且或者b是A的一个综合属性并且c1,c2,，ck是产生式右边文法符号的属性或者非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值。属性文法为：if(VTopr='=') /"="判断；arrd1=arr_iopd;arrd0='='arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='>') /">"判断；arrd1=arr_iopd;arrd0='>'arrd2=i

5、d;arrd3=' 'arrd4=' 'id+;else if(VTopr='<') /"<"判断；arrd1=arr_iopd;arrd0='<'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='+') /"+"判断；arrd1=arr_iopd;arrd0='+'arrd2=id;arrd3=' 'arrd4=' 'id+;else

6、if(VTopr='-') /"-"判断；arrd1=arr_iopd;arrd0='-'arrd2=id;arrd3=' 'arrd4=' 'id+; else if(VTopr='*') /"*"判断；arrd1=arr_iopd;arrd0='*'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='/') /"/"判断；arrd1=arr_iopd

7、;arrd0='/'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(opr=-2) /其他字符判断；arrd1=id-1; arrd0=' 'arrd2=arr_iopd;arrd3=' 'arrd4=' 'else if(VTopr!='<'&&VTopr!='>'&&VTopr!='+'&&VTopr!='-'&&VTopr!=

8、'*'&&VTopr!='/')/"#"结束符判断； arrd1=id-1;d+;4 词法分析 首先应该创建一个枚举类型的变量来存放一些关键字： char VN11='K','L','P','S','E','G','T','R','F','Q','0' /产名生式头 char VT16='i','=','<&

9、#39;,'>','+','-','*','/','(',')','f','t','e','','0' /特征字符集 再创建一个结构体，用来存放词法分析的结果，共有两个域，一个关键字域，表明他是什么类型，以及它自身的内容。 这个词法分析程序比较简单，因为本身的程序就局限在if-else语句，所以保留字的类型我就只写了if、then和else三个；碰到数字开头的除了关键字就是标识符；碰到数字开头的就是

10、数字；碰到界限符和操作符（因为引入的类型也很少），所以也很容易区别。 在词法分析结束之后，就应该把分析的结果输出来。输出的格式是【（单词，类型编号） 类型名】 源程序文件字符的分离 单词的判断查找相应的表单词的类型的判断调用不同类型的单词处理函数进行单词的处理产生类型码将中间单词和其类型码存入数组处理完毕 词法分析程序如下： void lexical() /"ifm>n theni=i+9 elseb=b/3#"是其一条特殊的例子 int i,j,d; char ch; j=d=0; for(i=0;vari!='#'i+) ch=vari; if(c

11、h='i'&&vari+1='f') cout<<"if"<<'t'<<"keyword"<<'t'<<'t'<<"关键字"<<endl; queuej+='f'i+=1; /判断"if"关键字 else if(ch='t') ch=vari+1; if(ch='h') ch=vari+2;

12、 if(ch='e') ch=vari+3; if(ch='n') ch=vari+4;cout<<"then"<<'t'<<"keyword"<<'t'<<'t'<<"关键字"<<endl;queuej+='t'i+=3;/判断"then"关键字else if(ch='e')ch=vari+5;if(ch='l&

13、#39;)ch=vari+6;if(ch='s')ch=vari+7;if(ch='e')ch=vari+8;cout<<"else"<<'t'<<"keyword"<<'t'<<'t'<<"关键字"<<endl;queuej+='e'i+=3;/判断"else"关键字else if(index(ch,VT)<=0)if(ch!=&

14、#39;'&&ch!=''&&ch!='('&&ch!=')')cout<<ch<<'t'<<"variable:i"<<d+<<""<<'t'<<"标示符"<<endl;arr_id-1=ch;queuej+='i'else cout<<ch<<'t'

15、;<<"bound"<<'t'<<'t'<<"括 号"<<endl;else if(index(ch,VT)>0)cout<<ch<<'t'<<"operator"<<'t'<<"运算符"<<endl;queuej+=ch; queuej='#'/"#"就直接跳出 for(i=0;

16、queuei!='#'i+)cout<<queuei; cout<<endl; 5 语法分析 主要的思想是设置一个分析栈和一个输入串队列，栈中最开始时存放的是文法开始符和“#”。因为我这个程序本身已经确定是以if语句开头，所以，就不再把if放在输入串中，而只是分析if以后的句子。在语法分析之前应该判定该文法是不是一个LL(1)文法。判别的主要方法是做出文法中所有产生式的select集，对于同一个非终结符的不同产生式，如果他们的select集合没有交集，则说明这个文法是LL(1)文法。这个文法的预测分析表也设计的比较简单，如下表所示： -1, -1, -1

17、, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1,1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 2, -1,4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,5, -1, -1, -1, -1, -1, -1, -1, 5, -1, -1, -1, -1, -1,-1, -1, -1, -1, 6, 7, -1, -1, -1, -1, -1,

18、8, 8, 8,9, -1, -1, -1, -1, -1, -1, -1, 9, -1, -1, -1, -1, -1,-1, -1, -1, -1 , 12, 12, 10, 11, -1, -1, -1, 12, 12, 12,14, -1, -1, -1, -1, -1,- 1, -1, 13, -1, -1, -1, -1, -1,-1, 15, 16, 17, -1, -1, -1, -1, -1, -1, -1,- 1,- 1, -1, /预测分析表注：除了-1代表此处有产生式与之对应，具体的产生式在程序中给出。-1代表此处无产生式与之对应。void syntax()int n;

19、count+;print();X=stacksp;a=queuefront;if(X='#'&&a='#')f=4;if(X<'A'|X>'Z') /判断字符集不是大写字母集合if(X=a)sp-;front+;if(a!='i') /"i"是特征字母if(a!='f'&&a!='t'&&a!='e'&&a!=''&&a!='#

20、9;)opr=index(a,VT);semantic();else if(a=''|a='e'|a='t'|a='#') opr=-2;semantic();cout<<'t'<<'''<<a<<"'匹配"<<endl;elseopd=c;/cout<<opd1<<" "<<opd2;cout<<'t'<<&

21、#39;''<<arr_ic+<<"'匹配"<<endl;else f=1; /字符不匹配,转去出错处理elseint tx=index(X,VN);/索引选择int ta=index(a,VT);/索引选择n=Mtxta; /产生式选择tdt+=Mtxta; /产生式选择if(ta=-1)f=2;cout<<a<<endl; /字符没有出现在产生式终结符集VT中,转去出错处理else if(n=-1)f=3; /没有找到合适的候选产生式来做进一步推导,转去出错处理else /用产生式Mtx

22、ta来做进一步推导sp-;cout<<'t'<<X<<"->"if(len(pn)!=0)for(int i=len(pn)-1;i>=0;i-)stack+sp=pni;cout<<pnlen(pn)-1-i;cout<<endl;else cout<<"空串"<<endl; if(f=0)syntax();else tdt='-1'err(f);因为在推导过程中，会一并完成产生式后面附加的语义动作，所以这两部分是一起做的。另

23、外，在LL(1)分析过程中，会出现错误信息，如字符不匹配，或字符没有出现在产生式终结符集VT中，或没有找到合适的候选产生式来做进一步推导，会调用相应的出错处理函数err(f)。另外，此函数是递归实现，结束标志是f!=0，即成功或失败。6 出错处理由于输入的表达式有错误就要产生相应的出错处理函数void err(int n)if(n=1)cout<<"字符不匹配"<<endl;else if(n=2)cout<<"字符没有出现在产生式终结符集VT中"<<endl;else if(n=3)cout<<

24、;"没有找到合适的候选产生式来做进一步推导"<<endl;else cout<<"该句子是文法语言的句子！"<<endl;7 语义分析及中间代码输出 根据上面给出的属性文法所规定的翻译方案，即可对输入的程序进行相应的语义分析。对于中间代码部分，老师给的题目是以三地址的形式输出。对于三地址形式，在学习编译原理的时候接触的不是很多。我们接触的多的一般都是逆波兰式和四元式。仔细看书才发现，三地址和四元式是很相近的。比如说计算一个表达式a+b-c，四元式的形式是（+，a,b,t1）,(-,t1,c,t2)。而三地址的形式为t1

25、:=a+b,t2=t1-c。而对于跳转语句，无条件跳转如jump L1的四元式形式为(jump,-,-,L1)；而其对应的三地址形式为goto L1。而对于条件跳转语句，则四元式为（jrop，a，b，L1），而三地址形式为if a rop b goto L1。产生跳转的主要有三个地方，第一，就是if条件成立，则跳转到then后面的语局；第二，执行完then后面的语句后跳转到程序的出口；第三，就是if条件不成立则跳转到else后面的语句。在判断完if后面的条件后，保存这个布尔值，并产生跳转地址，这时，应该继续向前读取，如果碰到then这个关键字，则回填地址到then前面，否则报错。 关键是回填地

26、址的那个函数一定要写准确。在有跳转的语句后面，一定要有跳转的地址，即要跳到什么地方。产生跳转的语句有在token这个结构体中有个地址域，用来保存转向的地址。而在产生运算结果的语句中，token这个结构体中有个result域，用来保存这个结果。 /打印词法分析结果void print()cout<<"("if(count<10)cout<<'0'cout<<count<<")"int i;for(i=0;i<=sp;i+)cout<<stacki;for(;i<=

27、20;i+)cout<<" "for(i=0;i<front;i+)cout<<" "for(;queuei!='#'i+)cout<<queuei;cout<<queuei;for(;i<=20;i+)cout<<" "/语义分析程序void semantic()if(VTopr='=') /"="判断；arrd1=arr_iopd;arrd0='='arrd2=id;arrd3=' &

28、#39;arrd4=' 'id+;else if(VTopr='>') /">"判断；arrd1=arr_iopd;arrd0='>'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='<') /"<"判断；arrd1=arr_iopd;arrd0='<'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTo

29、pr='+') /"+"判断；arrd1=arr_iopd;arrd0='+'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='-') /"-"判断；arrd1=arr_iopd;arrd0='-'arrd2=id;arrd3=' 'arrd4=' 'id+; else if(VTopr='*') /"*"判断；arrd1=arr_iopd;arrd0

30、='*'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='/') /"/"判断；arrd1=arr_iopd;arrd0='/'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(opr=-2) /其他字符判断；arrd1=id-1; arrd0=' 'arrd2=arr_iopd;arrd3=' 'arrd4=' 'else if(VTopr!=&

31、#39;<'&&VTopr!='>'&&VTopr!='+'&&VTopr!='-'&&VTopr!='*'&&VTopr!='/')/"#"结束符判断； arrd1=id-1;d+;/输出三地址cout<<"输出三地址:"<<endl;for(i=0;i<d;i+)for(int j=0;j<5;j+)if(arrij>=0&

32、&arrij<=9)cout<<"("<<char(arrij+'0')<<")"<<" "else cout<<arrij<<" "cout<<endl; 而三元式的输出则很简单。但也要根据它具体的语义来进行输出。如果是if语句，则要根据if后面的bool语句来实现跳转。如果为真，应该调到then后面的语句，如果为假，则跳转到else后面的语句，每个语句都有自己的标号，用label来标识。而对于每个计

33、算结果的表达式，则首先用一个中间变量来存放结果，每次按照运算符的优先级算出一个结果，保存在中间变量中，最后将中间变量的结果赋给语句中的变量。 8 软件测试方法和结果 输入一组正确的词法和语法的if-else语句，和一组有词法错误和语法错误的if语句。 1. if m>n then i=i+3else b=b/2 测试结果如下： 2. if1 m>n then i=i*3else b=b-1测试的结果如下所示：9 分析本次设计 这次设计大体上还是自己动脑筋去想了，去做了。所以觉得并不是那么的难。关键的步骤就是三个，设计词法分析程序，语法分析程序，及语义分析程序和中间代码的输出程序。词

34、法分析程序由于上次实验做过了，所以这次做起来还是比较的顺手，只是这次的单词设计的比较简单，如关键字就只有三个，if、else和then；用户自定义变量的标识符也没有考虑以下划线开头的部分。 我做的语法分析方法是ll（1）的分析方法，这个方法的关键首先要构造一个if else语句的文法，然后将其转换为ll（1）文法，再根据每个产生式的select集构造预测分析表。然后就是相应的分析。构造一个分析栈和一个输入串队列，栈的初始内容是文法的开始符号和“#”，输入串队列则是输入串的内容。然后根据预测分析表做出相应的推导和匹配动作，最后如果栈里的内容和队列里的内容都是以“#”号的形式匹配的话，这个语句就分

35、析成功。我这次主要只是考虑了表达式的分析过程，而没有把if else then这些关键字的分析过程加入进来。因为我们这次设计也是针对一个特定的语句（如我的if else语句）来进行分析的，所以我就假设所有的输入串当中都在相应的位置有那些关键字了。所以程序做起来就比较简单，容易实现。 而语义分析则是要识别这句话要做什么，并且将其要做的事情用三地址的形式翻译出来。这个对我来说的确有点困难，所以见参考了一下其他同学的设计方法。这个也是这次设计的不足之处，望老师见谅-。10 参考文献1 张素琴、吕映芝、蒋维杜、戴桂兰等编译原理（第2版）清华大学出版社2005年2月参考书：2 程序设计语言编译原理 国防

36、工业出版社 陈火旺著3 编译原理习题与解析 清华大学出版社出版社 伍春香著 11 源程序清单#include<iostream.h>#define MAX 100 char X,a;char VN11='K','L','P','S','E','G','T','R','F','Q','0' /产名生式头char VT16='i','=','<','&

37、gt;','+','-','*','/','(',')','f','t','e','','0' /特征字符集char p188="fLtLeS0","SP0","0","0","iQE0","TG0","+TG0","-TG0","0"

38、,"FR0","*FR0","/FR0","0","(E)0","i0","=0","<0",">0"/产生式集合数组char stackMAX;char queueMAX;int sp,front;int M1014= -1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,-1,-1,-1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-

39、1,-1,-1,-1,-1,-1,-1,-1, 3, 2,-1,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,6,7,-1,-1,-1,-1,-1, 8, 8, 8,9,-1,-1,-1,-1,-1,-1,-1,9,-1,-1,-1,-1,-1,-1,-1,-1,-1,12,12,10,11,-1,-1,-1,12,12,12,14,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,-1,-1,-1,-1,15,16,17,-1,-1,-1,-1

40、,-1,-1,-1,-1,-1,-1,; /预测分析表int f=0;int count=0;int c=0;char arr_iMAX; /字符管理char varMAX; /表格管理int tdMAX; /输出产生式序列int t=0;int opd=-1;int opr=-1;int id=0;/int ptrMAX;int d=0;char arrMAX5; /存放待输出的三地址/char keyword211="if0","then0","else0"int len(char str)int i=0;while(stri!=

41、'0')i+;return i;int index(char ch,char str)int i=0;while(stri!='0')if(ch!=stri)i+;else break;if(stri='0')return -1;return i;/出错管理选项void err(int n)if(n=1)cout<<"字符不匹配"<<endl;else if(n=2)cout<<"字符没有出现在产生式终结符集VT中"<<endl;else if(n=3)cou

42、t<<"没有找到合适的候选产生式来做进一步推导"<<endl;else cout<<"该句子是文法语言的句子！"<<endl;/打印此法分析结果void print()cout<<"("if(count<10)cout<<'0'cout<<count<<")"int i;for(i=0;i<=sp;i+)cout<<stacki;for(;i<=20;i+)cout<&

43、lt;" "for(i=0;i<front;i+)cout<<" "for(;queuei!='#'i+)cout<<queuei;cout<<queuei;for(;i<=20;i+)cout<<" "/语义分析程序void semantic()if(VTopr='=') /"="判断；arrd1=arr_iopd;arrd0='='arrd2=id;arrd3=' 'arrd4='

44、 'id+;else if(VTopr='>') /">"判断；arrd1=arr_iopd;arrd0='>'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='<') /"<"判断；arrd1=arr_iopd;arrd0='<'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='+')

45、 /"+"判断；arrd1=arr_iopd;arrd0='+'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='-') /"-"判断；arrd1=arr_iopd;arrd0='-'arrd2=id;arrd3=' 'arrd4=' 'id+; else if(VTopr='*') /"*"判断；arrd1=arr_iopd;arrd0='*'arr

46、d2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='/') /"/"判断；arrd1=arr_iopd;arrd0='/'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(opr=-2) /其他字符判断；arrd1=id-1; arrd0=' 'arrd2=arr_iopd;arrd3=' 'arrd4=' 'else if(VTopr!='<'&a

47、mp;&VTopr!='>'&&VTopr!='+'&&VTopr!='-'&&VTopr!='*'&&VTopr!='/')/"#"结束符判断； arrd1=id-1;d+;/语法分析程序void syntax()int n;count+;print();X=stacksp;a=queuefront;if(X='#'&&a='#')f=4;if(X<'A&

48、#39;|X>'Z') /判断字符集不是大写字母集合if(X=a)sp-;front+;if(a!='i') /"i"是特征字母if(a!='f'&&a!='t'&&a!='e'&&a!=''&&a!='#')opr=index(a,VT);semantic();else if(a=''|a='e'|a='t'|a='#') opr

49、=-2;semantic();cout<<'t'<<'''<<a<<"'匹配"<<endl;elseopd=c;/cout<<opd1<<" "<<opd2;cout<<'t'<<'''<<arr_ic+<<"'匹配"<<endl;else f=1; /字符不匹配,转去出错处理elsei

50、nt tx=index(X,VN);/索引选择int ta=index(a,VT);/索引选择n=Mtxta; /产生式选择tdt+=Mtxta; /产生式选择if(ta=-1)f=2;cout<<a<<endl; /字符没有出现在产生式终结符集VT中,转去出错处理else if(n=-1)f=3; /没有找到合适的候选产生式来做进一步推导,转去出错处理else /用产生式Mtxta来做进一步推导sp-;cout<<'t'<<X<<"->"if(len(pn)!=0)for(int i=len

51、(pn)-1;i>=0;i-)stack+sp=pni;cout<<pnlen(pn)-1-i;cout<<endl;else cout<<"空串"<<endl; if(f=0)syntax();else tdt='-1'err(f);/测法分析程序void lexical() /"ifm>n theni=i+9 elseb=b/3#"是其一条特殊的例子int i,j,d;char ch;j=d=0;for(i=0;vari!='#'i+)ch=vari;if(c

52、h='i'&&vari+1='f')cout<<"if"<<'t'<<"keyword"<<'t'<<'t'<<"关键字"<<endl; queuej+='f'i+=1;/判断"if"关键字else if(ch='t')ch=vari+1;if(ch='h')ch=vari+2;if(ch=

53、'e')ch=vari+3;if(ch='n')ch=vari+4;cout<<"then"<<'t'<<"keyword"<<'t'<<'t'<<"关键字"<<endl;queuej+='t'i+=3;/判断"then"关键字else if(ch='e')ch=vari+5;if(ch='l')ch=va

54、ri+6;if(ch='s')ch=vari+7;if(ch='e')ch=vari+8;cout<<"else"<<'t'<<"keyword"<<'t'<<'t'<<"关键字"<<endl;queuej+='e'i+=3;/判断"else"关键字else if(index(ch,VT)<=0)if(ch!=''&&ch!=''&&ch!='('&&ch!=')')cout<<ch<<'t'<<"variable:i"<<d+<<""<<'