Re: Convert to LL(1) (Dennis Mickunas,297D,3336351,0000000)
7 Nov 1998 01:26:06 -0500

          From comp.compilers

Related articles
Convert to LL(1) (Andre) (1998-11-06)
Re: Convert to LL(1) (1998-11-07)
Re: Convert to LL(1) (Ziemowit Laski) (1998-11-08)
Re: Convert to LL(1) (Beeblebrox) (1998-11-12)
| List of all articles for this month |

From: (Dennis Mickunas,297D,3336351,0000000)
Newsgroups: comp.compilers
Date: 7 Nov 1998 01:26:06 -0500
Organization: University of Illinois at Urbana-Champaign
References: 98-11-046
Keywords: parse, LL(1)

Andre <> writes:
>I have a BNF of a grammar for ANSI C, but I think it isn't in the LL(1)
>form. So I want to write a program which transforms it to an LL(1)
>grammar using it with a recursive-descent parser.

>So, my question is, can anybody send me an algorithm for transforming
>it. I don't exactly know what to do.

Since the LL *languages* are a proper subset of the context-free
languages, this cannot be done. For example, consider the language

{0^n 1^n | n>0} U {0^m 2^m | m>0}

It is easy to write an LR(0) grammar for this language:

S -> A | B
A -> 01 | 0A1
B -> 02 | 0B2

However the language itself is not LL(k) for any finite k. Stated
differently, there is no algorithm to transform the LR(0) grammar
shown to an LL(k) grammar, nor could such an LL(k) grammar be found
using any technique at all, including divine intervention.

M. Dennis Mickunas
Department of Computer Science 1304 W. Springfield Ave.
University of Illinois Urbana, Illinois 61801 (217) 333-6351

Post a followup to this message

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