删除间接左递归

Question

我想从这些规则中删除间接左递归：

    S-->TU,
    T-->US|b,
    U-->ST|a

.

我不知道我是否可以正确地实现算法。我的假设是这样做：

S-->TU, T-->U'b, U'b-->U'a

.

是正确的吗？

Answer 1

这是古怪的......我希望我没有犯错误...

S->TU
T->US|b
U->ST|a

1.
S->TU
T->U(TU)|b 
U->(TU)T|a

2.
S->TU
T->aTU|(TUT)TU|b 
U->bUT|(UTU)UT|a

3. * is regex for "repeated 0 or more times"
S->TU
T->aTU|T(UTTU)*|b 
U->bUT|U(TUUT)*|a

4.
S->TU
T->aTU|aTUX|bX|b 
U->bUT|bUTY|aY|a

X->UTTUX|UTTU
Y->TUUTY|TUUT

.

通过替换所有T和U的可能性，您可以在表达式前面删除x，y和s的前面的非终端。

Answer 2

否。第一个语言是非空的（例如，它包含“BA”字样），而第二语言是空的。