Mon, 18 May 1992 13:09:16 GMT

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.