---

LR(0)项目定义及四种项目类型

规约项目：点在产生式最右边，且该产生式不是拓广文法G'[S]的第一个产生式S' ---> S。

移进项目：点的右边是终结符T。

待约项目：点的右边是非终结符V。

接受项目：点在产生式最右边，且该产生式是S' ---> S。

---

 为什么需要拓广文法？

---

LR(0)项目集闭包与项目集规范族

每个项目集闭包对应着分析器的一个状态！

① 什么是闭包？

② 后继项目与转移 

 

③ 项目规范族 

---

识别拓广文法所有规范句型活前缀的DFA（构造LR(0)项目集规范族）

构造LR(0)项目集规范族的步骤：

 ① 把文法G[S]写出拓广文法G'[S]。

② 构造初始项目集Ⅰ0，直接把拓广文法G'[S]的全部产生式抄过来，并在每个产生式的右部的最前面加上一个点。

③ 遍历项目集Ⅰ0的每个产生式的点后面是什么？有什么就依次识别什么。（类似广度优先搜索）

把能识别的产生式的点右移。构造出新的项目集Ⅰ1。

④ 对新得到的项目集Ⅰi，如果里面的新产生式的点的右边是终结符，那就不管。

如果右边是非终结符，那么还要把Ⅰ0中所有左部为该非终结符的产生式抄过来。

直到没有新的产生式需要加入，则Ⅰi 构造完成。

⑤ 方向的画法：

如果构造出的项目集Ⅰi 和自身相同，就画一个弧，指向自身。

如果构造出的项目集Ⅰi 和自身不同，并且和其他已有项目集也不相同，就画一个箭头，从自身指向Ⅰi。

如果构造出的项目集Ⅰi 和自身不同，但是和其他已有项目集Ⅰk相同，就画一个箭头，从自身指向相同的已有项目集Ⅰk。

---

构造LR(0)分析表

 根据LR(0)项目集规范族，构造LR(0)分析表！

① 画出LR(0)分析表的框架。

纵向：项目集的编号0,1,2,3,4,....... (对应Ⅰ 0，Ⅰ 1，Ⅰ 2 ......)

横向：分为两大块。

文法G[S]中全部的非终结符，外加#，组成ACTION表。

文法G[S]中全部的终结符，组成GOTO表。

（此处针对的是文法G[S]，不是拓广文法！）

② 对所有存在状态转换的项目做如下操作：

项目集Ⅰ 0 通过识别S，到达Ⅰ 1。所以，GOTO[0][S] = 1 。

项目集Ⅰ 0 通过识别B，到达Ⅰ 2。所以，GOTO[0][B] = 2 。

项目集Ⅰ 0 通过识别b，到达Ⅰ 4。所以，ACTION[0][b] = s4 。

项目集Ⅰ 0 通过识别a，到达Ⅰ 3。所以，ACTION[0][a] = s3 。

（s 表示 移进操作）

同理，完成其他项目集的GOTO表状态填写 和 ACTION表中的移进操作填写。

③ 对所有的规约项目做如下操作：

项目集Ⅰ 4是一个规约项目，其中的产生式对应于拓广文法G'[S]的第3个产生式。（拓广文法G'[S]产生式编号从0开始计数），就在ACTION表中，与项目集Ⅰ 4对应的第4行整行填写 r3。

同理，完成其他规约项目集的ACTION表中的规约操作填写。

④ 对唯一的接受项目做如下操作：

在接受项目的ACTION表的这一行的第#列，填写Acc，表示接受。

最终得到我们构造的LR(0)分析表！

---

LR(0)分析法的问题 （无法处理所有的冲突）

即LR(0)文法不存在冲突项目，既没有移进-规约冲突，也没有规约-规约冲突！

 

---

LR(0)分析法的算法实现

---

 对LR(0)分析法的改进 （SLR(1)分析法）

SLR（1）分析法可以解决项目集中存在的移进-规约冲突。

SLR（1）文法中，允许存在移进-规约冲突。

由下图可以看出，项目集Ⅰ4和Ⅰ5都存在移进-规约冲突。（既可以移进，又可以规约）

构造SLR（1）分析表

Step 1：写出该文法G[S]的拓广文法G'[S]，方法同上。

 Step 2：构造LR(0)项目集规范族，方法同上。

Step 3：构造LR(0)分析表，方法同上。此时，我们会发现有些位置存在冲突。

Step 4：求拓广文法G’[S]的FOLLOW集。 

Step 5：用FOLLOW集消除LR（0）分析表的冲突，得到SLR（1）分析表。 

即对于某一个规约项目，只有它左部的FOLLOW集中有的非终结符，才能在这一列上进行规约。

例如：状态9中，规约项目为E--->E+T. ，对应拓广文法的第1条产生式，这个项目的左部E的FOLLOW集FOLLOW(E)中只包含 ), +, #。

所以，只能在第9行的第), +, #列填写 r1 。

---

SLR（1）分析法的问题 

---

本节覆盖的重点、难点