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

灰太狼 2023-02-16 12:02 27阅读 0赞

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

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

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

*  **LALR(1)** 状态中也是针对展望符对应的总结符号进行该归约动作（一般为FOLLOW集的真子集）  
    即LR分析表中的状态5所在的那一行中只对展望符b和$填写归约动作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)分析时也会方便很多，减少很多状态，  
![状态][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjg1NDQ1_size_16_color_FFFFFF_t_70]  
如图，左为有优先级的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+b*c需要先对b\*c进行计算，所以此时不会进行归约操作，而是只进行移入操作。  
故而状态7的冲突得到解决。  
状态8同理，可自行尝试。

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjg1NDQ1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200609195350849.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjg1NDQ1,size_16,color_FFFFFF,t_70