27

我不明白一个明确的语法是如何从一个不明确的语法推导出来的？考虑现场示例：Example。语法是如何派生的让我感到困惑。

谁能指导我？

4

2 回答 2

53

该示例有两个语法：

模糊的：

E → E + E | E ∗ E | (E) | a

明确：

E → E + T | T
T → T ∗ F | F
F → (E) | a

无歧义语法是使用歧义语法中未指定的信息从歧义语法导出的：

  • 运算符“*”比运算符“+”绑定得更紧密。
  • 运算符 '*' 和 '+' 都是左结合的。

没有外部信息，就无法进行转换。

通过外部信息，我们可以看出：

a * a + b * b

被分组，好像写成：

(a * a) + (b * b)

而不是：

a * ((a + b) * b)

第二个假设 '+' 比 '*' 绑定更紧密，并且运算符从右到左而不是从左到右绑定。

评论

例如，关联性如何出现在图片中，例如：

    S → aA | Ba
    A → BA | a
    B → aB | epsilon

这是一个模棱两可的语法，那么如何将其转换为明确的呢？

我想知道'epsilon'是否是空字符串ε；让我们从两个方面分析语法。

ε 是空字符串

B 的规则说一个 B 要么是一个空字符串，要么是一个后跟一个有效 B 的 a，这相当于一个由 0 个或多个 a 组成的无限长字符串。

A 的规则说 A 是一个 a 或一个 B 后跟一个 a。因此，无限长的 a 字符串也可能是 A。因此，语法无法选择 a 的字符串是 A 还是 B。

S 的规则是没有帮助的；一个 S 要么是一个 a 后跟一个无限长的 a 字符串，要么是一个无限长的 a 后跟一个 a 的字符串。它至少需要一个 a，但是从一个以上的任意数量的 a 都可以，但是语法没有根据来决定左右选择。

所以，这个语法本质上是模棱两可的，据我估计，不能明确；如果没有我们不掌握的其他信息，它当然不能明确。

ε 不是空字符串

如果 ε 不是空字符串呢？

  • B是ε或aε。
  • A 是一个 a 或一个 B，后跟一个 a（所以要么是 a，要么是 aε，要么是 aaε）。
  • 任一个：S 是一个 a，后跟一个 A（因此是 aa、aaε 或 aaaε）
  • 或者：S 是一个 B，后跟一个 a（因此是 εa 或 aεa）。

在这种情况下，语法是明确的（尽管不一定是 LR(1)）。显然，很大程度上取决于评论/问题中“epsilon”的含义。

关联性

我认为关联性不会影响这种语法。它通常与中缀运算符一起使用（例如 'a + b' 中的 '+'）。

于 2010-06-23T23:28:21.903 回答
11

来自维基百科（关于识别歧义语法）：

一些模棱两可的文法可以转换为明确的文法，但是没有通用的过程可以做到这一点，就像不存在用于检测模棱两可的文法的算法一样。

为了想出第二个语法，你必须找到一个语法是

  1. 相当于第一个：两者都生成相同的语言
  2. 明确：对于语言的每个句子，解析树都是唯一的
于 2010-06-23T23:35:18.257 回答