Search code examples
parsingrecursive-descentleft-recursion

recursive descend parser - avoiding left recursion

I have the following productions

A -> Aa
A -> b

so it is clear that there is left recursion like

parseA() {
   parseA();//recursion
   parsea();
}

It is said that the left recursion can be avoided using the following rule

A -> bA'
A' -> aA'|null

How is left recursion avoided here?.There is still recursion in function A'. Can anybody explain me this.I am a beginner in this subject?

Solution

  • How is left recursion avoided here?.There is still recursion in function A'.

    Read this again. Left recursion is avoided. Non-left recursion is not.