3
$\begingroup$

Consider the following grammar:

$$ A\to Ba|Aa|c \\ B\to Bb|Ab|d $$

How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion?

I have tried applying the rule which converts $A \to A\alpha|\beta$ to $A \to \beta A'$ and $A' \to \alpha A'$:

  • For $A \to Ba|Aa|c$, $\beta = Ba|c$ and $\alpha = a$.
  • For $B \to Bb|Ab|d$, $\beta = Ab|d$ and $\alpha = b$.

In this way I eliminate direct recursion from each one, but then when I try to substitute A or B with its product and eliminate indirect left recursion, the parsing table finds collisions so the grammar is not LL(1). Any ideas?

$\endgroup$
1
$\begingroup$

Mutual recusive definitions are tricky to eliminate. You'll have to work with the unwieldy expanded form of one of the rules. Here, let's expand $B$ \begin{align*} B &\to Bb \mid Ab \mid d \\ & \to (Bb \mid Ab \mid d)b \mid Ab \mid d \\ &\to ((Bb \mid Ab \mid d)b \mid Ab \mid d)b\mid Ab \mid d \\ & \to ~\cdots \\ &\to (d \mid Ab) \mid (db \mid Abb) \mid (dbb \mid Abbb) \mid \cdots \\ &\to (d \mid Ab)b^* \end{align*} In general, $B \to B(x_0 \mid x_1 \mid \dots) \mid (y_0 \mid y_1 \mid \dots)$ will have an expanded form of $B \to y\cdot x^*$. Things get even more complicated if $B \to z B x \mid y$ and $z$ is nullable. But let's not worry about that just yet, instead, let's turn our attention back to $B$.

Now, notice that I have used the term $b^*$, this is actually just the nonterminal $b^* \to \epsilon \mid b b^*$; this is a standard trick that many "extended" BNF based parsers use as well.

Finally, we can inline $B$ into $A$ to get \begin{align*} A &\to Ba \mid Aa \mid c \\ &\to db^* a \mid Abb^*a \mid Aa \mid c \\ &\to (c \mid db^*a)(bb^*a \mid a)^* \end{align*}

where once again $(bb^*a \mid a)^* \to \epsilon \mid (bb^*a \mid a)(bb^*a \mid a)^*$.

Now, if all you need is $A$, then this is already fine and dandy. However, if you need to expose $B$ as a public method as well, then you'll notice that there is a slight hitch: $\text{follow}((bb^*a \mid a)^*) = \text{follow}(A) = b$, since $B \to Abb*$. But since $\text{first}((bb^*a \mid a)^*)$ also contains $b$, then we can't decide whether we should shift to $\epsilon$ or $bb^*a$ when we encounter a $b$. You might try to inline $A$, so that $$ B \to (d \mid (c \mid db^*a)(bb^*a \mid a)^*b)b^* $$ but you still have the same problem. Now you can reason that $(bb^*a \mid a)^*bb^* = b^*(ab^*)^*$, but this is not very generalizable, and it breaks down fast when your language takes a step out of its regular territory. Instead, you'll want to start from the beginning. Expand $A$ first, and inline into $B$.

$\endgroup$
  • $\begingroup$ Τhe truth is i didn't understand everything, and this is supposed to be an undergraduate homework,is it possible that the answer is so complex ? I mean none of the examples we have been taught had something that complex $\endgroup$ – primitzisgate7 Dec 6 '16 at 18:09
  • $\begingroup$ but anyways thanks a lot for the answer !! :D $\endgroup$ – primitzisgate7 Dec 6 '16 at 18:10

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.