Revision history [back]

The process for eliminating left recursion in a grammar that contains both left and right recursion can be done in the following steps:

Step 1: Identify the left recursive productions i.e. the productions that start with the same non-terminal symbol.

Step 2: Replace the left recursive productions with new non-terminals and new productions that do not have left recursion.

Step 3: Reorder the new productions so that the non-left recursive productions come before the left-recursive productions.

Step 4: Eliminate any remaining left recursion using the same process as step 2.

Step 5: Remove any unit productions that may have been created during the process.

Example:

Consider the following grammar:

A → Aa | bA | cB B → Bc | dB | ε

This grammar has both left and right recursion.

Step 1: The left recursive productions are A → Aa and B → Bc.

Step 2: Replace the left recursive productions with new non-terminals.

A → bA' | cB A' → aA' | ε B → dB | ε

Step 3: Reorder the productions so that the non-left recursive productions come before the left-recursive productions.

A → cB | bA' A' → aA' | ε B → dB | ε

Step 4: Eliminate any remaining left recursion using the same process as step 2.

A → cB | bA' A' → aA' | ε B → dBB' | ε B' → cB' | ε

Step 5: Remove any unit productions that may have been created during the process.

A → cB | bA' A' → aA' | ε B → dBB' | ε B' → cB' | ε