LL(1) Questions (Re: LL vs LR, strengths and weaknesses)

bart@cs.uoregon.edu (Barton Christopher Massey)
Fri, 15 May 1992 00:53:42 GMT

          From comp.compilers

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)
| List of all articles for this month |

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.