parsing - SLR(1) 或 LR(1) 解析

Question

我们找到 follow(A) 以防我们找到类型的产生式

A → α

这里的 α 可以是 ε 吗？

就像在下面的例子中：

P → aPa | 铅 ε

如果 α 可以是 ε，则它不是 LR(1)

Answer 1

是的，α 可以是 ε。α 表示任意字符串，并且由于 ε 是字符串，因此它是可能的 α

因此，您的语法不是 LR(1)，因此也不是 SLR(1)（因为所有 SLR(1) 语法也是 LR(1)）。

为了看到这一点，我们可以构造 LR(1) 配置集：

(1)  P' -> .P     ($)
     P  -> .aPa   ($)
     P  -> .bPb   ($)
     P  -> .      ($)

(2)  P  -> a.Pa   ($)
     P  -> .aPa   (a)
     P  -> .bPb   (a)
     P  -> .      (a)

在这一点上我们可以停下来，因为有一个移位/减少冲突：我们无法判断是移位a还是减少给定终端的 P → ε a。

通过一些更高级的数学，您可以证明这种语言（所有偶数长度回文的语言）没有LR(1) 语法。这是因为具有 LR(1) 语法的语言正是确定性上下文无关语言，所有偶数长度回文的集合不是确定性上下文无关语言。

希望这可以帮助！