Re: Parse tree problem
- From: Rick Decker <rdecker@xxxxxxxxxxxx>
- Date: Sun, 22 Oct 2006 14:33:16 -0400
anandr86@xxxxxxxxx wrote:
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)
Derivation 1:
E -> E + E -> E + E * E -> E + E * id -> E + id * id -> id + id * id
Derivation 2:
E -> E * E -> E * id -> E + E * id -> E + id * id -> id + id * id
The parse trees for these derivations are different. The first yields
what we would write id + (id * id) while the second is what we would
write (id + id) * id. We say that this grammar is ambiguous, and hence
would be unsuitable for use in a shift-reduce parser.
If you've gotten to the stage where you can make a shift-reduce parser
you might try making one for this grammar and see where it fails.
Regards,
Rick
.
- References:
- Parse tree problem
- From: anandr86
- Parse tree problem
- Prev by Date: Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
- Next by Date: Re: how to prove: let L be any subset of 0*. is L regular?
- Previous by thread: Parse tree problem
- Next by thread: Top down parsing
- Index(es):
Relevant Pages
|
