Re: Convert to LL(1)

Andre <sky4walk@gmx.de> 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
mickunas@cs.uiuc.edu (217) 333-6351

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