Re: LL(k) vs Strong_LL(k)

Sylvain Schmitz <schmitz@i3s.unice.fr>
21 Oct 2006 13:54:08 -0400

          From comp.compilers

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)
| List of all articles for this month |

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.