# Proof that the grammar is LL(2)

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

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.

• 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? – Leftismer Nov 5 '18 at 14:12
• @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? – rici Nov 5 '18 at 15:08
• @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$. – rici Nov 5 '18 at 22:09