LL(1)、LR(1)、SLR(1)、LALR(1)判定方法

1、本节主要讲解LL(1)、LR(1)、SLR(1)、LALR(1)文法的判定方法，即满足什么条件的文法是该文法。copyright hujianfei(一) LL(1) 判定方法判定规则：龙书上有很明确的规则，龙书上这样说，对形如足A a | b这样的文法，满 FIRST (a ) FIRST ( b ) = f若eFIRST ( b)，要满足FIRST (a ) FOLLOW ( A) = f这两个条件的才是LL(1)文法。这里要注意一下条件，a 和 b是可以互换的，意思就是只要其中有一个FIRST集包含 e ，那么就要看另一个了。但是我有个问题，对形如 A a | b | g这样的文法，我们

2、该怎么判断呢？是FIRST (a ) FIRST ( b ) FIRST (g ) = f？我不知道，也许是这样递推的吧。(二)LR(1)判定方法判定规则：此文法在 LR(0)自动机的基础之上加入了向前搜索符号，（什么是向前搜索符号，在形如 A d ., a 的项目集中 a ，是 LR(0) 中不具备的，就是我们的向前搜索符号，而 A d. 就称作核心，找同心集，看的就是它。）。所以，当先判断 SLR(1) 文法有冲突的时候，并且找到 SLR(1) 所有冲突，然后判断加入向前搜索符号之后能否解决所有的冲突，不能的话，就不是SLR(1)文法了。(三) SLR(1) 判定方法判定规则：直接找冲突，

3、如何找冲突？经验！只要能找到一个冲突，就不是 SLR(1) 文法，我们就可以结束了。如果暂时没有找到冲突，那就把自动机图在草稿纸上画出来，就一目了然了，有冲突的话也就能看出来，没有冲突也就是 SLR(1) 文法了。注：SLR(1) 文法的自动机，语法分析表啊，都是 LR(0) 的方法，不懂的去看我的的讲解。上边规则说到了找冲突一般有经验，经验是什么呢？我总结如下：若某一产生式右部是另一产生式的前缀，如：LR(0)U X .aY和 V X .有可能出现移进归约冲突，什么时候出现呢？同时满足以下两个条件：两个产生式必须能出现在同一个状态（就是指我们自动机中的每个状态） FOLLOW (V ) a

4、f那就是冲突了，就不是 SLR(1)文法了。说明：为什么求FOLLOW (V )？因为VX .是需要归约了，归约就需要求出FOLLOW (V)的呀，不懂得去看LR(0)分析表的构造方法。那a怎么解释呢？因为UX .aY要移进a了嘛。举个例子：有如下文法：S Ua | VbU abCV a考虑项目集U a.bC，可以出现在同一个状态中（自己画自动机可以证明），V a.并且 FOLLOW (V ) b = b b = b f ，于是就移进归约冲突喽。若两个不同的产生式有相同的右部或者某一产生式右部是另一产生式右部的后缀，U X .U XY.形如V X . 、V Y.有可能出现归约归约冲突。什么时候

5、出现冲突呢？同时满足一下两个条件，两个产生式出现在同一个状态中（跟上边的一样的解释） FOLLOW(U ) FOLLOW (V ) f那么就是冲突了，就不是SLR(1)文法了。这里为什么又要都求FOLLOW集了呢？因为都要归约了嘛！举个例子：有如下文法，SUV Ua | Vb | Ub aVc | a Vc | aU a.考虑项目集V a. 他们都出现在同一状态，可以自己在草稿纸简略的画自动机证明。并且 FOLLOW (U ) FOLLOW (V ) = a, b b, c = b f ，于是归约归约冲突，不是SLR(1)文法，结束。再者，考虑项目集U V aVc. Vc.他们都出现在同一状态

6、，可以自己在草稿纸简略的画自动机证明。并且FOLLOW (U ) FOLLOW (V ) = a, b b, c = b f，于是归约归约冲突，不是SLR(1)文法，结束。(四)LALR(1)判定方法在 LR(1) 文法基础之上，找到同心集。（什么是同心集，已经解释了。什么是向前搜索符号，在形如 A d ., a 的项目集中 a ，是 LR(0) 中不具备的，就是我们的向前搜索符号，而 A d. 就称作核心，找同心集，看的就是它。）同心集合并之后，举个例子如下： A d ., a , B d .c A d ., c , B d .a合并为 A d ., a / c , B d .c / a，我们看到向前搜索符号相同，当输入符号是 a 或 c 的时候，既按照 A dB d 归约，故发生归约归约冲突，所以不是