How would this grammar be converted to a non-left recursive rule?

Question

With recursive-descent parsing, direct/indirect left recursive rules do not allow top-down parsing.

How would this grammar be converted to be non-left recursive?

S-> Aa | b, A -> Ac | Sd | epsilon

I have gotten this far but I am not sure if it is correct.

S-> bS'
S'-> epsilon | AaS'
A-> SdA'
A'-> cA'

I wasn't sure if the 'S' rule had to be changed since it did not have an 'S'(itself) in it. From reading online, it looked like each rule should be checked before starting to change it but I'm a bit stuck right now. Does anyone know if this is the right approach or have any suggestions?

Answer 1

The given grammar has a direct and an indirect recursion. There is no rule to solve this or such which mentions whether any production is to be changed or not. However one way to keep things clear would be to consider one rule at a time for removing left recursion, which in your case would be as follows $$S\rightarrow Aa\mid b$$$$A\rightarrow Ac\mid Sd\mid \epsilon$$

Removing left recursion from productions of $A$ $$A\rightarrow Sd{A}'\mid {A}'$$$${A}'\rightarrow c{A}'\mid \epsilon$$

substituting these productions in the productions of $S$ and removing left recursion$$S\rightarrow {A}'a{S}'\mid b{S}'$$$${S}'\rightarrow d{A}'a{S}'\mid \epsilon$$

This is just one way. Likewise you could remove the indirect recursion first and work it out.