Epsilon(ε)乘积与LR(0)文法和LL(1)文法 [英] Epsilon(ε) productions and LR(0) grammars and LL(1) grammars
问题描述
在很多地方(例如在这个答案中here)，我已经看到，LR(0)文法不能包含ε乘积。
我也在Wikipedia中看到过这样的语句：无ε的LL(1)文法也是SLR(1)。
现在我面临的问题是，我无法推理出这些陈述背后的逻辑。
我知道LR(0)文法通过空栈接受DPDA接受的语言，即它们接受的语言必须具有前缀属性。[然而，如果我们假定结束标记，则可以处理该前缀属性，并且在给定任何语言的情况下，应该始终满足前缀属性。许多文本，如Sipser的计算理论都假定这个结束标记是为了简单地说明他们的论点]。话虽如此，我们可以说(非正式地？)如果在具有移位-归约冲突或归约-归约冲突的LR(0)项的规范集合中没有状态，则语法是LR(0)。在这样的背景下，我试着考虑以下语法：
S -> Aa
A -> ε
LR(0)项的规范集合
在上面的DFA中，我发现没有任何状态具有移位-减少冲突或减少-减少冲突。
因此，根据我的分析，这个语法应该是LR(0)。但它也有ε生产。此示例是否与以下陈述相矛盾：
带有ε产生式的语法不能是LR(0)
我想，如果我知道上面引用的语句背后的逻辑，我就可以更好地理解这个概念。
实际上我的主要问题出现在以下语句中：
无ε的LL(1)文法也是SLR(1)。
当我问我的一个朋友时，他给出的论点是，由于LL(1)文法是无ε的，因此它是LR(0)，因此它是SLR(1)。
但我也不明白他的逻辑。当我问他关于推理的问题时，他开始分享关于语法和ε产品永远不可能是LR(0)的帖子...
但就我个人而言，我想不出任何逻辑来说明&ε自由LL(1)文法是什么。它是否真的与ε积不能为LR(0)&Quot；的&Quot；文法的上述属性有关？如果是的话，请一定要帮帮我。如果不是，那么我是否应该考虑为第二个混淆单独提出问题？我对编译器设计的概念只是从Ullman的《龙》一书中获得的。另外，从乌尔曼和西普瑟、林茨等少数几个文本中了解TOC。
推荐答案
语法的一个显著特点是A可以直接删除。它完全没有任何作用。(我所说的消除，是指简单地删除对它的所有引用；保持产品原封不动。)
因此，更准确地说，如果一个文法具有Productive非终结符和ε-Products和一些其他Productive结果，则它不可能是LR(0)。但由于我们通常只考虑简化的语法，而不考虑毫无意义的非终结符，我不确定这种额外的迂腐做法是否有多大作用。
关于您提出的关于无ε的LL(1)文法的问题，这里有一个粗略的概述：
如果无ε文法不是LR(0)，则存在同时具有移位和归约动作的状态。因为语法是无ε的，所以这种状态是通过Shift或GOTO来达到的。因此，前一个状态必须具有两个具有相同第一集的不同结果，这与LL(1)条件相冲突。
这篇关于Epsilon(ε)乘积与LR(0)文法和LL(1)文法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
