如何生成 LR(0) 分析算法所需要的 Action 表和 Goto 表

Conception of Items

LR(0) Item：在产生式 RHS 的某个位置添加特殊圆点 • 的语法规则

E → • E + B    // 还未识别任何符号
E → E • + B    // 已识别 E，期待 '+'
E → E + • B    // 已识别 E+，期待 B
E → E + B •    // 整个产生式已识别，可归约

特殊情况：E → ε 只有一个 item：E → •

Item 数量计算

k 个符号 ⇒ k+1 个 items

Item Set

一个 parser 的状态，通常不能只用一个 item 表示，而要用一个 item 的集合 来表示。

为什么？

因为在某个时刻，分析器可能还不能确定最终会走哪条产生式。

例如如果文法里同时有：

• E → E + B
• E → E * B

那么当已经识别出一个 E 后，可能同时面临：

• E → E • + B
• E → E • * B

所以一个状态要用 一个 item set 表示，而不是单个 item

Closure

任意一个 item 集都可以扩展成满足上面规则的最小集合，这个最小扩展就叫 closure。

也就是说：

• 先放入核心 item
• 如果点前面是非终结符，就补入它的产生式初始 item
• 如果新补进来的 item 又出现点前非终结符，继续补
• 直到不能再加为止

其实 closure = 把 item set 补完整（遇到非终结符就展开）

注意新加进来的 closure-added items 前面要加上 + 号要和 kernel / core 做区分

Augmented Grammar

the grammar is always augmented with an extra rule 在构造 parsing table 之前，一定要先加一条新产生式 形式是：

(0) S → E

• S：新的开始符号（new start symbol）
• E：原来的开始符号（old start symbol）

Constructing the action and goto table

第一步：增广文法

加一条新开始规则：

• S → 原开始符号

第二步：写出 item

每条产生式右侧加点，得到所有 items。

第三步：求初始 item set

从：

• S → • 原开始符号

开始求 closure，得到状态 0。

第四步：不断求后继状态

对每个状态，看点后面有哪些符号；

对每个符号：

• 移点
• 求 closure
• 得到新状态或连到旧状态。

第五步：画状态转移图

把所有 item set 和转移关系整理出来。

第六步：填 Goto 表

非终结符转移填入 Goto 表。

第七步：填 Action 表中的 shift

终结符转移填成 s编号。

第八步：填 accept

若状态包含：

• S → E •

则在 $ 列填 acc。

第九步：填 reduce

若状态包含：

• A → w •

则该状态填 rm