1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ When you say "the grammar I came up with is LL(4)", do you mean that you think the grammar in your question is LL(4), based on your reasoning in the following paragraph? Or do you mean that you presented this grammar as an answer, and were told that it is LL(4)? $\endgroup$ – rici Jun 16 '18 at 4:54
  • $\begingroup$ Ah apologies for the confusion. What I meant is that, based on my reasoning, that I think it is LL(4), but in fact it's LL(2). The grammar presented is also something I came up with, and isn't provided in the question. $\endgroup$ – Seankala Jun 16 '18 at 4:56
  • $\begingroup$ Thanks for the clarification. Could you explain to me why it's LL(2) though, please? $\endgroup$ – Seankala Jun 16 '18 at 5:12
  • 1
    $\begingroup$ Hope that the answer is clear $\endgroup$ – rici Jun 16 '18 at 5:19
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.