WHILE循环语句的翻译程序设计

课程设计

题目WHILE循环语句的翻译程序设计学院计算机科学与技术学院

专业计算机科学与技术专业

班级计科1002班

姓名

指导教师

2013 年 1 月9 日

课程设计任务书

学生姓名：专业班级：计算机班

指导教师：蔡菁工作单位：计算机科学与技术学院题目: WHILE循环语句的翻译程序设计（LL（1）法、输出四式）初始条件：

理论：学完编译原理课程，掌握一种计算机高级语言的使用。

实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以其上进行设计。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写

等具体要求）

（1）写出符合给定的语法分析方法的文法及属性文法。

（2）完成题目要求的中间代码四元式的描述。

（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程计。

（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。

（5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：

1 系统描述（问题域描述）；

2 文法及属性文法的描述；

3 语法分析方法描述及语法分析表设计；

4 按给定的题目给出中间代码形式的描述及中间代码序列的结

构设计；

5 编译系统的概要设计；

6 详细的算法描述（流程图或伪代码）；

7 软件的测试方法和测试结果；

8 研制报告（研制过程，本设计的评价、特点、不足、收获与体

会等）；

9 参考文献（按公开发表的规范书写）。

时间安排：

设计安排一周：周1、周2：完成系统分析及设计。

周3、周4：完成程序调试及测试。

周5：撰写课程设计报告。

设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。

设计报告书收取时间：设计周的次周星期一上午10点。

指导教师签名： 2013年 1月 9日

系主任（或责任教师）签名： 2013年 1月 9日

WHILE循环语句的翻译程序设计

（LL(1)法、输出四元式）

1.系统描述

(1) 按照课程设计的要求，写一个能识别while循环语句的文法，通过一

定的变换使它符合预测分析法的要求，然后按照这个文法编写一个程序，该程序能识别输入的语句是否符合while语句的文法，或者能不能通过文法的开始符号推导出该语句。

(2) 该程序应该包括词法分析器，能对输入的语句进行词法分析，然后再

对输出结果。词法分析器应能识别关键字，标示符，常量，操作符等。

(3) 该程序的语法分析器能对输入的语法进行分析，判断输入语句能否满

足while循环语句的文法。通过预测分析方法对语句进行分析，看能否由文法开始符号推导出输入语句。

(4) 该程序的语义分析器就是对分析结果进行输出，要求输出结果是四元

式。

2 文法及属性文法的描述：

2.1 文法描述：

2.1.1 基本概念：

文法是对语言结构的定义与描述。即从形式上用于描述和规定语言构的称为“文法”。

2.1.2 此设计针对的文法为：

消除左递归后的产生式：

S->while(A){B}

A->CDC

D-> ==|>|<|>=|<=

C->EG

G->+EG|-EG|e

E->FH

H->*FH|/FH|e

F->(C)|i

B->i=C

其中e代表为空

2.2 属性文法的描述:

2.2.1属性文法的定义形式:

每个文法符号有一组属性,每个文法产生式A->α有一组产生式

b:=f(c1,c2,……，ck)的语义规则，其中f式函数，b和c1,c2,……，

ck式该产生式文法符号的属性。

2.2.2 此设计题目的属性文法为：

3 词法分析方法描述及词法分析表设计

3.1词法分析定义

词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。程序语言的单词符号一般分为五种：关键字（保留字/基本字）if、while、begin…；标识符：常量名、变量名…；常数,运算符；界限符。

3.2词法分析输出形式

词法分析器输出的单词符号常常表示为二元式：（单词种别，单词符号的属性值）

4．语法分析方法描述及语法分析表设计；

4.1语法分析方法描述

4.1.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(一般在表中用空白表示)。

4.1.3 简单优先文法的操作步骤

求SELECT (A->a）的算法:

(1)若FIRST(a);

(2)若ε∈FIRST(a),则令SELECT（A->a)=FIRST(a),否则求FOLLOW(A),并

令SELECT (A->a）= FIRST(a)∪FOLLOW(A)

对以上产生式求select集合为：

SELECT(S_>w(A){B})={w}

SELECT(A->CDC)={i,C}

SELECT( D->>|<|==|>=|<= ) ={ >|<|==|>=|<=}

SELECT（C->EG）={(,i}

SELECT（G->+EG）={+} SELECT（G->-EG）={-}

SELECT（G->e）={ ）,>=,<=，>,<,},==}

SELECT（E->FH）={(,i}

SELECT(H->*FH）={*} SELECT（H->/FH）={/}

SELECT（H->e）={ +,-,）,>=,<=，>,<,},==}

SELECT（F->(C)）={(}

SELECT（F->i）={i }

SELECT（B->i=C）={i}

根据select集得到预测分析表

分析模型：

5 中间代码的描述:

5.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

5.2本次设计的中间代码：

本次程序的中间代码是根据一定的语义规则写出的：

F

代码结构：

S．begin ：

E.ture ：

to E.false ：

本次设计最终应产生的3地址形如：

[1] (*,b,c,t1)

[2] (*,b,,d,t2)

[3] (+,t1,t2,t3)

[4] (:=,t3,-,t4)

6 简要的分析与概要设计

6.1文法的分析设计

(1) 在这次课程设计中,第一步就是要设计一个良好的健壮的文法,这就要求对简单优先分析方法要有较深地理解.首先文法应该满足3.1.2目中的文法的限制.

(2) 另外要保证文法完全没有问题是不可能的,我是在建立优先关系矩阵后,选取一个简单的例子按照最初的简单优先关系矩阵来归约测试,看看能不能归约成文法的开始符,如果不能则说明文法有问题再慢慢地修改.不断完善从而得到

最终的文法.

6.2词法的分析设计

(1) 词法分析的主要任务是从左到右一个字符一个字符地读入源程序,对构成源程序的字符流进行扫描和分解,从而识别出一个个的单词.

(2) 词法分析因为在平时实验已经做过,所以实现较简单,但是针对此次试验是对while循环语句的翻译,我把相应的存放关键字和限制符的数组相应的只放与本次实验有关的内容进行稍微的削减,这样既可以把输入的while循环语句分析成为一个个具有独立意义的单词并且又相应的类型说明,而且还可以简化代码,从而提高分析效率.

6.3语法的分析设计

(1) 语法分析的任务就是判断输入的符号串是不是给定文法的一个句子.在此次课程设计中,语法分析的重点是由文法开始符号如何推导,就是判断能否由文法开始符号推导出输入符号串.

(2) 在设计中,按照预测分析法的步骤对文法开始符号进行推导,如果能够推导产生输入符号串,则说明该字符串符合设计的文法,否则说明输入的字符串不合法.

6.4语义的分析设计

(1) 语义分析的主要任务是审查源程序有无语义错误,为代码生成阶段收集类型信息.对于本课程设计来说,就是把输入的符合文法规定的字符串转换翻译成有具体意义的三地址形式输出来.

(2) 在设计中,我觉得这一模块的实现相对要困难一些.while循环语句由两种不同的语句翻译,要分别对待,即赋值语句的翻译和布尔表达式的翻译.前者的实现相对较容易,后者设计时要用到拉链算法中的合并和回填(参见2．3属性文法的描述).

6.5总体的分析设计

(1) 总体设计的主要任务是把词法分析、语法分析、语义分析这几个模块有

机的结合起来形成一个完整的while循环语句的翻译器.

(2) 词法分析是从一个文件中读入字符,经过处理输出一个文件内容是一个个单词;而语法分析是从词法分析的输出结果中读出一个个单词并进行归约,如果规约不成功,则显示错误提示,如果归约成功,输入的字符串是合法的,那么就由语义分析器来输出输入符号串的三地址表示形式.从而完成翻译工作.

7 详细的算法描述

7.1主要程序流程图

7.1.1 程序总流程图

图6.1.1程序总流程图

7.1.2 词法分析流程图

图6.1.2词法分析流程图

7.1.3 语法语义分析流程图

图6.1.3语法语义分析流程图8.程序伪代码

8.1词法分析程序

void lexcal(){

infile.open("input.txt",ios::in);

while(infile.fail()){

显示出错处理;

}

outfile.open("wordoutput.txt",ios::out);

先读一个字符;

while(读入的字符不为文件结束符) {

if(读入标识符和关键字){

对应的词法分析子程序;

}

if(读入无符号整数){

对应的词法分析子程序;

}

if(读入运算符){

对应的词法分析子程序;

}

if(读入界限符){

对应的词法分析子程序;

}

if(读入字符串常量){

对应的词法分析子程序;

}

}//while

}//lexcal

8.2语法分析程序

建立一个链表strList和分析栈destList,其中strList用来存放输入代码序列，而destList存放待推导的非终结符串。取strList表头元素和destList的栈顶元素，查找预测分析表，得到要推导得到的产生式右部，然后逆序压到destList栈中，如果查表为空，则表示出错，返回。检查strList的队首元素与destList的栈顶元素是否相同，把相同的元素出队，出栈。判断destList栈中是否仅剩“#”，是则表示分析完成。

8.3输出四元式

采用了两个栈，一个操作符栈optr，一个操作数栈opnd事先存储各运算符之间的栈内与栈外优先级

(1)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。

(2)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接压入opnd栈。

(4)如果不是数字，该字符则是运算符，此时需比较优先关系。

做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符θ从栈中弹出，将该字符入栈。从opnd栈中弹出两个操作数a1和a2，调用Expression(string m,string n,string k,string s)，形成四元式。

(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理

9 实验结果

9.1测试用例

9.2词法分析结果

9.3语法分析和四元式结果

10.心得体会

这次的课程设计使我无论在理论基础知识上,动手实践方面,还是在心理素质方面都得到了锻炼和提高。首先是基础知识方面，由于授课学时的限制和自己学习中的疏忽，遗漏了一些比较细小的知识点，例如：数组下标的问题，和栈使用的时候的栈顶指针指向问题，问题虽然小，但是在运行程序时，这种错误的确是比较具有隐蔽性的，也比较困扰人的。

其次是在上机实验方面，在平时的学习中，学习的是理论知识，所以在进行课程设计的时候，发现一定的难度，首先是文件的预定义包含，在程序中用到的函数不清楚是在哪个预定义的函数中，因此在编译的时候总会出现“未定

义的函数”的错误提示。

其次是设计的思想，由于语句相对比较多，很多函数的组合没有处理好，经常会出现函数类型不匹配的错误。由于程序比较长，语句的包含关系的搞错和匹配问题也是编译时的瓶颈。

总之，在这次课程设计后我的理论知识，动手动脑能力，和心理素质都有了一定的提高，经过这次实验，我基本明白了自己做一个课题的实验过程，从中也学到很多东西，这是以前按教科书上照搬照套的实验得不到的。我明白了自己以后还要继续努力，在这里，我也要感谢我的同学和老师，正是他们帮助我解决了课程设计中遇到的一个又一个难题。

附录源码

#include

#include

#include

#include

#include

#include

#include "ctype.h"

#include

using namespace std;

char save[20];

int total=1;

char

*sum[10]={"int","char","bool","do","while","if","else","for","switch","case"}; FILE *pWrite=fopen("cout.txt","w");

FILE *pRead=fopen("cpp.txt","r");

struct expression { //存储四元式

string symbol; //操作符

string num1; //第一个操作数

string num2; //第二个操作数

string result; //结果变量

};

list expList;

void produceExp();

long alpha(char c1,long pos)//标识符分析函数

{

int i,j=0;

long curpos2;

char *opp,ch;

i=0;

memset(save,0,20);

save[i++]=c1;

fseek(pRead, pos, SEEK_SET);

while(fgets(&ch,2,pRead)&&!feof(pRead)&&isalnum(ch))

{ save[i++]=ch; }

opp=save;

curpos2= ftell(pRead);

for(i=0;i<10;i++)/*把字母与关键字表核对，如果是关键字就设置j=1*/ if(!(strcmp(opp,sum[i])))/*比较两个字符串*/

{

fprintf(pWrite,"W\n"); /*识别关键字*/

j=1;

}

if(j==0)

fprintf(pWrite,"%s\n",opp); /*识别标识符*/

return curpos2;}

long digit(char c1,long pos)//无符号数识别函数

{

long curpos3;

int N=0,P=0,j=0,isint=1;

int e=1,d;

float t;

char ch;

fseek(pRead, pos-1, SEEK_SET);

while(fgets(&ch,2,pRead)&&!feof(pRead)&&isdigit(ch))

{

d=atoi(&ch);

N=N*10+d;

}

curpos3=ftell(pRead);

if(ch=='.')

{

fseek(pRead, curpos3, SEEK_SET);

fgets(&ch,2,pRead);

isint=0;

if(!isdigit(ch))

{

cout<<"数字输入有误！"<

else

{

fseek(pRead, curpos3, SEEK_SET);

while(fgets(&ch,2,pRead)&&isdigit(ch))

{

d=atoi(&ch);

N=N*10+d;

j++;

}

}

curpos3=ftell(pRead);

}

if(ch=='e')

{

fseek(pRead, curpos3, SEEK_SET);

fgets(&ch,2,pRead);

if(ch=='-')

e=-1;

if(ch=='+'||ch=='-')

{

fseek(pRead, curpos3+1, SEEK_SET);

fgets(&ch,2,pRead);

}

curpos3=ftell(pRead);

if(isdigit(ch))

{

d=atoi(&ch);

P=P*10+d;

}

fseek(pRead, curpos3, SEEK_SET);

while(fgets(&ch,2,pRead)&&!feof(pRead)&&isdigit(ch))

{

d=atoi(&ch);

P=P*10+d;

}

curpos3=ftell(pRead);

t=N*pow(10,e*P-j);

fprintf(pWrite,"%0.2f\n",t);

}

else

{

t=N*pow(10,e*P-j);

fprintf(pWrite,"%0.2f\n",t);

}

return curpos3;

}

int cifafenxi()

{

char ch;

long curpos;

if(pRead==NULL)

{

cout<<"Can't open input file!\n";

return -1;

}

while(fgets(&ch,2,pRead)&&!feof(pRead))

{

if(ch==' '||ch=='\n'||ch=='\t')continue;

if(isalpha(ch))

{

curpos = ftell(pRead);

curpos=alpha(ch,curpos);

fseek(pRead, curpos-1, SEEK_SET);

}

else if(ch==';')

fprintf(pWrite,"%c\n",ch);

else if(ch=='/')

fprintf(pWrite,"%c\n",ch);

else if(ch=='*')

fprintf(pWrite,"%c\n",ch);

else if(ch=='(')

fprintf(pWrite,"%c\n",ch);

else if(ch==')')

fprintf(pWrite,"%c\n",ch);

else if(ch=='{')

fprintf(pWrite,"%c\n",ch);

else if(ch=='}')

fprintf(pWrite,"%c\n",ch);

else if(ch=='=')

{

fgets(&ch,2,pRead);

if(ch=='=') fprintf(pWrite,"==\n");

else { fprintf(pWrite,"=\n");curpos = ftell(pRead);fseek(pRead, curpos-1, SEEK_SET);}

}

else if(ch=='+')

fprintf(pWrite,"%c\n",ch);

else if(ch=='-')

fprintf(pWrite,"%c\n",ch);

else if(ch=='>')

{

fgets(&ch,2,pRead);

if(ch=='=') fprintf(pWrite,">=\n");

else { fprintf(pWrite,"<\n");curpos =

ftell(pRead);fseek(pRead, curpos-1, SEEK_SET);}

}

else if(ch=='<')

{

fgets(&ch,2,pRead);

if(ch=='=') fprintf(pWrite,"<=\n");

else { fprintf(pWrite,"<\n");curpos = ftell(pRead);fseek(pRead, curpos-1, SEEK_SET);}

}

else if(isdigit(ch))

{

curpos = ftell(pRead);

curpos=digit(ch,curpos);

if(curpos==-1)

return -1;

fseek(pRead, curpos-1, SEEK_SET);

}

total++;

}

cout<<"词法分析完成！"<

fclose(pWrite);

fclose(pRead);

}

string getAction(string ter,string nonter)

{

// cout<

string

terminal[18]={"W","(",")","i","=","+","-","*","/",">","<",">=","<=","==","{","} ","#",";"};

string nonterminal[9]={"S","A","D","C","G","E","H","F","B"};

string action[17][9];

action[0][0]="W(A){B}";

action[1][1]=action[1][3]="CDC";

action[2][9]=">"; action[2][10]="<"; action[2][11]=">="; action[2][12]="<="; action[2][13]="==";

action[3][1]=action[3][3]="EG";

action[4][2]=action[4][9]=action[4][10]=action[4][11]=action[4][12]=action[ 4][13]=action[4][15]="e";

action[4][5]="+EG";action[4][6]="-EG";

action[5][1]=action[5][3]="FH";

action[6][2]=action[6][5]=action[6][6]=action[6][9]=action[6][10]=action[6] [11]=action[6][12]=action[6][13]=action[6][15]="e";

action[6][7]="*FH"; action[6][8]="/FH";

action[7][1]="(C)"; action[7][3]="i";

action[8][3]="i=C;";