Re: LL(k) vs Strong_LL(k)

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

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