recursioncompiler-constructioncontext-free-grammarleft-recursioncontext-free-language

How to remove left recursion from A -> Aα | ε

I think the left-recursion for this grammar is not removable. Correct me if I am wrong. α is Alpha that is a Non-terminal ε is Epsilon.

Solution

  • Left recursion can be removed from the grammar; Here is the grammar without left recursion:

    A -> A' | ε
A' -> α A

    You could also do how @Mephy did with right recursion:

    A -> α A | ε

    Note that (as @Mephy said) this grammar is just zero or more αs (α*).