IFELSE条件语句的翻译程序设计递归下降法输出四元式Word下载.docx
《IFELSE条件语句的翻译程序设计递归下降法输出四元式Word下载.docx》由会员分享，可在线阅读，更多相关《IFELSE条件语句的翻译程序设计递归下降法输出四元式Word下载.docx（25页珍藏版）》请在冰点文库上搜索。
（5）设计报告格式按附件要求书写。
课程设计报告书正文的内容应包括：
1系统描述（问题域描述）；
2文法及属性文法的描述；
3语法分析方法描述及语法分析表设计；
4按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；
5编译系统的概要设计；
6详细的算法描述（流程图或伪代码）；
7软件的测试方法和测试结果；
8研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；
9参考文献（按公开发表的规范书写）。
时间安排：
设计安排一周：
周1、周2：
完成系统分析及设计。
周3、周4：
完成程序调试及测试。
周5：
撰写课程设计报告。
设计验收安排：
设计周的星期五第1节课开始到实验室进行上机验收。
设计报告书收取时间：
设计周的次周星期一上午10点。
指导教师签名：
2011年12月23日
系主任（或责任教师）签名：
3、语法分析方法描述及语法分析表设计..........................4
3.2语法分析表设计.........................................5
4、按给定的题目给出中间代码形式的描述及中间代码序列的结构设计.......5
5、编译系统的概要设计.......................................5
10、附加代码................................................11
1、系统描述（问题域描述）
本次实验使用windowsXP的visualC++软件，利用递归下降法实现IF-ELSE的条件语句的翻译程序设计，输出四地址表示，程序只能处理简单的布尔表达式和最简单的赋值语句，布尔表达式能够实现大于和小于的识别，也能处理关系运算符>
=和<
=的布尔表达式。
程序的词法分析的结果和用到的文法是显示到dos界面上，而语法分析的结果则保存在1.txt中，打开它就知道语法分析的结果和中间代码的输出了。
2.文法及属性文法的描述；
2.1文法的描述:
if->
XthenYelseY;
X->
id<
id;
id>
=id;
Y->
id=id；
2.2属性文法的描述：
属性文法（也称属性翻译文法）是Knuth在1968年首先提出的。
它是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“特性”（称为属性）。
产生式
语义规则
S->
ifEthenS1elseS2
E.true:
=biaozhi++;
E.fals:
=ebiaozhi++;
S1.next:
=S.next;
S2.next:
S.code:
=E.cod||
gen（E.true‘:
’）||S1.code||
gen（‘goto’S.next）||
gen（E.false‘:
’）||S2.code
3.1语法分析方法描述：
在程序语言的语法定义中有许多采用递归定义。
我们在对它进行语法分析时，编制的处理程序也采取递归的方式，可使其结构简单易读。
但由于频繁地调用子程序大大地降低了分析速度。
递归下降法的主要思想是：
对每个非终结符按其产生式结构写出相应语法分析子程序。
因为文法递归相应子程序也递归，子程序的结构与产生式结构几乎一致。
所以称此种方法称为递归子程序法或递归下降法。
程序是以一个个单词的形式向后读取，读取到if之后就开始执行E的递归子程序，程序根据布尔表达式的真假，进而选择执行相应的分支，即如果布尔表达式为真，就执行then后面的赋值语句，如果布尔表达式为假，就执行else后面的赋值语句，递归子程序E分别赋予布尔表达式真和假不同的地址，并将跳转相应的信息写到处理四元式的结构体数组中去，E执行完以后，回到S中继续执行后面的，读取到then之后，就表示当条件为真的时候，执行then之后的赋值表达式，处理赋值的信息写到处理四元式的结构体数组中去，当读取到else之后，同理的执行当条件为假的时候的赋值表达式，处理完了之后赋值相应的信息也写到处理四元式的结构体数组中去，这样反复执行就实现的对语法的分析。
3.2语法分析表设计：
实验要求的是递归下降法，主要是调用不同的递归子程序，所以没有什么语法分析表，流程图在后面。
4.1if-else四元式表示的描述:
中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。
三地址代码可看成中间代码的一种抽象形式。
三地址代码通常有三种表示方法：
四元式、三元式、间接三元式。
我使用三元式输出实验的中间代码。
四元式在三元式的基础上增加看result运算结果，四元式之间的联系是通过临时变量实现的。
4.2if-else三地址四元式表示序列的就够设计:
四元式结构形式:
编号（OP，ARG1，ARG2，RESULT）
If-else变成这种形式形式如下：
Ifa>
bgotot1
gotot2
t1：
x=a;
gotot50
t2:
x=b;
t50:
如（jump,-,-,L）写成gotoL；
把（jrop，B,C,L）写成ifBropCgotoL。
5编译系统的概要设计
5.1概要分析：
首先在源程序相同的目录下创建一个txt文档，并在文档中输入需要编译的程序即if-else语句，然后定义一个输入流文件，利用这个流文件中的open函数打开我需要编译的txt文件，在调用初始化各种变量的初始化函数。
接着开始进行词法分析，词法分析程序的主要任务是对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。
并确定其属性（如保留字、标识符、运算符、界限符和常量等）。
再把它们转换成长度统一的标准形式—属性字。
词法分析是编译过程中的第一个阶段，在语法分析前进行。
也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
单词的分类（五类）：
1.关键字：
由程序语言定义的具有固定意义的标识符。
也称为保留字或基本字。
2.标识符：
用来表示程序中各种名字的字符串。
3.常数：
常数的类型一般有整型、实型、布尔型、文字型。
4.运算符：
如+、－、*、/等。
5.界限符：
如逗号、分号、括号等。
但是我做的这个实验没有用到那么多东西，词法分析的有效字符串为:
IF,ELSE,THEN,<
>
.<
=,>
=,=，和从a到z的单个标识符，但是程序还是相对来说比较简单，复杂的表达式可能不能处理，以后会改进。
而词法分析的结果就是将相应的单词赋予不同的属性值，利用词法分析表将结果保存起来，为后面的语义分析做准备。
词法分析完成之后就是把词法分析的结果都显示出来。
语法分析的过程在上面已经有了说明，语法分析完了之后就是打印中间代码的四元式形式，根据上面的结果，四元式的数组里面已经存储了编译的具体信息，之需要按照相应的算符，将他们输出出来，即可看到四元式表示形式。
5.2词法分析的具体实现：
词法分析的具体过程如下，首先将我们需要的编译的内容读到一个数组之中，利用输入流函数的和获取符号函数配合完成，将数组的的空格、回车等无用的内容去掉，从而将处理过后的转存到该数组中，在利用的这个数组中符号书写的连贯性来进行进行词法分析。
例如，then的写法是先写t，再查看下一字符串是否为HEN，那么词法分析一个个单词来进行，发现数组中存储的是t，在判断数组接下来的存储的分别是否为hen，就能够识别关键字then了，其他的是一个道理，处理完成之后就对每个单词的属性都做了出来，就实现了词法分析应该的功能。
6详细的算法描述（流程图或伪代码）
6.1词法分析输出部分：
voidprint（）
{
for（token_index=0;
token_index<
total_len;
token_index++）
{
if（tokentable[token_index].type==$IF）
cout<
<
"
IF"
"
关键字"
endl;
if（tokentable[token_index].type==$ELSE）
ELSE"
if（tokentable[token_index].type==$THEN）
THEN"
if（tokentable[token_index].type==$ID）
tokentable[token_index].ch<
标识符"
if（tokentable[token_index].type==$ASSIGN）
'
='
运算符"
if（tokentable[token_index].type==$GREAT）
>
if（tokentable[token_index].type==$LESS）
}
token_index=0;
}
6.2流程图：
7软件的测试方法和测试结果
导入文件1.txt，其内容为：
IF（a<
b）THEN
IF（c>
d）THEN
x=f;
ELSEx=t;
ELSE
IF（b>
y）THEN
x=y;
ELSEx=r;
词法分析结果为：
语法分析结果和四元式显示为：
错误的文件：
输入：
b）
THENix=a;
i=b;
#
显示：
8.研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）
本次实验是针对IF-ELSE递归下降输出四元式，没有对复杂的布尔表达式和复杂赋值语句进行处理,基本上满足了实验的基本要求，输出的格式也符合三地址表示的形式，特点是基本实现了嵌套，可以实现对>
=,<
等的处理，体现出了递归下降法的思想，递归函数的算法符合题目的要求。
本次实验的不足还有很多，程序只能对单个字母的标识符进行识别，上面的错误例子1就是这样的不足导致的。
同时对于复杂的赋值语句也无法进行处理。
对于带有运算符的赋值语句，暂时还没有实现，等以后水平提升了以后，应该会进一步完善改算法。
收获：
通过本次实验，我收获了很错东西。
首先对编译有了进一步的深刻理解，对递归下降法的思想有了很深的认识，同时对于语法分析的原理和过程都有了进一步的巩固，对于C++的编程水平也起到了锻炼的作用，巩固了平时所学的知识，真正做到了学以致用，对于各种结构体的运用也有了深刻的认识。
体会：
在做实验的过程中，发现自己在编程序的过程中总是会忽略各种细节，从而导致每次都要改正很错小的低级错误才能正确运行，不仅浪费时间，还会影响到对其他错误地方的修改，此外还缺少较为全面和系统的眼光看待问题，在今后的编程中我会注意改正这方面的缺点，这样才能促使自己编程水平的不断进步。
编译原理是一门非常专业的学科，对于现阶段的我来说，只能掌握它的基本原理，然后在利用C++编程来具体实现，在编译和C++的互相印证中，我不仅对编译原理有了更深的理解，同时也锻炼了自己的动手编程能力，对于将知识转化为能力有了很大的帮助，总之，我学习到了很多的知识。
9参考文献（按公开发表的规范书写）
［1］张素琴、吕映芝、蒋维杜、戴桂兰等．编译原理（第2版）．清华大学出版社．2005年2月
参考书：
［1］胡元义等．编译原理实践教程．西安电子科技大学出版社．2002年1月
［2］王雷等．编译原理课程设计．机械工业出版社．2005年3月
[3]何克右等.C++程序设计教程.武汉理工大学出版社.2005年7月
10附加代码
#include<
iostream.h>
fstream.h>
string.h>
#define$ASSIGN249
#define$IF250
#define$THEN251
#define$ELSE252
#define$GREAT253
#define$LESS248
#define$ID254
typedefstructWtoken
inttype;
charch;
}Wtoken;
typedefenum{JUMP,JG,JL,ASSIGN,END}OpKind;
typedefstruct
intlabel;
//标号
OpKindop;
charpar1,par2;
union{
charresult;
intaddress;
};
}Fourtable;
//四元式
#defineMAX_TOKEN256//Wtoken表大小
#defineMAX_QUAD256//四元式数组大小
Wtokentokentable[MAX_TOKEN];
Fourtablequad[MAX_QUAD];
inttoken_index;
//token表索引
inttotal_len;
//token表有效长度
intquad_len;
//四元式表有效长度
intquad_index;
//四元式索引
intlabel;
ifstreamins;
boolinit（charfilename[255]）;
boolcifafenxi（）;
voidprint（）;
voidERROR（）;
voidS（int,int）;
voidE（int,int,int）;
boolnexttoken（）;
intnewlabel（）;
voidyufafenxi（）;
voidprintFourtable（）;
voidmain（）
cout<
Pleaseinputthenameoffile:
;
charfname[200];
cin>
fname;
if（!
init（fname））
return;
cifafenxi（））
while
（1）
if（ins.eof（））
break;
ins>
ch;
TheresultofCIFAanalyse:
print（）;
endl<
nexttoken（）;
TheGrammar:
yufafenxi（）;
TheFourTableasfollowings:
printFourtable（）;
intnewlabel（）
returnlabel++;
boolinit（charfilename[255]）
total_len=0;
quad_len=0;
quad_index=0;
label=100;
ins.open（filename,ios:
:
nocreate|ios:
in）;
if（ins.fail（））
cout<
文件打开出错!
returnfalse;
returntrue;
//
boolcifafenxi（）
charbuf[16];
if（ins.fail（））
if（ch=='
I'
）
{
ins>
buf;
if（strcmp（buf,"
F"
）==0）
tokentable[total_len++].type=$IF;
}
elseif（ch=='
T'
HEN"
tokentable[total_len++].type=$THEN;
E'
LSE"
tokentable[total_len++].type=$ELSE;
tokentable[total_len++].type=$GREAT;
tokentable[total_len++].type=$LESS;
tokentable[total_len++].type=$ASSIGN;
x'
||（ch>
a'
&
&
ch<
z'
））
tokentable[total_len].type=$ID;
tokentable[total_len++].ch=ch;
#defineAD_RESULT（nlabel,nop,npar1,npar2,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++;
#defineAD_ADDRESS（nlabel,nop,npar1,npar2,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++;
Wtokencur;
boolnexttoken（）
if（token_index>
=total_len）
cur.type=tokentable[token_index].type;
cur.ch=tokentable[token_index].ch;
token_index++;
voidERROR（charstr[20]）
error!
str<
voidS（intbegin,intnext）
if（cur.type==$ID）
chara,b;
cur.ch;
a=cur.ch;
if（!
nexttoken（））
ERROR（"
S"
）;
if（cur.type!
=$ASSIGN）
="
=$ID）
cur.ch<
b=cur.ch;
AD_RESULT（begin,ASSIGN,b,0,a）;
AD_ADDRESS（-1,JUMP,0,0,next）;
nexttoken（）;
elseif（cur.type==$IF）
ifEthenSelseS"
intetrue=newlabel（）;
intefalse=newlabel（）;
E（begin,etrue,efalse）;
if（cur.type==$THEN）
{
if（!
ERROR（"
S（etrue,next）;
if（cur.type==$ELSE）
{
if（!
ERROR（"
S（efalse,next）;
}
else
}
else
voidE（intbegin,intetrue,intefalse）
intmark=0;
E->
E（）"
if（cur.type==$GREAT）
{cout<
mark=1;
elseif（cur.type==$LE
升级会员 