上周作业涉及到了LR(0) SLR分析表的构造，花了比较多的时间回顾，打算这次再整合一下
LR（0）分析表
自底向上的语法分析
结构
image
LR分析表的结构如上，其分为两个部分Action Goto
Action
两个参数状态i，终结符号a（s(i)代表第i个状态，r(i)代表第i条表达式）
- 移入j：j是一个状态，把j压入栈（同时移入a）
- 归约A->B：把栈顶的B归约到A（并根据Goto表项压入新状态）
- 接受：接受输入，完成分析
- 报错：在输入中发现语法错误
Goto
Goto[i,A]=j
以作业例子来说明
文法
若有定义二进制数的方法如下：
(1) S → L·L | L
(2) L → LB | B
(3) B → 0 | 1
试为该文法构造 LR 分析表
容易得知这个文法可以推出0 1 00 01 等的字符串。因为它是左递归。不适用于LL文法分析，只能使用LR分析。
因为本题入口有两个——S → L·L S → L，所以需要构造额外的产生式S'->S
造表
- 扩充
0) S‘-> S
1) S -> L·L
2) S -> L
3) L -> LB
4) L -> B
5) B -> 0
6) B -> 1
- 状态
2.1 第一次遍历
State 0
我们从[S -> . L·L]开始，构造这个状态的闭包，也就是加上所有能从这个产生式推出的表项。
首先，判断.后面是否为非终结符号A。如果是，那我们就得找所有由A->推出的产生式，并将它们添加进入闭包里(也就是State包里)。循环做即可。
因此我们可以得到 State 0 有
- S'-> . S
- S -> . L·L
- S -> . L
- L -> . LB
- L -> . B
- B -> . 0
- B -> . 1
下一步，就是我的.往下一位移动。对每个符号X后有个.的项，都可以从State 0过渡到其他状态。
由以上6条式子可以得知下一位符号可以是 S L B 0 1。所以自然可以得到5个状态。
State 1
State 1 是由 State 0 通过 S 转移到这里的，所以我们找出所有State 0中在 S前有.的项。
- S' -> S .
此状态作为结束状态Accept，不需要继续状态转移了。
State 2
State 2 是由 State 0 通过 L 转移到这里的，所以我们找出所有State 0中在 L前有.的项。
S -> . L·L S -> . L L -> . LB
有3条式子，现在我们将.向后推一格，就得到State 1的项了。
但是.之后的符号分别是· $ B ，B为非终结符号，我们得包含B ->的项
- S -> L. ·L
- S -> L.
- L -> L. B
- B -> . 0
- B -> . 1
State 3
State 3 是由 State 0 通过 B 转移到这里的，所以我们找出所有State 0中在 B前有.的项。
- L -> B.
因为.后没有其他符号了，因此这个状态不需要继续转移了。
State 4
State 4 是由 State 0 通过 0 转移到这里的，所以我们找出所有State 0中在 0前有.的项。
- B -> 0.
因为.后没有其他符号了，因此这个状态不需要继续转移了。
很简单，同样的道理找State 5
State 5
State 5 是由 State 0 通过 1 转移到这里的，所以我们找出所有State 0中在 1前有.的项。
- B -> 1.
因为.后没有其他符号了，因此这个状态不需要继续转移了。
好的，现在我们第一次遍历完成。
2.2 第二次遍历
第二次遍历自然从State 2开始。
我们回到State2 ，可以看出. 之后的符号有· B 0 1 。
State 6
State 6 是由 State 2 通过 · 转移到这里的，所以我们找出所有State 2中在 ·前有.的项。
S -> L. ·L 只有1条，我们往后移发现L又为非终结符号，参考State 0做的操作，我们得找出所有的式子。
- S -> L· .L
- L -> . LB
- L -> . B
- B -> . 0
- B -> . 1
共有5条式子，共同组成State 6，由上面的式子可以看出我们还得继续下一次遍历。先不管着，我们进行下一次状态查找。
State 7
State 7 是由 State 2 通过 B 转移到这里的，所以我们找出所有State 2中在 B前有.的项。
L -> L. B 也是只有1条，我们往后移发现没有非终结符号了，那就不需要再继续添加其他式子了。
- L -> LB.
这个状态也不需要继续进行转移了。
接下来很关键，因为我们通过State2的.后的符号找出了State 6 State 7 ，接下来还差符号0 1 ，那么是否像之前一样按例添加状态呢，答案是不是的，因为我们发现通过0 1 找到的闭包集分别是B -> 0 B -> 1 ，这与我们的之前的State 4 State 5 相同。所以我们得将其整合起来，相当于State 2通过 0 1 符号找到了 State 4 State 5 状态。
2.3 第三次遍历
回头看第二次遍历，可以看出只有State 6可以进行状态转移了。
那么就将State 6作为第三次遍历的源头，可以看出. 之后的符号有L B 0 1 。
State 8
State 8 是由 State 6 通过 L 转移到这里的，所以我们找出所有State 6 在 L前有.的项。
S -> L· .L L -> . LB 有两条式子，往后移发现有非终结符号B，所以经过整合可以得到
- S -> L·L.
- L -> L.B
- B -> .0
- B -> .1
可以看出.的后面还有一个符号，所以这里我们还得再进行一次遍历。
接下来，又是遇到重复的包的情况，可以看出我们由 State 6通过B 0 1 得到的闭包分别是L->B B->0 B->1 ，很明显，这分别对应于State 3 State 4 State 5 。
第三次遍历也就结束了。
2.4 第四次遍历
回看第三次遍历，可以看出只有State 8 可以进行状态转移，其. 之后的符号分别是B 0 1 。
诶，感觉很熟悉，就是上面几行刚说的情况，也就是说通过这三个符号找到的闭包是我们之前遇到的状态，分别是State 3 State 4 State 5 。
做到这里，我们发现我们已经全部遍历完毕！
- 作图
总共有8个状态，通过以上流程做成个图是什么样子的？来看看！
image
这么一看就很清晰明了了，我们就可以通过这个图做出我们的LR分析表
其实就是我们之前呈现的表
image
-
Action就是我们指向的下一个终结符号的状态（S(i)) -
Goto就是我们指向的下一个非终结符号的状态（i）
在状态 I2 和 I8 中，既有移入项目，也有规约项目，存在移入 - 规约的冲突，所以不是 LR(0) 文法，但是因为 FOLLOW(S) ∩ {0, 1}= ∅，所以可以用 FOLLOW 集解决冲突，所以该文法是 SLR(1) 文法。
上表我们发现还有r1，r2，r3等。这个其实就是代表状态停止转移时为第几条表达式，r3代表第三条表达式L -> LB。
根据SLR分析器识别输入字符串
当我们构建了表之后，我们如何运用起来呢？
下面我们通过一个例子来说明
011·101
以上字符串是如何被SLR分析器识别的呢？
| 栈 | 符号 | 输入 | 动作 | |
|---|---|---|---|---|
| （1） | 0 | 011·101 $ | 移入 | |
| （2） | 0 4 | 0 | 11·101$ | 根据 B->0 归约 |
| （3） | 0 3 | B | 11·101$ | 根据 L->B 归约 |
| （4） | 0 2 | L | 11·101$ | 移入 |
| （5） | 0 2 5 | L 1 | 1·101$ | 根据 B->1 归约 |
| （6） | 0 2 7 | L B | 1·101$ | 根据 L->LB 归约 |
| （7） | 0 2 | L | 1·101$ | 移入 |
| （8） | 0 2 5 | L 1 | ·101$ | 根据 B->1 归约 |
| （9） | 0 2 7 | L B | ·101$ | 根据 L->LB 归约 |
| （10） | 0 2 | L | ·101$ | 移入 |
| （11） | 0 2 6 | L · | 101$ | 移入 |
| （12） | 0 2 6 5 | L · 1 | 01$ | 根据 B->1 归约 |
| （13） | 0 2 6 3 | L · B | 01$ | 根据 L->B 归约 |
| （14） | 0 2 6 8 | L · L | 01$ | 移入 |
| （15） | 0 2 6 8 4 | L · L 0 | 1$ | 根据 B->0 归约 |
| （16） | 0 2 6 8 7 | L · L B | 1$ | 根据 L->LB 归约 |
| （17） | 0 2 6 8 | L · L | 1$ | 移入 |
| （18） | 0 2 6 8 5 | L · L 1 | $ | 根据 B->1 归约 |
| （19） | 0 2 6 8 7 | L · L B | $ | 根据 L->LB 归约 |
| （20） | 0 2 6 8 | L · L | $ | 根据 S->L·L 归约 |
| （21） | 0 1 | S | $ | 根据 S'->S 归约 |
| （22） | 0 | S' | $ | 接受 |
网友评论