   Next: More examples of shift/reduce Up: CS2121: The Implementation and Previous: Left and Right recursion

Subsections

# More examples of Ambiguous and confusing grammars

Ambiguous and confusing grammars

## Ambiguous expressions

We looked at this grammar when I talked about making precedence and associativity explicit using `%left`, `%right` and `%nonassoc`: in 4.4

```  exp   : exp '+' exp | exp '-' exp | exp '*' exp | exp '/' exp
| number | '(' exp ')' | exp '^' exp  | exp '=' exp | '!' exp
;
```

Without the extra information about precedence and associativity provided by `%left` etc., there is no single parse for even something as simple as `1 + 2 * 3` - this could be recognised either as `( 1 + 2 ) * 3` or as `1 + ( 2 * 3 )`.

## A deliberately confusing example

```  A : B c d | E c f ;
B : x y ;
E : x y ;
```

For this grammar, an example input that starts `x y c` is enough to confuse an LR(1) parser, as it has to decide whether `x y` matches `B` or `E` after only seeing 1 symbol further (i.e. `c`).

An LL(1) parser would also be confused, but at the `x` - should it expand `A` to `B c d` or to `E c f`, as both can start with `x`. An LL(2) or LL(3) parser would have similar problems at the `y` or `c` respectively.

An LR(2) parser would be able to also see the `d` or `f` that followed the `c` and so make the correct choice between `B` and `E`.

An LL(4) parser would also be able to look far enough ahead to see the `d` or `f` that followed the `c` and so make the correct choice between expanding `A` to `B c d` or to `E c f`.

However, the following grammar would confuse any LR(n) or LL(n) parser with a fixed amount of look-ahead:

```  A : B C d | E C f ;
B : x y ;
E : x y ;
C : c | C c ;
```

As usual, the simplest solution is to rewrite the grammar to remove the confusion e.g.:

```  A    : BorE c d | BorE c f ;
BorE : x y ;
```
or assuming we left-factorise the grammar for an LL(n) parser:
```  A    : BorE c tail ;
tail : d | f ;
BorE : x y ;
```   Next: More examples of shift/reduce Up: CS2121: The Implementation and Previous: Left and Right recursion
Pete Jinks
2004-10-26