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

学 号：
0120810340605

课 程 设 计

题 目
IF-ELSE条件语句的翻译程序设计（LL（1）法、输出三地址表示）
学 院
计算机科学与技术学院
专 业
计算机科学与技术
班 级
0806
姓 名
周雪
指导教师
郭羽成

2010
年
1
月
6
日
课程设计任务书

学生姓名： 周 雪 专业班级： 计算机0806班
指导教师： 郭 羽 成 工作单位：计算机科学与技术学院
题目: IF-ELSE条件语句的翻译程序设计（LL（1）法、输出三地址表示）
初始条件：
理论：学完编译课程，掌握一种计算机高级语言的使用。
实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。

要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
（1） 写出符合给定的语法分析方法的文法及属性文法。
（2） 完成题目要求的中间代码三地址表示的描述。
（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。
（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。
（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：
1 系统描述（问题域描述）；
2 文法及属性文法的描述；
3 语法分析方法描述及语法分析表设计；
4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；
5 编译系统的概要设计；
6 详细的算法描述（流程图或伪代码）；
7 软件的测试方法和测试结果；
8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；
9 参考文献（按公开发表的规范书写）。
时间安排：
设计安排一周：周1、周2：完成系统分析及设计。
周3、周4：完成程序调试及测试。
周5：撰写课程设计报告。
设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。
设计报告书收取时间：设计周的次周星期一上午10点。
指导教师签名： 2010年 11月 23日
系主任（或责任教师）签名： 2010年 11月 23日

1 问题描述
要求用LL(1)自顶向下分析方法及三地址中间代码，对IF-THEN-ELSE条件语句完成编译各阶段过程，包括词法、语法、语义等分析。
2 问题分析及编译系统的概要设计
编译过程一般分为六个阶段的过程，可以由六个模块完成，它们称为词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序，此外，一个完整编译程序还必须包括“表格管理程序”和“出错处理程序”。
这次实验涉及到词法分析、语法分析、语义分析及表格管理和出错管理。其中，词法分析至少要能识别关键字“if”、“then”和“else”，标识符（即自定义变量），数字，和运算符等等；语法分析要分析程序结构的合法性，即是否为文法的句子；语义分析要能够语法制导翻译出中间代码（三地址）并将其输出；表格管理是指符号表；出错处理是指在语法分析时，所有非文法句子的错误类型处理.
3 文法及属性文法的定义
3.1 文法：
文法是用于描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的、易于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序.
IF-ELSE条件语句的文法如下所示：
0．A->EB
1.B->+EB|-EB|ε
2.E->FT
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 属性文法：
属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配备若干相关的“值”（与文法符号相关的属性）。
在一个属性文法中，对应于每个产生式A→a都有一套与之相关联的语义规则，每规则的形式为：b:=f(c1,c2,…，ck)其中f是一个函数，而且或者①b是A的一个综合属性并且c1,c2,…，ck是产生式右边文法符号的属性或者②非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值。
属性文法为：
0.S->if A THEN B ELSE C
{ S.chain:=merge(A.chain,B.chain, C.chain)}
1.A->m rop n
{ A.true:=nextstat;
A.false=nextstat+1;
backpatch(A.chain,nextstat);
emit(“if p” rop “q goto —”)
emit(“goto —”) ; }
2.B->x=m arop n
{ backpatch(B.chain,nextstat);
emit(“ x:= m” arop “n”);
emit(“goto —”); }
3.C->x=n arop m
{ backpatch(C.chain,nextstat);
emit(“ x:= n” arop “m”);
emit(“goto —”); }
4.rop -> = { emit(“ = ”); }
5. rop -> <{ emit(“ < ”); }
6. rop -> >{ emit(“ > ”); }
7. arop -> +{ emit(“ + ”); }
8. arop-> - { emit(“ - ”); }
9.arop-> *{ emit(“ * ”); }
10.arop-> /{ emit(“ / ”); }

4 词法分析
首先应该创建一个枚举类型的变量来存放一些关键字，enum keyword{$right_paren,$left_paren,$mul,$div,$add,$sub,$fenhao,$equal,$IF,$THEN,$ELSE,$greater,$less,$id,$num,$end};
再创建一个结构体，用来存放词法分析的结果，共有两个域，一个关键字域，表明他是什么类型，以及它自身的内容。
这个词法分析程序比较简单，因为本身的程序就局限在if-else语句，所以保留字的类型我就只写了if、then和else三个；碰到数字开头的除了关键字就是标识符；碰到数字开头的就是数字；碰到界限符和操作符（因为引入的类型也很少），所以也很容易区别。
在词法分析结束之后，就应该把分析的结果输出来。输出的格式是【（单词，类型编号） 类型名】

源程序文件

字符的分离

单词的判断

查找相应的表

单词的类型的判断

调用不同类型的单词处理函数进行单词的处理

产生类型码

将中间单词和其类型码存入数组

处理完毕

词法分析程序如下：
bool lexcal()
{
int k=0;
char buf[16];
char ch;
while(1)
{
ins>>ch;
if(ins.fail())
break;
while(ch==' ')
{ ins>>ch;}
if(ch=='I')
{
ins>>buf;
if(strcmp(buf,"F")==0)
tokentable[total_len++].type=$IF;
}
else if(ch=='T')
{
ins>>buf;
if(strcmp(buf,"HEN")==0)
tokentable[total_len++].type=$THEN;
}
else if(ch=='E')
{
ins>>buf;
if(strcmp(buf,"LSE")==0)
tokentable[total_len++].type=$ELSE;
}
else if(ch=='>')
{
tokentable[total_len++].type=$greater;
}
else if(ch=='<')
{
tokentable[total_len++].type=$less;
}
else if(ch=='=')
{
tokentable[total_len++].type=$equal;
}
else if((ch>='A'&& ch<='Z' )|| (ch>='a' && ch<='z'))
{
tokentable[total_len].type=$id;
tokentable[total_len++].ch=ch;
}
else if(ch>='0' && ch<='9')
{ tokentable[total_len].type=$num;
tokentable[total_len++].ch =ch;
}
else
switch (ch)
{ case '+' :
tokentable[total_len].type=$add;
tokentable[total_len++].ch =ch;

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

i
+
-
*
/
(
)
#
E
1
0
0
0
0
1
0
0
A
0
1
1
0
0
0
1
1
T
1
0
0
0
0
1
0
0
B
0
1
1
1
1
0
1
1
F
1
0
0
0
0
1
0
0
注：1代表此处有产生式与之对应，具体的产生式在程序中给出。0代表此处无产生式与之对应。

void syntax()
{
count++;
print();
X=stack[sp];
a=queue[front];
if(X=='#'&&a=='#')f=4;
if(X<'A'||X>'Z'){
if(X==a){
sp--;
front++;
if(a!='i'){
if(a!='d'&&a!='w'&&a!=';'&&a!='#'){opr=index(a,VT);semantic();}
else if(a==';'||a=='w'||a=='#'){opr=-2;semantic();}
cout<<'\t'<<'\''<<a<<"'匹配"<<endl;}
else {
opd=c;
cout<<'\t'<<'\''<<arr_i[c++]<<"'匹配"<<endl;}
}
else f=1; //字符不匹配,转去出错处理
}
else {
tx=index(X,VN);
ta=index(a,VT);
n=M[tx][ta];
td[t++]=M[tx][ta];
if(ta==-1){f=2;cout<<a<<endl;}
else if(n==-1)f=3;
else { //用产生式M[tx][ta]来做进一步推导
sp--;
cout<<'\t'<<X<<"->";
if(len(p[n])!=0){
for(i=len(p[n])-1;i>=0;i--){
stack[++sp]=p[n][i];cout<<p[n][len(p[n])-1-i];}
cout<<endl;}
else cout<<"空串"<<endl;}
}
if(f==0)syntax();
else {td[t]='-1';err(f);}
}

因为在推导过程中，会一并完成产生式后面附加的语义动作，所以这两部分是一起做的。
另外，在LL(1)分析过程中，会出现错误信息，如字符不匹配，或字符没有出现在产生式终结符集VT中，或没有找到合适的候选产生式来做进一步推导，会调用相应的出错处理函数err(f)。另外，此函数是递归实现，结束标志是f!=0，即成功或失败。

6 语义分析及中间代码输出
根据上面给出的属性文法所规定的翻译方案，即可对输入的程序进行相应的语义分析。对于中间代码部分，老师给的题目是以三地址的形式输出。对于三地址形式，在学习编译原理的时候接触的不是很多。我们接触的多的一般都是逆波兰式和四元式。仔细看书才发现，三地址和四元式是很相近的。比如说计算一个表达式a+b-c，四元式的形式是（+，a,b,t1）,(-,t1,c,t2)。而三地址的形式为t1:=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前面，否则报错。
关键是回填地址的那个函数一定要写准确。在有跳转的语句后面，一定要有跳转的地址，即要跳到什么地方。产生跳转的语句有在token这个结构体中有个地址域，用来保存转向的地址。而在产生运算结果的语句中，token这个结构体中有个result域，用来保存这个结果。
//产生数值语句
void AD_RESULT(int nlabel,OpKind nop,char npar1,char npar2, char nresult)
{quad[quad_len].label=nlabel;
quad[quad_len].op=nop;
quad[quad_len].par1=npar1;
quad[quad_len].par2=npar2;
quad[quad_len].result=nresult;
quad_len++;
}
//产生跳转地址
void AD_ADDRESS(int nlabel,OpKind nop,char npar1,char npar2,int naddress)
{ quad[quad_len].label=nlabel;
quad[quad_len].op=nop;
quad[quad_len].par1=npar1;
quad[quad_len].par2=npar2;
quad[quad_len].address=naddress;
quad_len++;
}
//回填出口
void backpath(int nlabel,int addr)
{
quad[nlabel].address=addr;
}
而三元式的输出则很简单。但也要根据它具体的语义来进行输出。如果是if语句，则要根据if后面的bool语句来实现跳转。如果为真，应该调到then后面的语句，如果为假，则跳转到else后面的语句，每个语句都有自己的标号，用label来标识。而对于每个计算结果的表达式，则首先用一个中间变量来存放结果，每次按照运算符的优先级算出一个结果，保存在中间变量中，最后将中间变量的结果赋给语句中的变量。

7 软件测试方法和结果
输入一组正确的词法和语法的if-else语句，和一组有词法错误和语法错误的if语句。
1. IF m<n THEN
x=m*5;
ELSE
x=n*5;
测试结果如下：

2. IF1 m<n THEN
x=m*5;
ELSE
x=n*5;
测试的结果如下所示：

8 分析本次设计
这次设计大体上还是自己动脑筋去想了，去做了。所以觉得并不是那么的难。关键的步骤就是三个，设计词法分析程序，语法分析程序，及语义分析程序和中间代码的输出程序。词法分析程序由于上次实验做过了，所以这次做起来还是比较的顺手，只是这次的单词设计的比较简单，如关键字就只有三个，if、else和then；用户自定义变量的标识符也没有考虑以下划线开头的部分。
我做的语法分析方法是ll（1）的分析方法，这个方法的关键首先要构造一个if else语句的文法，然后将其转换为ll（1）文法，再根据每个产生式的select集构造预测分析表。然后就是相应的分析。构造一个分析栈和一个输入串队列，栈的初始内容是文法的开始符号和“#”，输入串队列则是输入串的内容。然后根据预测分析表做出相应的推导和匹配动作，最后如果栈里的内容和队列里的内容都是以“#”号的形式匹配的话，这个语句就分析成功。我这次主要只是考虑了表达式的分析过程，而没有把if else then这些关键字的分析过程加入进来。因为我们这次设计也是针对一个特定的语句（如我的if else语句）来进行分析的，所以我就假设所有的输入串当中都在相应的位置有那些关键字了。所以程序做起来就比较简单，容易实现。
而语义分析则是要识别这句话要做什么，并且将其要做的事情用三地址的形式翻译出来。这个对我来说的确有点困难，所以见参考了一下其他同学的设计方法。这个也是这次设计的不足之处，望老师见谅----。

9 参考文献
1． 张素琴、吕映芝、蒋维杜、戴桂兰等．编译原理（第2版）．清华大学出版社．2005年2月参考书：
2． 《程序设计语言编译原理》 国防工业出版社 陈火旺著
3． 《编译原理习题与解析》 清华大学出版社出版社 伍春香著

本科生课程设计成绩评定表
班级：　　　0806　　　姓名：周雪　　 学号：0120810340605
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10

2
设计分析合理性
10

3
设计方案正确性、可行性、创造性
20

4
设计结果正确性
40

5
设计报告的规范性
10

6
设计验收
10

总得分/等级

评语：

注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下为不及格