LR(0) 分析

核心概念

对于起始符号为 $S$ 的文法 $G$ ，增加一条产生式 $S^{'} \to S$ ，初始符号设为 $S^{'}$ ，得到增广文法 $G^{'}$

若 $α, β \in (V_{N} \cup V_{T})^{*}, w \in V_{T}^{*}$ ，且 $S \Rightarrow^{*} α A w, A \Rightarrow β$ ，则 $α β$ 的任何前缀均为活前缀

一个 LR(0) 项目是在右端某一位置有圆点的产生式
- 产生式 $A \to x yz$ 对应 4 个 LR(0) 项目： $A \to . x yz, A \to x . yz, A \to x y . z, A \to x yz .$
- 圆点标志着已分析过的串与该产生式匹配的位置
根据圆点所在位置和圆点后是否是终结符分为以下几种：
- 移进项目： $A \to α . a β$
- 待约项目： $A \to α . Bβ$
- 归约项目： $A \to α .$
- 接受项目： $S^{'} \to S .$
LR(0) FSM 的状态是一个 LR(0) 项目集的闭包，计算方法：
- 对于项目集 $I$ ，重复：对于其中每个项目 $A \to α . Bβ$ 和产生式 $B \to γ$ ，加 $B \to . γ$ 到 $I$ 中，直到没有新项目加入
初态： $I_{0} = CLOSURE ({S^{'} \to . S})$
转移函数： $GO (I, X) = CLOSURE (J)$ ，其中 $J = {A \to α X . β ∣ A \to α . Xβ \in I}$
从初态开始重复遍历所有状态和文法符号 $X$ 可以构造出所有状态

增广文法的每个活前缀都有唯一对应的状态。

$C = {I_{0}, \dots, I_{n}}$ ，状态 $I_{k}$ 对应的 LR(0) 分析表的栈顶状态为 $k$

若项目 $A \to α . a β \in I_{k}$ 且 $GO (I_{k}, a) = I_{j}$ ， $a$ 为终结符，则 $ACTION [k, a] = s j$
若项目 $A \to α . \in I_{k}$ ，则对任何终结符 $a$ ， $ACTION [k, a] = r j$ ，其中 $A \to α$ 为第 $j$ 个产生式
若项目 $S^{'} \to S . \in I_{k}$ ，则 $ACTION [k, #] = a cc$
若 $GO (I_{k}, A) = I_{j}$ ， $A$ 为非终结符，则 $GOTO (k, A) = j$
其余位置为 $err$

按上述算法构造的分析表，如果各表项无多重定义，则称该文法为一个 LR(0) 文法

LR(0) FSM 中，每个状态满足：