编译原理 更强的LR分析方法
更强的LR分析方法SLR(1)与LR(1)
SLR(1)分析法
LR0文法比较简单,描述的语言也比较有限,如下面这个文法不属于LR0,先构造LR0项目集规范族可以看出。
注意 I1 I2 I9出现了移进和归约的冲突
消解移进归约冲突是有可能的,可以细分。
如,当前输入的单词不在要归约生成的A的FOLLOW集中,那不能采取归约动作。
如,当前单词是+时,那它不在S‘的FOLLOW集合中,不采用归约,而是采用移进。 相当于向后看了一个单词,所以是1不是0
SLR1冲突解决方法
将这个方法一般化后得到
称为 SLR(1)冲突解决方法
SLR分析表构建
文法拓广
- 开始符号只有唯一产生式
- G’只有唯一的接收状态
- 文法开始符号不会出现在产生式右部
最重要的还是第三步——构造ACTION和GOTO表,和LR0分析表构造有差异。
主要注意第二步,如果状态集中存在归约项目,遇到该非终结符的FOLLOW集中的终结符时,进行归约(使用对应该归约项目的产生式)。
与LR0分析表的区别,LR0分析表的归约是不加区分的放在了Ik的所有列,而SLR1先要判断这一列对应的符号在非终结符的FOLLOW集中,减少了冲突
构建示例
对于之前的非LR(0)文法来说
当前已经拓广了文法以及构建了DFA。之后需要消解冲突。
注意,(待约项目的)非终结符FOLLOW集中不能有同一项目集中移进项目需要的符号,如下面两个FOLLOW集对于I1,S'的FOLLOW集没有出现+号(+号是归约时需要的符号),对于I2,E的FOLLOW集中没有出现*号。
?FOLLOW集怎么求,还不够熟练
注意状态1的状态转换函数,分别检查了待约和移进项目,仅对于指定的符号进行状态转换。
状态2也是,如果采用的是之前LR0分析方法,*这一列会同时出现移进s7和归约r2冲突。
注意第三个状态,虽然只有一个待约项目,但是也进行了FOLLOW集的检测。
LR1分析法
SLR1分析法的局限性
SLR冲突消解方法还是存在一些问题。如在同一个项目集中,归约项目的非终结符的FOLLOW集和移进项目期待的下一个终结符(点后面的终结符)有交集。
但是实际上状态二位于分析栈栈顶,面临输入符号=时,也不能归约,因为所有的规范句型中,不存在R=为前缀的规范句型,只有以*R=为前缀的规范句型(在L0中),之所以=能在R的FOLLOW集中,是因为R前面有*。
所以状态2处于栈顶时,面临输入串=是不能按照I2中的归约项目进行归约的。
FOLLOW集合计算得到的超前符号集合可能大于实际能够出现的超前符号集!!存在局限性 如该表中
*R后面才能加=号
所以我们需要更加精确的预测信息,不能只看FOLLOW集合,来判断下一步操作,所以需要LR1分析方法。
构造LR1分析表
LR1的项目
a1a2ak是终结符,称为向前搜索串(展望串),每个状态除了LR(0)项目,还有和项目相关的展望信息。而不是用FOLLOW集合做展望。
展望串对归约项目具有指导意义。
如能否把α归约为A,还需要看后面的k个终结符。如果是SLR中,只需要后面的一个单词在FOLLOW集合中即可归约,这点它们是不同的。
对于移进项目,展望串没有直接意义,随着点向后移动,展望串最终传递到规约项目。
一般只使用k=1的情况
LR1有效项目
α和β都形成,即将归约的时候,面临的单词应该是a。
之所以是βa的FIRST集,因为β可能是空串。
LR1项目集规范族
通过计算有效项目,构造项目集规范族
第一个项目的展望串是#,因为希望归约到开始符时,所有的串都处理完了,面临句末符。
分析表构造
注意归约项目仅仅放在 a的那一列,(SLR1中放在FOLLOW集合中的列)
第四项指的是归约到A后,对应状态j
使用了更加精确的展望信息。
展望信息哪来的??
构造示例
I0中第三项展望串为a或b的原因,aB归约成B的时候,后面跟着的会是B(第二项),B的开头是a或者b。
注意I2中的展望串变了,因为后面没有东西了(这是第二个B)。
I3中a后面期望的是B,B的开头是a/b
另外注意I6,识别a后剩下的B是在末尾的B,所以展望串是#,因为后面不会再有一个额外的B,和I3不一样。
注意,移进项目的展望串传递到了后面的归约项目
分析示例
LR分析器,总是根据当前栈顶与当前单词查找分析表,只向前检查一个单词,所以称为LR1分析。
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。