Re: Simple Expression Recursion vs Expression/Term/Factor

Mike Stogden wrote:
> 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?


The first way of describing the expressions leads to ambiguities when
parsing for instance input strings like 1 + 2 +3 or 1 + 2 * 3. The
first expression can be parsed as (1 + 2) + 3 as well as 1 + (2 + 3),
the second one can also be parsed in 2 different ways. The second way
of defining the expressions expresses that the "+" and "*" operators
are left-associative and that the "*" operator has a higher priority
than the "+" operator. So, the first expression given above is parsed
as (1 + 2) + 3 and the second one as 1 + (2 * 3).


-- Mark
----------------------------------------------------------------
M.G.J. van den Brand,
Department of Software Engineering
CWI
Kruislaan 413, NL-1098 SJ AMSTERDAM, The Netherlands.


Tel___(+31) 20 5924213 WWW____http://www.cwi.nl/~markvdb/
Fax___(+31) 20 5924199 Email__Mark.van.den.Brand@cwi.nl
----------------------------------------------------------------

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