证明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​