Re: Simple Expression Recursion vs Expression/Term/Factor

Douglas Gregor <gregod@cs.rpi.edu>
6 Aug 2001 04:06:53 -0400

          From comp.compilers

Related articles
Simple Expression Recursion vs Expression/Term/Factor stoggers@uniquest.demon.co.uk (Mike Stogden) (2001-08-02)
Re: Simple Expression Recursion vs Expression/Term/Factor Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2001-08-06)
Re: Simple Expression Recursion vs Expression/Term/Factor lucadesantis@infinito.it (luca) (2001-08-06)
Re: Simple Expression Recursion vs Expression/Term/Factor gregod@cs.rpi.edu (Douglas Gregor) (2001-08-06)
Re: Simple Expression Recursion vs Expression/Term/Factor joachim_d@gmx.de (Joachim Durchholz) (2001-08-08)
Re: Simple Expression Recursion vs Expression/Term/Factor lucads@xoommail.xoom.it (Luca) (2001-08-08)
Re: Simple Expression Recursion vs Expression/Term/Factor andi@diagonal.ch (Andreas Gieriet) (2001-08-15)
| List of all articles for this month |

From: Douglas Gregor <gregod@cs.rpi.edu>
Newsgroups: comp.compilers
Date: 6 Aug 2001 04:06:53 -0400
Organization: RPI
References: 01-08-016
Keywords: parse
Posted-Date: 06 Aug 2001 04:06:53 EDT

Mike Stogden wrote:


> Hi,
>
> Please could someone offer an explanation as to the relative merits of
> describing expressions as productions based on two comparable
> specifications?
>
> I have seen expressions for the same language described as...
>
> expr -> expr + expr
> expr -> expr * expr
> etc...
>
> alternatively...
>
> expr -> expr + term
> term -> factor | term * factor
> factor -> number | identifier
> etc...
>
> Just by working through these rules by hand I suspect that they pass the
> same language constructs - so what are the relative merits of each
> approach?
>
> Regards,
>
> Mike Stogden.
> [They both define the same language, but the first form has many parses
> for any input string while the second defines a unique parse for each
> input. -John]


The first one is ambiguous and would require other methods of
disambiguation (i.e., precedence and associativity must be taken into
account). For instance, think about how this expression is parsed by each:


x + y + 2 * z;


The second grammar will parse this as:
(x + y) + (2 * z)


The first grammar, however, has no notion of associativity or precedence,
so it has other possible parses, so of which might be surprising to the
user, such as:
x + (y + (2* x))
((x + y) + 2) * x


Note that with many generation tools, you could essentially tack on the
following declarations to disambiguate the first grammar:
+ is left associative
* is left associative
+ has a lower precedence than *


Theoretically, the second (non-ambiguous) grammar is the better choice,
because the precedence/associativity is built-in to the grammar.


                Doug


Post a followup to this message

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