CFG 解析树 - 最右推导

Question

因此我们有一个活动，我们必须根据给定的语法生成解析。

我们还被问到语法将生成以下给定字符串中的哪一个。

我能够生成

abcd

但在问题 2 中，它说要重新生成问题 1 中的字符串，但使用最右推导。 但只有 2 次扩展，据我所知，最右/最左推导是解析树的哪一侧扩展更多。

所以我尝试延长我的解析树，但现在的问题是我无法生成任何给定的字符串来生成。

我是否遗漏了什么，或者我有什么错误？

Answer 1

推导以起始符号（在本例中为

<S>

）开始，以推导句子（

abcd

）结束。推导中的每个步骤都包括用其可能的产生式之一替换一些非终结符。如果推导的结果仍然包含至少一个非终结符，则该结果被称为“句子形式”；否则为派生句，派生结束。

在推导的第一步之后（如解析树所示），您就得到了句子形式

a <S> c <B>

下一个推导步骤要么需要使用其产生式之一替换

<S>

，要么用其产生式之一替换

<B>

。 （两种可能性都会导致相同的解析树，因为这是上下文无关语法，因此推导的顺序并不重要。）如果我们选择使用产生式

<S>

来扩展

<S>→b

，则推导的结果步骤将是句子形式

a b c <B>

在最右边的推导中，为每个推导步骤选择的非终结符是句子形式中最右边的非终结符。在最左推导中，它是最左边的非终结符。如果句子形式中只有一个非终结符，那么无论如何都会选择它，因为它既是最左也是最右。

这与解析树的倾斜方式无关。不管怎样，都会生成相同的解析树。 （或者相同的解析树，如果语法不明确。）

您不必按照最左或最右的顺序进行推导，除非您的试卷要求这样做。如果您始终使用中间非终结符，那么您仍然会得到相同的解析，以获得“中间”的明确定义。或者，如果您只是选择一个随机的非终结符并将其扩展。但据我所知，没有人发现有必要谈论中间派生。

Answer 2

正如@rici所说，但换句话说1“任何推导都有一个等价的最左推导和一个等价的最右推导。”

此外，@rici 写道

这与解析树的倾斜方式无关。不管怎样，都会生成相同的解析树。 （或者相同的解析树，如果语法不明确。）

有趣的是，你的语法不明确，正如字符串 acccc 所示：

：Hopcroft 等人。自动机理论、语言和计算简介，Addison-Wesley，第三版。