Eliminate this indirect left recursion

3
votes

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.

1
parsingcompiler-constructiongrammarcomputation-theory
How to Eliminate Left recursion in Context-Free-Grammar First consider Z then X. – Grijesh Chauhan

1 Answers

3
votes
-- 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