regex - 文脈自由文法で左再帰をなくすには?

Question

この CFG で左再帰を削除するにはどうすればよいですか?

<RE> -> <RE>'|'<CONCAT> | <CONCAT>
<CONCAT> -> <CONCAT><KLEEN> | <KLEEN>
<KLEEN> -> <KLEEN>'*' | <ELEM>
<ELEM> -> 'a' | 'b' | 'c' | 'd' | '('<RE>')'

Answer 1

ウィキペディアの左再帰の削除に関するセクションをご覧ください。

以下に、正確な方法の説明があります。

ムーア、ロバート C. (2000 年 5 月)。「文脈自由文法からの左再帰の削除」 . 第 6 回応用自然言語処理会議: 249–255。http://aclweb.org/anthology-new/A/A00/A00-2033.pdf .