← Back to Notes
Notes

Parsing Table

Explains how to construct LR(0) Action and Goto tables using items, closures, augmented grammar, and state transitions for parsing.

Part of the series · 11 / 12

Languages and Compilation

如何生成 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

Comments