Re: LL1 grammar conversion Algorithms

John Lilley <>
16 Feb 1997 22:25:10 -0500

          From comp.compilers

Related articles
LL1 grammar conversion Algorithms (1997-02-11)
Re: LL1 grammar conversion Algorithms (John Lilley) (1997-02-16)
Re: LL1 grammar conversion Algorithms (Scott Stanchfield) (1997-02-16)
| List of all articles for this month |

From: John Lilley <>
Newsgroups: comp.compilers
Date: 16 Feb 1997 22:25:10 -0500
Organization: Nerds for Hire, Inc.
References: 97-02-075
Keywords: parse, LL(1) 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

Post a followup to this message

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