Consider the following grammar and language again.
S → 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.
