【编译原理】LR(0)分析算法

概述

LR(0)找出句柄前缀，构造分析表，然后根据输入符号进行规约。见到First集就移进，见到终态就归约

LR(0)分析表的构造

两个函数

• goto转移函数：就是在产生式C的状态上，后面接符号x后产生新的自动机状态的过程。
• closure闭包函数：参数是goto()产生的集合。简而言之，如果下一个期待输入的是非终结符B，那么把该非终结符的产生式也并入到集合当中。

LR(0)分析表构造算法

C0 = closure (S’ -> ● S $) // the init closure
SET = {C0} // 标记已经计算过的状态
Q = enQueue(C0) // a queue
while (Q is not empty)
  C = deQueue(Q)
  foreach(x ∈ (N∪T) )
    D = goto(C, x)
    if (x ∈ T)
      ACTION[C, x] = D
    else
      GOTO[C, x] = D
    if (D not ∈ SET)
      SET ∪= {D}
      enQueue(D)

案例

案例：

0: S'-> S$
1: S -> x x T
2: T -> y

LR(0)分析表

	动作(ACTION)			转移(GOTO)
状态符号	x	y	$	S	T
s1	s2			g6
s2	s3
s3		s4			g5
s4	r2	r2	r2
s5	r1	r1	r1
s6			accept

• s2(shift 2)，改变到自动机的状态s2
• g5(goto 5)，转移到自动机的状态s5
• r2(reduce 2)，归约到文法上的编号2

分析过程

以xxy$为例

步骤	状态栈S	符号栈/分析栈	输入符号	下一步动作
1	s1	$	xxy$	s2
2	s1s2	$x	xy$	s3
3	s1s2s3	$xx	y$	s4
4	s1s2s3s4	$xxy	$	r2(T -> y)
5	s1s2s3	$xxT	$	g5
6	s1s2s5	$xxT	$	r1(S -> x x T)
7	s1	$S	$	g6
8	s6	$	$	accept
				分析成功

goto和closure算法

goto(C, x):
  temp = {} // a set
  foreach (C’s item i: A -> β ● x γ )
    temp ∪= {A -> β x ● γ }
  return closure(temp)
// goto转移函数，就是在产生式C的状态上，后面接符号x后产生新的自动机状态的过程。
closure(C):
  while(C is still changing)
      foreach (C’s item i: A -> β ● B γ )
            C ∪= {B -> …}
  return C;
// closure闭包函数，参数是goto()产生的集合。简而言之，如果下一个期待输入的是非终结符B，那么把该非终结符的产生式也并入到集合当中。

LR(0)分析算法问题分析

对每一个形如X -> α ● 的项目：

1. 直接把 α 归约成 X, 紧跟一个 “goto”，尽管不会漏掉错误，但会延迟错误发现时机。
2. LR(0)分析表中可能包含 移进-归约冲突 与 归约-归约冲突 。

问题1：错误定位

FOLLOW(S) = { $}, 如果输入的是● x x y x到状态3的时候是x x y ● x下一个输入是x，而非$，此时应该就该抛出异常，而实际上他会一直归约到状态4后再报错。这就是错误定位

问题2：冲突

而事实上FOLLOW(E) = {$} ，+号并不是FOLLOW集里的，所以并不应该执行第2个(归约)操作，而应该是第1个(移进)操作。

因为E的FOLLOW集不包含+，所以假如此时进行归约，归约后，E后面跟着的输入此时是+，直接就报错了。

解决

解决错误定位&冲突问题 → SLR算法