From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar:

\begin{align} &E \to E+T \mid T \\ &T \to T\cdot F \mid F \\ &F \to F^* \mid a \mid b \end{align}

I actually changed this to:

\begin{align} &E \to TE' \\ &T \to +TE' \mid \epsilon \\ &T \to F\cdot T' \\ &T \to \cdot FT' \mid \epsilon \\ &F \to aF' \mid bF' \\ &F' \to ^*F' \mid \epsilon \end{align}

This is done using the left-recursion elimination formula.

But then I have a doubt about whether it is correct or not, because the last $F$ transition cannot now generate $abb$, which it was able to generate. And if it is still able to do that, I would love to know, how?

Another transition that I tried for $F$ was:

\begin{align} &F \to G^* \mid G \\ &G \to a \mid b \end{align}

This was done to remove the left recursion without using any formula.

But then I realized that it made the last transition nondeterministic.

Then I tried changing it by using the left-recursion elimination formula on $F \to G^* \mid G$, making it:

\begin{align} &F \to GF' \\ &F' \to ^*F' \mid \epsilon \\ &G \to a \mid b \end{align}

And now I am all confused!


2 Answers 2


I don't know that there is a "standard" way to do left recursion elimination from Kleene star. But this is one obvious translation:

$$\begin{eqnarray*}F & \rightarrow & F^*\,|\, a \,| \,b \\ & & \Downarrow \\ F & \rightarrow & a F\,|\,b F\,|\,\epsilon\end{eqnarray*}$$

here is code:
F -> W F | ϵ
W -> a|b|F

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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