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

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
--

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