Re: LL(1) Questions

Barton Christopher Massey (bart@cs.uoregon.edu) writes:
>OK, here's a couple of conjectures ...
>
> 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.
>...
>I suspect that full left-factorization and left-recursion removal will
>satisfy the requirements of (1) ...


You should add substitution of leading nonterminals in right parts of rules
to your list, as this can solve problems with overlapping firstsets.


You should note however that blind application of these transformations
might get you in an infinite loop like the next grammar:


S -> A a
S -> B b
A -> c A
A -> /* epsilon */
B -> c B
B -> /* epsilon */


FIRST(S) = {a,b},
FIRST(A) = {c, epsilon}, FOLLOW(A) = {a},
FIRST(B) = {c, epsilon}, FOLLOW(B) = {b},


The S-rules have overlapping firstsets, so let's substitute A and B


S -> c A a
S -> a
S -> c B b
S -> b
A -> c A
A -> /* epsilon */
B -> c B
B -> /* epsilon */


Now factorize the S-rules on the common leading c:


S -> c C
S -> a
S -> b
A -> c A
A -> /* epsilon */
B -> c B
B -> /* epsilon */
C -> A a
C -> B b


So starting from a collision of A and B in the S-rules, we end up
with a collision of A and B in the C-rules.


There exits however a LL(1) grammar:


S -> c S
S -> a
S -> b


We just have to be smarter.


Let's start again:


S -> A a
S -> B b
A -> c A
A -> /* epsilon */
B -> c B
B -> /* epsilon */


Couple a and b to the A-rules en B-rules:


S -> A
S -> B
A -> c A
A -> a
B -> c B
B -> b


Join A and B into one nonterminal AorB:


S -> AorB
A -> c A
A -> a
B -> c B
B -> b
AorB -> c A
AorB -> a
AorB -> c B
AorB -> b


Factorize on the common c:


S -> AorB
A -> c A
A -> a
B -> c B
B -> b
AorB -> c D
AorB -> a
AorB -> b
D -> AorB {add D->A to D->B giving D->AorB}


Now remove the obsolete A and B.


S -> AorB
AorB -> c D
AorB -> a
AorB -> b
D -> AorB


Finally notice S, AorB and D are identical due to
the productions of the form X -> Y, calling them all S.


S -> c S
S -> a
S -> b


Suggesting this grammar can indeed be found automatically


Jan Schramp (jan@si.hhs.nl)
--

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