parsingcompiler-constructionleft-recursion

How to remove left recursion from a grammar with beta missing?

Here's the problem:

A -> A*B | A+CDE | Aab

All of the productions start with A. I guess that satisfies the rule? As you can see, it is missing beta. How do I perform left recursion on it? Can left recursion be even performed on it?

What I have learned so far is that if it was like this: A -> A*B | A+CDE | Aab | b

Then I would consider b as beta and solve as:

A -> bA'

A' -> *BA' | +CDEA' | abA' | ϵ

Without beta, I am confused. What do I consider as beta?

Solution

  • I think firstly it is needed to add new rule to A production to stop recursion. Something like b in your example.

    A -> A*B | A+CDE | Aab | b

    If this is not possible I guess production will looks like this:

    A -> A*B | A+CDE | Aab | e

    So, first step will be left factoring:

    A -> AT | e
T -> *B | +CDE | ab

    And then remove left recursion:

    A -> A'
A' -> TA' | e
T -> *B | +CDE | ab