CODEWITHSUNDEEP
parsingcompiler-constructionleft-recursion
Sakib Arifin
Sakib Arifin

Reputation: 269

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?

Upvotes: 1

Views: 1222

Answers (2)

Larty
Larty

Reputation: 36

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

Upvotes: 2

rici
rici

Reputation: 241671

You need to reduce the grammar by removing all useless and non-productive non-terminals before you try to remove right-recursion. Since A is non-productive (it has no non-recursive production), it will get eliminated along with any production which uses it. That certainly gets rid of the left-recursion :-).

Upvotes: 2

Related Questions