Grammatica LL(1)

[alessia86]

Qualcuno sa dirmi se una regola del tipo T->aGs/T , T sia una ricorsione sinistra o destra??
Grazie

[Vincenzo1968]

È destra.

Nella ricorsione destra, il non terminale specificato nella testa della produzione(nel tuo esempio, T), si trova, nel corpo della produzione, alla fine(è, appunto, il terminale più a destra):

T -> aGs/T , T

Nella ricorsione a sinistra, invece, il non terminale si trova, nel corpo della produzione, all'inizio. Per esempio:

T-> TaGs

è ricorsiva a sinistra.

La ricorsione a sinistra va sempre eliminata per i parser di tipo LL(k). Si può trasformare una produzione ricorsiva a sinistra in una ricorsiva a destra modificando la grammatica(il simbolo 'e' indica la stringa vuota):

T = T'
T' -> aGsT' | e

[alessia86]

Grazie mille.. Quindi trattandosi di una ricorsione destra,e siccome io devo produrre una grammatica del tipo LL(1), non c'è bisogno di eliminarla vero? :stordita:

[Vincenzo1968]

Esatto.

La ricorsione sinistra porterebbe il parser in un loop infinito. La ricorsione destra, invece, non comporta alcun problema per i parser top-down(con grammatiche, quindi, di tipo LL(k)).

;)

[alessia86]

ok..ci sono...Mentre,un ultima domanda..Se la regola era T->T/aGs...in questo caso si trattava di ricorsione sinistra,vero?

[Vincenzo1968]

Si,

perché il non terminale T è il primo simbolo(quello più a sinistra) nel corpo della produzione T->T/aGs.

EDIT:
Occhio, non sempre la ricorsione a sinistra è immediata. Per esempio,

T -> ATcbS
A -> b | e

Nella grammatica precedente, T non compare come simbolo più a sinistra nella produzione T -> ATcbS; tuttavia si tratta di una produzione ricorsiva a sinistra perchè il non terminale A deriva la stringa vuota(indicata dal simbolo 'e').

[alessia86]

ho capito..grazie mille..mi sei stato davv d'aiuto :)