编译原理:LL(1),LR(0),SLR(1),LALR(1),LR(1)对比

电玩女神 2022-07-14 04:52 318阅读 0赞

LL(1)定义：一个文法G是LL（1）的，当且仅当对于G的每一个非终结符A的任何两个不同产生式 A→α|β，下面的条件成立：SELECT( A→α)∩SELECT( A→β)=![symbol01.gif][],其中，

α|β不能同时![symbol04.gif][]![1x1pixel.gif][]ε。

解释：LL(1)的意思是，第一个L,指的是从左往右处理输入，第二个L,指的是它为输入生成一个最左推导。1指的是向前展望1个符号。LL(1)文法是上下文无关文法的一个子集。它用的方法是自顶向下的(递归式的处理)。它要求生成的预测分析表的每一个项目至多只能有一个生成式。上面的定义说的是，任何两个不同的产生式 A→α和 A→β,选择A→α或者 A→β是不能有冲突的，即SELECT( A→α)∩SELECT( A→β)=![symbol01.gif][]，具体来说，就是，第一:First( A→α) ∩  
First( A→β)=![symbol01.gif][],首符集不能有交集，否则当交集中的元素出现时，选择哪个产生式进行推导是不确定的，（这其中也包含了α|β不能同时![symbol04.gif][]ε![1x1pixel.gif][]，否则交集就是\{ ε\}不为空），第二：若任何一个产生式β，有ε属于First(β),应有First(A)∩Follow(  
A)为空（当ε属于First(β)，则A有可能被空串代替，那么就要看A的下一个字符，即Follow集，即要求Follow集和First集不能相交，否则可能发生冲突）。

LR文法：定义：如果某一文法能够构造一张分析表，使得表中每一个元素至多只有一种明确动作，则该文法称为LR文法。

拓展：由上面的定义可以看到，LL(1)和LR文法都是无二义性的：LL(1)要求生成的预测分析表的每一个项目至多只能有一个生成式，即对于读头下的每一个字符，都可以明确地选择哪个产生式来推导，LR文法要求每一步都有明确的动作，移进和归约都是可确定的，没有二义性。

比较两大类型（自顶向下　vs 自底向上）的文法的特点：

1.首先LL(1)分析法是自上而下的分析法。LR(0),LR(1),SLR(1),LALR(1)是自下而上的分析法。  
   2.自上而下:从开始符号出发，根据产生式规则推导给定的句子。用的是推导  
   3.自下而上:从给定的句子规约到文法的开始符号。用的是归约  
   4.自上而下就是一种试探过程，怎么试探？需要你写出它的FIRST()集与FOLLOW()集。写出这两个集合后根据LL(1)分析表构造规则画出LL(1)分析表。现在基本完成了大半，当计算机输入句子时，分析[程序][Link 1]便会根据输入去和分析表进行匹配，如果每步都能够匹配成功则说明符合该语法规则，分析成功。  
   FIRST()集：其实是终结符的集合，看该非终结符A能不能产生以它里面的某个符号开头的句子。（这也是自上而下分析法的思想）  
   5.自下而上就是把句子变成非终结符，在把非终结符变成非终结符，这样不断的进行如果能到根节点则成功。

LL(1)就是向前只搜索1个符号，即与FIRST()匹配，如果FIRST为空则还要考虑Follow。  
　 LR需要构造一张LR分析表，此表用于当面临输入字符时，将它移进，规约（即自下而上分析思想），接受还是出错。  
   LR(0)找出句柄前缀，构造分析表，然后根据输入符号进行规约。不考虑先行，只要出现终结符就移进，只要出现归约状态，就无条件归约,这样子可能出现归约－移进，归约－归约冲突。  
   SLR(1)使用LR(0)时若有归约－归约冲突，归约－移进冲突，所以需要看先行，则只把有问题的地方向前搜索一次。

SLR(1)定义：满足下面两个条件的文法是SLR(1)文法

a.对于在s中的任何项目 A→α.Xβ,当X是一个终结符，且X在Follow(B)中时，s中没有完整的项目B→r.

b.对于在s中的任何两个完整项目A→α.和 B→β.,Follow(A)∩Follow(B)为空。

解释：a.当X是一个终结符且X出现在读头上，对于项目 A→α.Xβ应该采用移进，若有完整的项目B→r.且Follow(B)中有X，当X出现在读头上时，此时应该归约，于是，就产生了移进和归约冲突

b.假设Follow(A)∩Follow(B)为\{ X \},对于A→α.，若Follow(A)\[A后面的元素\]出现时，应该归约，同理B也一样，于是，会产生归约－归约冲突，SLR(1)是为了消除LR(0)的两个冲突。  
   LR(1)1.在每个项目中增加搜索符。2.举个列子如有A->α.Bβ，则还需将B的规则也加入。  
   LALR(1)就是假如两个产生式集相同则将它们合并为一个，几合并同心集

总结：

见到First集就移进，见到Follow集就归约。

LR(0):见到First集就移进，见到终态就归约

SLR(1)见到First集就移进，见到终态先看Follow集，与Follow集对应的项目归约，其它报错。

SLR分析法包含的展望信息是体现在利用了Follow(A)信息，可以解决“归约－归约”冲突

SLR分析法没有包含足够的展望信息，不能完成解决“移进－归约”冲突，需要改进。

下面是LR(0),SLR(1),LALR(1),LR(1)文法处理能力的比较，圆圈越大说明能力越强。

![20130703204706828][]

[symbol01.gif]: http://eduunix.ccut.edu.cn/index2/edu/%C7%E5%BB%AA%B4%F3%D1%A7%BC%C6%CB%E3%BB%FA%BF%CE%B3%CC/%B1%E0%D2%EB%D4%AD%C0%ED/img/chap05/symbol01.gif
[symbol04.gif]: http://eduunix.ccut.edu.cn/index2/edu/%C7%E5%BB%AA%B4%F3%D1%A7%BC%C6%CB%E3%BB%FA%BF%CE%B3%CC/%B1%E0%D2%EB%D4%AD%C0%ED/img/chap04/symbol04.gif
[1x1pixel.gif]: http://eduunix.ccut.edu.cn/index2/edu/%C7%E5%BB%AA%B4%F3%D1%A7%BC%C6%CB%E3%BB%FA%BF%CE%B3%CC/%B1%E0%D2%EB%D4%AD%C0%ED/img/index/1x1pixel.gif
[Link 1]: http://www.xuebuyuan.com/
[20130703204706828]: /images/20220714/f5d5c3bfb88244bab0fcbe8079339d65.png