|LL vs LR, no jihad initiation, but... email@example.com (1992-05-11)|
|Re: LL vs LR, strengths and weaknesses firstname.lastname@example.org (1992-05-13)|
|LL(1) Questions (Re: LL vs LR, strengths and weaknesses) email@example.com (1992-05-15)|
|Re: LL(1) Questions (Re: LL vs LR, strengths and weaknesses) firstname.lastname@example.org (1992-05-17)|
|Re: LL(1) Questions email@example.com (1992-05-18)|
|From:||firstname.lastname@example.org (Barton Christopher Massey)|
|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
Return to the
Search the comp.compilers archives again.