Left Recursion in Compiler Design

Problems with left recursion in compiler design

The problem with left recursion is that if left recursion is present in the grammar, then it gives rise to ambiguity, and during parsing in the syntax analysis part of the compilation, there is a possibility that the grammar will create an infinite loop. This will happen because, at every time of production of grammar, S will produce another S without checking any condition.

We can use left factoring to remove left recursion from our grammar.

How to Eliminate Left Recursion in Compiler Design?

To eliminate left recursion in compiler design, transform the grammar by replacing left-recursive rules with right-recursive ones. Use intermediate non-terminals to break the recursion, ensuring the grammar is suitable for top-down parsing.

Elimination of Direct Left Recursion

Let us the algorithm to remove direct left recursion with an example.

The given production rule is-

A ⇒ A x | A y | A B | c | d
B ⇒ e

We need to separate the rules, and we need to introduce a new non-terminal at the end of every terminal symbol.

A ⇒ cA` | dA`  where A` is the new non-terminal that we introduced.

For the non-terminal that we introduced, we write the non-terminal A` on the left side, and on the right side, it can either produce ε which is null, or it can produce new production rules in which the terminals or non-terminals which follow the previous LHS, i.e., A will be replaced by the new non-terminal A' at the end of the term.

A` ⇒ ε | x A` | y A` | B A`  where ε is the null symbol.

Hence the final set of productions after the removal of the left recursion would be-

A  ⇒ cA` | dA`
A` ⇒ ε | x A` | y A` | B A`
B  ⇒ e

Elimination of Indirect Left Recursion

Let us the algorithm to remove indirect left recursion with an example.

A ⇒ B C
B ⇒ C A | b
C ⇒ A A | a 

Here A, B, and C are non-terminals while a and b are terminals.
We need to identify the production rule which will cause the indirect left recursion. In the example, the production rule C ⇒ A A | a causes left recursion.

Substitute its production at the place the terminal is present in any other production: substitute A ⇒ B C in production of C. 

C ⇒B C A | a 

Now in this production substitute B ⇒ C A | b

C ⇒(C A | b) C A | a 
C ⇒ C A C A | b C A | a

Now we can see that we have formed a production rule with direct left recursion.

Now we can use the approach we discussed for removing this direct left recursion-

C ⇒ b C A C` | a C`
C`⇒ C A C A C` | ε

The resulting grammar will be-

A ⇒ B C
B ⇒ C A | b
C ⇒ b C A C' |  a C'
C' ⇒ε | A C A C'

In this way, we can remove indirect left recursion from our grammar

Code Implementation

• C++
• Java
• Python

C++

#include <iostream>
#include <string>

void eliminateLeftRecursion(const std::string& production) {
    std::cout << "Original Production: " << production << std::endl;

    std::string alpha = production.substr(2); // Aα
    std::string beta = production.substr(4);  // β

    std::cout << "Transformed Productions:\n";
    std::cout << "A → " << beta << "A'\n";
    std::cout << "A' → " << alpha << "A' | ε\n"; // A' is the new non-terminal
}

int main() {
    std::string production = "A → Aα | β";
    eliminateLeftRecursion(production);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

public class LeftRecursionElimination {

    public static void eliminateLeftRecursion(String production) {
        System.out.println("Original Production: " + production);

        String alpha = production.substring(3, production.indexOf('|')).trim(); // Aα
        String beta = production.substring(production.indexOf('|') + 1).trim();  // β

        System.out.println("Transformed Productions:");
        System.out.println("A → " + beta + "A'");
        System.out.println("A' → " + alpha + "A' | ε"); // A' is the new non-terminal
    }

    public static void main(String[] args) {
        String production = "A → Aα | β";
        eliminateLeftRecursion(production);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def eliminate_left_recursion(production):
    print(f"Original Production: {production}")

    alpha = production[3:production.index('|')].strip()  # Aα
    beta = production[production.index('|') + 1:].strip()  # β

    print("Transformed Productions:")
    print(f"A → {beta}A'")
    print(f"A' → {alpha}A' | ε")  # A' is the new non-terminal

if __name__ == "__main__":
    production = "A → Aα | β"
    eliminate_left_recursion(production)

You can also try this code with Online Python Compiler

Run Code

Output

Original Production: A → Aα | β
Transformed Productions:
A → βA'
A' → αA' | ε

Must Read Recursion in Data Structure

Frequently Asked Questions

What is the difference between left recursion and left factoring?

Left recursion occurs when a non-terminal in a grammar directly or indirectly refers to itself at the start of its production, causing infinite recursion. Left factoring is a technique to transform a grammar to remove ambiguity by factoring out common prefixes, aiding in top-down parsing.

In which phase of the compiler do we encounter left recursion?

Left recursion occurs and is encountered during the syntax analysis phase of the compiler design. It is the second phase of the compiler design. In this phase of the compiler, parsing of the syntax is done. It is done to ensure that the syntax is correct.

What is a left recursive rule?

A left recursive rule occurs when a grammar rule refers to itself at its beginning, creating loops in parsing. For example, in "A -> A something," the non-terminal "A" appears leftmost.

What are the disadvantages of left recursion?

There are several disadvantages of left recursion. It can trigger infinite loops during parsing due to self-reference, stalling the process. It also can complicates parsing, demanding more resources and making it less efficient. 

Conclusion

In this article, we have discussed what left recursion is in compiler design. In compiler design, addressing left recursion is crucial for enabling efficient top-down parsing methods. By transforming left-recursive grammars into right-recursive forms or employing other techniques like left factoring, we can ensure that parsers can correctly and efficiently process input.

Also, check out some of the Guided Paths and some Interview Experiences curated by top Industry Experts only on Code360.