Fri, 15 May 1992 00:53:42 GMT

Related articles |
---|

LL vs LR, no jihad initiation, but... parrt@ecn.purdue.edu (1992-05-11) |

Re: LL vs LR, strengths and weaknesses mauney@adm.csc.ncsu.edu (1992-05-13) |

LL(1) Questions (Re: LL vs LR, strengths and weaknesses) bart@cs.uoregon.edu (1992-05-15) |

Re: LL(1) Questions (Re: LL vs LR, strengths and weaknesses) jos@and.nl (1992-05-17) |

Re: LL(1) Questions jan@si.hhs.nl (1992-05-18) |

Newsgroups: | comp.compilers |

From: | bart@cs.uoregon.edu (Barton Christopher Massey) |

Keywords: | LL(1), question |

Organization: | minimal |

References: | 92-05-059 92-05-090 |

Date: | Fri, 15 May 1992 00:53:42 GMT |

OK, here's a couple of conjectures I floated around the dept. a while

back without getting a definite answer. How about all you parsing and

language gurus telling me how simple it is?

Conjecture 1: an algorithm exists which, given any unambiguous

(but otherwise unrestricted) grammar for an LL(1) language,

produces in finite time an LL(1) grammar for the same language.

Conjecture 2: an algorithm exists which, given any unambiguous

(but otherwise unrestricted) grammar, determines in finite time

whether the grammar describes an LL(1) language.

I suspect that full left-factorization and left-recursion removal will

satisfy the requirements of (1), and that conjecture (2) is false.

I'm sure these are trivial, but not to me :-). The application of these

conjectures to compilers is immediately obvious :-). Thanks for your

help,

Bart Massey

bart@cs.uoregon.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.