Left Recursion (LR) and Left Factoring (LF)

Introduction

Left Recursion (LR) and Left Factoring (LF) are two important concepts in compiler design related to grammar transformation. Left Recursion occurs when a non-terminal in a grammar rule refers to itself as the first symbol, causing issues in recursive descent parsers. Left Factoring is used to transform a grammar when multiple productions share a common prefix, helping in predictive parsing. 

In this article, we will learn the differences between Left Recursion and Left Factoring with examples.

1. Left Recursion

In formal grammar, left recursion occurs when a non-terminal symbol appears on the leftmost side of its own production rule. This can cause issues in top-down parsers, particularly recursive descent parsers, leading to infinite recursion.

1.1 Why Is Left Recursion a Problem?

When using recursive descent parsing, a left-recursive grammar leads to an infinite loop, making it impossible for the parser to terminate. This happens because the parser keeps expanding the leftmost non-terminal indefinitely without reaching a terminal symbol.

Example of Left Recursion

Consider the following grammar:

A -> Aα | β

Here, A calls itself at the beginning, making it left-recursive. If we try to parse using recursive descent, it keeps calling itself indefinitely.

Example (Problem Demonstration)

# This function enters an infinite loop due to left recursion
def left_recursive_parser():
    print("Calling A")
    left_recursive_parser()  # Recursive call without termination
# Uncommenting this will result in infinite recursion
# left_recursive_parser()

Since the function keeps calling itself without a base condition, it results in infinite recursion.

1.2 How to Eliminate Left Recursion?

To convert a left-recursive grammar into a non-left-recursive form, we follow a transformation process:

1. Identify the left-recursive production rule: A -> Aα | β
    
2. Replace it with:

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

Example of Left Recursion Elimination

Original Grammar

S -> S a | b

Transformed Grammar:

S -> b S'
S' -> a S' | ε

Example (Fixed Version)

def non_left_recursive_parser(input_string):
    if input_string.startswith("b"):
        print("Valid string starting with 'b'")
        remainder = input_string[1:]
        while remainder.startswith("a"):
            print("Processing 'a'")
            remainder = remainder[1:]
        print("Parsing complete")
    else:
        print("Invalid string")
# Example usage
non_left_recursive_parser("baaa")

You can also try this code with Online Python Compiler

Run Code

Output:

Valid string starting with 'b'
Processing 'a'
Processing 'a'
Processing 'a'
Parsing complete