|LL1 grammar conversion Algorithms firstname.lastname@example.org (1997-02-11)|
|Re: LL1 grammar conversion Algorithms email@example.com (John Lilley) (1997-02-16)|
|Re: LL1 grammar conversion Algorithms firstname.lastname@example.org (Scott Stanchfield) (1997-02-16)|
|From:||John Lilley <email@example.com>|
|Date:||16 Feb 1997 22:25:10 -0500|
|Organization:||Nerds for Hire, Inc.|
> 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.
Return to the
Search the comp.compilers archives again.