Re: LL1 grammar conversion Algorithms

gholness@bu.edu wrote:
> Does anyone know of any implementation of an algorithm which will
> convert an LALR grammar to LL1.
> Particularly elimination of common prefix and left recursion ( as in
> Fischer and LeBlanc's "Crafting a Compiler in C )


> [It's not possible in general...


I should also add that LALR grammars that were automatically converted
to LL can be totally unreadable. Some of the issues are:


1) LL grammar tools like PCCTS have repition constructs like ()* and
()+ which remove much recursion found in LALR grammars. An automatic
tool will probably ignore that feature.


2) It is often better to backtrack in an LL grammar than to
left-factor for particularly awful cases. The automatic tool may find
that the common prefix is quite long and generate a perfectly awful
and grotesquely verbose LL grammar as a result.


3) There are some differences between actions embedded in an LL
grammar and those in an LR grammar, so the automatic conversion may
make incorrect action placement.


john lilley
--

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