written 8.5 years ago by | • modified 4.1 years ago |
S => XA | BB - B => b | SB - X => b - A => a -
written 8.5 years ago by | • modified 4.1 years ago |
S => XA | BB - B => b | SB - X => b - A => a -
written 8.5 years ago by |
Step 1: Rename variables
Let S be $A_1$, X be $A_2$, A be $A_3$ and B be $A_4$
Therefore, the grammar now becomes
$A_1 =\gt A_2A_3 \ | \ A_4A_4$
$A_4 =\gt b \ | \ A_1A_4$
$A_2 =\gt b$
$A_3 =\gt a$
Step 2 : For each $A_i =\gt A_j$, ensure i <= j
This is not satisfied by $A_4 =\gt A_1A_4$
Replace $A_1 =\gt A_4A_4$
Hence, we get
$A_4 =\gt A_4A_4 A_4 | b$
Step 3: Remove left recursion, which is not satisfied by $A_4 =\gt A_4A_4 A_4$
Let $B_4 =\gt A_4A_4 A_4 \ | \ A_4A_4 A_4B_4$
Therefore, we get
$A_4 =\gt bB_4$
So left recursion has been removed
Step 4: Get all productions into GNF
Consider $B_4 =\gt A_4A_4 A_4 \ | \ A_4A_4 A_4B_4$
Replacing $A_4 =\gt bB_4$ , which is already in GNF, we get
$B_4 =\gt bB_4 A_4A_4 A_4 \ | \ bB_4A_4A_4B_4$, which is now in GNF
The remaining productions are already in GNF