6 Feb 2006 00:05:45 -0500

Related articles |
---|

generating recursive parsers from grammars. rpboland@gmail.com (Ralph Boland) (2006-02-03) |

Re: generating recursive parsers from grammars. peteg42@gmail.com (Peter Gammie) (2006-02-06) |

Re: generating recursive parsers from grammars. grosch@cocolab.de (Josef Grosch) (2006-02-06) |

Re: generating recursive parsers from grammars. scavadini@ucse.edu.ar (2006-02-07) |

generating recursive parsers from grammars. lowell@coasttocoastresearch.com (Lowell Thomas) (2006-02-20) |

From: | Josef Grosch <grosch@cocolab.de> |

Newsgroups: | comp.compilers |

Date: | 6 Feb 2006 00:05:45 -0500 |

Organization: | CoCoLab, Germany |

References: | 06-02-039 |

Keywords: | parse, tools |

Content-Disposition: | inline |

Ralph Boland <rpboland@gmail.com> wrote:

*> Can anyone point me to papers or parser generator tools that*

*> that deal with generating recursive parsers from non-LL(1)*

*> grammars?*

nThe parser generator Ell of the Cocktail Toolbox can handle certain non-LL(1)

grammars. Ell generates recursive parsers from grammars in EBNF notation.

Operators are |, [], + and *. Non-LL(1) grammars are handled as follows:

Sometimes grammars do not obey the LL(1) property. They are said to con-

tain LL(1) conflicts. A well-known example is the dangling-else problem of

Pascal: in case of nested it-then-else statements it may not be clear to which

IF an ELSE belongs. It is very easy to solve this conflicts in hand-written

solutions. Ell handles LL(1) conflicts in the following ways:

- Several alternatives (operator |) cause a conflict if their FIRST sets

are not disjoint: the alternative given first is selected.

- An optional part (operators [] and *) causes a conflict if its FIRST set

is not disjoint from its FOLLOW set: the optional part will be analyzed

because otherwise it would be useless.

- Parts that may be repeated at least once cause a conflict if their FIRST

and FOLLOW sets are not disjoint (as above): the repetition will be con-

tinued because otherwise it would be executed only once.

With the above rules it can happen that alternatives are never taken or

that it is impossible for a repetition to terminate for any correct input.

These cases as well as left recursion are considered to be serious design

faults in the grammar and are reported as errors. Otherwise LL(1) conflicts

are resolved as described above and reported as warnings.

The complete document on Ell can be found at

ftp://www.cocolab.com/products/cocktail/doc.pdf/ell.pdf

Best regards

Dr. Josef Grosch

CoCoLab - Datenverarbeitung

Hoehenweg 6

77855 Achern

Germany

Phone : +49-7841-669144

Fax : +49-7841-669145

Email : grosch@cocolab.com

Internet: www.cocolab.com

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.