IF-ELSE条件语句的翻译程序设计(LR方法、输出四元式)

《IF-ELSE条件语句的翻译程序设计(LR方法、输出四元式)》由会员分享，可在线阅读，更多相关《IF-ELSE条件语句的翻译程序设计(LR方法、输出四元式)（23页珍藏版）》请在装配图网上搜索。

1、精选优质文档-倾情为你奉上目录10本科生课程设计成绩评定表.22IF-ELSE条件语句的翻译程序设计（LR方法、输出四元式）1 系统描述（问题域描述）对条件语句： if 布尔表达式then赋值语句 else 赋值语句， 进行词法，LR(1)语法分析，并根据语法制导翻译方法将条件语句翻译成四元式中间代码形式，最后输出翻译后的四元式代码。2 文法及属性文法的描述2.1文法GS: S-CS S-TS S-A C-if E then T-CS else T-else其中，E代表布尔表达式，可由界符（）括起来，A代表赋值表达式。在这里E、A都代表终结符，具体的表达式在程序会判断其类型。2.2 属性文法S

2、-C S S.clain:=merge(C.clain,S.clain)S-T S S.clain:=merge(T.clain,S.clain)S-A S.clain:0/* 空链 */C-if E then backpatch(E.true,nextstat) C.clain:=E.falseT-C S else q:=nextstatEmit(GOTO )Backpatch(C.clain,nextstat)T.clain:=merge(S.clain,q)3 语法分析方法描述及语法分析表设计3.1语法分析方法描述3.11 LR方法的基本思想一个LR分析器实质上是一个带先进后出存储器的确

3、定有限状态自动机。我们将把“历史”和“展望”材料综合地抽象成某些“状态”。分析栈用来存放状态。栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。任何时候，栈顶的状态都代表了整个的历史和已推测出的展望。因此，在任何时候都可从栈顶状态得知所想了解的一切，而绝对没有必要从称底而上翻阅整个栈。LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一决定的。为了有助于明确归约手续，我们把已归约出的文法符号串也同时放在栈里。于是，我们可以把栈的结构看成是:栈的每一项内容包括状态S和文法符号X两部分。（S0，#）为分析开始前预先放到栈里的初始状态和句子括号。栈顶状态为SM，符号串X

4、1X2.XM是至今已移进归约出的部分。3.1.2 LR分析器模型LR分析器模型如下图:LR分析器的核心部分是一张分析表。这张分析表包括两部分，一是“动作”（ACTION）表，另一个是“状态转换表”（GOTO）表。它们都是二维数组。ACTIONs，a规定了当状态s面临输入符号a时应采取什么动作。GOTOs，a规定了状态s面对文法符号X（终结符或非终结符）时下一个状态是什么。显然GOTOS，x定义了一个以文法符号为字母表的DFA。每一项ACTIONs，a所规定的动作不外是下述四种可能之一：1.移进 把（S，A）的下一状态SGOTOS，A和输入符号A推进栈，下一输入符号变成现行输入状态。2.规约 指

5、用某一产生式A 进行规约。假若 的长度为r，归约动作是A，去除栈顶的r个项，使状态Sm-r变成栈顶状态，然后把（Sm-r，A）的下一状态S1GOTOSm-r,A和文法符号A推进栈。归约动作不改变现行输入符号。执行归约动作意味着（Xm-r+1.Xm）已呈现于栈顶而且是一个相对于A的句柄。3.接受 宣布分析成功，停止分析器的工作。4.报错 发现源程序含有错误，调用出错处理程序。LR分析器的总控程序本身的工作是非常简单。它的任何一步只需要按栈顶状态和现行输入符号a执行ACTIONS，a所规定的动作。不管什么分析表，总控程序都是一样地工作。一个LR分析器的工作过程可看成是栈里的状态序列，已归约串和输入

6、串所构成的三元式的变化过程。分析地的初始三元式（S0,#,a1a2an#）其中，S0为分析器的初态；#为句子的左括号；a1a2an为输入串；其后的#为结束符。分析过程每步的结果可表示为（s0s1sm,# X1X2,ai.an#）分析器的下一步动作是由栈顶状态Sm和现行输入符号ai所唯一决定。即，执行ACTIONSm,ai所规定的动作。经执行每种可能的动作之后，三元式的变化的情形是：（1）若ACTIONSm,ai为移进，且S=GOTOSm,ai,则三元式变成： （S0S1Sm,#X1X2Xmaian#）（2）若ACTIONSm,aiA ，则按产生式A 进行归约。此时三元式变为 (S0S1Sm-r

7、S,#X1Xm-rA,aiai+1an#) 此处S GOTOSm-r,A，r为 的长度， Xm-r+1Xm。（3）若ACTIONSm,ai为：接受，则三元式不再变化，变化过程终止，宣布分析成功。（4）若ACTIONSm,ai为“报错”，则三元式的变化过程终止，报告错误。 一个LR分析器的工作过程就是一步一步地变换三元式，直至执行“接受”或“报错”为止。3.2语法分析表设计在做语法分析前需建立SLR(1)语法分析表ACTIONGOTOiteAE#SCT0S5S4S1S2S31ACC2S5S4S6S2S33S5S4S10S2S34r3r35S86S7r17r5r58S99r4r410r2r2此表中

8、引用记号的意义是：（1）Sj 把下一状态j和现行输入符号移进栈；（2）rj 按第j个产生式进行规约；（3）acc 接受；（4）空白格 出错标志，报错；4中间代码形式的描述及中间代码序列的结构设计4.1中间代码形式的描述四元式是一种比较普遍采用的中间代码形式。四元式的四个组成部分是：操作符OP，第一个和第二个运算 对象ARG1和ARG2及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a:=b*c+b*d的四元式表示如下：(1) (*,b,c,t1)(2) (*,b,d,t2)(3) (+,t1,t2,t3)(4) (:=,t3,-,a)4.2

9、中间代码序列的结构设计If E then A1else A2100 （关于E的布尔表达式）101 （goto, - , - ,104）102 (关于A1的赋值表达式)103 （goto, - , - ,105）104 (关于A2的赋值表达式)105 exit5 编译系统的概要设计本课程设计需要写一个条件语句的LR文法及其属性文法，运用LR分析方法对此文法进行语法和语义分析，中间代码采用四元式输出。在这个条件语句的翻译分析程序设计中，主要通过以下四个过程来完成：1.词法分析。由于编译程序是在单词的级别上来分析和翻译源程序的，那么在这里，词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一

10、个一个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。所以词法分析是编译的基础。在此程序中是将词法分析作为一遍处理的，通过一次分析把全部的字符串都分析完成，并将其保存在数组中便于下一步进行语法分析。 2.语法分析。在完成词法分析的基础上对条件语句进行语法分析，在这里我采用了自下而上分析法SLR(1)分析方法，来分析判定程序的语法结构是否符合语法规则，在分析前首先要构造SLR(1)分析表，然后在进行语法分析，在此程序中，以；为结束符号来判断一条条的条件语句，并且独立的对每条语句进行语法分析。并把算法中的移近、规约操作3.语义分析、输出四元式。在进行语法分析的同时进行语义分析，在此次

11、设计中式将二者结合起来作为一遍进行处理的。在进行语义时同时生成中间语言四元式。4.出错处理。如果在词法分析时遇到非法字符就会输出出错信息，同时输出从出错点开始往后的一串字符，但是它仍然能跳过该非法字符继续分析；如果在语法分析中有错误的话，就会显示在DOS环境下输出“ERROR”,但是它能跳过出错的地方继续往后执行，分析出一部分结果并保存在文件中。6 详细的算法描述6.1系统流程图开始词法分析语法分析出错处理语义分析中间代码生成 结束初始化语法6.2算法描述本程序中，选用C+程序设计语言的部分常用的单词作为词法分析的对象，词法分析后，将识别的所有单词符号以及相关信息保存在数组中，以便后面语法分析

12、和语意分析及中间代码生成使用，同时将识别出的单词符号输出到文件中，并分类别地存储到相应的数组中一便进行查看。采用SLR(1)分析法，生成状态表，然后根据栈的移近、移出生成分析过程表。在经过语法、语义分析之后，生成中间代码四元式，同时进行出错管理。void initGrammar();/初始化产生式表bool isJchar(char c)/检测是否为分界符int word() /进行词法分析，并存到fenxi.txt文件中wnode* lexcial(wnode *head)/把词法分析得来的词分类别放到表达式数组int check(int s,char v);/查LR分析表void gamm

13、arAnalysis(wnode *head);/语法分析及进行相应的语义操作并产生四元式void showS(int opS,int tops,char opC,int topc,wnode *hp);/显示分析栈的内源程序代码：# include #include#include# include #include#include using namespace std;char Filename100;struct wnodechar id;int n;/编号char text20;wnode * next;struct Gnode/存储产生式string gen;int id;Gnod

14、e grammar6;void initGrammar();/初始化产生式表wnode* lexcial(wnode *head);int check(int s,char v);/查LR分析表void gammarAnalysis(wnode *head);/语法分析及进行相应的语义操作并产生四元式void showS(int opS,int tops,char opC,int topc,wnode *hp);/显示分析栈的内容/用于if-else分析 int LR119=/_ACTION_|_GOTO_/ i t e A E # S C T105, 0, 0,104, 0, 0,101,1

15、02,103,/0 0, 0, 0, 0, 0, -1, 0, 0, 0,/1105, 0, 0,104, 0, 0,106,102,103,/2105, 0, 0,104, 0, 0,110,102,103,/3 0, 0, 3, 0, 0, 3, 0, 0, 0,/4 0, 0, 0, 0,108, 0, 0, 0, 0,/5 0, 0,107, 0, 0, 1, 0, 0, 0,/6 5, 0, 0, 5, 0, 0, 0, 0, 0,/7 0,109, 0, 0, 0, 0, 0, 0, 0,/8 4, 0, 0, 4, 0, 0, 0, 0, 0,/9 0, 0, 2, 0, 0,

16、2, 0, 0, 0 /10;void initGrammar()grammar0.gen=S-S;grammar0.id=0;grammar1.gen=S-CS;grammar1.id=1;grammar2.gen=S-TS;grammar2.id=2;grammar3.gen=S-A;grammar3.id=3;grammar4.gen=C-if E then;grammar4.id=4;grammar5.gen=T-CS else;grammar5.id=5;cout所用文法:endl;int i,j;for(i=1;i6;i+)coutgrammari.id-1tgrammari.ge

17、nendl;cout5telseendl;cout注：i-if t-then e-elseendl;cout E布尔表达式（在语法分析中看成是终结符）endl;cout A赋值语句（在语法分析中看成是终结符）endl;coutSLR(1)分析表：endl;coutsetw(22)ACTIONsetw(18)|setw(10)GOTOendl;coutsetw(8)isetw(6)tsetw(6)esetw(6)Asetw(6)Esetw(6)#setw(6)Ssetw(6)Csetw(6)Tendl;for(i=0;i11;i+)coutsetw(2)i;for(j=0;j=110)couts

18、etw(4)S100)coutsetw(5)S0)coutsetw(5)rLRij;else if(LRij=0)coutsetw(6) ;else coutsetw(6)ACC;coutendl;bool isJchar(char c)/检测是否为分界符bool r=false;switch(c)case :case n:case ;:r=true;break;default:;return r;int word()char ch= ;int num=0;ifstream source(source.txt);ofstream fenxi(fenxi.txt);char yunsuanfu1

19、1=+,-,*,/,=,!,%,&,|;char jiefu9=,;,(,),#;char *guanjianzi20=int,if,else,then,do,while,break,continue,switch,return,when,for,double,main,break,include,short,long,float,char,;char *biaoshifu100=0; / while(!source.eof()source.get(ch);char shuzi20=;int i=1;if(ch=0&ch=0&ch=9)|ch=.)&!source.eof()coutch; s

20、huzii+=ch;source.get(ch);fenxishuzi数字endl;for(i=0;i=10;i+) /运算符判断if(ch=yunsuanfui)fenxich运算符endl;for(i=0;i9;i+) /界符if(ch=jiefui)fenxich界符=a&ch=a&ch=0&ch=9)|ch=_)&!source.eof()str1n=ch;source.get(ch);n+;str1n=0;for(i=0;i20;i+)if(!strcmp(str1,guanjianzii)fenxistr1关键字endl;sign=1;if(sign=0)fenxistr1标识符e

21、ndl;for(i=0;i=10;i+) /运算符判断 if(ch=yunsuanfui) fenxich运算符endl; for(i=0;i9;i+) /界符 if(ch=jiefui) fenxich界符text0=0; q-n=0; q-next=NULL; fstream infile(Filename);/根据输入的路径名来打开这个文件 while (infile.get(c) if(isJchar(c) if(mark=1) q-textk=0; for(i=0;q-texti!=0;i+) if(q-texti=) loc=i; if(p-id=i) q-id=E;q-n=+Ec

22、ount; else if(loc!=-1) q-id=A;q-n=+Acount; else q-id=q-text0; if(q-id=i) head-n+; p-next=q; p=q; mark=0; else if(mark=0) q=new wnode; q-n=0; q-next=NULL; loc=-1; k=0; mark=1; q-textk+=c; /在末尾加上一个# q=new wnode; q-next=NULL; q-id=#; q-text0=0; q-n=0; p-next=q; return head;/语法分析void gammarAnalysis(wnod

23、e *head)char E20;char A20;char r,d1,d2;int tn=0,en=head-n;ofstream table;table.open(siyuanshi.txt);if(!table)coutCannot open output file!endl;exit(1); cout语法分析过程：endl; cout分析栈 输入串 操作next;int tops=0;int topc=0;opStops=0;opCtopc=#;while(p)showS(opS,tops,opC,topc,p);if(topsid;if(c=E)for(i=0;itexti!=0;i

24、+)Ei=p-texti;Ei=0;if(c=A)for(i=0;itexti!=0;i+)Ai=p-texti;Ai+=;Ai=0;mark=check(opStops,c);switch(mark)case -1:coutt语法分析,翻译成功endl;table+loc;table.close();return;case 1:tops=tops-2;topc=topc-1;opCtopc=S;couttt 归约 grammar1.genendl;break;case 2:tops=tops-2;topc=topc-1;opCtopc=S;couttt 归约 grammar2.genendl

25、;break;case 3:tops=tops-1;topc=topc-0;opCtopc=S;couttt 归约 grammar3.genendl;r=A3;d1=A2;d2=A4;table+loct(rtd1td2tT+tn)endl;table+loct(=tTtnttA0)endl;break;case 4:tops=tops-3;topc=topc-2;opCtopc=C;couttt 归约 grammar4.genendl;r=E2;d1=E1;if(r=)d2=E4;else d2=E3;table+loct(r;if(r=)tablertd1td2tloc+2)endl;el

26、se tabletd1td2tloc+2)endl;if(en=1)table+loct(gototttloc+4)endl;elsetable+loct(gototttloc+4+2*(en)endl;break;case 5:tops=tops-3;topc=topc-2;opCtopc=T;couttt 归约 grammar5.genendl;table+loct(gototttloc+3)next;opS+tops=mark-100;if(topstopc)opC+topc=c; couttt 移入endl;break;case 0:coutERROR!endl;return;void

27、 showS(int opS,int tops,char opC,int topc,wnode *hp)/coutendl;int i=0,j=0;wnode *tp=hp;for(i=0;i=topc;i+)coutopCi;coutt;while(tp)coutid;tp=tp-next;coutendl;for(i=0;i=tops;i+)coutopSi;/coutendl;int check(int s,char v)int t=-1;switch(v)case i:t=0;break;case t:t=1;break;case e:t=2;break;case A:t=3;brea

28、k;case E:t=4;break;case #:t=5;break;case S:t=6;break;case C:t=7;break;case T:t=8;break;default:;int r=LRst;return r;int main() FILE *fp; int n=100; coutn*IF-ELSE条件语句的翻译程序设计（LR方法、输出四元式）*endl; initGrammar(); cout请输入文件名:; cin.getline(Filename,n); fp=fopen(Filename,r); while (fp=NULL)/若打入的文件没有，则提示继续打入有效

29、的路径名 coutSorry,文件不存在!endl; coutid=#; wlist-n=0; wlist-text0=0; wlist-next=NULL; wlist=lexcial(wlist); fclose(fp); word(); gammarAnalysis(wlist); ifstream fin(siyuanshi.txt); string s; cout输出四元式为：endl; while( getline(fin,s) ) cout s endl; return 0; 7 软件的测试方法和测试结果7.1软件的测试方法 程序刚写完时，有几个错误，根据系统的提示，合理设置断点

30、进行调试7.2测试结果运行程序出现DOS界面，显示所用语法与SLR（1）分析表输入保存已写好的程序的文件名source.txt,回车键，词法分析生成单词表，语法分析生成语法分析过程和中间代码四元式条件语句代码：词法分析单词表：8设计的特点、不足、收获与体会8.1特点与不足在此次课程设计中，我运用C+语言实现了用LR分析方法对条件语句的翻译分析程序设计，最后输出中间代码形式为四元式。在此次课程设计中，对于词法分析这一块，由于以前在做实验时就做过，所以此次的语法分析只是在以前的基础上添加了一些关键字，没有做太多的改变，因此很快就完成了。对于语法分析这一块，我感觉是最复杂的。刚开始对各种字符的判定容

31、易出错，后来我采用先把词法分析来的字符分成关键字和表达式来对待，在语法分析过程中就变简单了些。 对于语义分析这一块，它是结合语法分析同时进行的，这是此次课程设计的最大的特点，在进行规约时我想出了用栈来保存规约出来的信息，使用栈结构可以保证当前进行规约的所有的信息都在栈的顶部，然后将规约后的信息再保存到栈顶，以便进行下一次规约。这次课程设计的过程中不足主要是在语法分析时，当遇到语法错误时，只能输出出错信息，但是不能指出出错的位置。对于输入程序中，多重赋值语句的识别还有些问题，在四元式中不会显示出来，而且对于if-else语句的嵌套，四元式会出错，有待改进。8.2收获与体会通过这次的课程设计使我在

32、各个方面都得到了很大的提高。首先，在此次课程设计的初期，查阅了很多的书籍，进而编译原理这门课有了更深的理解，并且对以前遗漏的知识点进行了补充。并且对LR分析法有了更加深刻的理解，同时也学会了构造SLR(1)分析表。其次，在此次课程设计的中期，自己对语义分析这一块进行了全面的分析，使我掌握了语法制导翻译的方法。总之，在这次课程设计后我的理论知识，动手动脑能力，有了一定的提高，经过这次课程设计，我从中学到了很多东西，这是以前在书上学不到的，同时也使我认识到同学之间的相互帮助是多么的重要。9 参考文献编译原理（第二版） 张素琴 主编 清华大学出版社数据结构（C语言版）严蔚敏 主编 清华大学出版社C+程序设计 闵联营 主编 清华大学出版社Visual C+ 编程宝典 刘锐宁 主编 人民邮电出版社本科生课程设计成绩评定表班级：计科1006姓名：柯文达 学号：05序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：2013年 月 日专心-专注-专业