LR(0)分析法
一、基本概念
-
拓广文法：
对于文法 G = (VN, VT, P , S ) , 增加如下产生式：S’->S ，其中， S’ ∈ VN∪ VT ， 得到 G 的拓广文法，G’ = (VN ’, VT, P ’ , S’ )
其实就是增加了一条右部为开始符号的产生式，就变成了拓广文法
-
可归前缀：
采取归约过程前符号栈中的内容，称做可归前缀。
这种前缀包含句柄且不包含句柄之后的任何符号； -
活前缀
对于文法 G = (VN, VT, P , S ) , 设 S’ 是其拓广文法的开始符号（即有产生式 S’-> S）， 且α,β∈(VN∪VT)* , ω∈VT*。
若 S’ =*=>α A ω 且 A ->β， 即 β 为句柄，则 αβ 的任何前缀 γ 都是文法 G 的活前缀。
注：由于 S’ =*=>S’ 且 S’ -> S， 故 S 是 G 的活前缀 。也就是说可归前缀的所有前缀（包括可归前缀）都是活前缀。
例：文法 G[S] :
（1） S -> AB
（2） A -> aA
（3） A -> ε
（4） B -> b
（5） B -> bB
句子 aaab 是一个句型，其唯一的句柄为：ε （aaaεb）； 活前缀有：ε，a，aa，aaa。当前分析了的部分（符号栈中的符号）为规范句型的活前缀，表示当前分析了的部分是某规范句型的正确部分。
-
LR(0)项目 :
在文法G中每个产生式的右部适当位置添加一个圆点构成项目。
每个项目的含义是：欲用改产生式归约时，圆点前面的部分为已经识别了的句柄部分，圆点后面的部分为期望的后缀部分。
分类：
移进项目: 形如 A -> α• aβ，对应移进状态，把a移进符号栈。
待约项目: 形如 A -> α • Bβ，对应待约状态，需要等待分析完非终结符B的串再继续分析A的右部。
归约项目: 形如 A -> α •，句柄已形成，可以归约。
接受项目: 形如 S’ -> S •。
初始项目: 形如 S’ -> • S。
其中a∈VT , α,β∈(VN∪VT)*， A,B∈VT
后继项目: 表示同属于一个产生式的项目，但是圆点的位置仅相差一个文法符号，则称后者为前者的后继项目。例：对于产生式S -> aAcBe，它有6个项目：
S -> ·aAcBe
S -> a·AcBe
S -> aA·cBe
S -> aAc·Be
S -> aAcB·e
S -> aAcBe·
二、LR(0) 有限状态机的构造方法
1.用闭包函数（CLOSURE）来求DFA一个状态的项目集：
CLOSURE(I)是这样定义的：
首先I的项目都属于CLOSURE(I)；
如果A->α• Bβ,则左部为B的每个产生式中的形如B->·γ项目，也属于CLOSURE(I)；
例子：已知文法G[E]如下:
(1) E -> E+T
(2) E -> T
(3) T ->( E )
(4) T -> d可以直到它的拓广文法G’ [E’]为 ：
(0) E’ -> E
(1) E -> E+T
(2) E -> T
(3) T -> ( E )
(4) T -> d令I0 = CLOSURE({E’->.E})
则I0 = {
E’ -> • E，
E -> • E+T，
E -> • T，
T -> •( E ),
T -> • d
}
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，符号栈初始栈顶为#。
算法流程图为：
