Separate Rule

Consider the following grammar and language again.

  IF b THEN S ELSE S
               |    IF b THEN S
               |    a

An ambiguity can be removed if we arbitrary decide that an ELSE should be attached to the last preceding THEN, like:

Figure

 

We can revise the grammar to have two nonterminals S1 and S2. We insist that S2 generates IF-THEN-ELSE, while S1 is free to generate either kind of statements.

The rules of the new grammar are:

S1     IF b THEN S1
         |      IF b THEN S2 THEN S1
         |     a
S2  IF b THEN S2 ELSE S2
         |     a

Although there is no general algorithm that can be used to determine if a given grammar is ambiguous, it is certainly possible to isolate rules which leads to ambiguity or ambiguous grammar.

A grammar containing the productions.

A AA | Alpha

is ambiguous because the substring AAA has different parse tree.

Figure

This ambiguity disappears if we use the productions

A AB | B
B α

or

A BA | B
B α

Syntax of Expressions
   
A grammar of arithmetic expressions looks like:

Expr   expr + term | expr - term | term
term   term * factor | term/factor | factor
factor id | num | (expr)

That is, expr is a string of terms separated by '+' and '-'.
A term is a string of factors separated by '*' and '/' and a factor is a single operand or an expression wrapped inside of parenthesis.