recursion - CFG からの左再帰の削除

Question

次の文法は左再帰を持っています:

T -> Tx | TYx | YX | x
X -> xx
Y -> Yy | Yx | y

左再帰を削除するにはどうすればよいですか。ウィキペディアの説明を読みましたが、CFG にはかなり慣れていないので、あまり意味がありませんでした。何か助けていただければ幸いです。平易な英語の説明はさらに高く評価されます。

Answer 1

この例では、Robert C. Mooreの一般的なアルゴリズムに従って、左再帰のルールを右再帰のルールに変換できます。

A -> A a1 | A a2 | ... | b1 | b2 | ...
# converts to
A  -> b1 A' | b2 A' | ...
A' -> e | a1 A' | a2 A' | ...                 # where e = epsilon

私たちの最初のケースでは： A=T, a1=x, a2=Yx, b1=y, b2=x ...（同様にY）

T  -> YXT' | xT'
T' -> e | xT' | YxT'
X  -> xx
Y  -> yY'
Y' -> e | yY' | xY'