parsing - 消除这种间接左递归

Question

下面的文法有左递归。

X 是起始符号。

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

如何删除它？请逐步解释。

Answer 1

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