20 Apr 2003 17:38:04 -0400

Related articles |
---|

top-down and bottom-up rjdepauw@xs4all.nl (Rob) (2003-04-13) |

Re: top-down and bottom-up joachim_d@gmx.de (Joachim Durchholz) (2003-04-15) |

Re: top-down and bottom-up haberg@matematik.su.se (2003-04-20) |

Re: top-down and bottom-up JeffKenton@attbi.com (Jeff Kenton) (2003-04-20) |

Re: top-down and bottom-up thp@cs.ucr.edu (2003-05-06) |

From: | haberg@matematik.su.se (Hans Aberg) |

Newsgroups: | comp.compilers |

Date: | 20 Apr 2003 17:38:04 -0400 |

Organization: | Mathematics |

References: | 03-04-039 03-04-048 |

Keywords: | parse, practice |

Posted-Date: | 20 Apr 2003 17:38:04 EDT |

Rob wrote:

*> I would like to know if a parse tree created by a top-down parser*

*> differs from a parse tree created by a bottom-up parser given that the*

*> grammar is the same.*

Some grammars can be ambiguous, even though they become unambiguous when

imposing the condition of using the leftmost derivation (as in LL,

top-down parsing) or rightmost derivation (as in LR, bottom-up, parsing).

Take the "calculator" grammar G = (T, N, P, E), terminals T = {i, `+',

`*', `(', `)'}, nonterminals N = {E, T, F}, sentence symbol E, and the

set of productions P containing:

P_1: E -> T

P_2: E -> E `+' T

P_3: T -> F

P_4: T -> T `*' F

P_5: F -> i

P_6: F -> `(' F `)'

The expression i + i*i has several parses, for example the leftmost (as in

LL, top-down, parsing) and rightmost (as in LR, bottom-up parsing):

E E

-> E + T -> E + T

-> T + T -> E + T * F

-> F + T -> E + T * i

-> i + T -> E + F * i

-> i + T * F -> E + i * i

-> i + F * F -> T + i * i

-> i + i * F -> F + i * i

-> i + i * i -> i + i * i

So this grammar is ambiguous, even though when imposing the condition that

the rightmost or leftmost derivation should be used, the ambiguity

disappears: So LL parsers (if removing left recursion) and LR parsers

would not complain. (Strictly speaking, LL parsers cannot generally handle

left recursion, so then one may have to rewrite the grammar. So for the

example above to work, one has to pretend there is a push-down autamaton

that can produce the leftmost derivation.)

The example above also has a mixed derivation (neither leftmost nor

rightmost). I got from the book by Waite & Goos, "Compiler Construction",

p. 107.

Hans Aberg * Anti-spam: remove "remove." from email address.

* Email: Hans Aberg <remove.haberg@member.ams.org>

* Home Page: <http://www.math.su.se/~haberg/>

* AMS member listing: <http://www.ams.org/cml/>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.