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)?


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$ – Leftismer Nov 5 '18 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 '18 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 '18 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.