题
我想从这些规则中删除间接左递归:
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”字样),而第二语言是空的。
不隶属于 cs.stackexchange