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!


Your Answer

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

Browse other questions tagged or ask your own question.