context-free-grammar - 上下文无关语法：当 lambda 离开递归时，如何终止非终端中的 lambda？

Question

我有这个上下文无关的语法，我正在尝试删除非终端 B 中的 lambda。如果没有它在 B 中递归地有一个 lambda，我该如何解决这个问题？

S -> B
A -> λ | aAb
B -> BB | λ | C
C -> A | aCc

Answer 1

在 λ 消除过程中，可能会将相同的产生式添加到一个产生式的集合中两次或更多次。由于它是一个集合，它最多只能有一个元素，所以添加一个已经存在的元素什么都不做。右手边是空的这一事实并没有改变。

因此，为了 λ-eliminate B，我们需要找到所有实例B并添加新的产生式并删除该使用。的唯一用途B是本身S，B所以我们继续添加产生式：

• S → λ
• B → B（通过删除 B → BB 中的第一个 B）；
• B → B（通过删除 B → BB 中的第二个 B）；
• B → λ（通过从我们刚刚添加的产生式 B → B 中删除 B。）

但是，B 的任何新作品实际上都没有添加到集合中。递归单位产生式 (B → B) 被简单地删除，并且 B → λ 已经存在。

如果我们为起始符号以外的符号添加新的 λ 产生式，我们需要将该符号标记为需要 λ 消除（或递归调用消除过程）。但这不会在这里发生，因为添加的产品已经存在。

一旦我们完成了 λ 消除，我们将删除除开始符号之外的所有 λ 产生式。

在实践中，有一些优化是可能的，但这样算法可能更清晰。