SLR(1)

[ciuf_ciuf]

Salve, chiedo aiuto per un piccolo dubbio che ho riscontrato mentre svolgevo un esercizio. Ho questa grammatica

Codice:

S -> rAIStI
A -> aA | epsilon
I-> iI | epsilon


e si chiede di verificare se si tratta di una grammatica di tipo SLR(1).
Dopo aver costruito tutti gli stati per LR(0), mi preparo ad analizzare tutti quelli che presentano conflitti di Riduzione/Spostamento all'interno dello stesso stato calcolando i Follow per le riduzioni e i First per gli spostamenti. Ad esempio uno stato che presenta questi conflitti è il seguente:

Codice:

S -> r . AIStI
A-> . aA
A-> .


Adesso arriva il problema, calcolo per gli spostamenti:

Codice:

First(AIStI) U First(aA) = {a}

e fin qui tutto ok
Invece per la riduzione bisogna calcolare (secondo quello che conoscevo):

Codice:

Follow(A) = First(I) = {i} U Follow(I) = {i} U First(S) U Follow(S) =  {i} U {r} U {$,t} = {i,r,$,t}

se vado però a controllare lo svolgimento dell'esercizio vedo che come Follow(A) hanno considerato soltanto {i,r}, inoltre se utilizzo questi generatori automatici
http://galileo.dmi.unict.it/utenti/reve ... oreparser/
http://hackingoff.com/compilers/predict ... follow-set
il Follow di A viene calcolato in maniera diversa, per uno è soltanto {i} per l'altro è {i,r}. Quindi a questo punto sono entrato in confusione e non sapevo più a chi credere . Se qualcuno è in grado di aiutarmi mi faccia sapere.
Grazie e spero in qualche risposta.

[Rggb]

Vado a rimembranze di roba fatta eoni fa, comunque

Codice:

Follow(A) = First(I) = {i} U Follow(I) = {i} U First(S) U Follow(S) =  {i} U {r} U {$,t} = {i,r,$,t}

Non mi torna... perchè unisci Follow(S)? Qual è la definizione che hai di "insieme Follow"?

se vado però a controllare lo svolgimento dell'esercizio vedo che come Follow(A) hanno considerato soltanto {i,r}

Mi torna, e torna anche con JFLAP. Verifica con quello
http://www.jflap.org/

[ciuf_ciuf]

Vado a rimembranze di roba fatta eoni fa, comunque

Codice:

Follow(A) = First(I) = {i} U Follow(I) = {i} U First(S) U Follow(S) =  {i} U {r} U {$,t} = {i,r,$,t}

Non mi torna... perchè unisci Follow(S)? Qual è la definizione che hai di "insieme Follow"?

se vado però a controllare lo svolgimento dell'esercizio vedo che come Follow(A) hanno considerato soltanto {i,r}

Mi torna, e torna anche con JFLAP. Verifica con quello
http://www.jflap.org/

Regole per il Follow:

regola 1- Il Follow(S) se S è l'assioma deve contenere 'dollaro'
regola 2- Il Follow(S) se S è un simbolo che sta in produzioni del tipo A -> $ alpha $S$beta $ deve contenere i First($beta$) - $ epsilon $
regola 3- Il Follow(S) se S è un simbolo che sta in produzioni del tipo A-> $ alpha $S oppure in produzioni del tipo A -> $ alpha $S$beta $ dove il First($beta $) contiene $ epsilon $ $ rArr $ tutti i simboli di Follow(A) devono essere inseriti nel Follow(S)

Quindi io ho ragionato così, per il Follow(A) applico la seconda regola alla produzione(S->rAIStI) e quindi calcolo i First(I).
I First(I) sono {i,epsilon} quindi prendo i e a causa di epsilon, per la terza regola, sono costretto a calcolare il Follow(I).
Il Follow(I) lo calcolo applicando sia la seconda regola, sia la terza regola(produzioni del tipo A-> $ alpha $S) alla produzione (S->rAIStI). Quindi significa che devo calcolare il First(S) che è {r} e il Follow(S) che contiene {$,t} riapplicando nuovamente le varie regole.

Bo, io non capisco dov'è che sbaglio.

[Rggb]

Quindi io ho ragionato così, per il Follow(A) applico la seconda regola alla produzione(S->rAIStI) e quindi calcolo i First(I).

Forse ho capito., secondo me sbagli nel calcolare FIRST(). Infatti hai
$FOLLOW(A)=FIRST(\I\S\t\I)={i} uu FIRST(\S\t\I)={i, r}$

Dà un'occhiata a queste dispense, secondo me molto chiare (sono segnalate nell'apposita sezione):
http://www.cs.nuim.ie/~jpower/Courses/Previous/parsing/

[ciuf_ciuf]

Quindi io ho ragionato così, per il Follow(A) applico la seconda regola alla produzione(S->rAIStI) e quindi calcolo i First(I).

Forse ho capito., secondo me sbagli nel calcolare FIRST(). Infatti hai
$FOLLOW(A)=FIRST(\I\S\t\I)={i} uu FIRST(\S\t\I)={i, r}$

Questo ragionamento è quello che ho fatto subito anche io quando ho visto che il mio risultato non coincideva con quello degli altri, però poi pensandoci meglio mi sono ricordato che l'operazione di slittamento dovuto all'epsilon viene fatto quando si calcolano i Predict delle produzioni e non i Follow, o almeno io so così. Comunque probabilmente l'errore è questo, anche se la cosa non mi torna.

Dà un'occhiata a queste dispense, secondo me molto chiare (sono segnalate nell'apposita sezione):
http://www.cs.nuim.ie/~jpower/Courses/Previous/parsing/

Oggi le guardo. Grazie

[Rggb]

Comunque probabilmente l'errore è questo, anche se la cosa non mi torna.

Cosa è che non ti torna?

[ciuf_ciuf]

Non mi torna perchè come ho detto nella risposta precedente l'operazione di slittamento, dovuto ad epsilon, viene fatto in caso di calcolo dei Predict o nel caso di calcolo di First che non derivi però dal calcolo di un Follow. Perchè nel calcolo dei Follow quando si incontra un epsilon bisogna applicare la regola opportuna, se faccio lo slittamento è come se ignorassi la regola 3.