Epsilon(ε)生产和LR(0)文法和LL(1)文法

Question

在许多地方(例如，在这个答案这里中)，我看到一个LR(0)语法不能包含ε生成。

在维基百科中，我也看到过这样的语句:ε免费LL(1)语法也是SLR(1)。

现在，我所面临的问题是，我无法推理出这些说法背后的逻辑。

我知道LR(0)语法通过空堆栈接受DPDA接受的语言，即它们接受的语言必须具有前缀属性。但是，如果我们假设结束标记，并且在给定任何语言时，前缀属性将始终得到满足，则可以处理该前缀属性。许多文本，如Sipser的“计算理论”()，都认为这是一个简单的论点。话虽如此，我们还是可以说(非正式的？)如果LR(0)项的规范集合中没有状态，则语法为LR(0)，这些项具有shift-还原冲突或约简冲突。

在这种背景下，我试图考虑以下语法：

S -> Aa
A -> ε

​

​

LR(0)项的规范集合

在上面的DFA中，我发现没有一个状态有转移-减少冲突或减少冲突。

根据我的分析，这个语法应该是LR(0)。但它也有ε的生产。

这个例子是否与以下说法相矛盾：

“没有任何具有ε生成的语法可以成为LR(0)”

我想，如果我知道上面引用的陈述背后的逻辑，那么我就能更好地理解这个概念。

实际上，我的主要问题来自以下声明：

ε免费LL(1)语法也是SLR(1)。

当我问我的一位朋友时，他提出了这样的论点:因为LL(1)语法是ε免费的，所以它是LR(0)，因此它是SLR(1)。

但我也不明白他的逻辑。当我问他关于推理的问题时，他开始分享关于“语法与ε产品永远不可能成为LR(0)”的帖子。

但就我个人而言，对于"ε免费LL(1)语法是SLR(1)“，我想不出任何逻辑。它真的与“ε产生的语法不能LR(0)”的上述性质有关吗？如果是的话，请帮帮我。若否，我应否考虑就第二项混淆问题另行提出质询？

我从Ullman的龙书中得到了我的编译器设计的概念。还有来自Ullman的TOC的知识，以及一些其他的文本，如Sipser，Linz。

Answer 1

语法的一个显著特点是A可以被删除。这完全没有用。(所谓“消除”，我的意思是删除对它的所有引用；保留原样的产品。)

确实，它的存在并不排除语法是LR(0)。类似地，具有不可到达的非终端的语法和该非终端的ε产生也可以是LR(0)。

因此，更准确的说法是，如果语法同时具有ε生产和其他生产性产品，那么语法就不能成为LR(0)。但由于我们通常只考虑简约语法，而没有无意义的非终端机，我不确定这种附加的学究是否有多大用处。

至于您关于ε免费LL(1)语法的问题，下面是一个粗略的大纲：

如果一个没有ε的语法不是LR(0)，那么就会有一个shift和reduce操作的状态。由于语法是无ε的，所以这种状态是通过移位或goto达到的。之前的状态必须有两个不同的结果，具有相同的第一组，这与LL(1)条件相矛盾。