IF-ELSE条件语句的翻译程序设计(LL(1)法、输出四元式).doc

武汉理工大学编译原理课程设计说明书目录课程设计任务书.21. 问题描述.32. 问题分析及编译系统的概要设计.33. 文法及属性文法的定义.3 3.1文法.3 3.2属性文法的描述.43.2.1 属性文法的定义形式.43.2.2 IF THEN ELSE 语句的属性文法.44.语法分析方法描述及语法分析表设计.5 4.1语法分析方法描述.55. 语法分析.86. 中间代码形式的描述及中间代码序列的结构设计.127. 语义分析及中间代码输出.128. 程序流程图.149. 设计结果显示.1510.研制报告.1610.1研制过程.1610.2本设计的评价、特点、不足、收获与体会等.1611.源程序清单.17课程设计任务书学生姓名： 专业班级： 指导教师： 高 曙 工作单位：计算机科学与技术学院 题目: 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点。指导教师签名： 2011年 12月 23日 系主任（或责任教师）签名： 2011年 12月 23日1.问题描述 要求用LL(1)自顶向下分析方法及中间代码四元式，对IF-THEN-ELSE条件语句完成编译各阶段过程，包括词法、语法、语义等分析，并完成以下要求： (1)写出符合给定的语法分析方法的文法及属性文法。 (2)完成题目要求的中间代码四元式的描述。 (3)写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。 (4)编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 (5)设计报告格式按附件要求书写。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)根据条件语句： IF 布尔表达式 THEN 赋值语句 ELSE 赋值语句，描述相应的文法，其中非终结符集为VN(A，B，E，T, F),终结符集为VT(+，-，*，/，i，(，) )。E为布尔表达式，B为赋值语句。 3.2 属性文法的描述 3.2.1 属性文法的定义形式 属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配备若干相关的“值”（与文法符号相关的属性）。在一个属性文法中，对应于每个产生式Aa都有一套与之相关联的语义规则，每规则的形式为：b:=f(c1,c2,，ck)其中f是一个函数，而且或者b是A的一个综合属性并且c1,c2,，ck是产生式右边文法符号的属性或者非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值。 3.2.2 IF THEN ELSE 语句的属性文法其属性文法为：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(“ emit(“ ”); 7. arop - + emit(“ + ”); 8. arop- - emit(“ - ”); 9.arop- * emit(“ * ”); 10.arop- / emit(“ / ”); 4. 语法分析方法描述及语法分析表设计 4.1语法分析方法描述 首先应该创建一个枚举类型的变量来存放一些关键字，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 accidence()int k=0;char buf16;char ch;while(1)insch;if(ins.fail()break;while(ch= )insch;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=$greater;else if(ch=A& ch=a & ch=0 & ch=9)tokentabletotal_len.type=$num; tokentabletotal_len+.ch =ch;elseswitch (ch)case + :tokentabletotal_len.type=$add; tokentabletotal_len+.ch =ch; break; case - :tokentabletotal_len.type=$sub; tokentabletotal_len+.ch =ch; break; case / : tokentabletotal_len.type=$div; tokentabletotal_len+.ch =ch; break; case * :tokentabletotal_len.type=$mul; tokentabletotal_len+.ch =ch;break; case ; :tokentabletotal_len.type=$fenhao; tokentabletotal_len+.ch =ch;break;case ( :tokentabletotal_len.type=$left_paren; tokentabletotal_len+.ch =ch; break;case ) :tokentabletotal_len.type=$right_paren; tokentabletotal_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代表此处无产生式与之对应。/算法函数char dosome(void) int t,a=0;char bian1,bian2; OpKind opa;char c=$;next();for(;) pop();if(cur.type!=$id & cur.type!=$num)curchar=cur.ch;elsecurchar=i;coutendl;coutcurchar curtocmp1) return c;else return bian1;因为在推导过程中，会一并完成产生式后面附加的语义动作，所以这两部分是一起做的。另外，在LL(1)分析过程中，会出现错误信息，如字符不匹配，或字符没有出现在产生式终结符集VT中，或没有找到合适的候选产生式来做进一步推导，会调用相应的出错处理函数err(f)。另外，此函数是递归实现，结束标志是f!=0，即成功或失败。6.中间代码形式的描述及中间代码序列的结构设计 四元式是一种比较普遍采用的中间代码形式。四元式的四个组成部分是：操作符OP，第一个和第二个运算 对象ARG1和ARG2及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例a:=b*c+b*d的四元式表示如下：(1)(*,b,c,t1)(2)(*,b,d,t2)(3)(+,t1,t2,t3)(4)(:=,t3,-,a)7.语义分析及中间代码输出 根据上面给出的属性文法所规定的翻译方案，即可对输入的程序进行相应的语义分析。对于中间代码部分，题目是以四元式的形式输出。对于四元式形式，在学习编译原理的时候接触的是比较多的了，所以是比较熟悉了。而对于跳转语句，条件跳转如jump L1的四元式形式为(jump,-,-,L1)；而其对应的三地址形式为goto L1。而对于条件跳转语句，则四元式为（jrop，a，b，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)quadquad_len.label=nlabel; quadquad_len.op=nop; quadquad_len.par1=npar1; quadquad_len.par2=npar2; quadquad_len.result=nresult; quad_len+; /产生跳转地址的四元式void AD_ADDRESS(int nlabel,OpKind nop,char npar1,char npar2,int naddress) quadquad_len.label=nlabel; quadquad_len.op=nop;quadquad_len.par1=npar1;quadquad_len.par2=npar2; quadquad_len.address=naddress;quad_len+; /回填出口void backpath(int nlabel,int addr) quadnlabel.address=addr;8.程序流程图 开始 “#”“S”进栈，读输入流一符号=a对产生式右部x1x2.xn按逆序即xnxn-1.x1 压入栈中栈顶元素出栈并送X读入符号=aX=a？XVTyy YN N出错处理X=#？MX,a为产生式？NNN NX=a? 出错处理N结束Y9.设计结果显示输入要编译文件的文件名:test.txt测试结果如下： 10.研制报告10.1研制过程 拿到设计题目以后，首先是构造符合题意的文法，然后构造文法所对应的优先关系表。完成这两步之后，开始编写源程序。编译程序主要分成三大模块，词法分析模块、语法语义分析模块和中间代码生成和输出。 首先进行词法分析，对输入的符号串进行分析，判断出关键字，数字，终结符和非终结符。然后进行语法分析，根据每个产生式的select集，然后得出文法的预测分析表。最后通过语义分析，完成分析过程，并生成相应的中间代码。最后，将生成的中间代码输出。 10.2本设计的评价、特点、不足、收获与体会等 本程序能正确实现对IF-ELSE条件语句的翻译工作，能够对所输入的字符串语句进行词法分析、语法语义分析以及生成相应的四元式中间代码并输出，正确完成了实验的要求。但是，程序本身还是不够完善的，如不能实现IF语句的嵌套，还有对单词的容错能力不强,另外，还有表达式的分析过程，而没有把if-else-then这些关键字的分析过程加入进来。虽然课设时间有限，但我相信随着自己编程水平的提高，这些缺陷一定会得到解决的。 LL(1)的分析方法，这个方法的关键首先要构造一个if-else语句的文法，然后将其转换为LL(1)文法，再根据每个产生式的select集构造预测分析表。然后就是相应的分析。然后根据预测分析表做出相应的推导和匹配动作，最后如果栈里的内容和队列里的内容都是以“#”号的形式匹配的话，这个语句就分析成功。这次设计也是针对一个特定的语句来进行分析的，所以我就假设所有的输入串当中都在相应的位置有那些关键字了。所以程序做起来就比较简单，容易实现。 这次课程设计使得我受益匪浅，尤其是对优先关系分析方法有了更深的理解和掌握。通过这次课程设计，我的编程能力又得到进一步的提高，同时也培养了我思维能力。总之，这次课程设计不仅丰富了我的理论知识，也加强了我的动手能力，还锻炼了我的思维能力。在实验程序编写和调试过程中我学会了很多，也认识到了自己的不足，我还需要进一步的努力，以致取得更大的进步。我需要的就是要对自己有信心，脚踏实地，持之以恒，遇到困难时要冷静思考，勇敢面对，直到得出结果。在实验设计过程中，我也养成了较好地习惯，先有框架，然后跟着框架发展，最后就是要注重细节，要做到严谨和缜密。不可否认这种好习惯让我受益无限，我也必须拥有它，以致我获得更多。11.源程序清单 /基于LL(1)法的条件语句语法语义分析程序 #include#include#include#include#includeenum keyword $right_paren,$left_paren,$mul,$div,$add,$sub,$fenhao, $equal,$IF,$THEN,$ELSE,$greater,$less,$id,$num,$end;typedef struct Token keyword type;char ch;Token;typedef enumJUMP,JG,JL,equal,END,add,mul,sub,divOpKind;typedef struct int label;/标号OpKind op;/操作符char par1,par2;/操作数unionchar result;/结果int address;/地址;Quad; /四元式入口#define MAX_TOKEN 256/Token表大小#define MAX_QUAD 256/四元式数组大小Token tokentableMAX_TOKEN;Quad quadMAX_QUAD;int token_index;/token表索引int total_len;/token表有效长度int quad_len;/四元式表有效长度int quad_index;/四元式索引Token cur;Token queue10;int label,k,one; /标记接口char curchar;/存储当前待比较字符char curtocmp;/存储当前栈顶字符ifstream ins;int trueadd,falseadd,end; int table58=1,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,0,0,0,1,0,0,0,1,1,1,1,0,1,1,1,0,0,0,0,1,0,0; /存储预测分析表，1为有产生式，0为没有int i,j;int flag;struct Lchar char char_ch;struct Lchar *next;Lchar,*temp,*top,*base;int right;/定义开关项bool initialize(char filename255);/文件打开初始化bool accidence();/词法分析void print();/输出单词表void backpath(int,int);/回填出口void ERROR();void sentence();/分析语句void boolean();/ 分析E-id id语句bool nexttoken();/读下一单词char newchar();void push();/进队列char dosome(void);/算法函数void pushs(char pchar);/入栈函数void pop(void);/出栈函数void doforpush(int t);/根据数组下标计算的值产生式入栈void changchartoint();/根据curchar,curtocmp转为数字以判断是否有产生式void semantic();/语法语义分析char LL1();/LL(1)文法分析void printQuad();/输出四元式void ERROR(char str20);void AD_ADDRESS(int nlabel,OpKind nop,char npar1,char npar2,int naddress);void AD_RESULT(int nlabel,OpKind nop,char npar1,char npar2, char nresult);void main() cout endl 基于LL(1)法的条件语句语法语义分析程序 endl endl;coutfname;if(!initialize(fname)return;if(!accidence()return;char ch;while(1) if(ins.eof()break;insch;coutendl词法分析结果如下:;print();coutendl;cout词法分析结束。endlendl;semantic(); /语法语义分析coutendl输出四元式:endl;printQuad();if(right=1)cout分析成功endl;elsecout分析失败endl;cout语法语义分析结束endl;char newchar() char p; p=char(k);k+;return p; /文件打开初始化bool initialize(char filename100) one=0;token_index=0;total_len=0;quad_len=0;quad_index=0;label=0;end=0;k=48;ins.open(filename,ios:nocreate | ios:in);if(ins.fail() cout文件打开出错!ch;if(ins.fail()break;while(ch= )insch;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=$greater;else if(ch=A& ch=a & ch=0 & ch=9)tokentabletotal_len.type=$num; tokentabletotal_len+.ch =ch;elseswitch (ch)case + :tokentabletotal_len.type=$add; tokentabletotal_len+.ch =ch; break; case - :tokentabletotal_len.type=$sub; tokentabletotal_len+.ch =ch; break; case / : tokentabletotal_len.type=$div; tokentabletotal_len+.ch =ch; break; case * :tokentabletotal_len.type=$mul; tokentabletotal_len+.ch =ch;break; case ; :tokentabletotal_len.type=$fenhao; tokentabletotal_len+.ch =ch;break;case ( :tokentabletotal_len.type=$left_paren; tokentabletotal_len+.ch =ch; break;case ) :tokentabletotal_len.type=$right_paren; tokentabletotal_len+.ch =ch;break; default:cout!endl; return true;/语法语义分析void semantic() if(!nexttoken()ERROR(s(0); cout开始进行语法语义分析:endl 所使用的产生式:endl - if E then S else Sendl if E then else P2endl abendl x:=a*cendl x:=b*cendl 语法语义分析过程如下:=total_len)return false;if(tokentabletoken_index.type=$fenhao)token_index+;cur.type=tokentabletoken_index.typ