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

2023-12-26 14:33:17

目录

一.构造LR(1)分析表

(1)拓广文法?编辑

(2)(带向前搜索符)项目集规范族

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

二.构造LALR(1)分析表


一.构造LR(1)分析表

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

(1)拓广文法

(2)(带向前搜索符)项目集规范族

向前搜索符的写法:

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

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

②先看左边,再看右边

A-->\alpha?B\beta,a

B--->....

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

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

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

?例如: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,\varepsilon},若遇到\varepsilon
若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)分析表如下:

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

文章来源:https://blog.csdn.net/weixin_69884785/article/details/135184189
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。