编译原理

发表于 分类于

编译原理

第2章 形式语言概论

2.1 字母表，符号串，语言

2.1.1 字母表

字母表是符号的非空优先集合，常记作Σ

例如

1
2
3
Σ = {a, b, c}
Σ = {0, 1}
Σ = {BEGIN, END, FOR, WHILE}

注意：字母表里的“符号”不一定是单个字符

BEGIN 也可以看作一个符号

2.1.2 符号串

符号串是字母表中符号组成的优先序列

例如：

abc, 0011, BEGIN END

空串记作：

ε

符号串的长度记作：

|x|

例如：

1
2
|abc| = 3
|ε| = 0

如果：

Σ = {BEGIN, END, FOR, WHILE}

那么

|BEGINEND| = 2

2.1.3 符号串的基本运算

1. 连接

若x和y是符号串，则把y接在x后面得到

第5章 自上而下的语法分析

5.1 基本思想

5.1.1

自上而下语法分析就是：

从文法开始符号出发，一步步推导，看看能不能推出输入串。

从推导角度来看，它试图构造一个最左推导序列；从语法分析树的角度看，他说从识别符号作为根结点，向下构造语法树。

5.2 自上而下分析会遇到的问题：

  1. 回溯

  2. 左递归

5.2.1 问题一：回溯

假设有产生式：

A → α1 | α2 | α3

现在分析的时候遇到了非终结符A,问题来了：

到底该选哪个候选式展开？

如果选错了，推导到一半发现和输入串对不上，就要退回去重新选，这就叫回溯。

5.2.2 问题二：左递归

5.3 怎么避免呢？

  • 消除左递归

  • 避免回溯

5.4 消除左递归

5.4.1 标准形式：

如果有：

U → Ux1 | Ux2 | ... | Uxm | y1 | y2 | ... | yn

其中：

  • Ux1, Ux2, ..., Uxm是左递归候选式

  • y1, y2, ..., yn是非左递归候选式

那么可以改写成

1
2
U  → y1U' | y2U' | ... | ynU'
U' → x1U' | x2U' | ... | xmU' | ε

这就是直接改写法：引进新的非终结符号，把左递归改写成右递归。

5.4.2 经典例子：表达式文法

原文法：

1
2
3
E → E + T | T
T → T * F | F
F → (E) | i

消除后:

1
2
3
4
5
6
7
E  → T E'
E' → + T E' | ε

T  → F T'
T' → * F T' | ε

F  → (E) | i

5.5 间接左递归：

5.5.1 什么是间接左递归？

一般的左递归长这样：

A -> Aα

但是间接左递归不是直接写出来的，而上绕一圈又回到自己：

A => Bα => Aβα

于是：

1
A => Bα => Aβα

这就叫间接左递归

5.5.2 消除间接左dd递归的核心思想：

不要背一堆伪代码，记住一句话：

按照非终结符的顺序，把“前面的非终结符开头”的产生式逐步代入，直到间接左递归暴露成直接左递归，再按照直接左递归的消除方法处理。

5.6 LL(1)文法

现在解决第二个问题：

有多个候选式的时候，怎么不回溯的选出正确的产生式？

比如：

A -> α1 | α2 | α3

自上而下分析时遇到A时，我们希望只看到当前输入符号，就知道该选哪一个产生式

5.6.1 LL(1)这三个符号什么意思？

1
2
3
L:从左到右扫描输入串
L:构造最左构造
1:只向前看一个输入符号

所以LL(1)分析法就是：

从左到右看输入串，每一步构造最左推导，并且只看当前 1 个符号就能决定用哪个产生式

5.6.2 为什么需要FIRST集？

假设：

A -> α | β

如果输入符号是a，我们要判断：

A 应该展开成 α 还是 β？

那就看：

α 能以什么终结符开头？
β 能以什么终结符开头？

5.6.2 FIRST集的定义

FIRST(α)表示：

符号串α能够推导出的所有串中，可能出现在最前面的终结符的集合。

如果α能够推出空串，那么空串也属于FIRST(α)

5.6.3 LL(1)的第一个条件

对于同一个非终结符号的多个候选式：

A -> α1 | α2 | ... | αn

要求：

FIRST(αi) ∩ FIRST(αj) = ∅ i ≠ j

不同的候选式开头的符号不能撞车

如果有几个候选式，有相同的开头符号

则提取公共左因子

如果有：

A -> aB | aC

可以改成：

1
2
A  -> aA'
A' -> B | C
但是只有FIRST集还不够

看这个文法：

A -> a | ε

假设当前要展开A，如果输入符号是a，当然选

A -> a

但是如果输入符号不是a，比如是)或者#呢？

这时候可能应该选:

A -> ε

问题来了，什么时候该选空串？

得看A后面允许根什么符号，这就需要FOLLOW集。

5.6.4 FOLLOW集

FOLLOW(A) 表示：

在某种句型中，可能紧跟在非终结符A后面的终结符的集合。

如果A可能出现在句尾，那么结束符#也属于FOLLOW(A)。

举个简单的例子：

文法：

1
2
S -> A b
A -> a | ε

因为在：S -> A b中，A后面紧跟着b，所以：

FOLLOW(A) = { b }

如果输入符号是a，那么选择A -> a

如果输入符号是b，那么说明A应该什么都不吃，让后面的b去匹配，所以选择A -> ε

选择 ε 产生式的依据不是FIRST集，而是FOLLOW集.

怎么求FOLLOW集？
rule1: 如果S是开始符号，那么：

# ∈ FOLLOW(S)

rule2: 后面有东西，就看后面东西的FIRST

如果有 A -> α U β

也就是说U后面紧跟着β，那么

FIRST(β) - {ε} 加入 FOLLOW(U)

rule3: 后面的东西可能为空，就继承左部的FOLLOW

如果有：

A -> α U β

并且：

β =>* ε

也就是说U后面的β可能会消失，于是：

FOLLOW(A) 加入 FOLLOW(U)

特殊情况，U已经在产生式的最右边，也可以用

第6章 自下而上的语法分析

6.1 基本思想

6.1.1

自上而下的语法分析是：

从输入符号串出发，反复用产生式的右部归约成左部，

最终希望规约到开始符号。

也就是：

输入串 -> 归约 -> 开始符号

从语法分析树来看：

  • 自上而下：根往叶子长

  • 自下而上：叶子往根合

6.1.2 和自上而下分析的对比

对比项 自上而下分析 自下而上分析
起点 开始符号 输入串
方向 从根到叶 从叶到根
主要动作 推导 归约
对应推到 构造最左推导 规范推导的逆过程
方法 LL(1)、递归下降 移进-归约、LR

6.2 移进-归约分析

6.2.1 为什么需要栈？

自下而上分析需要不断扫描输入符号，并判断栈顶某段符号串是否可以归约。

因此需要一个栈：

  • 符号栈：保存已经读入但是尚未完全归约的符号

  • 输入串：保存尚未读入的符号

按照扫描顺序把当前的输入符号推进栈，再查看栈顶符号串是否可以归约。

6.2.2 四种动作

移进-归约分析主要有四种动作

1
2
3
4
1. 移进 shift
2. 归约 reduce
3. 接受 accept
4. 报错 error

1. 移进

读入下一个输入符号，并且把它压入栈

1
2
stack：# a                        stack:# a b
input: b c #        shift->       input:c #

2. 归约

如果栈顶某个符号串是某条产生式的右部，就把他替换成产生式的左部

加入有产生式A -> b

现在的栈中为：stack: # a b

归约后为：stack:# a A

3. 接受

当stack中只剩#和开始符号

输入也只剩#

即：stack:# S input: #

则分析成功，结束工作

4. error

如果当前的状态既不能移进，也不能归约，又不能接受，则出错。

6.3 自下而上分析的两个基本问题

自下而上分析看起来简单：不断归约就行

但是问题是：

1
2
什么时候归约？
由哪条产生式归约？

6.4 短语、直接短语、句柄

6.4.1 短语

设有文法G[S]，句型xuy中的子串u，如果存在：

1
2
S-> *xUy
U-> +u

则称u是句型xuy对于非终结符U的短语

通俗理解：

    短语 = 某个非终结符能推出的一段子串

6.4.2 直接短语

如果：

1
2
S-> *xUy
U-> u

也就是说U一步可以直接推出u，则u是直接短语

通俗理解：

    直接短语 = 某个非终结符一部推出的子串

6.4.3 句柄

句柄是：

    最左直接短语

三者关系总结

1
2
3
- 短语：可以多步推出
- 直接短语：一步推出
- 句柄：最左边的直接短语

6.5 用语法树理解短语和句柄

6.5.1

语法树中：

    某课子树的所有叶子节点从左到右组成的串，就是一个短语。

6.5.2 直接短语和简单子树：

如果一个子树只有两层：

1
父节点 -> 孩子节点

也就是说父节点可以一步推出这些孩子节点，那么这些叶子节点从左到右组成的符号串，就是一个直接短语

6.5.3 句柄和最左简单子树

句柄是：

最左直接短语

从语法树的角度看：

句柄 = 最左简单子树的叶子串

6.6 为什么句柄重要？

自下而上分析的本质是：

不断的把句柄归约成对应的非终结符

也就是说，每次归约的时候，不能随便看到一个产生式右部就归约。

必须找：

当前句型中的句柄

6.6.1 句柄和规范推导

第7章 自下而上LR(k)分析方法

7.1 LR分析法和LR分析程序

1
2
3
4
5
6
7
8
9
┌─────────────────┐
│   总控程序       │  ← 驱动程序，对所有 LR 分析器都一样
│  (Driver)       │
│   ┌─────────┐   │
│   │ 分析表   │   │  ← 核心，因文法不同而不同
│   │(ACTION &│   │
│   │  GOTO)  │   │
│   └─────────┘   │
└─────────────────┘

  • 总控程序：固定的“骨架”，负责查表、压栈、归约等机械操作。

  • 分析表：文法相关的“灵魂”，决定了看到某个状态和输入符号时该做什么。

1. 栈结构（双栈并行）

LR分析使用一个栈，但是逻辑上每个元素包含晾干部分：

状态栈 (State) q₀ q₁ q₂ … qₘ
符号栈 (Symbol) # X₁ X₂ … Xₘ

  • 状态栈：存放DFA状态编号，用于记住“当前的分析进行到了哪一步“

  • 符号栈：存放文法符号（终结符或非终结符），#作为栈底

为什么需要两个栈？

因为自下而上分析的本质是识别句柄。状态栈相当于一个”记忆装置“，把历史信息编码成状态，避免总控程序需要回头查看栈中信息。

2. 分析表：

分析表是二维数组，分为两部分：

(1) ACTION表

ACTION[q, a]：状态q面临输入符号a（终结符或#）时采取的动作。

动作 含义 效果
Sj（Shift） 移进 把a和状态j压入栈，输入指针后移
rj（Reduce） 归约 用第j条产生式U -> x进行归约，弹出x个状态和符号，把U压栈，再通过GOTO表查新状态
acc（Accept） 接受 分析成功，结束
ERROR 出错 报告语法错误

(2) GOTA表

GOTO[q, X]：状态q面对文法符号X（通常是归约后的非终结符）时，要转移的新状态。

注意：

  • ACTION只看终结符（输入串里的符号）。

  • GOTO只看非终结符（归约后产生的符号），用于规约后压入新状态。

3. LR分析过程（三元式）

分析过程中每一步格局用三元式表示：

1
（状态栈、符号栈、剩余输入串）

初始状态

1
(q0, #, a1a2...an#)

① 移进

若ACTION[qi, ak] = Sj ，则：

1
(q0...qiqj, #X1...Xiak, ak+1...an#)

-> 输入指针移到ak+1

② 归约

若ACTION[qi, ak] = rj，且第j条产生式为U->x（|x| = m）：

  1. 弹出栈顶的m个状态n符号；

  2. 把U压入符号栈；

  3. 设此时状态栈顶为qt，查GOTO[qt, U] = qu

  4. 把qu压入状态栈。

1
(q0...qtqu, #X1...Xi-mU, ak...an#)

输入指针不动（归约不消耗输入符号）

③ 接受

若ACTION[qi, ak] = acc分析成功

④ 出错

若ACTION[qi, ak] = ERROR报错

7.2 LR(0) 分析表的构造

1. 基本原理：句柄识别和活前缀

自上而下分析的核心是找句柄（最左直接短语）。但是又两个难题

  1. 句柄在哪？（在栈顶的哪个子串？）

  2. 用哪个产生式归约的？（若有多个右部相同的产生式）

LR的解决思路：

把句柄的识别过程拆成一步一步的状态转移。每读入一个符号，就更新一次识别进度，用状态来记录这个进度。

  • 活前缀：规范句型的一个前缀，不包含该句型句柄右侧的任何符号。换句话说：活前缀就是句柄及之前部分的前缀。
    • 例如句型...句柄...,从左边开始读到句柄右端为止，都是活前缀
    • 分析过程中，栈里的符号串应该始终是一个活前缀。
  • 可归前缀：活前缀中，已经把完整句柄包含进来的那个前缀，叫做可归前缀，此时应该归约。

关键结论：

对句柄的识别 -> 等价于对活前缀的识别。

只要栈内符号始终是活前缀，分析就是正确的。

2. LR(0)项目

为了把”识别进度“形式化，引入LR(0)项目。

定义：在产生式的右部某个位置加一个圆点·,表示已经识别到了这里。

例如产生式A -> xyz对应四个LR(0)项目：

1
2
3
4
A -> ·xyz
A -> x·yz
A -> xy·z
A -> xyz·

项目类型：

类型 形式 含义 下一步
移进项目 A → α·aβ（a 是终结符） 期待读入终结符 a 移进 a
待约项目 A → α·Bβ（B 是非终结符） 期待先归约出 B 转去识别 B
归约项目 A → α· 句柄已完整 归约
接受项目 S' → S· 拓广文法的开始符号已归约完 接受

圆点右边是终结符 -> 移进；是非终结符 -> 待约；圆点在末尾 -> 归约。

3. 拓广文法

为了统一处理“接受”条件，引入新的开始符号S‘：

1
S' -> S

其中S是原文法的开始符号。当栈中出现S且输入为#时，就能用S' -> S进行归约，然后接受。

4. 构造识别活前缀的DFA

LR(0)的核心就是构造一个DFA，他的每个状态是一个项目集（一组LR（0）项目），用来识别所有的活前缀。

(1) 项目集的闭包CLOSURE(I)

目的：如果一个项目集里有A → α·Bβ（待约），那么要识别B，必须先把B的所有产生式开头也加进来。

算法：

  1. I中所有项目属于CLOSURE(I);

  2. 若A → α·Bβ属于CLOSURE(I),则对B的每个产生式B -> γ把B → ·γ;
    重复2直到不再扩大。

直观理解：看到 ·B 意味着“接下来要归约 B”，但 B 怎么归约？先把 B 的所有“开头项目”放进来备用，这就是闭包。

(2)：GOTO函数（状态转移）

GOTO(I, X)：从项目集I出发，经过符号X能到达的新项目集。

算法：

  1. 把 I 中所有形如 A → α·Xβ 的项目，变成 A → αX·β，构成集合 J；

  2. 对 J 求闭包：GOTO(I, X) = CLOSURE(J)。

直观理解：
圆点向右移过 X，表示“已经读入了 X”，然后对新产生的待约项目做闭包。

5. 构造项目集规范族 C（即 DFA 的所有状态）

算法（从初态开始不断扩展）：

1
2
3
4
5
6
C = { I₀ }，其中 I₀ = CLOSURE({ S' → ·S }) 
    while C 还有新状态: 
        for C 中每个状态 I: 
            for 每个文法符号 X: 
                if GOTO(I, X) 非空且不在 C 中: 
                    把 GOTO(I, X) 加入 C

结果：C 就是所有活前缀对应的项目集，也就是 DFA 的状态集合。
DFA 的初态是 I₀，转移边由 GOTO 定义。

6. 有效项目（Valid Item）

项目 A → α·β 对活前缀 γ 是有效的，如果存在规范推导：
S ⇒* δAω ⇒ δαβω

且 γ = δα。

通俗版： 活前缀 γ 已经包含了 α，接下来如果能看到 β，就能归约出 A。那么 A → α·β 就是 γ 的一个有效项目。

一个状态里可能有多个有效项目（对应不同的活前缀推导路径），这是正常的。

7. LR(0)文法

如果构造出的DFA中，每个项目集（状态）都不含冲突项目，则称该文法为LR(0)文法。

冲突类型：

冲突 形式 含义
移进-归约冲突 同一状态里既有 A → α·（归约），又有 B → β·aγ（移进） 不知道应该归约还是读入 a
归约-归约冲突 同一状态里有两个不同的归约项目 A → α· 和 B → β· 不知道用哪个产生式归约

注意：LR(0)文法要求没有任何冲突。

8. 构造LR(0)分析表

有了DFA后，按照以下5条规则填表

设状态集Ii对应状态i。

规则 条件 操作
① 移进 若 A → α·aβ ∈ Iᵢ 且 GOTO(Iᵢ, a) = Iⱼ，a 为终结符 ACTION[i, a] = Sⱼ
② 接受 若 S' → S· ∈ Iᵢ ACTION[i, #] = acc
③ 归约 若 A → α· ∈ Iᵢ（A ≠ S'），对任意终结符 a 和 # ACTION[i, a] = rⱼ，ACTION[i, #] = rⱼ（j 为产生式编号）
④ GOTO 若 A → α·Bβ ∈ Iᵢ 且 GOTO(Iᵢ, B) = Iⱼ，B 为非终结符 GOTO[i, B] = j
⑤ 报错 其余空白格 填 ERROR

重点：LR(0)完整手推实例

一、原文法和拓广文法

PPT给出的原文法G[S]:

1
2
3
4
5
6
7
1. S -> E
2. E -> aA
3. E -> bB
3. A -> cA
4. A -> d
5. B -> cB
6. B -> d

拓广文法：引入新开始符号，保证唯一接受状态

1
2
3
4
5
6
7
8
[0'] S' → S
[0]  S → E
[1]  E → aA
[2]  E → bB
[3]  A → cA
[4]  A → d
[5]  B → cB
[6]  B → d

二、写出所有LR(0)项目

在每个产生式右部所有可能位置插入圆点：

产生式 对应项目
S' → S S' → ·S , S' → S·
S → E S → ·E , S → E·
E → aA E → ·aA , E → a·A , E → aA·
E → bB E → ·bB , E → b·B , E → bB·
A → cA A → ·cA , A → c·A , A → cA·
A → d A → ·d , A → d·
B → cB B → ·cB , B → c·B , B → cB·
B → d B → ·d , B → d·

三、构造项目集规范族（DFA的状态）

step1：求初态I0

I0 = CLOSURE({S’ -> ·S})

求闭包的过程就像“看到待约项目就自动展开“：

  1. 初始放入：S' → ·S

  2. 圆点后是非终结符 S，把 S 的所有开头项目加进来：

    • 加入 S → ·E

  3. 圆点后是非终结符 E，把 E 的所有开头项目加进来：

    • 加入 E → ·aA

    • 加入 E → ·bB

  4. 圆点后是终结符 a、b，停止。

I0 = {

  • S' -> ·S
  • S -> ·E
  • E -> ·aA
  • E -> ·bB

}

从I0求GOTO(出边)

对I0中每个圆点后紧跟符号X的项目，把圆点右移，再求闭包

符号 X 圆点右移后的项目 求闭包 新状态
S S' → S· 圆点已在末尾，无新增 I1
E S → E· 圆点已在末尾 I2
a E → a·A A 在圆点后，加入 A→·cA, A→·d I3
b E → b·B B 在圆点后，加入 B→·cB, B→·d I8

例如：求GOTO(I0, a)：

  • 把I0中的E -> ·aA的圆点右移，得到E -> a·A

  • 对{E -> a·A}求闭包：圆点后面是A(非终结符)，加入A的所有开头项目A->·cA,A->·d，

  • c和d是终结符，停止

  • 结果 I3 = {E -> a·A, A -> ·cA, A -> ·d}

处理I1 = {S’ -> S·}

  • 只有接受项目，没有出边。

  • 分析表中：ACTION[I1, #] = acc

处理 I2 = {S -> E·}

  • 只有归约项目（产生式0： S -> E）

  • 无出边

处理 I3 = { E→a·A, A→·cA, A→·d }

逐个看圆点后的符号：

符号 圆点右移 闭包计算 结果
A E → aA· 无 I4
c A → c·A 加入 A→·cA, A→·d I5
d A → d· 无 I7

I4 = { E → aA· } （归约，产生式 1）
I5 = { A→c·A, A→·cA, A→·d }
I7 = { A → d· } （归约，产生式 4）

处理 I5 = { A→c·A, A→·cA, A→·d }

符号 圆点右移 闭包计算 结果
A A → cA· 无 I6
c A → c·A 加入 A→·cA, A→·d = I5 自身
d A → d· 无 = I7

I6 = { A → cA· } （归约，产生式 3）

关键发现：GOTO(I5, c) 算出来的集合和 I5 完全一样！这叫自环（PPT 图中 I4 上有个 c 的自环箭头）。

处理 I7 = { A → d· }

  • 归约项目，无出边。

处理 I8 = { E→b·B, B→·cB, B→·d }

符号 圆点右移 闭包计算 结果
B E → bB· 无 I9
c B → c·B 加入 B→·cB, B→·d I10
d B → d· 无 I12

I9 = { E → bB· } （归约，产生式 2）
I10 = { B→c·B, B→·cB, B→·d }
I12 = { B → d· } （归约，产生式 6）

处理 I10 = { B→c·B, B→·cB, B→·d }

符号 圆点右移 闭包计算 结果
B B → cB· 无 I11
c B → c·B 加入 B→·cB, B→·d = I10 自身
d B → d· 无 = I12

I11 = { B → cB· } （归约，产生式 5）

四、完整的项目集规范族

状态 项目集内容 类型 对应 PPT
I0 S'→·S, S→·E, E→·aA, E→·bB 初态 I0
I1 S'→S· 接受 —
I2 S→E· 归约(r0) I1
I3 E→a·A, A→·cA, A→·d 移进/待约 I2
I4 E→aA· 归约(r1) I3
I5 A→c·A, A→·cA, A→·d 移进/待约 I4
I6 A→cA· 归约(r3) I5
I7 A→d· 归约(r4) I6
I8 E→b·B, B→·cB, B→·d 移进/待约 I7
I9 E→bB· 归约(r2) I8
I10 B→c·B, B→·cB, B→·d 移进/待约 I9
I11 B→cB· 归约(r5) I10
I12 B→d· 归约(r6) I11

结论：所有状态中，移进项目和归约项目从不共存，也不存在多个不同归约项目共存。

因此，该文法是 LR(0) 文法。

完整分析表如下：

状态 ACTION(a) ACTION(b) ACTION(c) ACTION(d) ACTION(#) GOTO(S) GOTO(E) GOTO(A) GOTO(B)
I0 S3 S8 1 2
I1 acc
I2 r0 r0 r0 r0 r0
I3 S5 S7 4
I4 r1 r1 r1 r1 r1
I5 S5 S7 6
I6 r3 r3 r3 r3 r3
I7 r4 r4 r4 r4 r4
I8 S10 S12 9
I9 r2 r2 r2 r2 r2
I10 S10 S12 11
I11 r5 r5 r5 r5 r5
I12 r6 r6 r6 r6 r6

观察：所有归约状态（I2, I4, I6, I7, I9, I11, I12）的 ACTION 行都是清一色的 rₖ，不管输入什么终结符都归约。这就是 LR(0) “盲目归约”的特点，也是它容易产生冲突的根源。

7.3 SLR(1)分析表的构造

一、LR(0)的”盲目归约”的问题

在LR(0)中，只要状态中出现归约项目A -> α·:

规则是：对所有终结符a和#，都填ACTION[i,a] = rj

比如刚才推出来的I2 = {S -> E·}, LR(0)表是这样填的：

状态 a b c d #
I2 r0 r0 r0 r0 r0

问题：状态I2意味着我已经读完了S -> E。在这个文法里，E后面只能根#(因为E是S的唯一直接组成，而S后面是#)。对a,b,c,d填r0是多余的，甚至是危险的，如果某个状态既有归约又有移进，这种“一刀切”就会发生冲突。

SLR(1)的改进就是：只有在该归约的时候才归约。

二、SLR(1)的核心改进

对归约项目A -> a·，不再对所有终结符填r，而是只对所有的 a ∈ FOLLOW(A) 填 ACTION[i, a] = r。

计算上述文法的FOLLOW集

文法：

1
2
3
4
5
S' → S
S → E
E → aA | bB
A → cA | d
B → cB | d

FIRST 集（辅助计算）：

  • FIRST(E) = {a, b}

  • FIRST(A) = {c, d}

  • FIRST(B) = {c, d}

FOLLOW 集（从后往前、从外往里推）：

非终结符 推导过程 结果
FOLLOW(S') 开始符号，末尾自动加 # ``
FOLLOW(E) S → E，E 在末尾，继承 FOLLOW(S) ``
FOLLOW(B) E → bB，B 在末尾，继承 FOLLOW(E)；B → cB 同理 {#}

这个文法太”瘦”了，所有非终结符后面都只有 #。所以 FOLLOW 集都很小。

三、SLR(1)分析表

我们只列出上述文法有归约的状态：

状态 项目内容 LR(0) 动作 (a,b,c,d,#) SLR(1) 动作 (a,b,c,d,#)
I1 S'→S· —,—,—,—,acc —,—,—,—,acc
I2 S→E· r0,r0,r0,r0,r0 —,—,—,—,r0
I4 E→aA· r1,r1,r1,r1,r1 —,—,—,—,r1
I6 A→cA· r3,r3,r3,r3,r3 —,—,—,—,r3
I7 A→d· r4,r4,r4,r4,r4 —,—,—,—,r4
I9 E→bB· r2,r2,r2,r2,r2 —,—,—,—,r2
I11 B→cB· r5,r5,r5,r5,r5 —,—,—,—,r5
I12 B→d· r6,r6,r6,r6,r6 —,—,—,—,r6

观察：SLR(1)表比LR(0)表稀疏的多，那些永远不会出现的输入(比如在 E→aA· 状态读 c),

SLR(1)直接留空(ERROR)。

但是分析过程完全一样，因为这个文法本手就是LR(0)文法，但是实际运行到这些状态时，输入确实只会是#。