系列文章戳这里👇

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)文法
10. 翻译方案、属性栈代码
11. 【运行时环境】什么是活动记录、 活动记录与汇编代码的关系

$(4)$习题$3.21、3.22、3.25$。

$3.21$:
$(a)$证明下面文法是$LL(1)$文法，但不是$SLR(1)$文法。
$$\begin{gathered} S\to AaAb|BbBa \\ A\to ϵ \\ B\to ϵ \end{gathered}$$
根据$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}
$First(AaAa)\cap First(BbBb)=\varphi$，所以该文法是$LL(1)$文法。
根据$SLR(1)$分析，存在如下状态
$$\begin{array}{rl}I:& \\ & S\to \cdot AaAb\\ & S\to \cdot BbBa\\ & A\to ϵ\cdot \\ & B\to ϵ\cdot \end{array}$$
此时，由于 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}，所以若输入符号为$aorb$则无法判断是将$ϵ$归约成 $A$还是$B$，出现归约-归约冲突，所以不是$SLR(1)$文法。

$3.22$:
证明下面文法是$LALR(1)$文法，但不是$SLR(1)$文法。
$$\begin{gathered} S\to Aa|bAc|dc|bda \\ A\to d \end{gathered}$$
该文法存在一个状态，$[S\to d\cdot c],[A\to d\cdot ]$出现在同一个项目集中，因为 F o l l o w ( A ) = { a , c } Follow(A)=\{a,c\} Follow(A)={a,c}，所以当 输入符号为$c$时，无法判断进行$[S\to d\cdot c]$移进还是$[A\to d\cdot ]$规约,出现移进-归约冲突，所以不是$SLR(1)$文法。

除上述冲突，同理还存在一个$[S\to bd\cdot a],[A\to d\cdot ]$的移进-归约冲突，但这两个冲突，在规范$LR(1)$情况下不存在，因为只有输入符号为$a$时，才进行$d$到$A$的归约操作，所以此文法是$LR(1)$文法，且此文法的规范$LR(1)$项目集中任意项目的搜索符只能为$＄ora$，所以不存在同心的$LR(1)$项目集，所以此文法也是$LALR(1)$文法。

$3.25$:
一个非$LR(1)$的文法如下：
$$\begin{gathered} L\to MLb|a \\ M\to ϵ \end{gathered}$$
请给出所有含移进-归约冲突的规范$LR(1)$项目集，以说明该文法确实不是$LR(1)$的。
以下项目集存在移进-归约冲突，即输入符号为$a$时，无法判断进行移进$a$还是进行$ϵ$规约，所以该文法不是$LR(1)$的。
$$\begin{array}{rl}{I}_0:& \stackrel{M}{⟶}\\ & L^{\prime }\to \cdot L,\$\\ & L\to \cdot MLb,\$\\ & L\to \cdot a,\$\\ & M\to \cdot ,a\end{array}\begin{array}{rl}{I}_2:& \stackrel{M}{⟶}\\ & L\to M\cdot Lb,\$\\ & L\to \cdot MLb,b\\ & L\to \cdot a,b\\ & M\to \cdot ,a\end{array}\begin{array}{rl}{I}_5:& \\ & L\to M\cdot Lb,b\\ & L\to \cdot MLb,b\\ & L\to \cdot a,b,b\\ & M\to \cdot ,a\end{array}$$