北邮《语法分析程序》实验报告

语法分析程序实验报告需求分析题目：语法分析程序的设计与实现。实验内容：编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。numEidFFFTFTTTTETEE|)(||/|*||实验要求：在对输入表达式进行分析的过程中，输出所采用的产生式。方法1：编写LL(1)语法分析程序，要求如下。(1)编程实现算法4.2，为给定文法自动构造预测分析表。(2)编程实现算法4.1，构造LL(1)预测分析程序。方法2：编写语法分析程序实现自底向上的分析，要求如下。(1)构造识别所有活前缀的DFA。(2)构造LR分析表。(3)编程实现算法4.3，构造LR分析程序。概要设计1.LL(1)语法分析程序（1）.原文法numEidFFFTFTTTTETEE|)(||/|*||（2）.消除左递归和回溯E-TRR-+TRR--TRR-eT-FWW-*FWW-/FWW-eF-idF-(E)F-num（3）.FISRT集和FOLLOW集FIRST(S)={id,num,(}FOLLOW(S)={$}FIRST(E)={id,num,(}FOLLOW(E)={$,+,-,)}FIRST(T)={id,num,(}FOLLOW(T)={$,+,-,*,/,)}FIRST(F)={id,num,(}FOLLOW(F)={$,+,-,*,/,)}（4）.LL(1)预测分析表2.LR实现，自底向上分析（1）.原文法numEidFFFTFTTTTETEE|)(||/|*||（2）.文法对应的拓广文法为：1E-E+T2E-E-T3E-T4T-T*F5T-T/F6T-F7F-(E)8F-id9F-num（3）.FISRT集和FOLLOW集FIRST(S)={id,num,(}FOLLOW(S)={$}FIRST(E)={id,num,(}FOLLOW(E)={$,+,-,)}FIRST(T)={id,num,(}FOLLOW(T)={$,+,-,*,/,)}FIRST(F)={id,num,(}FOLLOW(F)={$,+,-,*,/,)}（4）.构造项目集规范族I0=closure({S-·E})={S-·E,E-·E+T,E-·E-T,E-·T,T-·T*F,T-·T/F,T-·F,F-·id,F-·(E),F-·num};从I0出发：I1=go(I0,E)=closure({S-E·,E-E·+T,E-E·-T})={S-E·,E-E·+T,E-E·-T};I2=go(I0,T)=closure({E-T·,T-T·*F,T-T·/F})={E-T·,T-T·*F,T-T·/F};I3=go(I0,F)=closure({T-F·})={T-F·};I4=go(I0,id)=closure({F-id·})={F-id·};I5=go(I0,()=closure({F-(·E)})={F-(·E),E-·E+T,E-·E-T,E-·T,T-·T*F,T-·T/F,T-·F,F-·id,F-·(E),F-·num};I6=go(I0,num)=closure({F-num·})={F-num·};从I1出发：I7=go(I1,+)=closure({E-E+·T})={E-E+·T,T-·T*F,T-·T/F,T-·F,F-·id,F-·(E),F-·num};I8=go(I1,-)=closure({E-E-·T})={E-E-·T,T-·T*F,T-·T/F,T-·F,F-·id,F-·(E),F-·num};从I2出发：I9=go(I2,*)=closure({T-T*·F})={T-T*·F,F-·id,F-·(E),F-·num};I10=go(I2,/)=closure({T-T/·F})={T-T/·F,F-·id,F-(E),F-·num};从I5出发：I11=go(I5,E)=closure({F-(E·),E-E·+T,E-E·-T})={F-(E·),E-E·+T,E-E·-T};从I7出发：I12=go(I7,T)=closure({E-E+T·,T-T·*F,T-T·/F})={E-E+T·,T-T·*F,T-T·/F};从I8出发：I13=go(I8,T)=closure({E-E-T·,T-T·*F,T-T·/F})={E-E-T·,T-T·*F,T-T·/F};从I9出发：I14=go(I9,F)=closure({T-T*F·})={T-T*F·};从I10出发：I15=go(I10,F)=closure({T-T/F·})={T-T/F·};从I11出发：I16=go(I11,))=closure({F-(E)·})={F-(E)·};LR分析表如下：goto[0,E]=1;goto[0,T]=2;goto[0,F]=3;action[0,id]=S4;action[0,(]=S5;action[0,num]=S6;action[1,$]=ACC.;action[1,+]=S7;action[1,-]=S8;;action[2,)]=action[2,+]=action[2,-]=action[2,$]=R4;action[2,*]=S9;action[2,/]=S10;action[3,)]=action[3,+]=action[3,-]=action[3,*]=action[3,/]=action[3,$]=R7;action[4,)]=action[4,+]=action[4,-]=action[4,*]=action[4,/]=action[4,$]=R8;goto[5,E]=11;goto[5,T]=2;goto[5,F]=3;action[5,id]=S4;action[5,(]=S5;action[5,num]=S6;action[6,)]=action[6,+]=action[6,-]=action[6,*]=action[6,/]=action[6,$]=R10;goto[7,T]=12;goto[7,F]=3;action[7,id]=S4;action[7,(]=S5;action[7,num]=S6;goto[8,T]=13;goto[8,F]=3;action[8,id]=S4;action[8,(]=S5;action[8,num]=S6;goto[9,F]=14;action[9,id]=S4;action[9,(]=S5;action[9,num]=S6;goto[10,F]=15;action[10,id]=S4;action[10,(]=S5;action[10,num]=S6;action[11,)]=S16;action[11,+]=S7;action[11,-]=S8;action[12,)]=action[12,+]=action[12,-]=action[12,$]=R2;action[12,*]=S9;action[12,/]=S10;action[13,)]=action[13,+]=action[13,-]=action[13,$]=R3;action[13,*]=S9;action[13,/]=S10;action[14,)]=action[14,+]=action[14,-]=action[14,*]=action[14,/]=action[14,$]=R5;action[15,)]=action[15,+]=action[15,-]=action[15,*]=action[15,/]=action[15,$]=R6;action[16,)]=action[16,+]=action[16,-]=action[16,*]=action[16,/]=action[16,$]=R9;DFA:（5）.LR分析表状态actiongoto+-*/idnum()$ETF0s4S6S51231s7s8acc2r3r3s9s10r3r33r6r6r6r6r6r64r7r7r7r7r7r75s4s6s511236r9r9r9r9r9r97s4s6s51238s4s6s51339s4s6s51410s4s6s51511s7s8s161612r1r1s9s10r1r113r2r2s9s10r2r214r4r4r4r4r4r415r5r5r5r5r5r516r8r8r8r8r8r8运行结果LL(1):测试用例：(1+(a+b)*5/6)测试用例：1测试用例：a2+kLR:测试用例：(1+(a+b)*5/6)测试用例：1测试用例：a2+k源代码#includestdlib.h#includestring#includeiostream#includefstream#includevectorusingnamespacestd;//非终结字符类classChar{public:stringFIRST;//first集stringFOLLOW;//follow集Char(){};//构造函数~Char(){};//析构函数voidfirst(strings){FIRST=FIRST+s;}//读入first集voidfollow(strings){FOLLOW=FOLLOW+s;}//读入follow集};//产生式类classGene{public:charleft;//产生式左部非终结符stringright;//产生式右部字符串stringFIRST;//右部的first集stringFOLLOW;//左部的follow集Gene(){};~Gene(){};voidproduct(stringa){left=a[0];intk=a.size();for(inti=3;ik;i++)right[i-3]=a[i];}voidfirst(stringa){FIRST=FIRST+a;}voidfollow(stringa){FOLLOW=FOLLOW+a;}};intfind(strings,charch){intk=s.size();for(inti=0;ik;i++)if(ch==s[i])returni;return0;}voidLL1(){stringG1[11];//存入LL(1)文法//G1[0]=E-TA;G1[1]=A-+TA;G1[2]=A--TA;G1[3]=A-e;G1[4]=T-FB;G1[5]=B-*FB;G1[6]=B-/FB;G1[7]=B-e;G1[8]=F-d;G1[9]=F-(E);G1[10]=F-n;cout\n*********************************LL(1)************************************;cout\n消除左递归和回溯：endl;for(inti=11;i0;i--){coutG1[11-i]\t;if(i%3==0)coutendl;}coutendl;//存入非终结字符的first集follow集CharE;E.first(d(n);E.follow($));CharA;A.first(+_e);A.follow($));//A=E'CharT;T.first(d(n);T.follow(+-$));CharB;B.first(*/e);B.follow(+-$));//B=T'CharF;F.first(d(n);T.follow(*/+-$));//定义一个Gene类的vector存入全部产生式的左部和右部vectorGeneg(11);g[0].product(G1[0]);g[0].FIRST=T.FIRST;g[0