Re: Simple Expression Recursion vs Expression/Term/Factor

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

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