区分LR(0),SLR(1),LR(1)和LALR(1)

简介: 区分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:

目录
相关文章
|
网络安全
编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)
编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)
1227 1
|
自然语言处理 编译器
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
1365 0
|
存储 自然语言处理 算法
【编译原理】LR(1)分析法:C/C++实现
【编译原理】LR(1)分析法:C/C++实现
1665 0
|
自然语言处理 算法 编译器
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
1328 0
构造LR(0)分析表和SLR(1)分析表
构造LR(0)分析表和SLR(1)分析表
1102 0
构造LR(1)分析表和LALR(1)分析表
构造LR(1)分析表和LALR(1)分析表
653 3
DFA与NFA的区别,由正规表达式构造DFA,以及DFA的相关化简
DFA与NFA的区别,由正规表达式构造DFA,以及DFA的相关化简
2340 1
DFA与NFA的区别,由正规表达式构造DFA,以及DFA的相关化简
编译原理----0型,1型,2型,3型文法
编译原理----0型,1型,2型,3型文法
696 1
|
SQL 自然语言处理 Linux
探索 Linux 命令:Bison - 一个强大的语法分析器生成器
Bison是Linux下的一个语法分析器生成器,用于将上下文无关文法转换为C代码,简化编译器或解释器开发。它提供性能优化和灵活的语义动作定制,常用于创建解析器,如SQL解析器或自定义脚本语言解释器。通过编写.y文件定义语法规则,使用Bison生成解析器代码,然后集成到项目中,搭配词法分析器如Flex使用。Bison帮助开发者专注于应用逻辑,而非解析器实现。
编译原理-----逆波兰表示法,四元式,三元式,间接三元式
编译原理-----逆波兰表示法,四元式,三元式,间接三元式
822 0