将歧义语法转换为歧义 [英] Converting ambiguous grammar to unambiguous

问题描述

我不明白模棱两可的语法是如何派生出来的？考虑网站上的示例：示例。语法的衍生方式使我感到困惑。

I did not understand how a unambiguous grammar is derived from a ambiguous grammar? Consider the example on site: Example. How was the grammar derived is confusing to me.

有人可以引导我吗？

推荐答案

该示例有两个语法：

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

明确：

Unambiguous:

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

模棱两可的语法是使用模棱两可的语法中未指定的信息从模棱两可的语法中得出的：

The unambiguous grammar was derived from the ambiguous one using information not specified in the ambiguous grammar:

• 运算符'*'与运算符'+'的绑定更紧密。


• 两个运算符'*

有了外部信息，我们可以知道：

With the external information, we can tell that:

a * a + b * b

被分组，就像写成这样：

is grouped as if written:

(a * a) + (b * b)

而不是：

a * ((a + b) * b)

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

The second assumes that '+' binds tighter than '*', and that the operators bind from right to left rather than left to right.

如何关联进入例如：

How would associativity come into the picture for examples like:

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

这是一个模棱两可的语法，因此如何进行转换

我想知道'epsilon'是否为ε，即空字符串；让我们用两种方式来分析语法。

I wonder if the 'epsilon' is ε, the empty string; let's analyze the grammar both ways.

B的规则说B是一个空字符串或一个a，后跟一个有效的B，该字符串等于一个无限长的字符串，包含0个或多个a。

The rule for B says a B is either an empty string or an a followed by a valid B, which amounts to an indefinitely long string of 0 or more a's.

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

The rule for A says an A is either an a or a B followed by an a. So, an indefinitely long string of a's could be an A too. So, there is no way for the grammar to choose whether a string of a's is either an A or B.

S的规则没有帮助； S可以是a，后跟一个无限长的a字符串，或者是一个无限长的a后跟a的字符串。它至少需要一个a，但是从一个向上的任意多个a都可以，但是语法没有基础来决定左右两个替代项。

And the rule for S is no help; an S is either an a followed by an indefinitely long string of a's or an indefinitely long string of a's followed by an a. It requires at least one a, but any number of a's from one upwards is OK, but the grammar has no basis to decide between the left and right alternatives.

这种语法本质上是模棱两可的，而且据我估计，不可能是模棱两可的；

So, this grammar is inherently ambiguous and cannot, in my estimation, be made unambiguous; it certainly cannot be made unambiguous without other information not in our possession.

如果ε不是空字符串怎么办？

What about if ε is not the empty string?

• B是ε还是aε。


• A是a或B，后跟a（因此是a或aε或aaε）。


• 或者：S是a，后跟A（因此aa ，aaε或aaaε）


• 或：S是一个B，然后是a（因此是εa或aεa）。

• B is either ε or an aε.
• A is either an a or a B followed by an a (so either an a or an aε or an aaε).
• Either: S is an a followed by an A (hence aa, aaε, or aaaε)
• Or: S is a B followed by an a (hence εa or aεa).

在这种情况下，语法就目前而言是明确的（尽管不一定是LR（1））。显然，很多地方取决于评论/问题中 epsilon的含义。

In this case, the grammar is unambiguous as it stands (though not necessarily LR(1)). Clearly, a lot hinges on the meaning of 'epsilon' in the comment/question.

I不要以为联想会影响这种语法。它通常与中缀运算符（例如 a + b中的 +）一起使用。

I don't think associativity affects this grammar. It generally comes into play with infix operators (such as the '+' in 'a + b').

这篇关于将歧义语法转换为歧义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！