WHILE循环语句的翻译程序设计(LL(1)法、输出三地址表示).doc

武汉理工大学〈〈WHILE语句的翻译分析LL（1）法、输出三地址表示〉〉课程设计说明书
课程设计任务书
题 目: WHILE语句的翻译分析程序设计（LL（1）法、输出三地址表示）
初始条件：
理论：学完编译课程，掌握一种计算机高级语言的使用。
实践：计算机实验室提供计算机及软件软件环境。

要求完成的主要任务（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1) 写出符合LL（1）法的文法及属性文法。
2) 完成题目要求的中间代码三地址表示的描述。
3) 写出LL（1）法的思想，完成语法分析和语义分析程序设计。
4) 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。
5) 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：
1 问题描述；
2文法及属性文法的描述；
3语法分析方法及中间代码形式的描述；
4简要的分析与概要设计；
5详细的算法描述；
6给出软件的测试方法和测试结果；
7设计的特点、不足、收获与体会。

时间安排：
设计安排一周：周1、周2：完成程序分析及设计。
周3、周4：完成程序调试及测试。
周5：程序验收和撰写课程设计报告。
设计验收安排：18周的星期五第3节课到实验室进行上机验收。
设计报告书收取时间：19周的星期四下午。

指导教师签名： 年 月 日
系主任（或责任教师）签名： 年 月 日

目 录

1 问题描述…………………………………3

2 文法及属性文法的描述…………………3

3 语法分析方法及中间代码形式的描述…4

4 简要的分析与概要设计…………………7

5 详细的算法描述…………………………8

6 软件的测试方法和测试结果…………13

7设计的特点、不足、收获与体会………16

WHILE语句的翻译分析程序设计
----LL（1）法、输出三地址表示

1 问题描述：
1.1 能够写出一个while-do语句，此语句符合LL（1）的文法。
1.2 构造词法分析程序对while-do语句进行词法分析。
1.3构造语法分析程序对while-do语句进行语法分析，判断语法正确性。
1.4 运行程序，要求有正确的语义输出（3地址码）。
2 文法及属性文法的描述：
2.1 文法描述：
2.1.1 基本概念：
文法是对语言结构的定义与描述。即从形式上用于描述和规定语言
构的称为“文法”。
定义：文法G=（VN，VT，P，Z）
VN ：非终结符号集
VT ：终结符号集
P：产生式或规则的集合
Z：开始符号（识别符号） Z∈VN
其中:
A.产生式：产生式是一个有序对(U, x), 通常写为:
U ::= x 或U ® x； | U| = 1 |x| ³ 0
B.非终结符号：出现在产生式的左部,且能推出符号或符号串的
那些符号。其全体构成非终结符号集，记为VN 。
C.终结符号：不出现在产生式的左部,且不能推出符号或符号串
的那些符号。其全体构成终结符号集，记为VT 。
2.1.2 此设计针对的文法为：
S->while E do A
E->id1>id2| id1=id2| id1<id2
A-> id1= id2
(id1，id2代表标识符)
2.2 属性文法的描述:
2.2.1 属性文法的定义形式:
每个文法符号有一组属性,每个文法产生式A->α有一组产生式b:=f(c1,c2,……，ck)的语义规则，其中f式函数，b和c1,c2,……，ck式该产生式文法符号的属性。
2.2.2 此设计题目的属性文法为：
产 生 式
属 性 文 法（ 语 义 规 则 ）

S->while E do A
S．begin:=newlable;
E.true:=newlable;
E.false:=S.next;
A.next:=S.begin;
S.code:=gen(S.begin‘:’||E.code||
Gen(S.ture‘：’)||A.code||gen(‘goto’S.begin);
E->id1>id2| id1=id2| id1<id2
E.place:=newtemp;
E.code:=B1.code||B2.code||
gen(E.place':='id1.place'>'id2.place)
||gen(E.place':='id1.place'='id2.place)
||gen(E.place':='id1.place'<'id2.place)
A-> id1= id2
A.place:=newtemp;
A. code:= id1.code|| id2.code||
gen(A.place':=' id1.place'=' id2.place

3语法分析方法及中间代码形式的描述；
3.1 语法分析方法:
3.1.1本次设计采用LL（1）分析 ：
预测分析方法概述：
所谓的LL（1）方法是在实现时用到一个LL（1）分析钜阵和一个分析栈以及预测分析程序。
分析钜阵的元素M[A，a]中的下标A为非终结符，a为终结符或句子的结束标记“#”，钜阵元素M[A，a]的内容为一条关于A的产生式。它表明当用非终结符A向下推而当输入符a时，所应该采用的后选式。当钜阵元素为空时，则表示用A往下推导时遇到了不应该出现的符号，即A与a不能匹配，因此应该出错处理。
在构造预测分析表时，对每个终结符或“#”号用a表示，则若a∈SELECT（A->a)。令M[A，a]= A->a(一般为了简化,取M[A，a]= a)把所有的无定义的M[A，a]标上ERROR(一般在表中用空白表示)。
求SELECT (A->a）的算法:
(1) 若FIRST(a);()
(2)若ε∈FIRST(a),则令SELECT（A->a)=FIRST(a),否则求FOLLOW(A),并令SELECT (A->a）= FIRST(a)∪FOLLOW(A)
分析模型：

3.1.2 此程序预测分析方法：
此设计为非左递归while-do文法,应采用自上而下的预测分析方法。在此设计中，产生式只到E->id1>id2| id1=id2| id1<id2，A-> id1= id2，对A只有一种产生式而在输入串中的终结符a，b……等在程序中用id代替了，正好做到了输入串和符号栈的匹配抵消，因此简化了预测分析表的构造，对于E来说有3个侯选式，在本程序中通过函数firstset（）来判断应该选哪个产生式，但是firstset（）是依赖Token2数组来判断的，没有完全摆脱掉数组的限制，因此也是本程序的不足之处。
3.2 中间代码的描述:
3.2.1中间代码概述：
本此设计要求使用的是3地址的中间代码,3地址代码是由下面一般形式构成的语句序列: x:=y op z;
其中x,y,z为名字,常数或编译时产生的临时变量;op代表运算符号如标点,浮点运算符号等等。每个语句的右边只能有一个运算符。
表达式x + y * z翻译成的三地址语句序列是：
t1 := y * z
t2 := x + t1
常用的三地址语句有：
赋值语句x := y op z， x := op y， x := y
无条件转移goto L
条件转移if x relop y goto L
过程调用param x 和call p , n
过程返回 return y
索引赋值x := y[i]和 x[i] := y
地址和指针赋值x := &y，x := *y和*x := y
3.2.1本次设计的中间代码：
本次程序的中间代码是根据一定的语义规则写出的：

T
while A do E

F

代码结构：
S．begin ： E．code to E.ture
E.ture ： A．code to E.false
goto S.begin
to E.false ： ……
本次设计最终应产生的3地址形如：
L0: if Token2[2].b >Token2[4].b goto L2
L1: if not goto L4
L2: Token2[6].b:= Token2[8].b
L3: goto L0
L4:
4 简要的分析与概要设计：
4.1 简要的过程分析：
在词法分析部分，本次设计主要是通过Save(char* p,int x)将a
[ProgramLength]中通过函数GetChr()获取的单词符号提压入 Token栈，用函数Getcode()来识别Token栈中的单词符号。
在语法分析部分，用Ecode来放代码，当Ecode栈顶有非终结符号的时候，将非终结符号用pop（）函数出栈，并依据函数pabduanESA()判别Token栈顶的非终结符号，对非终结符号进行推导，将推导出的符号分别用函数InputG()，InputA()，InputE1()，InputE2()，InputE3()，逆序压入Ecode栈中，再对栈顶元素进行判断，并通过函数EStrcmp()识别关键字while和do，识别的同时将关键字放入ADDL L结构体，并且此函数可以判断语法分析是否结束。在进行非终结符识别的时候，函数体内有相应的对应不同非终结符的产生式的输出，即产生式右部的符号推进栈的同时做产生式相应的语义动作，从而实现语法制导翻译的目的，最后将语法的分析结果输出，最终以3地址表示出来。
在语义输出部分，因为在程序中已经将标识符替换成id，所以应该建立一个数组Token2[i]把Token[i]中的标识符保存下来，再通过cout语句将3地址输出。
4.2 设计流程图：
4.2.1词法分析部分简要图：

4.2.2语法分析部分简要图：

其中I代表是，T代表否
5 详细的算法描述:
5.1预定义声明部分：
包括文件的包含和常数的定义
5.2 词法分析部分：
思想概述：通过GetProgram() 函数将源程序中的逐个字符放到数组a中，并且通过函数GetChr() 将数组a中的字符逐个读出，并且在此过程中识别出单词符号，并调用函数save()，将单词符号放入Token中，再调用函数Getcode()为Token中的不同的符号赋予不同的种别编码,最后将单词符号和种别编码输出。词法分析成功！
……………………………………词法分析函数声明……………………………………
typedef struct
{……次结构体用于识别关键字while，do………}ADDL;
typedef struct
{ ……结构体用于存放单词符号…………}link;
link Token[MaxiTokenNumer]; / /存放单词符号
link Token[MaxiTokenNumer]; //拷贝单词符号
void GetProgram(); //把源程序装入数组a
char GetChr(); //将数组a中的元素读出
int Judge(char& chr); //用于判断'\0'
int IsLetter(char c); //用于判断是否为字母
void Input(char* p,char c,int& nx); //标识符关键字入指针p指向的数组第nx+1个元素
void Save(char* word,int x); //将关键字或标志符或算符装入Token
void Getcode(); //为不同的输入符号赋予不同的种别编码
char word[MaxiWordLength]; //声明临时数组
………………………………词法分析函数体……………………………………
int Wordanalyze()
{……GetProgram()
{ …… 把源程序装入数组a………}
while((chr=GetChr())!='\0')
{if(!(Judge(chr)))
{break;} //跳过空格和回车取元素
if(IsLetter(chr))
{ jieshu=1;
while(IsLetter(chr))
{…………将关键字，标识符装入数组word………… }
if(chr=='>' || chr=='='||chr=='<')
nLength=nLength-1; //指向算符
word[x]='\0';
Save(word,x); } //将算符装入Token
else if(chr=='>') //将'>'装入Token
{Input(word,chr,x);
word[x]='\0';
Save(word,x);}
else if(chr=='=') //将'='装入Token
{ Input(word,chr,x);
word[x]='\0';
Save(word,x);}
else if(chr=='<') //将'<'装入Token
{Input(word,chr,x);
word[x]='\0';
Save(word,x);}
else
{printf("输入出错!\n"); / /出错处理
jieshu=0;
return 0;}} //这个函数的作用是将输入符号放入Token
if(jieshu==1) //词法分析结束
{ Getcode();
………… 为存放在Token中的不同的单词符号配置不同的种别编码并输出，并且将单词符号拷贝到Token2数组中，以便在语法分析结束后仍能输出具体的标识符………………
}
5.3 语法分析部分：
思想概述：建立两个栈Token和Ecode，Token相当于输入串，Ecode相当于符号栈。将Ecode栈顶元素通过函数Pop()出栈，并且根据Token栈顶的符号，调用函数firstset()选择恰当的产生式，将推倒出的符号再逆着压入Ecode，并同时输出对应的产生式。当Ecode栈顶出现#符号时，语法分析成功！
………………………………语法分析部分函数声明…………………………
void Pop(); //出栈
void InputS(); //识别出S时，将其推倒出的单词符号逆着压栈
void InputE1(); //识别出E1时，将其推倒出的单词符号逆着压栈
void InputE2(); //识别出E2时，将其推倒出的单词符号逆着压栈
void InputE3(); //识别出E3时，将其推倒出的单词符号逆着压栈
void InputA(); //识别出A时，将其推倒出的单词符号逆着压栈
int firstset(); //求初始符
int panduanESA(); //识别非终结符
int EStrcmp(); //识别关键字
………………………………语法分析部分函数体…………………………
int ExpressionAnalyse() //语法分析
{printf("\n语法分析得出：\n");
strcpy(Ecode[Top++],"#"); //将#压栈
strcpy(Ecode[Top++],"S"); //将S压栈
int FLAG=1; //语法分析未结束标志
while(FLAG)
{int f1=0;
f1= panduanESA ();
if(f1==1)
{……输出S->while E do A，并将A do E while压栈 …… }
else if(f1==2)
{……当栈顶元素为E时……
if(f3==1)
{ ……输出 E->id>id，将id > id压栈……
}
else if(f3==2)
{…………输出E->id=id，将id = id压栈…… }
else if(f3==3)
{…………输出E->id<id，将id < id压栈… }
}
else if(f1==3) //Ecode栈顶元素为A时
{ …………输出A->id<id，将id < id压栈… }
else
{int f2=0;
f2=EStrcmp();
if(f2==1) //识别出关键字
{ Pop();
nID=nID+1; }
else if(f2==3) //识别出#，分析结束
{ cout<<endl<<"语法正确!"<<endl;
FLAG=0;
return 1; }
else
{ cout<<endl<<"语法错误啦!"<<endl;
FLAG=0;
return 0； } } }
getch();}
5.4 语义输出部分：
思想概述：输出文法，在词法和语法分析都成功的基础上，再根据识别的是while或是do，输出3地址。
void main(){…………输出所用的文法…………
if(Wordanalyze()) //词法分析成功
{if(ExpressionAnalyse()) //语法分析也成功
{int i;
L[nL].add=nadd;
for(i=0;i<nL;i++)
{if(strcmp(L[i].str,"while")==0) //输出3地址
{ cout<<endl;
cout<<"正确的语义输出为:"<<endl;
cout<<"L0: if "<<Token2[2].b<<" > "<<Token2[4].b<<" goto L2"<<endl;
cout<<"L1: if not goto L4"<<endl; }
else
{cout<<"L2: "<<Token2[6].b<<":="<<Token2[8].b<<endl;
cout<<"L3: "<<"goto L0"<<endl;
cout<<"L4: "<<endl;
}
}
}
}
}

6 软件的测试方法和测试结果：
6.1软件的测试方法：
本次课程设计在运行时，按照while语句的语法要求输入符合条件的语法，G->while E do A，其中G为初始符号，E应该是两个符号的ASCII码值的大小的判断，而A应该是一个赋值语句。最后语句应以#结束。
6.2 测试结果：

6.2.1测试用例1（词法，语法都正确）：

测试用例1分析：
词法部分：因为本此输入的单词符号都是符合词法分析程序定义的符号类别（ID从1到6），所以能够得到正确的词法分析结果。
语法部分：因为次此的输入a>b是E的正确的推导,并且A推导出的是一个赋值语句a=d,符合本程序定义的while-do语法规则,所以语法正确。
语义输出：在识别非终结符号的时候将与其相对应的产生式输出（相应的语义动作），实现了语法制导翻译，最后将其以3地址的形式输出。

6.2.2 测试用例2（词法错误）：

测试用例2分析：
因为符号%和@不属于本程序词法分析部分定义的正确的输入形式,即Wordanalyze()中将@和%定义为错误的输入,所以在词法分析的时候输入的语句没有通过词法分析。
本次的设计主要是针对字母，算符，关键字while和do。
6.2.3 测试用例3（语法错误）：
见下页

测试用例3分析：
词法分析部分：此次的输入将while误输入为whill，因此whill只能作为标识符被识别，而不能够作为关键字被识别，因此可以通过词法分析。
语法分析部分：在程序中一开始就将开始符号S压入栈中，因此能够识别S，并在识别S的时候把S所对应的产生式输出，因此运行结果中有S->while E do A，但是当识别出S后把S出栈，把A，do，E，whill依次压入栈中以后，在识别栈顶元素whill时，
因为whill不是关键字，所以语法错误，最终不能通过语法分析。
7 设计的特点、不足、收获与体会：
7.1 设计的特点：
此次设计的特点是在语法分析的时候当识别出一个非终结符，就将其对应的产生式输出，可将其看做为相应语义动作，并且在3地址码输出的时候，通过Token2这个数组把输入的标识符保留，这样可以避免在把标识符替换为id的时候导致的标识符的丢失。
7.2 设计的不足与改进：
7.2.1（调试的程序为改进后的）没改进之前不能对“<”条件进行判断
改进前的代码与运行界面：
代码: if(chr=='>' || chr=='=')
nLength=nLength-1; //指向算符
word[x]='\0';
Save(word,x); } //将关键字或标志符或算符装入Token
else if(chr=='>') //将'>'装入Token
{ Input(word,chr,x);
word[x]='\0';
Save(word,x); }
else if(chr=='=') //将'='装入Token
{ Input(word,chr,x);
word[x]='\0';
Save(word,x); }
else
{ printf("输入出错!\n"); //出错处理
jieshu=0;
return 0;}
界面:

改进后的代码与运行界面：
代码:（带下划线的为改动后的不同之处）
if(chr=='>' || chr=='='||chr=='<')
nLength=nLength-1; //指向算符
word[x]='\0';
Save(word,x); //将关键字或标志符或算符装入Token
else if(chr=='>') //将'>'装入Token
{ Input(word,chr,x);
word[x]='\0';
Save(word,x); }
else if(chr=='=') //将'='装入Token
{ Input(word,chr,x);
word[x]='\0';
Save(word,x); }
else if(chr=='<') //将'<'装入Token
{ Input(word,chr,x);
word[x]='\0';
Save(word,x); }
else
{ printf("输入出错!\n"); //出错处理
jieshu=0;
return 0; }
运行界面：

7.2.2（调试的程序为改进后的）没改进之前不能将具体的标识符输出
改进前的代码与运行界面：（带下划线的为改动后的不同之处）
代码：for(i=0;i<nL;i++)
{if(strcmp(L[i].str,"while")==0)
{ cout<<endl;
cout<<"正确的语义输出为:"<<endl;
cout<<"L0: if "<<Token [2].b<<" > "<<Token [4].b<<" goto L2"<<endl;
cout<<"L1: if not goto L4"<<endl;
}
else {
cout<<"L2: "<<Token[6].b<<":="<<Token[8].b<<endl;
cout<<"L3: "<<"goto L0"<<endl;
cout<<"L4: "<<endl;
} } } } }
界面如下：

改进后的代码与运行界面：
说明：改进是在把具体的标识符替换成id之前将其拷贝到Token2中，这样就可以将具体的标识符输出。
代码：for(i=0;i<nL;i++)
{if(strcmp(L[i].str,"while")==0)
{ cout<<endl;
cout<<"正确的语义输出为:"<<endl;
cout<<"L0: if "<<Token2 [2].b<<" > "<<Token 2[4].b<<" goto L2"<<endl;
cout<<"L1: if not goto L4"<<endl;
}
else {
cout<<"L2: "<<Token2[6].b<<":="<<Token2[8].b<<endl;
cout<<"L3: "<<"goto L0"<<endl;
cout<<"L4: "<<endl;
} } } } }
界面：

7.2.3（调试的程序为改进后的）不能识别算符：
改进前的代码与运行界面：
代码：
if(IsLetter(chr))
{ jieshu=1;
while(IsLetter(chr))
{Input(word,chr,x); //是字符就将其装入数组word
chr=GetChr(); }
word[x]='\0';
Save(word,x); }//将关键字或标志符或算符装入Token
运行界面：

改进后的代码与运行界面：（带下划线的为改动后的不同之处）
说明：因为改进前没有if(chr=='>' || chr=='='||chr=='<')nLength=nLength-1; 每次执行getchr（）函数后指针都会向后跳一个位置，如果不将nlength减1，那么算符就会被忽略。因此改动前当识别出E，并将E对应的产生式输出以后，在识别a>b时,因为识别不出>,所以会出现语法的错误。
代码：if(IsLetter(chr))
{ jieshu=1;
while(IsLetter(chr))
{Input(word,chr,x); //是字符就将其装入数组word
chr=GetChr();
}
if(chr=='>' || chr=='='||chr=='<')
nLength=nLength-1; //指向算符
word[x]='\0';
Save(word,x); //将关键字或标志符或算符装入Token
}
界面：

7.3心得体会:
这次的课程设计使我无论在理论基础知识上,动手实践方面,还是在心理素质方面都得到了锻炼和提高。
首先是基础知识方面，由于授课学时的限制和自己学习中的疏忽，遗漏了一些比较细小的知识点，例如：数组下标的问题，和栈使用的时候的栈顶指针指向问题，问题虽然小，但是在运行程序时，这种错误的确是比较具有隐蔽性的，也比较捆饶人的。
在本次的程序中，开始时候不能识别算符，即上述的7.2.3问题，这就属于数组下标指向问题，后来在程序中添加了代码if(chr=='>' || chr=='='||chr=='<')nLength=nLength-1; 使指针前移一个位置，运行结果就可输出算符了。
其次是在上机实验方面，在平时的学习中，学习的是理论知识，所以在进行课程设计的时候，发现一定的难度，首先是文件的预定义包含，在程序中用到的函数不清楚是在哪个预定义的函数中，因此在编译的时候总会出现“未定义的函数”的错误提示。
其次是设计的思想，由于语句相对比较多，很多函数的组合没有处理好，经常会出现函数类型不匹配的错误。由于程序比较长，语句的包含关系的搞错和匹配问题也是编译时的瓶颈。
在心理素质方面也使自己得到了锻炼，在面对困难的时候，学会要把问题逐步的细小化，给自己拟定在不同时期要功克不同的难点的计划，在困难面前不能轻言放弃。
这段时间的设计，我深刻的体会到编程的辛苦，一个优秀的程序在设计的过程中，不仅要求程序员要有清晰的思路更要有完成枯燥工作的毅力。
要结合面对的问题去图书馆找资料、上网去搜索。要静下心来读书，书读百遍，其义自现，遇到看不懂的地方，不要在那儿阻塞太久，实在看不懂就咕噜吞下去，等到看完这一章或者这一节再回过头来学习，学习就是一个往返的曲线！
心要细，天下大事，必作于细，要耐心对逐条语句进行分析，要勤动脑。要把每次的收获的点点滴滴都牢记于心，不可以不屑于小的收获，懂得不积跬步，无以至千里；不积小流，无以成江海的道理。即使再小的问题，再小的收获都要牢记，否则会对日后的编程造成阻碍。
要有真理必胜的科学理念，坚持真理，要学会承认和改进自己的错误与不足，学会否定自己，只有这样我们才能不断的提高。
要学会帮助他人，勤与与别人交流经验，无论是对方还是自己都能得到提高。
总之，在这次课程设计后我的理论知识，动手动脑能力，和心理素质都有了一定的提高，经过这次实验，我基本明白了自己做一个课题的实验过程，从中也学到很多东西，这是以前按教科书上照搬照套的实验得不到的。我明白了自己以后还要继续努力，在这里，我也要感谢我的同学和老师，正是他们帮助我解决了课程设计中遇到的一个又一个难题。
最后感谢指导老师抽出时间为我们验收，我期待下次课程设计的到来！

第 23 页 共 23 页