grammar - 将歧义语法转换为明确的语法

Question

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

谁能指导我？

Answer 1

该示例有两个语法:

模糊的:

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

明确:

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

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

运算符“*”比运算符“+”绑定(bind)得更紧密。

运算符 '*' 和 '+' 都是左结合的。

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

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

a * a + b * b

被分组，好像写成:

(a * a) + (b * b)

而不是:

a * ((a + b) * b)

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

评论

How would associativity come into the picture for examples like:

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

This is an ambiguous grammar, so how to go about converting it to unambiguous?

我想知道'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' 中的 '+')。