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

1、实验题目：语法分析程序设计与实现(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不在此进行显示）。该过程中考虑到文法是通过字符

2、串数组存储的，故分析过程是一个字符一个字符进行的，所以如果出现类似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(S·E)= S·E，E·E+T，E·E-T，E·T，T·T*F，T·T/F，T

3、83;F，F·i，F·(E)，F·n从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

4、), E·E+T，E·E-T，E·T，T·T*F，T·T/F，T·F，F·i，F·(E)，F·n I6=go(I0,n)= closure(Fn· )= Fn· 从I1出发的转移有I7=go(I1,+)= closure(EE+·T )=EE+·T，T·T*F，T·T/F，T·F，F·i，F·(E)，F·n I8=go(I1, -)= closure(EE-·T )= EE-·T ，T&

5、#183;T*F，T·T/F，T·F，F·i，F·(E)，F·n 从I2出发的转移有I9=go(I2, *)= closure(TT*·F )= TT*·F，F·i，F·(E)，F·n I10=go(I2, /)= closure(TT/·F )= TT/·F，F·i，F·(E)，F·n 从I5出发的转移有I11=go(I5, E)= closure(F(E·), EE·+T, EE·-T )=F(E·),

6、 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

7、-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

8、(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()$ETF0s4s6s51231s7s8ACC2r3r3s9s10r3r33r6r6r6r6r6r64r7r7r7r7r7r75s4s6s511236r9r9r9r9r9r97s4s6s51238s4s6s51339s4s6s51410s4s6s51511s7s8s1612r1r1s

9、9s10r1r113r2r2s9s10r2r214r4r4r4r4r4r415r5r5r5r5r5r516r8r8r8r8r8r84. 根据算法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）retur