regex - 如何消除上下文无关语法中的左递归？

Question

我将如何消除此 CFG 中的左递归？

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

Answer 1

查看Wikipedia上有关删除左递归的部分。

有一个关于如何做到这一点的描述，如下;

Moore, Robert C.（2000 年 5 月）。“从上下文无关语法中删除左递归”。第六届应用自然语言处理会议：249-255。http://aclweb.org/anthology-new/A/A00/A00-2033.pdf。