3.1 3.1 3.1文法： S → ( L ) ∣ a L → L , S ∣ S F o l l o w ( S ) = { ， , ) , $ } F o l l o w ( L ) = { ， , ) } S→(L)|a\\ L→L,S|S\\ Follow(S)=\{，,),\$\}\\Follow(L)=\{，,)\} S→(L)∣aL→L,S∣SFollow(S)={，,),$}Follow(L)={，,)}

( 1 ) (1) (1)习题 3.8 3.8 3.8，其中 ( b ) (b) (b)给出递归下降语法分析程序。

3.8 : 3.8: 3.8: ( a ) (a) (a)消除习题 3.1 3.1 3.1文法的左递归 消除左递归得到 S → ( L ) ∣ a L → S L ′ L ′ → , S L ′ ∣ ϵ S→(L)|a\\L→SL'\\L'→,SL'|\epsilon S→(L)∣aL→SL′L′→,SL′∣ϵ ( b ) (b) (b)为 ( a ) (a) (a)的文法构造预测分析器

F i r s t ( S ) = { ( , a } F i r s t ( L ) = F i r s t ( S ) = { ( , a } F i r s t ( L ′ ) = { ， , ϵ } F o l l o w ( L ) = { ) } F o l l o w ( L ′ ) = F o l l o w ( L ) = { ) } F o l l o w ( S ) = F i r s t ( L ′ ) − { ϵ } + F o l l o w ( L ) + F o l l o w ( L ′ ) + { $ } = { ， , ) , $ } \begin{aligned} First(S)&=\{(,a\}\\ First(L)&=First(S)=\{(,a\}\\ First(L')&=\{，,\epsilon\}\\ Follow(L)&=\{)\}\\ Follow(L')&=Follow(L)=\{)\}\\ Follow(S)&=First(L')-\{\epsilon\}+Follow(L)+Follow(L')+\{\$\}=\{，,),\$\}\\ \end{aligned} First(S)First(L)First(L′)Follow(L)Follow(L′)Follow(S)​={(,a}=First(S)={(,a}={，,ϵ}={)}=Follow(L)={)}=First(L′)−{ϵ}+Follow(L)+Follow(L′)+{$}={，,),$}​

递归下降程序：

( 2 ) (2) (2)习题 3.11 3.11 3.11，并描述该文法产生的语言。 3.11 3.11 3.11: 构造下面文法的 L L ( 1 ) LL(1) LL(1)分析表 S → a B S ∣ b A S ∣ ϵ A → b A A ∣ a B → a B B ∣ b     F i r s t ( S ) = { a , b , ϵ } F i r s t ( A ) = { a , b } F i r s t ( B ) = { a , b } F o l l o w ( S ) = { $ } F o l l o w ( A ) = { a , b , $ } F o l l o w ( B ) = { a , b , $ } S→aBS|bAS|\epsilon\\ A→bAA|a\\ B→aBB|b\\ \ \\ \ \\ \begin{aligned} First(S)&=\{a,b,\epsilon\}\\ First(A)&=\{a,b\}\\ First(B)&=\{a,b\}\\ Follow(S)&=\{\$\}\\ Follow(A)&=\{a,b,\$\}\\ Follow(B)&=\{a,b,\$\}\\ \end{aligned} S→aBS∣bAS∣ϵA→bAA∣aB→aBB∣b  First(S)First(A)First(B)Follow(S)Follow(A)Follow(B)​={a,b,ϵ}={a,b}={a,b}={$}={a,b,$}={a,b,$}​

该文法产生一个空串或者 a , b a,b a,b数量相等的 a b ab ab串。

( 3 ) (3) (3)为习题 3.1 3.1 3.1文法构造 S L R ( 1 ) SLR(1) SLR(1)分析表。 拓广文法 S ′ → S S → ( L ) S → a L → L , S L → S \begin{aligned} &S'→S\\ &S→(L)\\ &S→a\\ &L→L,S\\ &L→S \end{aligned}\\ ​S′→SS→(L)S→aL→L,SL→S​

该文法的 L R ( 0 ) LR(0) LR(0)项目集规范族： I 0 : S ′ → ⋅ S S → ⋅ ( L ) S → ⋅ a         I 1 : S ′ → S ⋅         I 2 : S → ( ⋅ L ) L → ⋅ L , S L → ⋅ S S → ⋅ ( L ) S → ⋅ a   I 3 : S → a ⋅              I 4 : S → ( L ⋅ ) L → L ⋅ , S           I 5 : L → S ⋅          I 6 : S → ( L ) ⋅           I 7 : L → L , ⋅ S S → ⋅ ( L ) S → ⋅ a         I 8 : L → L , S ⋅                                                     \begin{aligned} I_0:&\\ &S'→·S\\ &S→·(L)\\ &S→·a\\ \\ \\ \end{aligned}\ \ \ \ \ \ \ \begin{aligned} I_1:&\\ &S'→S·\\ \\ \\ \\ \\ \end{aligned} \ \ \ \ \ \ \ \begin{aligned} I_2:&\\ &S→(·L)\\ &L→·L,S\\ &L→·S\\ &S→·(L)\\ &S→·a\\ \end{aligned}\\ \ \\ \begin{aligned} I_3:&\\ &S→a·\\ \\ \\ \end{aligned}\ \ \ \ \ \ \ \begin{aligned}\ \ \ \ I_4:&\\ &S→(L·)\\ &L→L·,S\\ \ \\ \end{aligned}\ \ \ \ \ \ \ \begin{aligned} I_5:&\\ &L→S·\\ \\ \\ \end{aligned}\\ \begin{aligned}\ \ \ \ \ \ \ \ I_6:&\\ &S→(L)·\\ \\ \\ \end{aligned} \begin{aligned}\ \ \ \ \ \ \ \ \ I_7:&\\ &L→L,·S\\ &S→·(L)\\ &S→·a\\ \end{aligned}\ \ \ \ \ \ \ \begin{aligned} I_8:&\\ &L→L,S·\\ \\ \\ \end{aligned}\\ \begin{aligned} \end{aligned}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ I0​:​S′→⋅SS→⋅(L)S→⋅a​       I1​:​S′→S⋅       I2​:​S→(⋅L)L→⋅L,SL→⋅SS→⋅(L)S→⋅a​ I3​:​S→a⋅           I4​: ​S→(L⋅)L→L⋅,S​       I5​:​L→S⋅        I6​:​S→(L)⋅         I7​:​L→L,⋅SS→⋅(L)S→⋅a​       I8​:​L→L,S⋅​                                                   

S L R ( 1 ) SLR(1) SLR(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)文法。

( b ) (b) (b) 证明所有 L L ( 1 ) LL(1) LL(1)文法都是 L R ( 1 ) LR(1) LR(1)文法。 证 考虑证明：若一个文法不是 L R ( 1 ) LR(1) LR(1)文法，则它一定不是 L L ( 1 ) LL(1) LL(1)文法。 若一个文法不是 L R ( 1 ) LR(1) LR(1)文法，则它存在分析动作的冲突（移进-规约和归约-归约冲突），也就是说，该文法存在二义性的最左推导，于是不满足 L L ( 1 ) LL(1) LL(1)文法的要求，所以该文法不是 L L ( 1 ) LL(1) LL(1)文法。即说明所有 L L ( 1 ) LL(1) LL(1)文法都是 L R ( 1 ) LR(1) LR(1)文法。

另外，LL(1)文法和LR(1)文法对比，两者都是从左往右看，并且只看下一个符号，再进行相 应的动作。满足LL(1)文法的语言，对它进行LL(1)分析的每一步实际上也对应着LR(1)分析的每一步。但是，LL(1)文法看到一个符号后，就提前选择对应的产生式进行推导，而LR(1)文法有了句柄的概念后，拥有了更多的信息，可以在看到一个符号时，根据搜索符进行移进或规约动作（它可以看完了句柄再选择产生式），也就是说，LR(1)文法是大于LL(1)文法的，即所有LL(1)文法都是LR(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​

( 5 ) (5) (5)为以下文法构造 L R ( 1 ) LR(1) LR(1)分析表： S → a S S → A A → a A b A → \begin{aligned} &S→ a S\\ &S→ A\\ &A→ a A b\\ &A→ \end{aligned} ​S→aSS→AA→aAbA→​ 拓广文法 S ′ → S S → a S S → A A → a A b A → ϵ \begin{aligned} &S'→ S\\ &S→ a S\\ &S→ A\\ &A→ a A b\\ &A→\epsilon \end{aligned} ​S′→SS→aSS→AA→aAbA→ϵ​ 该文法的 L R ( 1 ) LR(1) LR(1)项目集规范族为

I 0 : S ′ → ⋅ S ,     $ S → ⋅ a S ,     $ S → ⋅ A ,     $ A → ⋅ a A b ,    $ A → ⋅ ϵ ,    $         I 1 : S ′ → S ⋅ ,     $         I 2 : S → a ⋅ S ,     $ A → a ⋅ A b ,    $ S → ⋅ a S ,     $ S → ⋅ A ,     $ A → ⋅ a A b ,    b / $ A → ⋅ ϵ ,    b / $   I 3 : S → A ⋅ ,     $                I 4 : S → a S ⋅ ,     $               I 5 : A → a A ⋅ b ,    $ S → A ⋅ ,     $   I 6 : S → a ⋅ S ,     $ S → ⋅ a S ,     $ S → ⋅ A ,     $ A → a ⋅ A b ,    b / $ A → ⋅ a A b ,    b / $ A → ⋅ ϵ ,    b / $        I 7 : A → a A b ⋅ ,     $          I 8 : S → A ⋅ ,     $ A → a A ⋅ b ,    b / $     I 9 : A → a A b ⋅ ,    b / $                                                                             \begin{aligned} I_0:&\\ &S'→·S,\ \ \ \$\\ &S→·aS,\ \ \ \$\\ &S→·A,\ \ \ \$\\ &A→·aAb,\ \ \$\\ &A→·\epsilon,\ \ \$ \\\\ \end{aligned}\ \ \ \ \ \ \ \begin{aligned} I_1:&\\ &S'→S·,\ \ \ \$\\ \\\\\\\\\\ \end{aligned} \ \ \ \ \ \ \ \begin{aligned} I_2:&\\ &S→a·S,\ \ \ \$\\ &A→a·Ab,\ \ \$\\ &S→·aS,\ \ \ \$\\ &S→·A,\ \ \ \$\\ &A→·aAb,\ \ b/\$ \\ &A→·\epsilon,\ \ b/\$\\ \end{aligned}\\ \ \\ \begin{aligned} I_3:&\\ &S→A·,\ \ \ \$\\ \ \\\\ \end{aligned}\ \ \ \ \ \ \ \begin{aligned}\ \ \ \ I_4:&\\ &S→aS·,\ \ \ \$\\ \ \\\\ \end{aligned}\ \ \ \ \ \ \ \begin{aligned} \ \ \ I_5:&\\ &A→aA·b,\ \ \$\\ &S→A·,\ \ \ \$\\ \\ \end{aligned}\\ \begin{aligned}\ I_6:&\\ &S→a·S,\ \ \ \$\\ &S→·aS,\ \ \ \$\\ &S→·A,\ \ \ \$\\ &A→a·Ab,\ \ b/\$ \\ &A→·aAb,\ \ b/\$ \\ &A→·\epsilon,\ \ b/\$\\ \end{aligned} \begin{aligned}\ \ \ \ \ \ I_7:&\\ &A→aAb·,\ \ \ \$\\ \\\\\\\\\\ \end{aligned} \begin{aligned}\ \ \ \ \ \ \ \ I_8:&\\ &S→A·,\ \ \ \$\\ &A→aA·b,\ \ b/\$ \\ \\\\\\\\ \end{aligned}\\ \ \ \ \begin{aligned}\\ I_9:&\\ &A→aAb·,\ \ b/\$ \\ \end{aligned} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ I0​:​S′→⋅S,   $S→⋅aS,   $S→⋅A,   $A→⋅aAb,  $A→⋅ϵ,  $​       I1​:​S′→S⋅,   $       I2​:​S→a⋅S,   $A→a⋅Ab,  $S→⋅aS,   $S→⋅A,   $A→⋅aAb,  b/$A→⋅ϵ,  b/$​ I3​: ​S→A⋅,   $           I4​: ​S→aS⋅,   $          I5​:​A→aA⋅b,  $S→A⋅,   $​ I6​:​S→a⋅S,   $S→⋅aS,   $S→⋅A,   $A→a⋅Ab,  b/$A→⋅aAb,  b/$A→⋅ϵ,  b/$​      I7​:​A→aAb⋅,   $        I8​:​S→A⋅,   $A→aA⋅b,  b/$   I9​:​A→aAb⋅,  b/$​                                                                            L R ( 1 ) LR(1) LR(1)分析表为：