为以下文法构造 SLR(1) 解析表 S → x A y |x B y |x A z A → qs | q B → q

解决方案

Step1 - 构建增强语法

(0) S′ → S

(1) S → x A y

(2) S → x B y

(3) A → q S

(4) A→q

(5) B→q

Step2 - 找到 Closure & goto 函数来构造 LR (0) 项目。这里 Boxes 代表新状态， Circles 代表重复状态。

Step3 - FOLLOW 的计算

• S → x A y

FOLLOW(S)= {$} (1)

应用 FOLLOW 的规则 (2a)。

比较 S → xay 与 A → α B β。

∴ FIRST(β) = FIRST(y)= {y}

∴ FOLLOW(A)= {y} (2)

不能适用规则 (3)

As, S → x A y 不能与 A → α B 比较

• S → x B y

应用 FOLLOW 的规则 (2a) 。

比较 S → x B y 与 A → α B β。

∴ FIRST(β) = {y}

∴ FOLLOW(B)= {y} (3)

不能适用规则(3)。

• S → x A y

应用 FOLLOW 的规则 (2a)。

∴ FIRST(β) = {z}

∴ FOLLOW(A)= {z} (4)

不能适用规则(3)。

• A → q S

不能适用规则 (2a)。因为 A → qs 不能与 A → α B β 进行比较。

应用规则 (3)

比较 A → qs 与 A → α B

∴ A = A, α = q, B = S

∴ 跟随 (S) = { FOLLOW(A)} (5)

FOLLOW 的规则 (2a) 和规则 (3) 不能应用于生产 A → q 和 B → q。

结合语句(1)到(5)

FOLLOW(A)= {y, z}

FOLLOW(S)= {$, y, z}

FOLLOW(B)= {y}

Step4 - SLR (1) 解析表的构建