7 Nov 1998 01:26:06 -0500

Related articles |
---|

Convert to LL(1) sky4walk@gmx.de (Andre) (1998-11-06) |

Re: Convert to LL(1) mickunas@cs.uiuc.edu (1998-11-07) |

Re: Convert to LL(1) laski@ics.uci.edu (Ziemowit Laski) (1998-11-08) |

Re: Convert to LL(1) jjan@cs.rug.nl (Beeblebrox) (1998-11-12) |

From: | mickunas@cs.uiuc.edu (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 <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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.