如何消除上下文無關語法中的左遞歸？

Question

如何消除此CFG中的左遞歸？

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

Answer 1

查看維基百科上有關Removing Left Recursion的部分。

Theres描述瞭如何做到這一點，以下;

Moore，Robert C.（2000年5月）。 「從上下文無關文法中去除左遞歸」。第六屆應用自然語言處理會議：249-255。 http://aclweb.org/anthology-new/A/A00/A00-2033.pdf。