[第五章自下而上语法分析.ppt

5.1 自下而上分析基本问题 例1： E→E+T | T T→T*F | F F→(E) | i i1*i2+i3 练习： E→E+T | T T→T*F | F F→(E) | i E+T*F+i 动作 栈 输入缓冲区 1) 准备 # i1+i2*i3# 2) 移进 #i1 +i2*i3# 3) 归约 F→i #F +i2*i3# 4) 归约 T→F #T +i2*i3# 5) 归约 E→T #E +i2*i3# 6) 移进 #E+ i2*i3# 7) 移进 #E+i2 *i3# 8) 归约 F→i #E+F *i3# 9) 归约 T→F #E+T *i3# 10) 移进 #E+T* i3# 11) 移进 #E+T*i3 # 12) 归约 F→i #E+T*F # 13) 归约 T→T*F #E+T # 14) 归约 E→E+T #E # 15) 接受 练习１： E→E+T | T T→T*F | F F→(E) | i 　 构造识别活前缀的NFA 若 i：X→X1…Xi-1·Xi…Xn j：X→X1…Xi-1 Xi ·…Xn 构造识别活前缀的NFA 例： S’→ E E → aA | bB A → cA | d B → cB | d 例： S’→ E E → aA | bB A → cA | d B → cB | d 四、LR(1)分析表的构造 1、基本概念 LR(0)项目：A→α·β LR(K)项目: A→α·β, a1a2…ak 2、LR(1)项目集规范族构造 （1）CLOSURE(I): ① I中的项目 ② [A→α·Bβ, a ]∈CLOSURE(I) [B →·γ, ] (2)GO(I,X) = CLOSURE(J) 例： (0)S’→S (1)S→BB (2)B→aB (3)B→b 练习：若有文法G[S]: 　　S→S;M|M 　　M→MbD|D 　　D→D(S)|ε （1）证明G[S]是SLR文法，并构造它的分析表； （2）给出G[S]的LR(1)项目集规范族中的I0。 五、LALR分析表的构造 同心集的合并： 同心集的合并 不会产生新的移进-归约冲突 但会产生新的归约-归约冲突 补充作业： 1、文法G[S]，构造LR(1)分析表： 　　　S→aAd|bAc|aec|bed 　　　A→e 2、文法G[S]： 　　S→AB 　　A→aBa|ε 　　B→bAb|ε （1）该文法是SLR的吗？ （2）若是，请构造它的分析表； （3）给出输入串baab#的分析过程。 2.SLR(1)分析法 5.3 LＲ分析法 (1)文法拓广:G?G’ ; (2)构造G’的LR(0)项目集规范族C ; (3)利用C和G,按下述算法构造G’的SLR分析表. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 5.3 LＲ分析法 构造G’的SLR分析表: A.移进项目:A?α? aβ∈Ik , Go(Ik,a)=Ij , 则: 置Action[k,a]=“Sj” B.归约项目:A?α?∈Ik , 则对?a∈follow(A), 置Action[k,a]=“rj” C.接受项目:若S’?S?∈Ik ,则置Action[k,#]=“acc” ; D.待约项目:若Go(Ik,A)=Ij , A∈VN , 则置Goto[k,A]=j Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例:(课本111页文法5.8) 考察下面的拓广文法: (0)S’?E (1)E?E+T (2)E?T (3)T?T*F (4)T?F (5)F?(E) (6)F?i 这个文法的LR(