构造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)分析表如下:
注意:对于合并的情况,只用分析其中一个项目即可
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!