|generating recursive parsers from grammars. email@example.com (Ralph Boland) (2006-02-03)|
|Re: generating recursive parsers from grammars. firstname.lastname@example.org (Peter Gammie) (2006-02-06)|
|Re: generating recursive parsers from grammars. email@example.com (Josef Grosch) (2006-02-06)|
|Re: generating recursive parsers from grammars. firstname.lastname@example.org (2006-02-07)|
|generating recursive parsers from grammars. email@example.com (Lowell Thomas) (2006-02-20)|
|From:||Josef Grosch <firstname.lastname@example.org>|
|Date:||6 Feb 2006 00:05:45 -0500|
|Posted-Date:||06 Feb 2006 00:05:45 EST|
Ralph Boland <email@example.com> wrote:
> Can anyone point me to papers or parser generator tools that
> that deal with generating recursive parsers from non-LL(1)
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
Dr. Josef Grosch
CoCoLab - Datenverarbeitung
Phone : +49-7841-669144
Fax : +49-7841-669145
Email : firstname.lastname@example.org
Return to the
Search the comp.compilers archives again.