# Re: LL(1) Questions

## jan@si.hhs.nl (Schramp)Mon, 18 May 1992 13:09:16 GMT

From comp.compilers

Related articles
LL(1) Questions (Re: LL vs LR, strengths and weaknesses) bart@cs.uoregon.edu (1992-05-15)
Re: LL(1) Questions jan@si.hhs.nl (1992-05-18)
| List of all articles for this month |

 Newsgroups: comp.compilers From: jan@si.hhs.nl (Schramp) Keywords: LL(1), question Organisation: Sector Informatica, Haagse Hogeschool, The Hague, The Netherlands Organization: Compilers Central References: 92-05-094 Date: Mon, 18 May 1992 13:09:16 GMT

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

Post a followup to this message