LR(0)分析法
一、基本概念
二、LR(0) 有限状态机的构造方法
1.用闭包函数（CLOSURE）来求DFA一个状态的项目集：
CLOSURE(I)是这样定义的：
首先I的项目都属于CLOSURE(I)；
如果A->α• Bβ,则左部为B的每个产生式中的形如B->·γ项目，也属于CLOSURE(I)；
2.LR(0) FSM 的状态转移函数
GO (I,X) = CLOSURE(J)
其中，I为LR(0) FSM 的状态（闭包的项目集），X为文法符号， J={ A -> αX•β | A -> α• Xβ∈I} ；
表示对于一个状态项目集中的一个项目A -> α• Xβ，在下一个输入字符是X的情况下，一定到另一个新状态 A -> αX•β。
3.LR(0) 有限状态机的构造
从 LR(0) FSM 的初态出发 ，先求出初态项目集的闭包（CLOSURE({S’->.S})），然后应用上述转移函数，通过项目分析每种输入字符下的状态转移，若为新状态，则就求出新状态下的项目集的闭包，级可逐步构造出完整的 LR(0) FSM。
LR(0) FSM 的构造举例
给定文法G[E]：
(1) E -> E+T
(2) E -> T
(3) T -> ( E )
(4) T -> d
构造LR(0) FSM
① G[E]的拓广文法，得到G’ [E’]：
(0) E’ -> E
(1) E -> E+T
(2) E -> T
(3) T -> ( E )
(4) T -> d
②构造G’[E’] 的 LR(0) FSM
LR(0) FSM
三、LR(0) 分析法
1.LR(0) 文法定义
文法 G 是 LR(0) 文法，当且仅当它的LR(0)FSM中的每个状态都满足：
①不同时含有移进项目和归约项目，即不存在移进-归约冲突。
②不含有两个以上归约项目，即不存在归约-归约冲突。
2.LR(0)分析表的构造
ACTION 表项和 GOTO表项可按如下方法构造：
-
若项目A ->α • aβ属于 Ik 且 GO (Ik, a)= Ij, 期望字符a 为终结符，则置ACTION[k, a] =sj (j表示新状态Ij);
-
若项目A ->α • Aβ属于 Ik，且GO (Ik, A)= Ij,期望字符 A为非终结符，则置GOTO(k, A)=j (j表示文法中第j个产生式);
-
若项目A ->α •属于Ik, 那么对任何终结符a, 置ACTION[k, a]=rj；其中，假定A->α为文法G 的第j个产生式；
-
若项目S’ ->S • 属于Ik, 则置ACTION[k, #]为“acc”;
-
分析表中凡不能用上述规则填入信息的空白格均置上“出错标志”
翻译一下：
- 如果圆点不在项目k最后且圆点后的期待字符a为终结符，则ACTION[k, a] =sj (j表示新状态Ij)；
- 如果圆点不在项目k最后且圆点后的期待字符A为非终结符，则GOTO(k, A)=j (j表示文法中第j个产生式)；
- 如果圆点在项目k最后且k不是S’ ->S，那么对所有终结符a，ACTION[k, a]=rj (j表示文法中第j个产生式)；
- 如果圆点在项目k最后且k是S’ ->S，则ACTION[k, #]为“acc”;
例子：
考虑文法G[S] :
S → （S） | a
相应的LR(0) FSM如下，构造其LR(0)分析表。
LR(0) FSM
从I0看，S‘->·S,期望字符是非终结符S，根据上面的规则2，得到GOTO(0,S)=1；
S‘->·(S),期望字符是终结符(，根据上面的规则1，得到ACTION(0,()=S2；
从I3看，S->a·，根据规则3，置ACTION[3, a]为r2;
从I1看，S‘->S·，根据规则4，置ACTION[1, #]为“acc”;
LR(0)分析表
3.LR(0) 分析流程
设输入串为w，ip指向输入串w的首符号a，i指向符号栈顶；状态栈的初始栈顶为0，符号栈初始栈顶为#。
算法流程图为：
LR(0) 算法流程图
