證明LL(1)、SLR(1)、LALR(1)文法—編譯原理第三章習題陳意雲張昱

系列文章戳這裡👇

1. 什麼是上下文無關文法、最左推導和最右推導
2. 如何判斷二義文法及消除文法二義性
3. 何時需要消除左遞歸
4. 什麼是句柄、什麼是自上而下、自下而上分析
5. 什麼是LL(1)、LR(0)、LR(1)文法、LR分析表
6. LR(0)、SLR(1)、LR(1)、LALR(1)文法之間的關系
7. 編譯原理第三章習題
8. 詞法分析、建構DFA、上下文無關文法、LL(1)分析、提取正規式
9. 證明LL(1)、SLR(1)、LALR(1)文法

( 4 ) (4) (4)習題 3.21 、 3.22 、 3.25 3.21、3.22、3.25 3.21、3.22、3.25。

3.21 3.21 3.21:

( a ) (a) (a)證明下面文法是 L L ( 1 ) LL(1) LL(1)文法，但不是 S L R ( 1 ) SLR(1) SLR(1)文法。

S → A a A b ∣ B b B a A → ϵ B → ϵ S→AaAb|BbBa\\ A→\epsilon\\ B→\epsilon S→AaAb∣BbBaA→ϵB→ϵ

根據 L L ( 1 ) LL(1) LL(1)文法定義， F i r s t ( A a A a ) = { a } , F i r s t ( B b B b ) = { b } First(AaAa)=\{a\},First(BbBb)=\{b\} First(AaAa)={a},First(BbBb)={b}

F i r s t ( A a A a ) ∩ F i r s t ( B b B b ) = ϕ First(AaAa)∩First(BbBb)=\phi First(AaAa)∩First(BbBb)=ϕ，是以該文法是 L L ( 1 ) LL(1) LL(1)文法。

根據 S L R ( 1 ) SLR(1) SLR(1)分析，存在如下狀态

I : S → ⋅ A a A b S → ⋅ B b B a A → ϵ ⋅ B → ϵ ⋅ \begin{aligned} I:&\\ &S→·AaAb\\ &S→·BbBa\\ &A→\epsilon·\\ &B→\epsilon· \end{aligned} I:​S→⋅AaAbS→⋅BbBaA→ϵ⋅B→ϵ⋅​

此時，由于 F o l l o w ( A ) = F o l l o w ( B ) = { a , b } Follow(A)=Follow(B)=\{a,b\} Follow(A)=Follow(B)={a,b}，是以若輸入符号為 a   o r   b a\ or\ b a or b則無法判斷是将 ϵ \epsilon ϵ歸約成 A A A還是 B B B，出現歸約-歸約沖突，是以不是 S L R ( 1 ) SLR(1) SLR(1)文法。

3.22 3.22 3.22:

證明下面文法是 L A L R ( 1 ) LALR(1) LALR(1)文法，但不是 S L R ( 1 ) SLR(1) SLR(1)文法。

S → A a ∣ b A c ∣ d c ∣ b d a A → d S→Aa|bAc|dc|bda\\ A→d\\ S→Aa∣bAc∣dc∣bdaA→d

該文法存在一個狀态， [ S → d ⋅ c ] , [ A → d ⋅ ] [S→d·c],[A→d·] [S→d⋅c],[A→d⋅]出現在同一個項目集中，因為 F o l l o w ( A ) = { a , c } Follow(A)=\{a,c\} Follow(A)={a,c}，是以當 輸入符号為 c c c時，無法判斷進行 [ S → d ⋅ c ] [S→d·c] [S→d⋅c]移進還是 [ A → d ⋅ ] [A→d·] [A→d⋅]規約,出現移進-歸約沖突，是以不是 S L R ( 1 ) SLR(1) SLR(1)文法。

除上述沖突，同理還存在一個 [ S → b d ⋅ a ] , [ A → d ⋅ ] [S→bd·a],[A→d·] [S→bd⋅a],[A→d⋅]的移進-歸約沖突，但這兩個沖突，在規範 L R ( 1 ) LR(1) LR(1)情況下不存在，因為隻有輸入符号為 a a a時，才進行 d d d到 A A A的歸約操作，是以此文法是 L R ( 1 ) LR(1) LR(1)文法，且此文法的規範 L R ( 1 ) LR(1) LR(1)項目集中任意項目的搜尋符隻能為 ＄  o r   a ＄\ or\ a ＄ or a，是以不存在同心的 L R ( 1 ) LR(1) LR(1)項目集，是以此文法也是 L A L R ( 1 ) LALR(1) LALR(1)文法。

3.25 3.25 3.25:

一個非 L R ( 1 ) LR(1) LR(1)的文法如下：

L → M L b ∣ a M → ϵ L→MLb|a\\ M→\epsilon\\ L→MLb∣aM→ϵ

請給出所有含移進-歸約沖突的規範 L R ( 1 ) LR(1) LR(1)項目集，以說明該文法确實不是 L R ( 1 ) LR(1) LR(1)的。

以下項目集存在移進-歸約沖突，即輸入符号為 a a a時，無法判斷進行移進 a a a還是進行 ϵ \epsilon ϵ規約，是以該文法不是 L R ( 1 ) LR(1) LR(1)的。

I 0 :                ⟶ M L ′ → ⋅ L ,    $ L → ⋅ M L b ,    $ L → ⋅ a ,    $ M → ⋅ ,    a         I 2 :                ⟶ M L → M ⋅ L b ,    $ L → ⋅ M L b ,    b L → ⋅ a ,    b M → ⋅ ,    a         I 5 : L → M ⋅ L b ,    b L → ⋅ M L b ,    b L → ⋅ a , b ,    b M → ⋅ ,    a \begin{aligned} I_0:&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \stackrel{M}{\longrightarrow}\\ &L'→·L,\ \ \$\\ &L→·MLb,\ \ \$\\ &L→·a,\ \ \$\\ &M→·,\ \ a\\ \end{aligned}\ \ \ \ \ \ \ \begin{aligned} I_2:&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \stackrel{M}{\longrightarrow}\\ &L→M·Lb,\ \ \$\\ &L→·MLb,\ \ b\\ &L→·a,\ \ b\\ &M→·,\ \ a\\ \end{aligned} \ \ \ \ \ \ \ \begin{aligned} I_5:&\\ &L→M·Lb,\ \ b\\ &L→·MLb,\ \ b\\ &L→·a,b,\ \ b\\ &M→·,\ \ a\\ \end{aligned} I0​:​              ⟶M​L′→⋅L,  $L→⋅MLb,  $L→⋅a,  $M→⋅,  a​       I2​:​              ⟶M​L→M⋅Lb,  $L→⋅MLb,  bL→⋅a,  bM→⋅,  a​       I5​:​L→M⋅Lb,  bL→⋅MLb,  bL→⋅a,b,  bM→⋅,  a​