构造LR(1)分析表和LALR(1)分析表

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

一.构造LR(1)分析表

拓广文法--->项目集规范族---->LR(1)分析表

(1)拓广文法
2)(带向前搜索符)项目集规范族

向前搜索符的写法:

① 文法开始符号的Follow集合:Follow(S')={#}

所以文法(0) S‘-->S后面添加的就是 (0)S'--->S,#

②先看左边,再看右边

A-->•B,a


B--->....


这里B能推出什么看的是B后面的是否为空:


为空:照抄“,”后面的字符


不为空:将First()加到“,”后面,其中为非终结符


例如:S-->•BB,左边为S,右边的“圆点”后面跟着S的只有:S'--->•S,S后面为空,照抄

S-->•BB,#

对于B--->•aB,左边是B,那么右边“圆点”后跟B的只有:S-->•BB,因为B后面有B(不为空),所以将First(B)写在“,”后面。First(B)={a,b}

所以B--->•aB ,a/b,所以I0的情况如下:

例题1:

这里注意,若左边为S,那么找右边“圆点”后跟S的,有两种情况:①S-->S;B        ②S’-->S

对于①:S后面为“;”,所以“,”后面写分号

对于②:S后面为空,照抄“,”后面的字符

例题2:

对于例题2这里需要注意:

若左边为B,那么右边符号条件的为A-->•BA,B后面为A,First(A)={a,b, },若遇到

若A为空,那么A--->•B,这时候B后面为空,照抄“,”后面的字符

继续下面的步骤:

这里与SLR(1)不同的地方在于:写完该项目时,还要再判断一次向前搜索符,判断条件与之前一样:

以此类推,得到最终的项目集规范族:

(3)构建LR(1)分析表

I4:B-->b,a/b,其是拓广文法中的(3)B--> b 那么我们将向前搜索符(“,”)后面的字符(a/b)填充入r3

以此类推得到:

二.构造LALR(1)分析表

拓广文法--->项目集规范族---->LR(1)分析表

这里与LR(1)分析表唯一不同的是项目集规范族的处理,加入了合并同心集的概念(表达式相同,向前搜索符不同)

如上,I3和I6表达式相同,向前搜索符号不同,将两者合并I3I6

同理:

变为

对于分析表,需要将合并的项目写在一起:

最终可以得到LALR(1)分析表如下:

注意:对于合并的情况,只用分析其中一个项目即可

目录
相关文章
|
存储 自然语言处理 算法
【编译原理】LR(1)分析法:C/C++实现
【编译原理】LR(1)分析法:C/C++实现
1630 0
|
安全 Linux iOS开发
Anaconda下载及安装保姆级教程(详细图文)
Anaconda下载及安装保姆级教程(详细图文)
36002 1
Anaconda下载及安装保姆级教程(详细图文)
|
编译器
区分LR(0),SLR(1),LR(1)和LALR(1)
区分LR(0),SLR(1),LR(1)和LALR(1)
2210 1
|
自然语言处理 算法 编译器
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
1287 0
构造LR(0)分析表和SLR(1)分析表
构造LR(0)分析表和SLR(1)分析表
1080 0
|
XML 机器学习/深度学习 数据格式
YOLOv8训练自己的数据集+常用传参说明
YOLOv8训练自己的数据集+常用传参说明
23819 3
|
缓存 分布式计算 资源调度
MapReduce入门(一篇就够了)
MapReduce入门(一篇就够了)
10493 1
MapReduce入门(一篇就够了)
|
Ubuntu Python
全网最简约的Vscode配置Anaconda环境(百分百成功)
全网最简约的Vscode配置Anaconda环境(百分百成功)
34633 0
全网最简约的Vscode配置Anaconda环境(百分百成功)
|
机器学习/深度学习 人工智能 自然语言处理
【强化学习】强化学习的概述及应用,附带代码示例
强化学习(Reinforcement Learning, RL)是机器学习中的一种重要范式,它通过让智能体(agent)在环境中采取行动并根据所获得的奖励(reward)来学习最优的策略(policy)。简而言之,强化学习的目标是让智能体学会在特定环境下做出决策,以最大化累积奖励。这种学习方式模拟了生物体如何在环境给予的正反馈(奖励)和负反馈(惩罚)中学习行为的过程。
3516 4
|
数据库
1NF | 2NF | 3NF的区分以及什么是函数依赖、部分函数依赖、值传递依赖(最详细的讲解1NF、2NF、3NF的关系)
这篇文章详细讲解了数据库范式中的1NF、2NF和3NF,包括它们的定义、区分方法和如何判断部分函数依赖和传递函数依赖,以及如何将数据表规范化到相应的范式。
1NF | 2NF | 3NF的区分以及什么是函数依赖、部分函数依赖、值传递依赖(最详细的讲解1NF、2NF、3NF的关系)

热门文章

最新文章