| Author |
Doubt with parse tree
|
|
| anandr86@gmail.com 2006-10-30, 7:32 pm |
| Hi,
I was recently going through "Principles of Compiler design, Aho
and Ullman". In that it was specified that one particular grammar the
one below had two right most derivations for a single input. How is
that possible ? RMD is expanding using the right most nonterminal right
......
E -> E + E
E -> E * E
E -> (E)
E -> id
and the input is id + id * id
( The above is cited in the context of shift-reduce parsers in the book
)
| |
| Wolfram Fenske 2006-10-30, 7:32 pm |
| anandr86@gmail.com writes:
[...]
> In that it was specified that one particular grammar the one below
> had two right most derivations for a single input. How is that
> possible ? RMD is expanding using the right most nonterminal right
> .....
>
> E -> E + E
> E -> E * E
> E -> (E)
> E -> id
>
> and the input is id + id * id
Easy, you can start with either E -> E + E or E -> E * E.
Wolfram
| |
| Hans-Peter Diettrich 2006-10-30, 7:32 pm |
| anandr86@gmail.com wrote:
> E -> E + E
> E -> E * E
> E -> (E)
> E -> id
>
> and the input is id + id * id
We just had such a discussion, the grammar is ambiguous. The + and *
operators have no specific priority and grouping.
Perhaps this example was given to demonstrate the need for more detailed
grammars?
DoDi
|
|
|
|