#句柄
右句型 $\gamma$ 的句柄是一个产生式的右部 $\beta$，并且该句柄 $\beta$ 通过产生式 $A\rightarrow\beta$ 归约后，得到的是最右推导中的前一个句型。
右句型：所有在最右推导中出现的句型都是右句型。
🌰$S \Rightarrow _ { r m }$ aABe $\Rightarrow _ { r m }$ aAde $\Rightarrow _ { r m }$ aAbcde $\Rightarrow _ { r m }$ abbcde
文法为：
$S \rightarrow$ aABe
${ A \rightarrow A b c | b }$
$B \rightarrow d$
abbcde 中的第一个 b 通过$A\rightarrow b$归约后得到 aAbcde，是最右推导的前一个句型，所以第一个 b 是句柄。而第二个 b 通过$A\rightarrow b$归约后得到 aAAcde，不是最右推导的前一个句型，所以第二个 b 不是句柄。（栗子中加粗部分为句柄）
- 句柄的右边仅含终结符。
- 如果文法二义，那么句柄可能不唯一。
#两个冲突
移进-归约冲突：既可以移进又可以归约时，无法决定。
归约-归约冲突：当不止一个产生式可以归约，无法决定对哪个产生式进行归约。
#活前缀
活前缀：右句型的前缀，该前缀不超过最右句型句柄的右端。
在移进-归约分析中，出现在栈中的串都是活前缀。
🌰$\mathcal { S } \Rightarrow * _ { r m } \gamma A w \Rightarrow _ { r m } \gamma \beta w$
$\gamma \beta$的任意前缀（包括$\varepsilon$和$\gamma \beta$本身）都是活前缀，这里的$\beta$是句柄。
#LR 分析表
L 表示从左到右扫描输入串，R 表示最右推导。分为 LR(0)/SLR(1)、LR(1)、LALR 三种。
#构造 SLR 分析表
- 拓广文法，即添加产生式$S ^ { \prime } \rightarrow S$
- 构建识别活前缀的DFA
- 根据DFA构建SLR分析表
#构建识别活前缀的 DFA
LR(0) 闭包函数 closure(I)
- I中的所有项都属于 closure(I)
- 如果$A \rightarrow \alpha \cdot B \beta$属于 closure(I)，并且$B \rightarrow \gamma$是产生式，那么如果$B \rightarrow \cdot \gamma$还不在 closure(I)中，则把它加入 closure(I) 中。
- 重复上面两个步骤，直至 closure(I) 不再变化。
LR(0) 状态转换函数 goto(I, X)
I状态集中所有形如$[ A \rightarrow \alpha \cdot X \beta ]$的产生式对应的产生式$[ A \rightarrow \alpha X \cdot \beta ]$的LR(0)闭包。X为终结符或非终结符。
🌰$S \rightarrow$ aABe ；${ A \rightarrow A b c | b }$ ；$B \rightarrow d$ 对于$I_0: S' \rightarrow S$；$S \rightarrow \cdot aABe$
$I_1=goto(I_0, a):$ $S \rightarrow a \cdot ABe$；$A \rightarrow \cdot Abc$；$A \rightarrow \cdot b$
识别文法 G 活前缀的 DFA 通过下面的方式构造：
- 令 $C = \lbrace closure(S' \rightarrow S) \rbrace$
- 对 $C$ 中的每一个项目集应用转换函数 $goto(I, X)$ 得到新的项目集 $I_n$，并把 $I_n$ 加入到 $C$ 中。
- 重复第二步，直到 $C$ 不再增大为止。
#根据 DFA 构建 SLR 分析表
状态 i 从 $I_i$ 构造，它的 action 函数如下确定：
- 如果 $[ A \rightarrow \alpha \cdot a \beta ]$ 在 $I_i$ 中，并且 $goto(I_i,a )=I_j$，那么置 $action[i, a]$ 为 $s_j$。
- 如果 $[ A \rightarrow \alpha \cdot ]$ 在 $I_i$ 中，那么对 FOLLOW(A) 中的所有终结符 $a$，置 $action[i, a]$ 为 $r_j$，$j$ 是产生式 $A \rightarrow \alpha \cdot$ 的编号。
- 如果 $\left[ \mathcal { S } ^ { \prime } \rightarrow \mathcal { S } \cdot \right]$ 在 $I_i$ 中，那么置 $action[i,\$]$ 为接受 acc。
如果出现动作冲突，那么该文法就不是 SLR(1) 的。
构造状态 i 的 goto 函数：
对所有的非终结符 $A$，如果 $goto(I_i,A) = I_j$, 那么 $goto[i, A] = j$。
不能由上面两步定义的条目都为 error。
#SLR(1) 文法的问题
每个 SLR(1) 文法都不是二义的，但是，有许多非二义的文法不是 SLR(1)，文法描述能力弱。SLR(1) 是在构造完DFA的 LR(0) 项目集之后才应用预测符号的，即对需要归约的产生式，当其遇到产生式左部非终结符的 FOLLOW 集中的终结符时才进行归约，而在 LR(0) 的构造中没有考虑预测。
#构造规范的 LR 分析表
基本步骤同 SLR 一样，只在第二步和第三步时有所不同，只说不同的地方。
#构建识别活前缀的 DFA
使用 LR(1) 文法，1 表示项目 $[A \rightarrow \alpha \cdot \beta , a]$ 中搜索符的长度。
LR(1) 闭包函数 closure(I)
- I 中的所有项都属于 closure(I)
- 若 $[A\rightarrow \alpha \cdot B \beta, a]$ 属于 closure(I)，$B\rightarrow \gamma$ 是产生式，则对于每个终结符 $b \in FIRST(\beta a)$，项 $[B\rightarrow \cdot \gamma ,b]$ 也加入到 closure(I) 中。
- 重复上面两个步骤，直至 closure(I) 不再变化。
搜索符 $b$ 的集合是 FOLLOW(B) 的一个子集。
LR(1) 状态转换函数 goto(I, X) I 状态集中所有形如 $[ A \rightarrow \alpha \cdot X \beta,b ]$ 的产生式对应的产生式 $[ A \rightarrow \alpha X \cdot \beta,b ]$ 的LR(1) 闭包。X 为终结符或非终结符。注意这里的搜索符集 $b$ 是直接由前面对应的项目抄过来的。
识别文法 G 活前缀的 DFA 通过下面的方式构造：
- 令 $C= \lbrace closure ( [S^\prime \rightarrow S, \$ ]) \rbrace$
- 对 $C$ 中的每一个项目集应用转换函数 $goto(I, X)$ 得到新的项目集 $I_n$，并把$I_n$ 加入到 $C$ 中。
- 重复第二步，直到 $C$ 不再增大为止。
#根据 DFA 构建 SLR 分析表
基本同 SLR，不同点在于：在 action 函数中，如果有归约，SLR 是根据左部非终结符的FOLLOW集决定进行归约；LR(1) 是根据搜索符决定进行归约。
#LR(1) 文法的问题
LR(1) 文法描述能力较强，但是由于状态数目多，分析表较大。
#构造 LALR 分析表
LALR 是在 SLR(1) 和 LR(1) 之间进行了文法描述能力与分析表紧凑程度之间做的折中。
#LALR 的做法
合并识别 LR(1) 文法的活前缀的 DFA 中的同心项目集。
#同心项目集
略去搜索符后相同的项目集。
🌰$B \rightarrow \cdot b B$ 和 $B \rightarrow \cdot b B ,b / a$
#合并同心集引起的冲突
同心集的合并不会引起新的移进-归约冲突。
🌰如果同心集中有移进-归约冲突 $\left[ A \rightarrow \alpha \cdot, a / b \right][ B \rightarrow \beta \cdot a \gamma , c / d ]$，当面对输入符号 a 时不知道该移进还是归约。合并前的项目集应该有 $\left[ A \rightarrow \alpha \cdot, x \right][ B \rightarrow \beta \cdot a \gamma , y ]$，肯定有个 x 为 a，所以一定存在移进-归约冲突，说明合并之前就存在移进-归约冲突了。
同心集的合并有可能产生新的归约-归约冲突。
🌰合并前项目集 $[A \rightarrow c \cdot, d][B \rightarrow c \cdot, e]$ 和 $[A \rightarrow c \cdot, e][B \rightarrow c \cdot, d]$，合并后为 $[A \rightarrow c \cdot, e/d][B \rightarrow c \cdot, d/e]$，此时就产生了新的归约-归约冲突。
#安利
求LR分析表的工具： LR(0)/SLR(1) SLR(1) LALR