Re: LL(k) vs Strong_LL(k)

Sylvain Schmitz <>
21 Oct 2006 13:54:08 -0400

          From comp.compilers

Related articles
LL(k) vs Strong_LL(k) (Fanta) (2006-10-21)
Re: LL(k) vs Strong_LL(k) (Sylvain Schmitz) (2006-10-21)
Re: LL(k) vs Strong_LL(k) (Fanta) (2006-10-24)
Re: LL(k) vs Strong_LL(k) (Juan Miguel Vilar) (2006-10-26)
| List of all articles for this month |

From: Sylvain Schmitz <>
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" <>
Posted-Date: 21 Oct 2006 13:54:08 EDT

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,


Post a followup to this message

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