编译原理上机实验程序(LR分析).docx

小型编译程序：高级语言到四元式的编译ttincludestdio.h/*如果使用TC的话，需要配置头文件路径*/#includestring.h/*如果使用VC的话，可以配置头文件conio.h*/ftdefineACC-2/*/ftdefinesy_if0ftdefinesythen1#definesyeIse2#definesywhile3#definesybegin4ftdefinesydo5ftdefinesyend6ftdefinea7ftdefinesemicolon8ttdefinee9#definejinghao10ftdefineS11ftdefineL12#definetempsy15ftdefineEA18*Eand*/ftdefineEO19*Eor*/#defineplus34#definetimes36ftdefinebecomes38ftdefineopand39ftdefineopor40ftdefineopnot41ftdefinerop42#define!parent48ftdefinerparent49ftdefineident56ftdefineintconst57/*/charch-0,;/*从字符缓冲区读取当前字符*/intcount=0;/*词法分析结果缓冲区计数器*/staticcharSPening10="*存放识别的单词符号*/staticcharIine81="*一行字符缓冲区，最多80个字符*/charSpline;/*字符缓冲区指针*/staticcharntabl10010;/*变量名表，共100项，每项长度10*/structntabintinttc;fc；ntab2200;intIabel=O;/*真值*/*假值*/*在布尔表达式E中保存有关布尔变量的真、假值*/*指向ntab2的指针*/*存放临时变量的表的定义*/structrwordscharsp10;intsy;)；*保存字表)匹配表的结构，用来与输入缓冲区中的单词进行匹配*/*匹配表初始化，大小为10*/structrwordsreswords10-zzifzz,sy_if),do，sy_do,z,elsezz,sy_else,whilez,sy_while,thenzz,sy_then),zbegin,z,sy_begin,end，sy_end,and，opand,zzorzz,opor,structaaintsyl;intpos;buf1000,n,nl,E,sstack100,ibuf100,stack1000;structaaoth;not，opnot);/*存放单词符号的种别编码*/*存放单词符号自身的值*/*词法分析结果缓冲区，保存识别出来的单词符号*/*读取二元式的当前符号*/*当前表达式中的符号*/*非终结符*/*算术或布尔表达式加工处理使用的符号栈*/*算术或布尔表达式使用的缓冲区*/*语法分析加工处理使用的符号栈*/*四元式中空白位置*/structfourexpcharop10;structaaargl;structaaarg2;intresult;fexp200;*四元式的结构定义*/intssp=O;/*指向SStaCk栈指针*/structaa*pbuf=buf;/*指向词法分析缓冲区的指针*/intnlength=O;intInum=O;/*词法分析中记录单词的长度*/*源程序行数记数，源程序长度*/intttl=O;FILEdefile;Afile*mfiie;*/*变量名表指针*/*源程序文件，为结束符*/intnewt=0;intnxq=100;/*临时变量计数器*/*nxq指向下一个形成的四元式的地址*/*每次执行gen）时，地址自动增1*/i11tIr;/*扫描LR分析表1过程中保存的当前状态值*/intIrl;intsp=O;/*扫描LR分析表2或表3所保存的当前状态值*/*查找LR分析表时状态栈的栈顶指针*/intStackl100;intspl=O;intnum=0;struct11intnxql;inttcl;intfcl;labelmark10;/*状态栈1的定义*/*状态栈1的栈顶指针*/*算术或布尔表达式缓冲区指针*/*记录下一条四元式的地址*/*真值链*/*假值链*/*记录语句嵌套层次的数组，*/*即记录嵌套中每层的布尔表达式E的首地址*/intIabeltempElO;/*记录语句嵌套层次的数组，*/*即记录每层else之前的四元式地址*/intpointmark=-l,pointtemp=-l;/5IcIabelmark数组指针*/*labeltemp数组指针*/intsign=O;Asign=I,为赋值语句；sign=2,为布尔表达式。/*程序语句LR分析表*/staticintaction1913=/*0*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,-1,-1),/*1*/-l,-1,-1,-1,-1,-1,-1,-1,-1,-1,ACC,-1,-1),/*2*/-l,-l,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,/*3*/-l,-l,-1,-1,-1,-1,-1,-1,-1,7,-l,-l,-l,/*4*/2,-l,-l,3,4,-1,-1,5,-1,-1,-1,9,8),/*5*/-l,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1,/*6*/1,10,十-1,1,1,1,1,1,1,1,1,/*7*/1,1,1,-1,11,1,1,1,1,1,1,1,/*8*/1,1,1,-1,-1,1,12,1,1,1,1,1,1),*9*T,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,T,/*10*/2,-l,-l,3,4,-1,-1,5,-1,-1,-1,14,-1),/*11*/2,-l,-l,3,4,-1,-1,5,-1,-1,-1,15,-1),*12*/-l,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1,/*13*/2,-l,-l,3,4,-1,-1,5,-1,-1,-1,9,16),/*14*/-l,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1),/*15*/-l,-1,102,-1,-1,-1,102,-1,102,-1,102,-1,-1),/*16*/-l,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1),/*17*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1),/*18*/-l,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1;/*算术表示式的LR分析表*/staticintactionl107=/*0*/3,-l,-l,2,-l,-l,1,/*1*/-l,4,5,-l,-l,ACC,-l,/*2*/3,-l,-l,2,-l,-l,6,*3*-l,104,104,-1,104,104,-1,/*4*/3,-l,-l,2,-l,-l,7,/*5*/3,-l,-l,2,-l,-l,8,/*6*/-l,4,5,-l,9,-l,-l,/*7*/-l,101,5,-1,101,101,-l,/*8*/-l,102,102,-1,102,102,-1,/*9*/-l,103,103,-1,103,103,-1;/*布尔表示式的LR分析表*/staticintaction21611=/*0*/1,-1,4,-1,5,-1,-1,-1,13,7,8,/*1*/-l,2,-l,101,-1,101,101,o,-,-,-,/*2*/3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1),*3*-l,-l,-l,102,-1,102,102,102,-1,-1,-1),/*4*/1,-1,4,-1,5,-1,-1,-1,11,7,8),/*5*/1,-1,4,-1,5,-1,-1,-1,6,7,8),/*6*/-l,-l,-l,104,-1,9,10,104,-1,-1,-1),/*7*/1,-1,4,-1,5,-1,-1,-1,14,7,8),/*8*/1,-1,4,-1,5,-1,-1,-1,15,7,8),/*9*/105,-1,105,-1,105,-1,-1,-1,-1,-1,-1),/*10*/107,-1,107,-1,107,-1,-1,-1,-1,-1,-1),/*11*/-l,-l,-l,12,-1,9,10,-l,-l,-l,-l,*12*/-l,-l,-l,103,-1,103,103,103,-1,-1,-1),/*13*/-l,-l,-1,-1,-1,9,10,ACC,-1,-1,-1),/*14*/-l,-l,-l,106,-1,9,10,106,-1,-1,-1),/*15*/-l,-l,-l,108,-1,9,10,108,-1,-1,-1;/*从文件读一4亍至U缓冲区*/voidreadline()charchi;pline=line;chl=fgetc(cfile);while(chi!=,n&&!feof(cfile)line=chl;pline+;chl=fgetc(cfile);*pline='0,;pline=line;/*从缓冲区读取一*个字符*/voidreadch()(if(Ch='0')readline();Inum+;)Ch=*pline;pline+;)/*初利白勺另"*/find(charspel)intssl=O;intii=0;while(SSI=O)&&(ii<nlength)if(!strcmp(spel,ntablii)ssl=l;ii+;)if(ssl=l)returnii-l;elsereturn-1;)voididentifier()(intiii=0,j,k;intss=O;k=0;dospellingk=ch;k+;readch();while(ch>=，a,)&&(Ch='z,)(ch>=，0')&&(Ch二'9,);pline一一;SPeningk='0,;while(SS=O)&&(iii<10)if(!strcmp(spelling,reswordsiii.sp)ss=l;iii+;*关键字匹配*/if(ss=l)bufcount.syl=reswordsiii-l.sy;)elsebufcount.syl=ident;j=find(spelling);if(j=-l)bufcount.pos=ttl;strcpy(ntablttl,spelling);ttl+;nlength+;elsebufcount.pos=j;)count+;for(k=0;k<10;k+)spellingk=，'/*数字的识另”*/voidnumber()intintdoivalue=0;digit;digit=ch-505;ivalue=ivalue*10+digit;readch();while(ch>三,0')&&(Ch='9,);bufcount.syl=intconst;bufcount.pos=ivalue;count+;pline一;/*扫描主函数*/voidscan()while(Ch!=')switch(ch)casebreak;case'a,:case'b,:case,c,:case'd,:case'e,:case,f,:case'g,:case'h,:case'i,:case'j,:case'k,:case':case'm,:case,n,:case'o,:case'p,:case'q,:case'r,:case's,:case't,:case'u,:case'v,:case,w,:case,:case'y,:case'z,:identifier();break;case0,:case':case2,:case3,:case4,:case,5,:case'65:case'7,:case,8,:case'95:number();break;case'<,:readch();if(Ch='=,)bufcount.pos=0;elseif(Ch='>,)bufcount.pos=4;elsebufcount.pos=l;pline一;)bufcount.syl=rop;count+;break;case,>>:readch();if(ch=，=,)(bufcount.pos=2;)elsebufcount.pos=3;pline一;)bufcount,syl=rop;count+;break;case,(,:bufcount.Syl=Iparent;count+;break;case'):bufcount.syl-rparent;count+;break;case'#':bufcount.syl=jinghao;count+;break;case'+':bufcount.syl=plus;count+;break;case'*':bufcount.syl=times;count+;break;case:readch();if(ch=，=,)bufcount.syl=becomes;count+;break;case'-:bufcount.syl=rop;bufcount.pos=5;count+;break;case':bufcount.syl=semicolon;count+;break;)readch();)bufcount.syl=l;voidreadnu()(if(pbuf->syl>=O)n.syl=pbuf->syl;n.pos=pbuf->pos;pbuf+;)/*中间变量的生成*/newtemp()newt+;returnnewt;)/*生成四元式*/gen(charopl,structaaargil,structaaarg22,intresultl)strcpy(fexpnxq.op,opl);fexpnxq.argl.syl=argll.syl;fexpnxq.argl.pos=argll.pos;fexpnxq.arg2.syl=arg22.syl;fexpnxq.arg2.pos=arg22.pos;fexpnxq.result=resultl;nxq+;returnnxq-1;/*布尔表示式的匹酉己*/merg(intpl,intp2)intp;if(p2=0)returnpl;elseP=p2;while(fexpp.result!=0)p=fexpp.result;fexpp.result=pl;returnp2;)voidbackpatch(intp,intt)inttempq;intq;q=P；while(q!=0)tempq=fexpq.result;fexpq.result=t;q=tempq;)changel(intchan)switch(chan)caseident:caseintconst:return0;caseplus:return1;casetimes:return2;case!parent:return3;caserparentreturn4casejinghaoreturn5casetempsy:return6;default:return100;)change2(intchan)switch(chan)caseident:caseintconst:return0;caserop:return1;case!parent:return2;caserparent:return3;caseopnot:return4;caseopand:return5;caseopor:return6;casejinghao:return7;casetempsy:return8;caseEA:return9;caseEO:return10;default:return100;)/*赋值语句的分析*/voidIrparsel(intnum)intIrl;lrl=actionlstacklsplchangel(nl.syl);if(lrl=-l)Printf(n算术表达式或赋值语句出错！n)；getchar();/exit(0);if(IrKlO)&&(Irl>=0)spl+;stacklspl=Irl;if(nl.syl!=tempsy)ssp+;num+;sstackssp.syl=nl.syl;sstackssp.pos=nl.pos;)nl.syl=ibufnum.syl;nl.pos=ibufnum.pos;Irparsel(num);)if(lrl>=100)&&(lrl,105)switch(Irl)case 100:break;case 101:E.pos=newtemp();gen(zz+zz,sstackssp-2,sstackssp,E.pos+100);ssp=ssp-2;sstackssp.syl=tempsy;sstackssp.pos=E.pos;spl=spl_3;break;case 102:E.pos=newtemp();gen(*，sstackssp-2,sstackssp,E.pos+100);ssp=ssp-2;sstackssp.syl=tempsy;sstackssp.pos=E.pos;spl=spl_3;break;case 103:E.pos=sstackssp-l.pos;ssp=ssp-2;sstackssp.syl=tempsy;sstackssp.pos=E.pos;spl=spl_3;break;case 104:E.pos=sstackssp.pos;spl;break;nl.syl=tempsy;*归约后为非终结符*/nl.pos=E.pos;Irparsel(num);)if(Irl=ACC)&&(stacklspl=l)gen(:=zz,sstackssp,oth,ibuf0.pos);ssp=ssp_3;spl=spl_3;)/*Jk,白勺*/lrparse2(intnum)inttemplabel;lrl=action2stacklsplchange2(nl.syl);if(lrl=-l)if(sign=2)Printf("nwhile语句出错！n)；if(sign=3)Printf(nif语句出错！n);getchar();/exit(0);)if(lrl<16)te(lrl>=0)(spl+;stacklspl=lrl;ssp+;sstackssp.syl=nl.syl;sstackssp.pos=nl.pos;if(nl.syl!=tempsy)&&(nl.syl!=EA)&&(nl.syl!=E0)num+;nl.syl=ibufnum.syl;nl.pos=ibufnum.pos;lrparse2(num);)if(lrl>=100)(lrl<109)(switch(Irl)case100:break;case101:ntab2label.tc=nxq;ntab2label.fc=nxq+l;gen(jnz，sstackssp,oth,0);gen(zzjzz,oth,oth,0);spl;ssp;label+;nl.syl=tempsy;break;case102:ntab2label.tc=nxq;ntab2label.fc=nxq+l;switch(sstackssp-l.pos)case0:gen(/zj<=zz,SStaCkssp-21,sstackssp,0);break;case 1:gen(/zj<zz,sstackssp-2,sstackssp,0);break;case 2:gen(/zj>=zz,sstackssp-2,sstackssp,0);break;case 3:gen(/zj>zz,sstackssp-2,sstackssp,0);break;case 4:gen(/zj<>z,sstackssp-2,sstackssp,0);break;case 5:gen(zzj=z,sstackssp-2,sstackssp,0);break;)gen(zzjzz,oth,oth,0);ssp=ssp_3;spl=spl-3;label+;nl.syl=tempsy;break;case 103: /*B->(B)*/Iabel=Iabel-I;ssp=ssp_3;spl=spl_3;label+;nl.syl=tempsy;break;case 104: *B->notB*/Iabel=Iabel-I;templabel=ntab2label.tc;ntab2label.tc=ntab2label.fc;ntab2label.fc=templabel;ssp=ssp-2;spl=spl_2;label+;nl.syl=tempsy;break;case 105: *A->Band*/backpatch(ntab2label_l.tc,nxq);Iabel=Iabel-I;ssp=ssp-2;spl=spl_2;label+;nl.syl=EA;break;case 106: /*B->AB*/label=label-2;ntab2label.tc=ntab2label+1.tc;ntab2label.fc=merg(ntab2label.fc,ntab2label+1.fc);ssp=ssp-2;spl=spl_2;label+;nl.syl=tempsy;break;case 107: /*0-Bor*/backpatch(ntab2label_l.fc,nxq);Iabel=Iabel-I;ssp=ssp-2;spl=spl_2;label+;nl.syl=E0;break;case 108: /*B->OB*/label=label-2;ntab2label.fc=ntab2label+1.fc;ntab2label.tc=merg(ntab2label.tc,ntab2label+1.tc);ssp=ssp-2;spl=spl_2;label+;nl.syl=tempsy;break;lrparse2(num);if(Irl=ACC)return1;elsereturnO;)/*测试字符是否为表达式中的值不包括；*/test(intvalue)(switch(value)caseintconst:caseident:caseplus:casetimes:casebecomes:case!parent:caserparent:caserop:caseopand:caseopor:caseopnot:return1;default:return0;)Irparse()*程序语句处理*/(intil=0;intnum=0;*指向表达式缓冲区*/if(test(n.syl)if(stacksp.syl=sywhile)sign=2;else(if(stacksp.syl=sy_if)sign=3;elsesign=l;)doibufil.syl=n.syl;ibufil.pos=n.pos;readnu();il+;while(test(n.syl);/*把表达式放入缓冲区*/ibufil.syl=jinghao;pbuf一;/*指针后退1,需要吗？*/sstack0.Syl=Jinghao;ssp=O;/*符号栈底的初始化*/if(sign=l)/*赋值语句处理*/spl=O;stacklspl=O;/*状态栈1的栈底初始化*/num=2;/*指向：=*/nl.syl=ibufnum.syl;nl.pos=ibufnum.pos;Irparsel(num);n.syl=a;/*当前文法符号置为a赋值语句*/)if(sign=2)II(sign=3)/*布尔表达式处理*/(pointmark+;labelmarkpointmark.nxql=nxq;spl=O;stacklspl=O;num=0;nl.syl=ibufnum.syl;nl.pos=ibufnum.pos;lrparse2(num);labelmarkpointmark.tcl=ntab2label-l.tc;labelmarkpointmark.fcl=ntab2label-l.fc;*在处理完E后，要回填真值链*/backpatch(labelmarkpointmark.tcl,nxq);n.syl=e;/*当前文法符号置为e布尔表达式*/)lr=actionstacksp.posn.syl;printf(zzstack%d=%dttn=%5dttlr=%dnzz,sp,stacksp.pos,n.syl,Ir);if(lr<19)&&(lr>=0)*移进*/sp+;stacksp.pos=lr;stacksp.syl=n.syl;readnu();Irparse();)if(lr<=106)&&(lr>=100)*归约*/switch(Ir)case 100: *S'一S*/break;case 101: *S->ifethenSelseS*/printf(zzS->ifethenSeiseS归约n)；sp=sp-6;n.syl=S;case 102: then后的无条件转移语句*/fexplabeltemppointtemp.result=nxq;pointtemp一;if(stacksp.syl=sythen)gen(zzjzz,oth,oth,0);backpatch(labelmarkpointmark.fcl,nxq);pointtemp+;IabeItemppointtemp=nxq-l;)pointmark-;if(stacksp.syl=sy_do)gen(zzjzz,oth,oth,labelmarkpointmark.nxql);backpatch(labelmarkpointmark.fcl,nxq);)break;case102:*S-WhiIeedoS*/printf(zzS->whileedoS归约n)；sp=sp-4;n.syl=S;pointmark一;if(stacksp.syl=sydo)(gen(j,oth,oth,labelmarkpointmark.nxql);backpatch(labelmarkpointmark.fcl,nxq);)fexplabeltemppointtemp.result=nxq;if(stacksp.syl=sythen)gen(zzjzz,oth,oth,0);fexplabelmarkpointmark.fcl.result=nxq;pointtemp+;Iabeltemppointtemp=nxq-l;)break;case 103: *S->beginLend*/printf(zzS->beginLend归约n)；sp=sp-3;n.syl=S;if(stacksp.syl=sythen)gen(zzjzz,oth,oth,0);backpatch(labelmarkpointmark.fcl,nxq);pointtemp+;IabeItemppointtemp=nxq-l;)if(stacksp.syl=sydo)gen(j，oth,oth,labelmarkpointmark.nxql);backpatch(labelmarkpointmark.fcl,nxq);)getchar();break;case 104: /*S->a*/printf(z,S->a归约n)；sp=sp-l;n.syl=S;if(stacksp.syl=sythen)gen(zzjzz,oth,oth,0);backpatch(labelmarkpointmark.fcl,nxq);pointtemp+;IabeItemppointtemp=nxq-l;)if(stacksp.syl=sydo)gen(j，oth,oth,labelmarkpointmark.nxql);backpatch(labelmarkpointmark.fcl,nxq);)break;case 105: /*L->S*/printf(zzL->S归约n)；sp=sp-l;n.syl=L;break;case 106: /*L->S;L*/printf(zzL->S;S归约n)；sp=sp-3;n.syl=L;break;)getchar();pbuf-一;Irparse();)if(Ir=ACC)returnACC;elsereturnO;/*displ*/voiddispl()inttempl=O;printf(n*词法分析结果*