# eliminate left recursion of below grammar

Please look at this grammar: $$𝑆 → 𝑆𝐴𝐵 \ | \ 𝐴𝑏 \ | \ 𝑏 \\ 𝐴 → 𝑆𝐵 \ | \ 𝑎 \ | \ 𝐵𝑆 \\ 𝐵 → 𝐴𝑆 \ | \ d$$

I eliminated B from the grammar and it converted to:

$$S → SAAS \ | SAd \ | \ Ab | \ b \\ A → SAS \ | \ Sd \ | \ a \ | ASS \ | dS$$

But I can't eliminate loop recursion between A and S.Was it a good solution I removed the B at first? How can I solve that?

any help is much appreciated.

## 1 Answer

$$𝑆 → YX \ | \ Y \\ Y → Ab \ | \ b \\ X → ABX \ | \ AB \\ A → SB \ | \ BS \ | \ a \\ 𝐵 → 𝐴𝑆 \ | \ d$$ At first I say which rules have a left recursion, considering that the middle tree which is A(the one that A node is the root) has not called itself in its children from the beginning of the left of each child so there is no left recursion in tree which A is root.Similarly the right tree(the one that B node is the root) in its children has not called itself from the beginning of the left of each child, so they do not need to remove the left recursion, so They they have the previous rule (the fourth and fifth lines of my answer A→SB|BS|a,𝐵→𝐴𝑆|d ).

So our problem is the tree with the S root. I come and look at the children of the S root, there is only one child who starts with S from the beginning of the left of child, so I just have to correct one left recursion to right recursion,

Now I know that there are two children left of the tree with S root, since I only have a left recursion which I want to convert to the right recursion, So I have to put those two children on the left side of this conversion to the right! (For example, if we have two of these conversions we have to pack each of two children(with no recursion) with those two conversions.)

So I write the second line of my answer (Y→Ab|b) and then I write the third line of my answer (X→ABX|AB), which is actually the left-to-right conversion, The first line that these two children connect to each other, and the last two lines are the two trees in the middle and right.

• Can you explain how you eliminated the left recursion? Your figure is hard to interpret. – Yuval Filmus May 3 at 20:49
• @YuvalFilmus Sorry I was late for your feedback, I edited the path I took ‌ I hope it's right but it may not be right and I am sorry about that, let me know if I made a mistake or I was not clear. – ryhn May 4 at 1:48