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

1、目录1 系统描述（问题域描述）22 文法及属性文法的描述22.1 文法22.2 属性文法23 语法分析方法描述及语法分析表设计33.1 语法分析方法描述33.1 .1LR方法的基本思想33.2 .2LR分析器模型43.2 语法分析表设计54 中间代码形式的描述及中间代码序列的结构设计64.1 中间代码形式的描述64.2 中间代码序列的结构设计65 编译系统的概要设计66 详细的算法描述76.1 系统流程图76.2 算法描述77 软件的测试方法和测试结果187.1 软件的测试方法187.2 测试结果188 设计的特点、不足、收获与体会218.1 特点与不足218.2 收获与体会219 参考文献2

2、110本科生课程设计成绩评定表.22IF-ELS磔件语句的翻译程序设计(LR方法、输出四元式)1 系统描述(问题域描述)对条件语句：if布尔表达式then赋值语句else赋值语句，进行词法，LR(1)语法分析，并根据语法制导翻译方法将条件语句翻译成四元式中间代码形式，最后输出翻译后的四元式代码。2 文法及属性文法的描述2.1 文法GS:S-CSS-TSS-AC-ifEthenT-CSelseT-else其中，E代表布尔表达式，可由界符()括起来，A代表赋值表达式。在这里E、A都代表终结符，具体的表达式在程序会判断其类型。2.2 属性文法S-CSS.clain:=merge(C.clain,S.

3、clain)S-TSS.clain:=merge(T.clain,S.clain)S-AS.clain:0/*空链*/C-ifEthenbackpatch(E.true,nextstat)C.clain:=E.falseT-CSelseq:=nextstatEmit(GOTO)Backpatch(C.clain,nextstat)T.clain:=merge(S.clain,q)3语法分析方法描述及语法分析表设计3.1 语法分析方法描述3.1 .1LR方法的基本思想一个LR分析器实质上是一个带先进后出存储器的确定有限状态自动机。我们将把“历史”和“展望”材料综合地抽象成某些“状态”。分析栈用来

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

5、型LR分析器模型如下图恢分析表图二LR分析器模型LR分析器的核心部分是一张分析表。这张分析表包括两部分，一是“动作”(ACTION表，另一个是“状态转换表”(GOTO羡。它们都是二维数组。ACTIONa规定了当状态s面临输入符号a时应采取什么动作。GOTOa规定了状态s面对文法符号X(终结符或非终结符)时下一个状态是什么。显然GOTOSx定义了一个以文法符号为字母表的DFA每一项ACTIONa所规定的动作不外是下述四种可能之一：1. 移进把(S,A)的下一状态S=GOTOSA和输入符号A隹进栈，下一输入符号变成现行输入状态。2. 规约指用某一产生式A-进行规约。假若的长度为r,归约动作是A,去

6、除栈顶的r个项，使状态Sm-r变成栈顶状态，然后把(Sm-r,A)的下一状态S1=GOTOSm-r,AW口文法符号At进栈。归约动作不改变现行输入符号。执行归约动作意味着(=Xm-r+11Xm)已呈现于栈顶而且是一个相对于A的句柄。3. 接受宣布分析成功，停止分析器的工作。4. 报错发现源程序含有错误，调用出错处理程序。L的析器的总控程序本身的工作是非常简单。它的任何一步只需要按栈顶状态和现行输入符号a执行ACTIONSa所规定的动作。不管什么分析表，总控程序都是一样地工作。一个L电析器的工作过程可看成是栈里的状态序列，已归约用和输入申所构成的三元式的变化过程。分析地的初始三元式(S0,#,a

7、1a2-an#)其中，SM分析器的初态；#为句子的左括号；a1a2an为输入用；其后的#为结束符。分析过程每步的结果可表示为(s0s1-sm,#X1X2,ai-.an#)分析器的下一步动作是由栈顶状态Srnf口现行输入符号ai所唯一决定。即，执行ACTIONSm,ai所规定的动作。经执行每种可能的动作之后，三元式的变化的情形是：(1)若ACTIONSm,ai为移进，且S=GOTOSm,ai,则三元式变成：(S0S1Sm,#X1X2Xmaian#)(2)若ACTIONSm,ai=A,则按产生式A进行归约。此时三元式变为(S0S1Sm-rS,#X1Xm-rA,aiai+1an#)此处S=GOTOS

8、m-r,A,r为的长度，=Xm-r+Xm(3)若ACTIONSm,ai为：接受，则三元式不再变化，变化过程终止，宣布分析成功。(4)若ACTIONSm,ai为“报错”，则三元式的变化过程终止，报告错误。一个LR分析器的工作过程就是一步一步地变换三元式，直至执行“接受”或“报错”为止。3.2 语法分析表设计在做语法分析前需建立SLR(1)语法分析表ACTIONGOTOiteAE#SCT0S5S4S1S2S31ACC2S5S4S6S2S33S51S4S10S2S34r3r35S86飞7r17r5r58S99r4r410r2r2此表中引用记号的意义是:(1)Sj才吁下一状态j和现行输入符号移进栈;(

9、2)rj按第j个产生式进行规约；(3)acc接受；(4)空白格出错标志，报错；4中间代码形式的描述及中间代码序列的结构设计4.1 中间代码形式的描述四元式是一种比较普遍采用的中间代码形式。四元式的四个组成部分是：操作符OP第一个和第二个运算对象ARG体口ARG级运算结果RESULT运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a:=b*c+b*d的四元式表示如下：(1) (*,b,c,t1)(2) (*,b,d,t2)(3) (+,t1,t2,t3)(4) (:=,t3,-,a)4.2中间代码序列的结构设计IfEthenA1elseA2100(关于E的布尔表达式

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

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

12、符就会输出出错信息，同时输出从出错点开始往后的一用字符，但是它仍然能跳过该非法字符继续分析；如果在语法分析中有错误的话，就会显示在DOS环境下输出“ERROR，但是它能跳过出错的地方继续往后执行，分析出一部分结果并保存在文件中。6详细的算法描述6.1 系统流程图6.2 算法描述本程序中，选用C+?序设计语言的部分常用的单词作为词法分析的对象，词法分析后，将识别的所有单词符号以及相关信息保存在数组中，以便后面语法分析和语意分析及中间代码生成使用，同时将识别出的单词符号输出到文件中，并分类别地存储到相应的数组中一便进行查看。采用SLR(1分析法，生成状态表，然后根据栈的移近、移出生成分析过程表。在

13、经过语法、语义分析之后，生成中间代码四元式，同时进行出错管理。voidinitGrammar();/初始化产生式表boolisJchar(charc)/检测是否为分界符intword()/进行词法分析，并存到fenxi.txt文件中wnode*lexcial(wnode*head)/把词法分析得来的词分类别放到表达式数组intcheck(ints,charv);/查LR分析表voidgammarAnalysis(wnode*head);/语法分析及进行相应的语义操作并产生四元式voidshowS(intopS,inttops,charopC,inttopc,wnode*hp);/显示分析栈的内

14、源程序代码：#include#include#include#include#include#includeusingnamespacestd;charFilename100;structwnodecharid;intn;/编号chartext20;wnode*next;structGnode/存储产生式stringgen;intid;Gnodegrammar6;voidinitGrammar();/初始化产生式表wnode*lexcial(wnode*head);intcheck(ints,charv);/查LR分析表voidgammarAnalysis(wnode*head);/语法分析及

15、进行相应的语义操作并产生四元式voidshowS(intopS,inttops,charopC,inttopc,wnode*hp);/显示分析栈的内容/用于if-else分析intLR119=/ACTION|_GOTO/iteAE#SCT105,0,0,104,0,0,101,102,103,/00,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,/30,0,3,0,0,3,0,0,0,/40,0,0,0,108,0,0,0,0,/50,0,107,0,0,1,0,0,0,/65,0,0,

16、5,0,0,0,0,0,/70,109,0,0,0,0,0,0,0,/84,0,0,4,0,0,0,0,0,/90,0,2,0,0,2,0,0,0/10;voidinitGrammar()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-ifEthen;grammar4.id=4;grammar5.gen=T-CSelse;grammar5.id=5;cout所用文

17、法:endl;inti,j;for(i=1;i6;i+)coutgrammari.id-1tgrammari.genendl;cout5telseendl;cout注：i-ift-thene-elseendl;coutE布尔表达式(在语法分析中看成是终结符)endl;coutA赋值语句(在语法分析中看成是终结符)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)

18、Tendl;for(i=0;i11;i+)coutsetw(2)i;for(j=0;j=110)coutsetw(4)S100)coutsetw(5)S0)coutsetw(5)rLRij;elseif(LRij=0)coutsetw(6);elsecoutsetw(6)ACC;coutendl;boolisJchar(charc)/检测是否为分界符boolr=false;switch(c)case:casen:case;:r=true;break;default:;returnr;intword()charch=;intnum=0;ifstreamsource(source.txt);ofs

19、treamfenxi(fenxi.txt);charyunsuanfu11=+,-,*,/,=,!,%,&,|;charjiefu9=,;,(,),#;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);charshuzi20=;inti=1;if(ch=O&ch=O&ch-9)

20、|ch=)&!source.eof()(coutch;shuzii+=ch;source.get(ch);)fenxishuzi数字vvendl;)for(i=0;i=10;i+)/运算符判断(if(ch=yunsuanfui)(fenxiwchvv运算符endl;)for(i=0;i=a&ch=a&ch=O&力为)|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)fenxistr

21、1标识符endl;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;fstreaminfile(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=+Ecount;elseif(l

22、oc!=-1)q-id=A;q-n=+Acount;elseq-id=q-text0;if(q-id=i)head-n+;p-next=q;p=q;mark=0;elseif(mark=0)q=newwnode;q-n=0;q-next=NULL;loc=-1;k=0;mark=1;q-textk+=c;/在末尾加上一个#q=newwnode;q-next=NULL;q-id=#;q-text0=0;q-n=0;p-next=q;returnhead;/语法分析voidgammarAnalysis(wnode*head)charE20;charA20;charr,d1,d2;inttn=0,e

23、n=head-n;ofstreamtable;table.open(siyuanshi.txt);if(!table)coutCannotopenoutputfile!endl;exit(1);cout语法分析过程：endl;cout分析栈输入串操作next;inttops=0;inttopc=0;opStops=0;opCtopc=#;while(p)showS(opS,tops,opC,topc,p);if(topsid;if(c=E)for(i=0;itexti!=0;i+)Ei=p-texti;Ei=0)if(c=A)(for(i=0;itexti!=0;i+)Ai=p-texti;A

24、i+=;Ai=0;)mark=check(opStops,c);switch(mark)(case-1:coutt语法分析，翻译成功endl;table+loc;table.close();return;case1:tops=tops-2;topc=topc-1;opCtopc=S;couttt归约grammar1.genendl;break;case2:tops=tops-2;topc=topc-1;opCtopc=S;couttt归约grammar2.genendl;break;case3:tops=tops-1;topc=topc-0;opCtopc=S;couttt归约grammar3

25、.genendl;r=A3;d1=A2;d2=A4;table+loct(rtd1td2tT+tn)endl;table+loct(=vtTtnttA0)endl;break;case4:tops=tops-3;topc=topc-2;opCtopc=C;couttt归约grammar4.genendl;r=E2;d1=E1;if(r=)d2=E4;elsed2=E3;table+loct(r;if(r=)tablertd1td2tloc+2)endl;elsetabletd1td2tloc+2)endl;if(en=1)table+loct(gototttloc+4)endl;elsetab

26、le+loct(gototttloc+4+2*(en)endl;break;case5: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;case0:coutERROR!endl;return;voidshowS(intopS,inttops,charopC,inttopc,wnode*hp)/coutendl;inti=0,j=0;wnode*tp=

27、hp;for(i=0;i=topc;i+)coutopCi;coutt;while(tp)coutid;tp=tp-next;coutendl;for(i=0;i=tops;i+)coutopSi;/coutendl;intcheck(ints,charv)intt=-1;switch(v)casei:t=0;break;caset:t=1;break;casee:t=2;break;caseA:t=3;break;caseE:t=4;break;case#:t=5;break;caseS:t=6;break;caseC:t=7;break;caseT:t=8;break;default:;i

28、ntr=LRst;returnr;intmain()FILE*fp;intn=100;coutn*IF-ELSE条件语句的翻译程序设计(LR方法、输出四元式)*endl;initGrammar();cout请输入文件名:;cin.getline(Filename,n);fp=fopen(Filename,r);while(fp=NULL)/若打入的文件没有，则提示继续打入有效的路径名coutSorry,文件不存在!endl;coutid=#;wlist-n=0;wlist-text0=0;wlist-next=NULL;wlist=lexcial(wlist);fclose(fp);word(

29、);gammarAnalysis(wlist);ifstreamfin(siyuanshi.txt);strings;cout输出四元式为：endl;while(getline(fin,s)coutscsS-TSS-ftC-ifEthenT-CSelseT-eIsei-ift-thene-eIseE敕叔日上在陶榜近赋值语句（走语法分析句配C,Windov.systern32cmd.exe输入保存已写好的程序的文件名source.txt,回车键，词法分析生成单词表，语法分析生成语法分析过程和中间代码四元式条件语句代码：source-记事本文件的铜瓦格式(0)查看才帮助(H)if(ab)then工

30、二y+z;elsex=y-z;|词法分析单词表:二fenxi-记事本五件内编辑后格式壹看M帮助两识算识符与只士具识算识符与识算识算识:装运标界he标运标运标界1S标运标运标寅(aXZb),tM=y+z.-es-y-z;5ttiE058ttLEt自589件名:source.txtSi：输入串操作iEtAeAUEtAeAtttAeAttAeAttAeASAeAltC-iFEthenSBC：MFindowssystem32cmd.exeS-AeAtl移入eAtt移入归约TACSelse移入移入tt归约8-Att移入tt归约S-TStt移入ttT03北TH034ttTSttTS0310bsns01SBC:WindowsXsystem32cmd.exepR24ItCS,2ttGS026ttCSe0267ItT移入移入移入归约移入4t语法5ah102105 yaTl?T1Q107 前出四元式为；130。101(goto102+103104s(ato105106107请按任意键继续8设计的特点、不足、收获与体会