删除左递归会引入歧义吗？

Question

假设我们有以下 CFG G：

A -> A b A
A -> a

哪个应该产生字符串 a、aba、ababa、abababa 等。现在我想删除左递归以使其 suitable 用于预测解析。龙书给出了如下规则去除立即左递归。鉴于

A -> Aa | b

重写为

A  -> b A'
A' -> a A'
    | ε

如果我们简单地将规则应用于上面的文法，我们得到文法 G':

A  -> a A'
A' -> b A A'
    | ε

这对我来说看起来不错，但显然这个语法不是 LL(1)，因为有些歧义。我得到以下 First/Follow 组：

First(A) = { "a" }
First(A') = { ε, "b" }
Follow(A) = { $, "b" }
Follow(A') = { $, "b" }

我从中构建解析 table

    |   a          |   b            |  $           |
----------------------------------------------------
A   | A -> a A'    |                |              |
A'  |              | A' -> b A A'   | A' -> ε      |
    |              | A' -> ε        |              |

并且 T[A',b] 中存在冲突，因此文法不是 LL(1)，尽管不再有左递归并且也没有产生式的公共前缀，因此它会需要左分解。

我不完全确定歧义从何而来。我猜想在解析过程中堆栈会填满 S'。如果不再需要它，您基本上可以将其删除（减少到 epsilon）。我认为如果另一个 S' 在堆栈下方，就会出现这种情况。

我认为我试图从原始语法中得到的 LL(1) 语法 G'' 是：

A  -> a A'
A' -> b A
    | ε

我错过了什么吗？我做错了什么吗？

是否有更通用的程序来删除考虑这种边缘情况的左递归？如果我想自动删除左递归，我应该能够处理这个，对吗？

第二个文法 G' 是某个 k > 1 的 LL(k) 文法吗？

Answer 1

原来的语法有歧义，所以新语法也有歧义也就不足为奇了。

考虑字符串 a b a b a。我们可以从原始语法中通过两种方式得出这一点：

A ⇒ A b A
  ⇒ A b a
  ⇒ A b A b a
  ⇒ A b a b a
  ⇒ a b a b a

A ⇒ A b A
  ⇒ A b A b A
  ⇒ A b A b a
  ⇒ A b a b a
  ⇒ a b a b a

明确的语法当然是可能的。以下是右递归和左递归版本：

A ⇒ a              A ⇒ a
A ⇒ a b A          A ⇒ A b a

（尽管它们表示相同的语言，但它们具有不同的解析：右递归版本关联到右侧，而左递归版本关联到左侧。）

Answer 2

移除左递归不会引入歧义。这种转换保留了歧义。如果CFG已经不明确，结果也将不明确，如果原来不是，结果也不是。

删除左递归会引入歧义吗？

can removing left recursion introduce ambiguity?

parsing

compiler-construction

context-free-grammar

ll