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

目录

一.构造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-->?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)分析表如下：

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