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

Question

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

A → α

这里的 α 可以是 ε 吗？

就像下面的例子:

P → aPa | bPb | ε

如果α可以是ε，它就不是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)文法的语言恰恰是确定性上下文无关语言，而所有偶数长度回文的集合不是确定性上下文无关语言。

希望这对您有所帮助!