Re: top-down and bottom-up

thp@cs.ucr.edu
6 May 2003 01:05:29 -0400

          From comp.compilers

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)
| List of all articles for this month |

From: thp@cs.ucr.edu
Newsgroups: comp.compilers
Date: 6 May 2003 01:05:29 -0400
Organization: University of California, Riverside
References: 03-04-039 03-04-048 03-04-068
Keywords: parse
Posted-Date: 06 May 2003 01:05:29 EDT

Hans Aberg <haberg@matematik.su.se> wrote:
[...]
+ So this grammar is ambiguous, even though when imposing the condition that
+ the rightmost or leftmost derivation should be used, the ambiguity
+ disappears:


AFAIK, a grammar is *ambiguous* iff some string has multiple syntax
trees. Every syntax tree has its own unique left-most derivation and
its own unique right-most derivation.


LL-grammars and LR-grammars are unambiguous, but many parser
generators (e.g., YACC) provide mechanism that use supplementary
disambiguation advice (e.g., precedence and associativity of rules)
over and above the grammar. Such mechanisms allow the use of much
more compact and intuitive grammars ambiguous grammars, whose syntax
trees are closer to abstract syntax trees.


Tom Payne


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.