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' | ε
Please start posting anonymously - your entry will be published after you log in or create a new account. This space is reserved only for answers. If you would like to engage in a discussion, please instead post a comment under the question or an answer that you would like to discuss
Asked: 2022-12-22 11:00:00 +0000
Seen: 10 times
Last updated: May 29 '21
Is it not possible to open a STEP file in Inventor AutoDesk?
How can I successfully install Firebase tools CLI on Windows 10?
How can I effectively implement my first method and verify the outcome of each step?
Why is the settling time not visible on the step response diagram?