Converting ambiguous grammar to unambiguous

Question

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.

Can anyone please guide me ?

Answer 1

The example has two grammars:

Ambiguous:

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:

• The operator '*' binds tighter than the operator '+'.
• Both the operators '*' and '+' are left associative.

Without the external information, there is no way to make the transformation.

With the external information, we can tell that:

a * a + b * b 

is grouped as if written:

(a * a) + (b * b) 

rather than as:

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.

---

Comment

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?

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

ε is the empty string

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.

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.

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.

ε is not the empty string

What about if ε is not the empty string?

• 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).

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.

Associativity

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

Answer 2

From Wikipedia (on Recognizing ambiguous grammars):

Some ambiguous grammars can be converted into unambiguous grammars, but no general procedure for doing this is possible just as no algorithm exists for detecting ambiguous grammars.

In order to come up with the second grammar, you have to find a grammar that is

1. Equivalent to the first one: Both generate the same language
2. Unambiguous: For every sentence of the language, the parse tree is unique