3

The following grammar has left recursion.

X is the start simbol.

X -> Xa | Zb
Z -> Zc | d | Xa

How to remove it? Please explain it step by step.

david_slb
  • 43
  • 4
  • 3
    [How to Eliminate Left recursion in Context-Free-Grammar](http://stackoverflow.com/questions/14033250/left-recursion-elimination/14041093#14041093) First consider `Z` then `X`. – Grijesh Chauhan Jun 17 '13 at 04:35

1 Answers1

3
-- remove Z left recursion--

X -> Xa | Zb
Z -> dZ' | XaZ'
Z' -> cZ' | empty

--next remove Z --

X -> Xa | dZ'b | XaZ'b
Z' -> cZ' | empty

--next factorize X--

X -> XaX' | dZ'b
X'-> Z'b | empty
Z'-> cZ' | empty

--next remove X recursion--

X -> dZ'bX''
X'' -> a X'X'' | empty
X' -> Z'b | empty
Z' -> cZ' | empty
gn66
  • 803
  • 2
  • 12
  • 33