21 Oct 2006 13:54:08 -0400

Related articles |
---|

LL(k) vs Strong_LL(k) anha2k47@gmail.com (Fanta) (2006-10-21) |

Re: LL(k) vs Strong_LL(k) schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-10-21) |

Re: LL(k) vs Strong_LL(k) anha2k47@gmail.com (Fanta) (2006-10-24) |

Re: LL(k) vs Strong_LL(k) Juan.Miguel.Vilar@gmail.com (Juan Miguel Vilar) (2006-10-26) |

From: | Sylvain Schmitz <schmitz@i3s.unice.fr> |

Newsgroups: | comp.compilers |

Date: | 21 Oct 2006 13:54:08 -0400 |

Organization: | Laboratoire I3S |

References: | 06-10-078 |

Keywords: | parse, LL(1), theory |

Cc: | "comp.compilers" <compilers@iecc.com> |

Fanta wrote:

*> I've proved that the families of LL(k) language and families of*

*> Strong LL(k) (SLL(k)) language are equal. It's very meaningful for*

*> LL(k) grammar analysis. But I wonder if it is a new result or not, is*

*> there any person who already proofed if before. Could anyone tell me.*

Your proof was certainly correct for k=1, and it is a well-known result.

However, the general case does not hold: the grammar with rules

S -> a A a b

| b A b

A -> a

| epsilon

is LL(2), but not SLL(k).

You can check that a SLL(k) parser for a large enough k considers

Follow_k(A)={ab$,b$}, and when it has to choose which rule to apply for

`A', its lookahead sets are not disjoint, being {aab$,ab$} for the rule

`A->a', and {ab$,b$} for the empty rule `A->epsilon'.

A LL(2) parser on the other hand uses the left context of `A' to infer

its decisions: `A' in the context of `a' has a Follow_2 set {ab} and in

the context of `b' has a Follow_2 set {b$}, and choosing between `A->a'

and `A->epsilon' is possible.

--

Hope that helps,

Sylvain

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.