lambda 产生式、一元规则和无用语法符号的简化

Question

我知道这不是一个普遍的问题，但我想知道如何用一个我已经研究过的例子来做。曾经说过：

我有以下语法。我试图简化它但我不确定它的正确性，有人可以帮我确认它是否正确吗？

S -> BC | lambda
A -> aA | lambda
B -> bB
C -> c

如果我必须简化语法，我首先应用 lambda-eliminations，我有类似的东西：

S -> BC | B | C
A -> aA | a
B -> bB
C -> c

最后我必须删除无用的符号： 首先，我删除了那些没有效率的，然后是那些无法访问的，所以..

S -> BC | bB | C
A -> aA | a
B -> bB  ---> non-productive
C -> c

S -> C | b | C
A -> aA | a --> unreacheable
C -> c

最后我有这样的东西，我消除了 C，因为它是不必要的，我也消除了 BC，因为被消除了，所以应该是这样的： S -> b | c

但老实说，我不认为我所做的是正确的，但我也不清楚

Answer 1

看来您的简化可能存在一些问题 - 或者我无法理解它。我将逐步介绍我会做什么，然后您将其与您的理解进行比较。

S -> BC | lambda
A -> aA | lambda
B -> bB
C -> c

我认为目标是消除尽可能多的 lambda 和非终端符号。首先要注意的是，产生式S -> lambda在不改变语言的情况下是无法消除的；但所有其他 lambda 作品都可以消除。我们看到了另一部作品，所以我们确信它可以被淘汰。我们如何消除A -> lambda？

我们注意到 A 无法从起始符号 S 到达。所以我们可以很容易地通过完全消除 A 来消除 A -> lambda 。我们得出这个更简单、等价的语法：

S -> BC | lambda
B -> bB
C -> c

现在，由于我们的目标是消除非终结符号（我们已经消除了所有无关的 -> lambda 产生式），我们可以查看 S、B 和 C.我们知道我们需要一个开始符号，所以我们不妨保持 S 不变。 B只能生成包含非终结符的bB；并且 bB 永远不会导致只有非终端的字符串。 B 没有生产力，我们可以消除它。当我们消除一个非生产性符号时，它出现的任何连接项也必须被消除，因为连接表达式永远不会到达只有非终端的字符串（任何出现非生产性符号的连接表达式也是非生产性的）：

S -> lambda
C -> c

将我们的分析应用于 C，我们很容易看出它与 A 最初一样无法访问，因此可以用相同的方式消除它：

S -> lambda

此语法用最简单的术语表达，并且在非终结符号和语言产生式方面最少 {lambda}。