Re: generating recursive parsers from grammars.

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

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