Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
eliminate left recursion
6
Eliminate Left Recursion
Thank You!
Left recursive
Why it is needed
Grammar is said to be a left recursive if the leftmost(non-terminal) variable of its RHS is same as (non-terminal)variable of its LHS.
For example:
S → S / a / b
Where S is non-terminal and a, and b are any set of terminals.
Top-down parsing cannot handle left recursive grammars.
We need to preform Eliminate Left Recursion to make an equivalent grammar which is not left recursive.
An example for direct eliminate left recursion
Direct
Grammar:
E → E + E / E x E / a
Step 1:
Add a new non-terminal (E')variable to all productions at the end
E → E + E E' / E x E E' / a E'
Step 2:
Take the left recursive productions and add them to the new non-terminal (E') then delete them from the original one (E). Lastly, add epsilon production to (E').
E → aE'
E'→ + E E'/ x EE' /epsilon
Example 1
Grammar:
S → A
A → Ad / Ae / aB / ac
B → bBc / f
The grammar after eliminating left recursion:
S → A
A → aBA’ / acA’
A’ → dA’ / eA’ / epsilon
B → bBc / f
Example 2
Grammar:
S → S0S1S / 01
The grammar after eliminating left recursion:
S → 01A
A → 0S1SA / epsilon
An example for indirect eliminate left recursion
Indirect
Grammar:
A → Ba / Aa / c
B → Bb / Ab / d
Follow the step to solve the problem !
A → BaA’ / cA’
A’ → aA’ / epsilon
B → cA’bB’ / dB’
B’ → bB’ / aA’bB’ / epsilon
The above grammar is the final grammar after eliminating left recursion.
Step 1
Step 1
First let us eliminate left recursion from A → Ba / Aa / c
After eliminating left recursion we get:
A → BaA’ / cA’
A’ → aA’ / epsilon
Now the grammar becomes:
A → BaA’ / cA’
A’ → aA’ / epsilon
B → Bb / Ab / d
Step 2
Substituting the productions of A in B → Ab, we get the following grammar:
A → BaA’ / cA’
A’ → aA’ / epsilon
B → Bb / BaA’b / cA’b / d
Step 3
Eliminating left recursion from the productions of B, we get the following grammar:
A → BaA’ / cA’
A’ → aA’ / epsilon
B → cA’bB’ / dB’
B’ → bB’ / aA’bB’ / epsilon
Example 1
Example 1
Grammer :
X → XSb / Sa / b
S → Sb / Xa / a
Step 1:
First eliminate left recursion from X → XSb / Sa / b
X → SaX’ / bX’
X’ → SbX’ / epsilon
S → Sb / Xa / a
Step 2:
Substituting the productions of X in S → Xa
X → SaX’ / bX’
X’ → SbX’ / epsilon
S → Sb / SaX’a / bX’a / a
Step 3:
Eliminating left recursion from the productions of S
X → SaX’ / bX’
X’ → SbX’ / epsilon
S → bX’aS’ / aS’
S’ → bS’ / aX’aS’ / epsilon
Example 2
Example 2
Grammar:
S → Aa / b
A → Ac / Sd / epsilon
Step 1:
First eliminate left recursion from S → Aa / b
This is already free from left recursion.
Step 2:
Substituting the productions of S in A → Sd
S → Aa / b
A → Ac / Aad / bd / epsilon
Step 3:
Eliminating left recursion from the productions of A
S → Aa / b
A → bdA’ / A’
A’ → cA’ / adA’ / epsilon
Some references that will help you!
References
1- https://youtu.be/WdnzcvQZkSU
2- https://youtu.be/CqDMI1tKSyM
3- https://www.gatevidyalay.com/left-recursion-left-recursion-elimination/
4- https://www.geeksforgeeks.org/removing-direct-and-indirect-left-recursion-in-a-grammar/