实验题目：语法分析程序设计与实现(LR).docx

实验题目：语法分析程序设计与实现(LR)一实验内容：编写语法分析程序，实现对算数表达式的语法分析。要求所分析算数表达式由如下的文法产生。E-E+T|E-T|TT-T*F|T/F|FF-id|(E)|num二实现要求：在对输入表达式进行分析的过程中，输出所采用的产生式。方法3：编写语法分析程序实现自底向上的分析，要求如下：1) 构造识别所有或前缀的DFA2) 构造LR分析表3) 编程实现算法4.3，构造LR分析程序三程序设计说明1.拓广文法。加入产生式 S-E。2.构造项目集规范族（由于作图能力有限，DFA不在此进行显示）。该过程中考虑到文法是通过字符串数组存储的，故分析过程是一个字符一个字符进行的，所以如果出现类似num,id多个字符构成一个整体的形式，难以处理，程序中对于这种情况采取只取第一个字符的方式处理，也就是用n代替num,i代替id。对生成式进行编号后：0. S-E1.E-E+T4.T-T*F7.F-i2.E-E-T5.T-T/F8.F-(E)3.E-T6.T-F9.F-n I0 =closure(SE)= SE，EE+T，EE-T，ET，TT*F，TT/F，TF，Fi，F(E)，Fn从I0出发的转移有I1=go(I0 ,E)=closure(SE, EE+T，EE-T)=SE，EE+T，EE-TI2=go(I0 ,T)=closure(ET, TT*F, TT/F)= ET，TT*F， TT/F I3=go(I0 ,F)=closure(TF )= TF I5=go( I0,( )= closure(F(E)= F(E), EE+T，EE-T，ET，TT*F，TT/F，TF，Fi，F(E)，Fn I6=go(I0,n)= closure(Fn )= Fn 从I1出发的转移有I7=go(I1,+)= closure(EE+T )=EE+T，TT*F，TT/F，TF，Fi，F(E)，Fn I8=go(I1, -)= closure(EE-T )= EE-T ，TT*F，TT/F，TF，Fi，F(E)，Fn 从I2出发的转移有I9=go(I2, *)= closure(TT*F )= TT*F，Fi，F(E)，Fn I10=go(I2, /)= closure(TT/F )= TT/F，Fi，F(E)，Fn 从I5出发的转移有I11=go(I5, E)= closure(F(E), EE+T, EE-T )=F(E), EE+T, EE-T go(I5, T)=I2 go(I5, i)=I4 go(I5, ( )=I5 go(I5, n)=I6从I7出发的转移有I12=go(I7, T)= closure(EE+T，TT*F，TT/F )= EE+T，TT*F, TT/F go(I7, F)=I3 go(I7, i)=I4 go(I7, ( )=I5 go(I7, n)=I6从I8出发的转移有I13=go(I7, T)= closure(EE-T，TT*F，TT/F )= EE-T，TT*F, TT/F go(I8, F)=I3 go(I8, i)=I4 go(I8, ( )=I5 go(I8, n)=I6从I9出发的转移有I14=go(I9,F)= closure(TT*F )= TT*F go(I9, i)=I4 go(I9, ( )=I5 go(I9, n)=I6从I10出发的转移有I15= go(I10,F)= closure(TT/F )go(I10, i)=I4 go(I10, ( )=I5 go(I10, n)=I6从I11出发的转移有I16= go(I11, )= closure(F(E) )=F(E) go(I11, +)=I7 go(I11, - )=I8从I12出发的转移有go(I12, *)=I9 go(I12, / )=I10从I13出发的转移有go(I13, *)=I9 go(I13, / )=I10 3.构造分析表状态ActionGoto+-*/in()$ETF0s4s6s51231s7s8ACC2r3r3s9s10r3r33r6r6r6r6r6r64r7r7r7r7r7r75s4s6s511236r9r9r9r9r9r97s4s6s51238s4s6s51339s4s6s51410s4s6s51511s7s8s1612r1r1s9s10r1r113r2r2s9s10r2r214r4r4r4r4r4r415r5r5r5r5r5r516r8r8r8r8r8r84. 根据算法4.3，构造LR预测分析程序。算法4.3：输入：文法G的一张分析表和输入符号串w输出：若w属于L(G)，得到w的自底向下的分析，否则报错。方法：首先，初始状态0入栈，w$存入从输入缓冲区中。置ip指向w$的第一个符号； Do令S是栈顶状态，a是ip所指向的符号；If（actionS,a=shift S） 把a和s依次入栈； 推进ip，使它指向下一个输入符号； ； Else if(actionS,a=reduce by A-b) 从栈顶弹出2*|b|个符号； 令s是现在的栈顶状态，把A和gotoS,A入栈； 输出产生式A-b； Else if（actionS,a=accept）return; Else error();while(1);其中函数i