I am given the following grammar:

$ S \rightarrow AabAba \\ A \rightarrow a | \epsilon $

and I have to prove it is LL(2).

I know what LL(k) means - one can choose a production based on k characters from the input.

So consider the input $ababa$. Of course we start with $S$, so we apply the production to $AabAba$. Now we see $ab$ in the input, so we choose the production to $\epsilon$ for the first $A$. We get rid of the $ab$ and we have $aba$.

And what now? A while ago, we've chosen $\epsilon$ for $A$, seeing $ab$ in the input. Now we see the same thing, but are supposed to choose $A \rightarrow a$. But, as I understand, we cannot do this, because that would mean nondeterminism.

Is this a counterexample? How is this grammar LL(2)?


1 Answer 1


Sippu and Soisalon-Soininen (1982) carefully distinguish between two definitions of LL(k) grammars, one of which -- the one I think you are using -- they call strong LL(k):

A grammar $G$ is $\text{LL}(k)$ if $\text{FIRST}_k(\omega_1\delta)$ and $\text{FIRST}_k(\omega_2\delta)$ are disjoint whenever $xA\delta$ is a left sentential form of $G$ and $A \to \omega_1$ and $A \to \omega_2$ are distinct productions of $G$.

Grammar $G$ is $\text{strong LL}(k)$ if $\text{FIRST}_k(\omega_1\text{FOLLOW}_k(A))$ and $\text{FIRST}_k(\omega_2\text{FOLLOW}_k(A))$ are disjoint whenever $A \to \omega_1$ and $A \to \omega_2$ are distinct productions of $G$.

The difference has to do with the state machine. A grammar is $\text{strong LL}(k)$ if you can use the same procedure to decide which production for a non-terminal to use regardless of the contents of the parser stack. An $\text{LL}(k)$ grammar, on the other hand, can use the contents of the stack ($x$ in the above definition) as well as the lookahead. (For these purposes the contents of the stack can be condensed into a finite state automaton.)

While the two definitions are not equivalent -- the strong condition is much more restrictive -- it can be demonstrated that every $\text{LL}(k)$ grammar can be changed to a $\text{strong LL}(k)$ grammar simply by labelling each usage of a non-terminal. So in the case of your grammar, which is $\text{LL}(k)$ but not $\text{strong LL}(k)$, we can create the equivalent grammar:

$\begin{align} S &\to A_1abA_2ba \\ A_1 &\to a | \epsilon \\ A_2 &\to a | \epsilon \\ \end{align}$

which is $\text{strong LL}(k)$.

For more details, see the paper linked above.

  • $\begingroup$ Consider the grammar $S \rightarrow Sa | \epsilon$. As far as I'm concerned, this grammar is LL(1) according to the definition You've written. Though it is clearly NOT LL(1), because it is left-recursive. What don't I understand? $\endgroup$
    – user84912
    Nov 5, 2018 at 14:12
  • $\begingroup$ @Leftismer: A left-sentential form in that grammar is $Sa$. Here, $x$ is $\epsilon$ and $\delta$ is $a$. $\omega_1\delta$ is $Saa$ and $\omega_2\delta$ is $a$. Clearly, $a \in \text{FIRST}_1(\omega_1\delta)$ and $a \in \text{FIRST}_1(\omega_2\delta)$. So how is the grammar LL(1) according to the definition? $\endgroup$
    – rici
    Nov 5, 2018 at 15:08
  • $\begingroup$ @Leftismer: By the way, you can extend the proof that there is a prediction conflict (from two comments ago) to LL(k) by choosing the sentential form $Sa^k$; $a^k$ will be in both FIRST sets. So, as you would expect for a left-recursive grammar, it is not LL(k) for any $k$. $\endgroup$
    – rici
    Nov 5, 2018 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.