Epsilon(ε)乘积与LR(0)文法和LL(1)文法 [英] Epsilon(ε) productions and LR(0) grammars and LL(1) grammars

查看:4
本文介绍了Epsilon(ε)乘积与LR(0)文法和LL(1)文法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

在很多地方(例如在这个答案中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可以直接删除。它完全没有任何作用。(我所说的消除,是指简单地删除对它的所有引用;保持产品原封不动。)

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

因此,更准确地说,如果一个文法具有Productive非终结符和ε-Products和一些其他Productive结果,则它不可能是LR(0)。但由于我们通常只考虑简化的语法,而不考虑毫无意义的非终结符,我不确定这种额外的迂腐做法是否有多大作用。


关于您提出的关于无ε的LL(1)文法的问题,这里有一个粗略的概述:

如果无ε文法不是LR(0),则存在同时具有移位和归约动作的状态。因为语法是无ε的,所以这种状态是通过Shift或GOTO来达到的。因此,前一个状态必须具有两个具有相同第一集的不同结果,这与LL(1)条件相冲突。

这篇关于Epsilon(ε)乘积与LR(0)文法和LL(1)文法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆