27 Apr 2003 16:46:04 -0400

Related articles |
---|

Grammars with semantics haberg@matematik.su.se (2003-04-20) |

Re: Grammars with semantics rda@lemma-one.com (Rob Arthan) (2003-04-27) |

Re: Grammars with semantics haberg@matematik.su.se (2003-04-27) |

Re: Grammars with semantics haberg@matematik.su.se (2003-05-06) |

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

Newsgroups: | comp.compilers |

Date: | 27 Apr 2003 16:46:04 -0400 |

Organization: | Mathematics |

References: | 03-04-067 03-04-100 |

Keywords: | parse |

Posted-Date: | 27 Apr 2003 16:46:03 EDT |

*>> 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):*

*>> So this grammar is ambiguous,*

*>No, it's not. Top-down and bottom-up parsing produce the same parse-trees,*

*>but they construct the nodes in different orders.*

I forgot to think about the parse trees. How silly! :-)

Thank you for pointing this out to me.

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.