【编译原理】自底向上分析方法——LR文法分析方法的总结

LR(0)、SLR(1)、LR(1)、LALR(1) de 若干方面的区别

推导过程

LR(0)的基础上才有SLR(1) SLR分析方法只用在分析表上，DFA与LR(0)相同
LR(1)的基础上才有LALR(1) LR(1)的DFA合并同心项才能为LALR(1)

分析能力

LR(1)>LALR(1)>SLR(1)>LR(0)
分析能力指的是分析方法对于文法的甄别能力，也就是可以理解成文法包括的范围，LR(1)范围最大，比如，是SLR(1)文法的文法也一定是LR(1)文法

本质区别

四个文法，区别都只在一点，LR分析表中ACTION表中的归约动作的差别：
先做一个假设，有文法G，其中：

文法的第二条产生式是 (2) A->a  （之后的r2表示按照第二条产生式进行归约）
终结符集合是 { a,b,c,$ }
FOLLOW(A) = { b,c }
有状态 I5: A->a·
（LR(1)时 有状态 I5: A->a·,b ）
（LALR(1)时 有状态  I5: A->a·,b 和同心项  I10: A->a·,$ 合并为  I5: A->a·,b|$ ）

• LR(0) 状态有归约状态，整个状态都会进行该归约动作
  即LR分析表中的状态5所在的那一整行全填 r2

状态	a	b	c	$
5	r2	r2	r2	r2

• SLR(1) 状态中针对FOLLOW集中有的终结符号会进行该归约动作
  即LR分析表中的状态5所在的那一行中对应的FOLLOW(A)中有的终结符填写r2

状态	a	b	c	$
5		r2	r2

• LR(1) 状态中针对展望符对应的总结符号进行该归约动作（一般为FOLLOW集的真子集）
  即LR分析表中的状态5所在的那一行中只对展望符b填写归约动作r2

状态	a	b	c	$
5		r2

• LALR(1) 状态中也是针对展望符对应的总结符号进行该归约动作（一般为FOLLOW集的真子集）
  即LR分析表中的状态5所在的那一行中只对展望符b和$填写归约动作r2

状态	a	b	c	$
5		r2		r2

文法对比

• SLR(1)对于LR(0) 排除不合理的归约，使用FOLLOW集解决移入-归约、归约-归约冲突。如果FOLLOW(A)与FIRST(B)存在交集，且A，B属于同一个项目集，则SLR无法解决该冲突。
• LR(1)对于SLR(1) SLR(1)无法解决的冲突使用LR(1)分析法可以解决。使用展望符，每个展望符是FOLLOW集的子集（一般为真子集）。
• LALR(1)对于LR(1) LALR(1)就是在LR(1)的基础上合并同心项集（具有相同核心的项集，也就是项集的第一分量也叫做核心项），与之同时可能会引出新的冲突且只能为归约-归约冲突（原因是合并同心项本质上只是将展望符合并了，对原本的移入动作并没有影响，所以只能是归约-归约冲突）。另外一个毛病是LALR(1)会将LR(1)的报错延后，会多进行若干次归约，直到碰到移入动作才能检测出错误。
• 另外，LR(0)、SLR(1)、LALR(1)的状态数都是一样的，但是LR(1)的状态数会多非常多，比如C语言的文法，LR(0)分析时只有几百个状态，而LR(1)分析会出现几千个状态，所以实际开发中使用LR(1)是不合理的，因而才出现LALR(1)分析方法。

可以适当利用物理意义对二义性文法进行冲突处理

有时候二义性文法相较于无二义性文法来说，少了很多非终结符，这样进行LR(0)分析时也会方便很多，减少很多状态，

如图，左为有优先级的LR分析的树、中为二义性文法的LR分析的树、右为LL分析的树
可以看出，二义性文法的LR分析比有优先级的LR、LL分析方法都简洁高效，因而，在某些时候，权衡性能和效益、确保正确使用文法的情况下，可以适当的使用LR(0)对二义性文法进行分析。

二义性文法

(1)E->E + E
(2)E->E * E
(3)E->(E) 
(4)E-> id

在一下两个状态中

I7
E→ E + E·
E→ E· + E
E→ E·*E

I8
E→ E * E·
E→ E· + E
E→ E·*E

使用SLR分析方法构造SLR分析表：FOLLOW(E) = { +,,),id,$}
对于状态7：
当输入符号是 ‘+’ 时，状态7出现移入-规约冲突，因为+可以移入，同时+属于FOLLOW(E)，可以进行归约动作r1
此时，根据物理意义，即加法的左结合律，a+b+c可以先a+b进行计算，所以此时不会进行移入操作，而是只进行归约操作。
当输入符号是 ‘ * ’ 时，状态7出现移入-规约冲突，因为可以移入，同时属于FOLLOW(E)，可以进行归约动作r2
此时，根据物理意义，即乘法的优先级，a+bc需要先对b*c进行计算，所以此时不会进行归约操作，而是只进行移入操作。
故而状态7的冲突得到解决。
状态8同理，可自行尝试。

一直学，你只是个学生，但只需自创一招，你便是宗师