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

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

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

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

是正确的吗?

有帮助吗?

解决方案

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

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的前面的非终端。

其他提示

否。第一个语言是非空的(例如,它包含“BA”字样),而第二语言是空的。

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top