5.3LR分析法
一、
LR分析方法是一种自下而上的分析方法
LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程
LR分析法是一种适用于一大类上下文无关文法的分析方法
1.动作表：
ACTION[s, a]:
当状态s面临输入符号a时，应采取什么动作
每一项ACTION[s, a]所规定的的四种动作：
(1) 移进
就是向前走一步，将下一个状态的GOTO和输入符号a推进栈，下一输入符号编程现行输入符号。
(2) 规约
指用某产生式A->β进行规约。假若β的长度为r，规约动作是A，， 去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s’=GOTO[sm-r, A]和文法符号A推进栈.。
(3) 接收
(4) 报错
2.状态转换表：
GOTO[s, X]
状态s面对文法符号X时，下一状态是什么
LR分析过程：
第一步 分析开始时，首先将初始状态S0及句子左界符#推入分析栈中。
第二步 设在分析的某一步，分析栈及余留的输入符号串处于如下的格局，
则以栈顶的状态及正扫视的输入符号ai组成符号对(Sm，ai)去查分析动作表，并 根据表元ACTION[Sm，ai]的指示完成相应的分析动作。每一分析表元所规定的动 作，仅能是四种动作之一。
第三步 重复上述第二步的工作，直到在分析的某一步，栈顶出现“接收状态”或 “出错状态”为止。
二、LR(0)项目集族和分析表的建造
1.活前缀
文法G的活前缀是他的规范句型的前缀，该前缀 不超过句柄的右端。
特点：
改前缀加上被分析串中未被分析的终结符， 就可以构成一个规范句型。
只要输入串的已扫描部分可规约成一个活前缀，意味着扫描过的部分没有错误。
活前缀和句柄间的关系：
(1)活前缀中已含有句柄的全部符号(句柄的符号即为其最右符号)。
(2)活前缀中含句柄的一部分符号(句柄开头的 若干符号与活前缀最右的若干个符号一致)。
(3)活前缀中全然不包含句柄的任何符号 。
2.分析表的构造
第一条指导规则说到， 若项目A→α·aβ属于Ik且转换函数GO(Ik,a)= Ij，当a为终结符时则置ACTION[k,a]为Sj，我们先考察对于I0，发现S->·aS属于I0，且GO(I0,a)=I1,所有我们ACTION[0,a]置为S1.同理S->·bS属于I0，GO(I0,b)=I2，所以ACTION[0,b]置为S2。
再来看第二条规则，若项目A→α· 属于Ik，则对任何终结符a 和’#'号置ACTION[k,a]和ACTION[k,#]为”rj”，j为在文法G′中某产生式A→α的序号，也就是说这里的j可不是I项目的标号，而是增广文法
(0)S’→S
(1)S→aS
(2)S→bS
(3)S→a
的标号，从0-3啦。我们考察I1，发现S→·aS属于I1，且GO(I1,a)=I1，所以应该置1和a的交的格子为S1，但是此时运用第二条规则会发现S->a·也属于I1，则又应该置ACTION[1,a]为=r3，ACTION[1,#]为r3，这样就发生了冲突。这是因为大多数文法不能满足LR(0)文法的条件，对于此冲突，我们不能确定看到S->a的时候是规约还是移进，有些文法是可以直接构造的，为此，此处不能够早LR(0)分析表了，我们构造经过改进后得到了一种新的SLR(1)文法，并没有什么太大差别，主要就是解决冲突。
解决冲突的指导原则如下：
* 假设一个LR（0）项目集规范族中有如下项目集合：
{X → α.bβ，A → γ.，B → δ.}
即存在移进-归约冲突和归约-归约冲突
* 如果FOLLOW（A）∩ FOLLOW（B）∩ {b} =ф，则可以如下来解决冲突（假设当前符号是 a ）：
1、若 a = b，则移进
2、若 a∈ FOLLOW（A），则用产生式 A → γ归约
3、若 a∈ FOLLOW（B），则用产生式 B → δ归约
4、否则，报错
此处的冲突发生时，当前符号是a，并且此时项目集中无B推导式，且指导规则中的b在此处其实是S->.aS中的a，所以计算Follow(S)∩ {a} ，发现为空，所以可以解决冲突，因为此时，当前符号是a，此处规则中的b也是a，所以，移进，也就是置ACTION[1,a]为=S1，运用分析表的ACTION表和GOTO表构造步骤的第一步，而不是置为r3，所以冲突解决。
然后再看构造步骤中的第三步，若GO(Ik,A)＝Ij，则置GOTO[k,A]为”j”，其中A为非终结符。此题中，只有S为非终结符，看DFA中的I0，发现GO(I0,S)＝I3，所以置GOTO[0,S]为3，ok
第四个步骤，若项目S′→S·属于Ik，则置ACTION[k,#]为”acc”，很简单，DFA中，I3符合，所以置ACTION[3,#]为”acc”。到此解释完了
反复运用，直到填完表。