区分LR(0),SLR(1),LR(1)和LALR(1)
目录
这几个文法大致的步骤都相同,只是细节不同:
拓广文法---->项目集规范族---->构造分析表
首先区分几个项目
为什么要进行拓广文法呢?
文法是自底向上,归约时,b和c是归约哪一个S,编译器是不能区分的,那么拓广文法通过S'--->S
区分了两个S
对于LR(0)文法:
对于SLR(1)文法:
若冲突项目存在,那么就无法构表,继续判断是不是SLR(1)文法,如果根据Follow集判断交集为空,那么就是SLR(1)文法,如果不为空,那么就无法构表,既不是LR(0)文法,也不是SLR(1)文法。
对于LR(0)和SLR(1)文法:
如果文法中没有冲突项目,他是LR(0)文法,也是SLR(1)文法,也就是SLR(1)中包含不冲突的项目,也包含符合条件的冲突项目,但是如果该冲突项目也不包含在SLR(1)中,那么既不是LR(0)文法,也不是SLR(1)文法。
所以,SLR(1)文法的目的就是减少冲突的产生
对于LR(1)和SLR(1)文法:
若存在冲突项目:
LR(1)文法根据向前搜索符来判断:如果为空,那么就是LR(1)文法
SLR(1)文法是根据Follow集判断的:如果为空,那么就是SLR(1)文法
LR(1)的使用场景:
若是冲突项目,并且也不满足SLR(1)的条件,那么就要回退,重新构建带向前搜索符号的项目,判断是否为LR(1)文法。
对于LALR(1)文法:
任何一个 SLR(1)文法一定是一个 LALR(1) 文法,即:
LALR(1)SLR(1)
LALR(1)文法与LR(1)文法的区别在于,LALR(1)文法合并了同心集
例题1:
对于I2,S->L?=R和R-->L?产生了(移进--归约冲突)
继续求Follow集
将移进项目的“点”后面的终结符和规约项目的Follow集进行交集,判断是否为空
通过构造向前搜索符号继续判断,在I2中存在(移进---归约)冲突:
通过移进的“点”后面的终结符和归约项目“逗号”后面的向前搜索符号的交集判断是否为空
{=}{#}=,所以是LR(1)文法
例题2:
① 整行填上r,就是LR(0)
② 若同样的表中,不同的行出现了同样的项目,那么就是LR(1)
③ 不同的行中是不同的项目,就是SLR(1)
例题3:
?
例题4:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!