构造LR(0)分析表和SLR(1)分析表

简介: 构造LR(0)分析表和SLR(1)分析表

1.构造LR(0)分析表

构造LR(0)分析表的步骤如下:


拓广文法--->列项目--->项目集规范簇--->分析表


拓广文法是一种用于描述上下文无关文法的元语法表示法,通过引入了一些扩展的符号和表示方式,以使得语法的描述更加直观


看下面的拓广文法,这里的(0)E'-->E:表示通过E'指向开始文法

列项目:


①首先将每个产生式的右部加“点”


②将通过不同符号的类列举出来


③若列举出来的语句中“点”后面是非终结符,那么需要将该非终结符所属的类都写下来,除了E'->E 。例如 E-->"点"E+T,"点"后面是E,所以将 E->"点" E +T 和 E-> "点" T 写下来,不写E'-->“点” E

接下来分析I0:

由于E'--->E"点"中的"点"已经到最后了,不需要进一步分析

同理可得:

分析表:

列出这样的表,0~8分别表示I0~I8:

第一行表示从I0出发,经过一个E,到达状态1,I0输入T,到达状态2,I0输入a,到达状态5,I0输入"(",到达状态3

以此类推:

若"点"已经在最后了, 表示这个项目已经结束,用”r“表示,在拓广文法中找到相同的项目,填入序号。例如这里的T2:E-->T,在拓广文法中对应(2)

最后,状态1包含"E'-->E",所以在状态1的“#”列表明all

2.构造SLR(1)分析表

SLR(1)步骤和LR(0)相同,只是多求了一部FOLLOW集


点在不同位置,代表的项目不同:


归约项目(A-->•):•在最后

移进项目(A-->•xB):•后面是终结符


接受项目(S--->•):开始文法对应的

待约项目(A--->•XB):•后面是是非终结符

来看以下例子:

通过DFA得到的表如下图所示,但是这里先不用填“r”,表示终结

接下来我们求非终结符的FOLLOW集合:

将Follow集的终结符,写在"r"的位置,例如,拓广文法中(2)E-->T,那么E的FOLLOW集={+,),#}

以此类推,得到:

SLR(1)的出现其实是为了解决LR(0)的两个矛盾,即同一个项目中会产生矛盾:移进---归约        归约---归约


(1)归约---归约


A--->a•


B--->a•


以上就出现了(归约---归约)错误,A的follow集/B的follow集不知是用"A--->a•"还是"B--->a•"


归约

(2)移进---归约(•后面是终结符---•在最后):

表中划圈部分满足,即I1和I3都存在移进---归约错误:

在I1中,我们将•后面的终结符“+”与该项目的开始符“ S’ ”的Follow集相交

I3同理:

得出的两个交集皆为 (空),那么说明LR(0)文法也满足SLR(1)文法的要求,是SLR(1)文法。

LR(0)和SLR(1)的联系

若不存在冲突项目,那么既是LR(0)文法,也是SLR(1)文法


若存在冲入项目,且满足Follow集为(空)的条件,那么就是SLR(1)文法,如果也不满足那么就既不是LR(0)文法,也不是SLR(1)文法


也就是说SLR(0)包含不冲突的项目,也包含符合条件的冲突项目:


SLR(0)LR(0)


目录
相关文章
|
自然语言处理 编译器
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
999 0
编译原理复习三:Bottom-Up LR(0)自动机构造 SLR(1)分析表与分析器的构造(附题目与答案 超详细)
编译原理复习三:Bottom-Up LR(0)自动机构造 SLR(1)分析表与分析器的构造(附题目与答案 超详细)
372 0
|
网络安全
编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)
编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)
889 1
|
存储 自然语言处理 算法
【编译原理】LR(1)分析法:C/C++实现
【编译原理】LR(1)分析法:C/C++实现
1428 0
|
编译器
区分LR(0),SLR(1),LR(1)和LALR(1)
区分LR(0),SLR(1),LR(1)和LALR(1)
1220 0
|
9月前
|
机器学习/深度学习 自然语言处理 搜索推荐
自注意力机制全解析:从原理到计算细节,一文尽览!
自注意力机制(Self-Attention)最早可追溯至20世纪70年代的神经网络研究,但直到2017年Google Brain团队提出Transformer架构后才广泛应用于深度学习。它通过计算序列内部元素间的相关性,捕捉复杂依赖关系,并支持并行化训练,显著提升了处理长文本和序列数据的能力。相比传统的RNN、LSTM和GRU,自注意力机制在自然语言处理(NLP)、计算机视觉、语音识别及推荐系统等领域展现出卓越性能。其核心步骤包括生成查询(Q)、键(K)和值(V)向量,计算缩放点积注意力得分,应用Softmax归一化,以及加权求和生成输出。自注意力机制提高了模型的表达能力,带来了更精准的服务。
10346 46
|
自然语言处理 算法 编译器
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
1008 0
|
9月前
|
机器学习/深度学习 人工智能 算法
机器学习算法的优化与改进:提升模型性能的策略与方法
机器学习算法的优化与改进:提升模型性能的策略与方法
1452 13
机器学习算法的优化与改进:提升模型性能的策略与方法
构造LR(1)分析表和LALR(1)分析表
构造LR(1)分析表和LALR(1)分析表
364 3
|
12月前
|
Shell 开发工具 git
上传文件到gitee(小白都能学会)
上传文件到gitee(小白都能学会)
2586 12