Re: generating recursive parsers from grammars.

Josef Grosch <>
6 Feb 2006 00:05:45 -0500

          From comp.compilers

Related articles
generating recursive parsers from grammars. (Ralph Boland) (2006-02-03)
Re: generating recursive parsers from grammars. (Peter Gammie) (2006-02-06)
Re: generating recursive parsers from grammars. (Josef Grosch) (2006-02-06)
Re: generating recursive parsers from grammars. (2006-02-07)
generating recursive parsers from grammars. (Lowell Thomas) (2006-02-20)
| List of all articles for this month |

From: Josef Grosch <>
Newsgroups: comp.compilers
Date: 6 Feb 2006 00:05:45 -0500
Organization: CoCoLab, Germany
References: 06-02-039
Keywords: parse, tools
Posted-Date: 06 Feb 2006 00:05:45 EST
Content-Disposition: inline

Ralph Boland <> 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

Best regards

Dr. Josef Grosch

CoCoLab - Datenverarbeitung
Hoehenweg 6
77855 Achern

Phone : +49-7841-669144
Fax : +49-7841-669145
Email :

Post a followup to this message

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