removendo a recursão indireta à esquerda
-
29-09-2020 - |
Pergunta
Quero remover a recursão indireta à esquerda destas regras:
S-->TU,
T-->US|b,
U-->ST|a
Não sei se consigo implementar o algoritmo corretamente.Minha suposição é fazer assim:
S-->TU, T-->U'b, U'b-->U'a
Isso está correto?
Solução
É tedioso...Espero não ter cometido um erro...
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
Ao substituir todas as possibilidades de T e U você pode remover os não-Terminais na frente das expressões para X, Y e S.
Outras dicas
Não.O primeiro idioma não está vazio (por exemplo, contém a palavra "ba"), enquanto o segundo idioma está vazio.
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange