if--else-语句-递归下降法-输出四元式.doc

学 号： 0121课 程 设 计课程名称 编译原理课程设计题 目IF-ELSE条件语句的翻译程序设计（递归下降法、输出四元式）学 院计算机科学与技术专 业计算机科学与技术班 级计算机1001班姓 名指导教师陈天煌2013年1月7日课程设计任务书学生姓名 专业班级： 计算机1001班 指导教师： 陈天煌 工作单位：计算机科学与技术学院 题目: IF-ELSE条件语句的翻译程序设计（递归下降法、输出四元式表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码四元式的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 年 月 日IF-ELSE条件语句的翻译程序设计（递归下降法、输出四元式）1.系统描述（问题域描述） 本次实验使用windows XP的visual C+软件，利用递归下降法实现IF-ELSE的条件语句的翻译程序设计，输出四元式表示，程序只能处理简单的布尔表达式和最简单的赋值语句，布尔表达式能够实现大于和小于的识别，也能处理关系运算符=和X then Y else Y; X-ididid; X-idid=id; Y-id=id；2.3属性文法的描述： 属性文法(也称属性翻译文法)是Knuth在1968年首先提出的。它是在上下文无关文法的基础上，为每个文法符号(终结符或非终结符)配备若干相关的“特性”（称为属性）。3 语法分析方法描述及语法分析表设计；3.1语法分析方法描述： 在程序语言的语法定义中有许多采用递归定义。我们在对它进行语法分析时，编制的处理程序也采取递归的方式，可使其结构简单易读。但由于频繁地调用子程序大大地降低了分析速度。 递归下降法的主要思想是：对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序也递归，子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。程序是以一个个单词的形式向后读取，读取到if之后就开始执行E的递归子程序，程序根据布尔表达式的真假，进而选择执行相应的分支，即如果布尔表达式为真，就执行then后面的赋值语句，如果布尔表达式为假，就执行else后面的赋值语句，递归子程序E分别赋予布尔表达式真和假不同的地址，并将跳转相应的信息写到处理四元式的结构体数组中去，E执行完以后，回到S中继续执行后面的，读取到then之后，就表示当条件为真的时候，执行then之后的赋值表达式，处理赋值的信息写到处理四元式的结构体数组中去，当读取到else之后，同理的执行当条件为假的时候的赋值表达式，处理完了之后赋值相应的信息也写到处理四元式的结构体数组中去，这样反复执行就实现的对语法的分析。3.2语法分析表设计： 实验要求的是递归下降法，主要是调用不同的递归子程序，所以没有什么语法分析表，流程图在后面。4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计； 4.1if-else四元式表示的描述:中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。四元式可看成中间代码的一种抽象形式。5 编译系统的概要设计5.1概要分析： 首先在源程序相同的目录下创建一个txt文档，并在文档中输入需要编译的程序即if-else语句，然后定义一个输入流文件，利用这个流文件中的open函数打开我需要编译的txt文件，在调用初始化各种变量的初始化函数。接着开始进行词法分析，词法分析程序的主要任务是对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。并确定其属性（如保留字、标识符、运算符、界限符和常量等）。再把它们转换成长度统一的标准形式属性字。词法分析是编译过程中的第一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。单词的分类（五类）：1. 关键字：由程序语言定义的具有固定意义的标识符。也称为保留字或基本字。2. 标识符：用来表示程序中各种名字的字符串。3. 常 数：常数的类型一般有整型、实型、布尔型、文字型。4. 界限符：如逗号、分号、括号等。但是我做的这个实验没有用到那么多东西，词法分析的有效字符串为: IF,ELSE,THEN, ,.=,=，和从a到z的单个标识符，但是程序还是相对来说比较简单，复杂的表达式可能不能处理，以后会改进。而词法分析的结果就是将相应的单词赋予不同的属性值，利用词法分析表将结果保存起来，为后面的语义分析做准备。词法分析完成之后就是把词法分析的结果都显示出来。语法分析的过程在上面已经有了说明，语法分析完了之后就是打印中间代码的四元式形式，根据上面的结果，四元式的数组里面已经存储了编译的具体信息，之需要按照相应的算符，将他们输出出来，即可看到中间代码的四元式表示形式。5.2词法分析的具体实现：词法分析的具体过程如下，首先将我们需要的编译的内容读到a这个数组之中，利用输入流函数的seekg()和get()函数配合完成，在利用for循环将a数组的的空格、回车等无用的内容去掉，从而将处理过后的转存到a1这个数组中，在利用的这个数组中符号书写的连贯性来进行进行词法分析。例如，then的写法是先写t，再写h，再写e，再写n，那么词法分析一个个单词来进行，发现a1i中存储的是t，在判断数组接下来的三个单元里面存储的分别是h、e、n，就能够识别关键字then了，其他的是一个道理，处理完成之后就对每个单词的属性都做了出来，就实现了词法分析应该的功能，6 详细的算法描述（流程图或伪代码）6.1词法分析的全部代码：词法分析读取下一单词是IF，调用E结束输出三地址四元式表示代码 输出词法分析初始化输入txt文件名E递归子程序读取下一单词语法分析:递归程序S置结束标志6.1程序代码/有效字符串: IF,ELSE,THEN, a,b,x,=/*文法: S-id=id | if E then S else S E-id id id*/#include#include#include#define $ASSIGN 249#define $IF 250#define $THEN 251#define $ELSE 252#define $GREAT 253#define $LESS 248 #define $ID 254typedef struct Wtokenint type;char ch;Wtoken;typedef enumJUMP,JG,JL,ASSIGN,ENDOpKind;typedef structint label;/标号OpKind op;char par1,par2;unionchar result;int address;Fourtable;/四元式#define MAX_TOKEN 256 /Wtoken表大小#define MAX_QUAD 256 /四元式数组大小Wtoken tokentableMAX_TOKEN;Fourtable quadMAX_QUAD;int token_index;/token表索引int total_len;/token表有效长度int quad_len;/四元式表有效长度int quad_index;/四元式索引int label;ifstream ins;bool init(char filename255);bool cifafenxi();void print();void ERROR();void S(int,int);void E(int,int,int);bool nexttoken();int newlabel();void yufafenxi();void printFourtable();void main()coutfname;if(!init(fname)return;if(!cifafenxi()return;char ch;while(1)if(ins.eof()break;insch;coutThe result of CIFA analyse :endl;print();coutendlendl;nexttoken();coutThe Grammar:endl;yufafenxi();coutThe FourTable as followings:endl;printFourtable();int newlabel()return label+;bool init(char filename255)token_index=0;total_len=0;quad_len=0;quad_index=0;label=100;ins.open(filename,ios:nocreate | ios:in);if(ins.fail()cout文件打开出错!ch;if(ins.fail()break;if(ch=I)insbuf;if(strcmp(buf,F)=0)tokentabletotal_len+.type=$IF;else if(ch=T)insbuf;if(strcmp(buf,HEN)=0)tokentabletotal_len+.type=$THEN;else if(ch=E)insbuf;if(strcmp(buf,LSE)=0)tokentabletotal_len+.type=$ELSE;else if(ch=)tokentabletotal_len+.type=$GREAT;else if(ch=a & ch=total_len)return false;cur.type=tokentabletoken_index.type;cur.ch=tokentabletoken_index.ch;token_index+;return true;void ERROR(char str20)couterror! strendl;void S(int begin,int next)if(cur.type=$ID)char a,b;coutcur.ch;a=cur.ch;if(!nexttoken()ERROR(S);if(cur.type!=$ASSIGN)ERROR(S);cout=;if(!nexttoken()ERROR(S);if(cur.type!=$ID)ERROR(S);coutcur.chendl;b=cur.ch;AD_RESULT(begin,ASSIGN,b,0,a);AD_ADDRESS(-1,JUMP,0,0,next);nexttoken();else if(cur.type=$IF)if(!nexttoken()ERROR(S);coutif E then S else Sendl;int etrue=newlabel();int efalse=newlabel();E(begin,etrue,efalse);if(cur.type=$THEN)if(!nexttoken()ERROR(S);S(etrue,next);if(cur.type=$ELSE)if(!nexttoken()ERROR(S);S(efalse,next);elseERROR(S);elseERROR(S);void E(int begin,int etrue,int efalse)if(cur.type=$ID)char a,b;int mark=0;a=cur.ch;coutcur.ch;if(!nexttoken()ERROR(E();if(cur.type=$GREAT)cout;mark=1;else if(cur.type=$LESS)cout;else ERROR(E(); if(!nexttoken()ERROR(E();if(cur.type!=$ID)ERROR(E();coutcur.chendl;b=cur.ch;if(mark=0)AD_ADDRESS(begin,JL,a,b,etrue);if(mark=1)AD_ADDRESS(begin,JG,a,b,etrue);AD_ADDRESS(-1,JUMP,0,0,efalse);if(!nexttoken()ERROR(E();elseERROR(E();void yufafenxi()S(-1,1000);AD_RESULT(1000,END,0,0,-);void print()for(token_index=0;token_indextotal_len;token_index+)if(tokentabletoken_index.type=$IF)coutIF 关键字endl;if(tokentabletoken_index.type=$ELSE)coutELSE 关键字endl;if(tokentabletoken_index.type=$THEN)coutTHEN 关键字endl;if(tokentabletoken_index.type=$ID)couttokentabletoken_index.ch 标识符endl;if(tokentabletoken_index.type=$ASSIGN)cout= 运算符endl;if(tokentabletoken_index.type=$GREAT)cout 运算符endl;if(tokentabletoken_index.type=$LESS)cout 运算符endl;token_index=0;void printFourtable()for(int i=0;i-1)coutLquadi.label:;else cout ;if(quadi.op=JG)cout,quadi.par1,quadi.par2,Lquadi.address)endl;else if(quadi.op=JL)cout(,quadi.par1,quadi.par2,Lquadi.address)endl;else if(quadi.op=JUMP)cout,-,-,Lquadi.addressendl;else if(quadi.op=ASSIGN)cout(= ,quadi.par1,-,quadi.result)endl;else if(quadi.op=END)cout-,-,-,-endl;7 软件的测试方法和测试结果以下是输入文件内容：IF (ad) THENx=f;ELSE x=t;ELSEIF (by) THENx=y;ELSE x=r;程序运行结果： 图一 词法分析结果 图二 文法分析 图三 四元式输出 8.研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）本次实验做的比较简单，不能对复杂的布尔表达式和复杂赋值语句进行处理,基本上满足了实验的基本要求，输出的格式也符合四元式表示的形式， 特点是基本实现了嵌套，可以实现对=,=,等的处理，体现出了递归下降法的思想，递归函数的算法符合题目的要求。 本次实验的不足还有很多，程序只能对单个字母的标识符进行识别，上面的错误例子1就是这样的不足导致的。同时对于复杂的赋值语句也无法进行处理，也就是上面的错误例子2。对于带有运算符的赋值语句，暂时还没有实现，等以后水平提升了