4

嗨，书中有一个问题说

鉴于这个语法

A --> AA | (A) | epsilon

a- 它产生什么\

b- 表明这是模棱两可的

现在我想到的答案是

a- 邻接括号

b-它生成不同的解析树，所以它模棱两可，我做了一个画图，显示了两个场景。

这是正确的还是有更好的答案？

4

4 回答 4

2

a几乎是正确的。
语法确实生成(), ()(), ()()(), ... 序列。
但是由于第二条规则，它可以生成(()),()((()))等。

b是不正确的。
由于立即左递归，此文法不明确：A → AA.

如何避免左递归：一，二。

于 2010-12-19T20:20:40.310 回答
1

a) 几乎正确...

该文法准确地生成由平衡括号组成的字符串集。要了解为什么会这样，让我们​​尝试快速演示一下。

第一：语法之外的所有内容都是平衡的括号字符串。为什么？，简单的归纳：

  • Epsilon 是一个平衡（空）括号字符串。
  • 如果 A 是平衡括号字符串，则 (A) 也是平衡的。
  • 如果 A1 和 A2 是平衡的，那么 A1A2 也是平衡的（我使用了太多不同的标识符只是为了明确表明 A -> AA 不必为每个 A 产生相同的事实）。

第二：每组平衡的字符串都是由你的语法产生的。让我们通过对字符串大小的归纳来做到这一点。

  • 如果字符串大小为零，则它必须是 Epsilon。
  • 如果不是，则 N 是字符串的大小，M 是平衡的最短前缀的长度（请注意，字符串的其余部分也是平衡的）：
    • 如果 M = N，那么您可以使用 (A) 生成该字符串。
    • 如果 M < N，您可以使用 A -> AA 生成它，前 M 个字符使用第一个 A，最后一个 N - M 使用最后一个 A。在任何一种情况下，您都必须生成一个短于 N 个字符的字符串，因此通过感应你可以做到。QED。

例如： （（）（））（（））

我们可以完全使用演示的想法来生成这个字符串。

A -> AA -> (A)A -> (AA)A -> ((A)(A))A -> (()())A -> (()())(A) -> ( ()())((A)) -> (()())(())

b）当然左右递归足以说它是模棱两可的，但是要了解为什么特别是这个语法是模棱两可的，请按照相同的想法进行演示：

这是模棱两可的，因为您不需要采用最短的平衡前缀。您可以采用不是字符串大小的最长平衡（或通常任何平衡前缀），并且演示（和生成）将遵循相同的过程。

前任： （（））（）（）

您可以选择 A -> AA 并使用第一个 A 生成 (()) 子字符串或 (())() 子字符串。

于 2012-05-02T16:13:45.203 回答
0

是的你是对的。

这就是模棱两可的语法的意思。

歧义语法的问题在于，如果您正在编写一个编译器，并且您想在某些代码行（或类似的代码）中识别每个标记，那么歧义会干扰您的识别，因为您将对此有“两个解释”行代码。

于 2010-12-19T20:21:50.800 回答
0

听起来您对 B 部分的方法是正确的，显示了语法定义的语言中同一字符串的两个独立派生。

但是，我认为您对 A 部分的回答需要做一些工作。显然，您可以递归地使用第二个子句来获得类似 (((((epsilon))))) 的字符串，但是同时使用第一个子句和第二个子句还有其他类型的推导。

于 2010-12-19T20:26:17.810 回答