In this article, we will learn What is Left Recursion, how to eliminate left recursion, and why we eliminate left recursion. We have implemented a C program to identify and eliminate left recursion with a brief explanation.

What is LEFT RECURSION?

A grammar in the form G=(V, T, S, P) is said to be in left recursive form if it has the production rules of the form A → Aα | β.

In the production rule above, the variable in the left side occurs at the first position on the right side production, due to which the left recursion occurs.

If we have a left recursion in our grammar, it leads to infinite recursion, due to which we cannot generate the given string.

In other words, a grammar production is said to have left recursion if the leftmost variable of its Right Hand Side is the same as the variable of its Left Hand Side. A grammar containing a production of having left recursion is called Left Recursive Grammar.

Eliminating Left Recursion

A left recursive production can be eliminated by rewriting the offending productions. Consider a nonterminal A with two productions

A → Aα | β.

where and are sequences of terminals and nonterminals that do not start with A. For example, in

expr → expr+term | term

nonterminal A = expr, string = +term, and string = term.

The nonterminal A and its productions are said to be left recursive because the production A → Aα has A itself as the leftmost symbol on the right side.

The left-recursive pair of productions A → Aα | β can be replaced by the non-left-recursive productions:

A → βA’
A’ → αA’ | ε

Why do we eliminate left recursion?

Left recursion often poses problems for parsers, either because it leads them into infinite recursion (loop) or because they expect rules in a normal form that forbids it.

Top-down parsing methods cannot handle left recursive grammars, so a transformation is needed to eliminate left recursion.

Therefore, grammar is often preprocessed to eliminate the left recursion.

Eliminate Left Recursion in C Program

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define SIZE 20

int main()
{
    char pro[SIZE], alpha[SIZE], beta[SIZE];
    int nont_terminal,i,j, index=3;

    printf("Enter the Production as E->E|A: ");
    scanf("%s", pro);

    nont_terminal=pro[0];
    if(nont_terminal==pro[index]) //Checking if the Grammar is LEFT RECURSIVE
    {
        //Getting Alpha
        for(i=++index,j=0;pro[i]!='|';i++,j++){
            alpha[j]=pro[i];
            //Checking if there is NO Vertical Bar (|)
            if(pro[i+1]==0){
                printf("This Grammar CAN'T BE REDUCED.\n");
                exit(0); //Exit the Program
            }
        }
        alpha[j]='\0'; //String Ending NULL Character

        if(pro[++i]!=0) //Checking if there is Character after Vertical Bar (|)
        {
            //Getting Beta
            for(j=i,i=0;pro[j]!='\0';i++,j++){
                beta[i]=pro[j];
            }
            beta[i]='\0'; //String Ending NULL character

            //Showing Output without LEFT RECURSION
            printf("\nGrammar Without Left Recursion: \n\n");
            printf(" %c->%s%c'\n", nont_terminal,beta,nont_terminal);
            printf(" %c'->%s%c'|#\n", nont_terminal,alpha,nont_terminal);
        }
        else
            printf("This Grammar CAN'T be REDUCED.\n");
    }
    else
        printf("\n This Grammar is not LEFT RECURSIVE.\n");
}

Input & Output

Eliminate Left Recursion
Output | Left Recursion

Code Explanation

#define SIZE 20

We are taking a global variable for the entire program.

char pro[SIZE], alpha[SIZE], beta[SIZE];
    int nont_terminal,i,j, index=3;

    printf("Enter the Production as E->E|A: ");
    scanf("%s", pro);

    nont_terminal=pro[0];

Here, we are taking index = 3 the 3rd character of the production and non_terminal = pro[0] the first character of the production.

String Indexing in Elimination of Left Recursion
String Indexing
if(nont_terminal==pro[index])

If the first character and the 3rd character of the string are the same then the production is left recursive. That’s what we are checking. Otherwise, it will print “Grammar is NOT LEFT RECURSIVE”.

If it is left recursive then it will do the following:

for(i=++index,j=0;pro[i]!='|';i++,j++){
            alpha[j]=pro[i];
            //Checking if there is NO Vertical Bar (|)
            if(pro[i+1]==0){
                printf("This Grammar CAN'T BE REDUCED.\n");
                exit(0); //Exit the Program
            }
        }
        alpha[j]='\0'; //String Ending NULL Character

First, we have to take alpha. Alpha will be the collection of characters from the 4th character to the vertical bar (|).
If there is no vertical bar then it will print the error and exit the program.

And lastly, after the loop, we will add a null character to our alpha string. If we don’t give null characters at the end of String it will show garbage values. alpha[j]='\0' its means the last character of alpha or we can say it is storing a null character at the last position.

if(pro[++i]!=0) //Checking if there is Character after Vertical Bar (|)
        {
            //Getting Beta
            for(j=i,i=0;pro[j]!='\0';i++,j++){
                beta[i]=pro[j];
            }
            beta[i]='\0'; //String Ending NULL character

            //Showing Output without LEFT RECURSION
            printf("\nGrammar Without Left Recursion: \n\n");
            printf(" %c->%s%c'\n", nont_terminal,beta,nont_terminal);
            printf(" %c'->%s%c'|#\n", nont_terminal,alpha,nont_terminal);
        }
        else
            printf("This Grammar CAN'T be REDUCED.\n");
    }

After getting the Alpha we need to get the beta. For getting beta, first, we need to verify if there is any character after the vertical bar(|). If there is no character after the vertical bar(|), it will show an error.

And if there is any character, it will store those characters in the beta string variable. After storing all the characters we need to put the end character and that’s it. 

After we get the beta, we just have to print those.

You Might Like: