编译原理——LR分析表

上周作业涉及到了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

造表

1. 扩充

0) S‘-> S
1) S -> L·L
2) S -> L
3) L -> LB
4) L -> B
5) B -> 0
6) B -> 1

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 。

做到这里，我们发现我们已经全部遍历完毕！

1. 作图

总共有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分析器识别的呢？