6 Aug 2001 04:06:53 -0400

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

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.