Why is this grammar an LL(2) grammar?

Question

I had a question regarding LL($k$) grammars. I came across a problem that I attempted to solve, but my answer varied from the solution and I wasn't sure why.

$$L = \{a^{n + 2}b^mc^{n + m}\ :\ n \ge 1,\ m \ge 1\}$$

The grammar I came up with is:

$$ \begin{align} S & \rightarrow aaA \\ A & \rightarrow aAc\ \vert\ bBc \\ B & \rightarrow bBc\ \vert\ bc \\ \end{align} $$

According to the solution, this given language has an LL($2$) grammar, but the answer I came up with was LL($4$).

My reasoning is that since the start of the language has at least three $a$'s, you need to check the fourth position in order to see which production to use afterwards. Then you can "slide" the window one position to the right to check subsequent productions.

Why is it considered LL($2$)?

Thank you.

Answer 1

An LL parse produces a leftmost derivation, which means that at each point in the derivation, the leftmost non-terminal must be replaced by one of its productions. The issue is to decide which production to use.

A grammar is LL(k) if the production to be used in the leftmost derivation can always be determined by examining only the terminals prior to the first non-terminal and the $k$ following terminals in the input. (These will be the next $k$ symbols in the input if we're doing a left-to-right parse; the terminals prior to the non-terminal will already have been input.)

In your grammar, neither $S$ nor $A$ present any problems at all. $S$ only has one production, so there is no need to examine any terminal at all to make a decision. $A$ has two productions, but their first terminal differs so it is trivial to predict which one to select: if the next input symbol is $a$, select the first alternative; if it is $b$, select the second one.

$B$ also has two productions, but both of them start with a $b$. So we need to look at least one symbol further in the input. Now, what is the second symbol in a derivation starting with each production for $B$? For $B \to b c$, the second symbol is clearly $c$. In $B \to b B c$, the second symbol must be the first symbol in some derivation of $B$. But, as we've just observed, every derivation of $B$ starts with $b$. So the second symbol in $B \to b B c$ must be a $b$.

With that, we have a complete decision procedure:

• If the non-terminal to expand is $S$:
  • choose the production $S \to a a A$
• If the non-terminal to expand is $A$:
  • If the next input is $a$:
    • choose the production $A \to a A c$
  • If the next input is $b$:
    • choose the production $A \to b B c$
• If the non-terminal to expand is $B$:
  • If the next two input symbols are $bb$
    • choose the production $B \to b B c$
  • If the next two input symbols are $bc$
    • choose the production $B \to b c$
• If there is no non-terminal left
  • Report success
• If none of the above rules apply
  • Report failure

The longest sequence of terminals we need to examine in any of those rules is 2. So the grammar is LL(2).

Answer 2

You can easily transform this grammar to LL(1) by extracting the common prefix $b$ in both productions of $B$, a procedure called left-factoring.

You get this:

$B \to b B'$

$B' \to B c$

$B' \to c$

Then $B$ always starts with $b$ and $B'$ starts either with $b$ or with $c$ which can be desided by looking at only one input symbol.