删除左递归会引入歧义吗?
can removing left recursion introduce ambiguity?
假设我们有以下 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) 文法吗?
原来的语法有歧义,所以新语法也有歧义也就不足为奇了。
考虑字符串 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
(尽管它们表示相同的语言,但它们具有不同的解析:右递归版本关联到右侧,而左递归版本关联到左侧。)
移除左递归不会引入歧义。这种转换保留了歧义。如果CFG已经不明确,结果也将不明确,如果原来不是,结果也不是。
假设我们有以下 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) 文法吗?
原来的语法有歧义,所以新语法也有歧义也就不足为奇了。
考虑字符串 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
(尽管它们表示相同的语言,但它们具有不同的解析:右递归版本关联到右侧,而左递归版本关联到左侧。)
移除左递归不会引入歧义。这种转换保留了歧义。如果CFG已经不明确,结果也将不明确,如果原来不是,结果也不是。