Rimozione della ricorsione a sinistra indiretta
-
29-09-2020 - |
Domanda
Voglio rimuovere la ricorsione a sinistra indiretta da queste regole:
S-->TU,
T-->US|b,
U-->ST|a
.
Non so se posso implementare correttamente l'algoritmo.La mia ipotesi è renderlo così:
S-->TU, T-->U'b, U'b-->U'a
.
è corretto?
Soluzione
È noioso ... Spero di non aver commesso un errore ...
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
.
Per sostituzione di tutte le possibilità di T e U puoi rimuovere i non terminali nella parte anteriore delle espressioni per X, Y e S.
Altri suggerimenti
no.La prima lingua non è vuota (ad esempio, contiene la parola "BA"), mentre la seconda lingua è vuota.
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange