0 
S -> ABCD
A -> ae | af | ag | ah
B -> b | ε
C -> hcd | bcd | cd
D -> e | f | g | h

我已经在 2 和 4 上尝试过左因式分解，但在我|的许多作品中都被困住了。

4

1 回答 1

0

在这个语法中，有 96 种方法可以导出一串终结符。我们怀疑其中一些派生会产生冗余的终结符字符串，因此生成的语言中的字符串数量实际上少于 96 个。我们希望对其进行安排，以便一串终结符的每个派生产生一个不同的字符串。

我们可以列出所有 96 个派生，按派生字符串对它们进行排序，然后找出如何避免这种歧义。这将比我想要的时间长一点，我们可以通过分析智能地缩小重复字符串的搜索空间。

我们别无选择，只能使用产生式 S -> ABCD。接下来，我们必须准确地选择产生式 A -> ae、A -> af、A -> ag、A -> ah 之一。尽管如此，迄今为止的选择中不可能有歧义。接下来，我们必须选择 B -> b 或 B -> e。仍然没有歧义。正是在我们选择去除 C 的产生式时，我们才首次引入了歧义。问题是 cd 是 hcd 和 bcd 的后缀，当连接到另一个字符串时，可能会创建后缀 hcd 或 bcd 本身。考虑到这一点，我们发现以下重复推导：

S -> ABCD -> axBCD -> axbCD -> axbcdD -> axbcy
S -> ABCD -> axBCD -> axCD -> axbcD -> axbcy

上面，x 代表符号 e、f、g 或 h 之一；y 代表符号 e、f、g 或 h 之一。产生歧义是因为我们可以从 B -> b 或从 C -> bcd 得到 b。

在我们继续之前，我们应该重写语法以消除这种歧义的来源；在我们克服这一点之前，再往前走是没有意义的。我们如何解决这个问题？在这种情况下，考虑如果我们将符号 A 和 B 组合成一个新的符号 A'，语法会是什么样子。那么产品将是：

A' -> ae | af | ag | ah | aeb | aef | aeg | aeh

但是，我们会发现同样的问题依然存在；问题最初不是在 B 和 A 的产生之间，而是在 B 和 C 的产生之间。我们可以尝试：

B' -> hcd | bcd | cd | bhcd | bbcd

请注意，至关重要的是，我们在上面仅列出了 5 个项，而不是 6 个 - 因为一个产生式 B' -> bcd 通过组合这些相邻产生式生成了两次。当您看到这种情况发生时，这意味着您正在消除歧义。新语法看起来像：

S  -> ABCD
A  -> ae | af | ag | ah
B' -> cd | hcd | bcd | bhcd | bbcd
C  -> e | f | g | h

我们可以从头开始重复分析，在这里，发现以下内容：

  • 我们必须选择 S -> ABCD
  • 我们必须选择 A -> ae、A -> af、A -> ag、A -> ah 之一，并且没有选择会引入歧义
  • 我们必须为 B' 选择一个产生式，并且这些不会引入歧义，因为我们附加的所有前缀都具有相同的基本长度（2 个符号），并且这些前缀是明确派生的
  • 我们必须为 D 选择一个产生式，这些不会引入歧义，因为我们附加的所有前缀都只包含一个出现在最后的 d 实例，所以我们总是可以明确地知道产生式引入的符号在哪里B' 结束，D 的产生式引入的符号开始
于 2019-03-26T16:55:01.130 回答