构造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++实现
1428 0
|
网络安全
编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)
编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)
889 1
|
安全 Linux iOS开发
Anaconda下载及安装保姆级教程(详细图文)
Anaconda下载及安装保姆级教程(详细图文)
31853 1
Anaconda下载及安装保姆级教程(详细图文)
|
机器学习/深度学习 人工智能 算法
人工智能中的知识表示与推理
人工智能中的知识表示与推理
640 1
|
编译器
区分LR(0),SLR(1),LR(1)和LALR(1)
区分LR(0),SLR(1),LR(1)和LALR(1)
1220 0
|
XML 机器学习/深度学习 数据格式
YOLOv8训练自己的数据集+常用传参说明
YOLOv8训练自己的数据集+常用传参说明
19776 1
|
12月前
|
PyTorch 算法框架/工具 Python
yolov5的完整部署(适合新人和懒人,一键安装)
这篇文章为新人和希望简化部署过程的用户介绍了如何一键安装和配置YOLOv5环境,包括安装Anaconda、设置镜像源、安装PyCharm、创建虚拟环境、下载YOLOv5项目、安装依赖以及在PyCharm中配置和运行项目。
6359 0
yolov5的完整部署(适合新人和懒人,一键安装)
|
12月前
|
算法
串ababaaababaa的next和串ababaabab的nextval
本文介绍了计算字符串的next数组和nextval数组的方法,通过分析两个具体的例子来展示如何计算这些数组,这些数组通常用于KMP算法中。
577 0
串ababaaababaa的next和串ababaabab的nextval