parsing - 如何判断一个文法是LL(1)、LR(0)还是SLR(1)？

Question

如何识别文法是 LL(1)、LR(0) 还是 SLR(1)？

任何人都可以使用这个示例或任何其他示例来解释它吗？

X → Yz | a

Y → bZ | ε

Z → ε

Answer 1

要检查语法是否为 LL(1)，一种选择是构造 LL(1) 解析表并检查是否有任何冲突。这些冲突可能是

• FIRST/FIRST 冲突，其中必须为非终结符/终结符对预测两个不同的产生式。
• FIRST/FOLLOW 冲突，其中预测了两种不同的产生式，一种表示应采用某些产生式并将其扩展为非零数量的符号，另一种表示应使用一种产生式来表明应最终扩展某些非终结符输出为空字符串。
• FOLLOW/FOLLOW 冲突，其中指示非终结符最终应扩展为空字符串的两个产生式相互冲突。

让我们通过为每个非终结符构建 FIRST 和 FOLLOW 集来尝试一下您的语法。在这里，我们明白了

FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon} 

我们还知道 FOLLOW 集是

FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}

据此，我们可以构建如下的LL(1)解析表:

    a    b    z   $
X   a    Yz   Yz  
Y        bZ   eps
Z             eps

由于我们可以构建没有冲突的解析表，因此语法为 LL(1)。

为了检查语法是 LR(0) 还是 SLR(1)，我们首先为该语法构建所有 LR(0) 配置集。在这种情况下，假设 X 是您的起始符号，我们得到以下结果:

(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ

(2)
X' -> X.

(3)
X -> Y.z

(4)
X -> Yz.

(5)
X -> a.

(6)
Y -> b.Z
Z -> .

(7)
Y -> bZ.

由此可见，该文法不是LR(0)，因为状态(1)存在移位/归约冲突。具体来说，因为我们有移位项 X → .a 和 Y → .，所以我们无法判断是移动 a 还是减少空字符串。更一般地说，没有 ε-产生式的文法是 LR(0)。

但是，这个文法可能是SLR(1)。为了看到这一点，我们使用特定非终结符的前瞻集来增强每次归约。这返回了这组 SLR(1) 配置集:

(1)
X' -> .X
X -> .Yz [$]
X -> .a  [$]
Y -> .   [z]
Y -> .bZ [z]

(2)
X' -> X.

(3)
X -> Y.z [$]

(4)
X -> Yz. [$]

(5)
X -> a.  [$]

(6)
Y -> b.Z [z]
Z -> .   [z]

(7)
Y -> bZ. [z]

状态 (1) 中的移位/归约冲突已被消除，因为我们仅在前瞻为 z 时进行归约，这不会与任何其他项冲突。