Re: LL1 grammar conversion Algorithms

John Lilley <jlilley@empathy.com>
16 Feb 1997 22:25:10 -0500

          From comp.compilers

Related articles
LL1 grammar conversion Algorithms gholness@bu.edu (1997-02-11)
Re: LL1 grammar conversion Algorithms jlilley@empathy.com (John Lilley) (1997-02-16)
Re: LL1 grammar conversion Algorithms thetick@scruz.net (Scott Stanchfield) (1997-02-16)
| List of all articles for this month |

From: John Lilley <jlilley@empathy.com>
Newsgroups: comp.compilers
Date: 16 Feb 1997 22:25:10 -0500
Organization: Nerds for Hire, Inc.
References: 97-02-075
Keywords: parse, LL(1)

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
--


Post a followup to this message

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