Parsing: Parser Predittivi, Funzione Follow
Spero che qualcuno conosca l'argomento e mi possa spiegare come funziona la funzione Follow per il parsing predittivo.
Allora per un grammatica:
$E->TA
$A->+TA|epsilon
$T->FB
$B->*FB|epsilon
$F->(E)|id
so che ad esempio:
FOLLOW(A)={),&}
FOLLOW(B)={+,),&}
Ma non ho capito come lo calcolo.
Allora per un grammatica:
$E->TA
$A->+TA|epsilon
$T->FB
$B->*FB|epsilon
$F->(E)|id
so che ad esempio:
FOLLOW(A)={),&}
FOLLOW(B)={+,),&}
Ma non ho capito come lo calcolo.
Risposte
[ Definizione
Dato $X in N$, si ha
$\FOLLOW(X) = { t\ |\ t in T\ ^^\ S rArr^+ uXtv, u,v in V^(**)}$
dove $T$ è l'insieme dei terminali (compreso $epsilon$) , $N$ dei non terminali, $V=T uu N$ e $S$ lo start-symbol. ]
Nella tua grammatica di esempio lo start-symbol sarebbe $E$. Spero la formula si legga bene. A parole, FOLLOW(X) è l'insieme di tutti i simboli terminali che possono apparire "a seguire" il non terminale X in una derivazione.
Io sono andato sempre "ad occhio", facendo le sostituzioni possibili, in quanto in genere sono esercizi semplici; ma forse ti conviene calcolarti prima FIRST(X). Ti lascio un riferimento utile:
http://www.cs.nuim.ie/~jpower/Courses/P ... ode48.html
di James Power. Ciò mi ricorda che non ho segnalato nulla su questi argomenti nell'apposita sezione, cercherò di rimediare.
Dato $X in N$, si ha
$\FOLLOW(X) = { t\ |\ t in T\ ^^\ S rArr^+ uXtv, u,v in V^(**)}$
dove $T$ è l'insieme dei terminali (compreso $epsilon$) , $N$ dei non terminali, $V=T uu N$ e $S$ lo start-symbol. ]
Nella tua grammatica di esempio lo start-symbol sarebbe $E$. Spero la formula si legga bene. A parole, FOLLOW(X) è l'insieme di tutti i simboli terminali che possono apparire "a seguire" il non terminale X in una derivazione.
Io sono andato sempre "ad occhio", facendo le sostituzioni possibili, in quanto in genere sono esercizi semplici; ma forse ti conviene calcolarti prima FIRST(X). Ti lascio un riferimento utile:
http://www.cs.nuim.ie/~jpower/Courses/P ... ode48.html
di James Power. Ciò mi ricorda che non ho segnalato nulla su questi argomenti nell'apposita sezione, cercherò di rimediare.
Il first non mi da problemi:
FIRST(E)={ (, id }
FIRST(A)={ +, $epsilon$}
FIRST(T)={ (, id }
FIRST(B)={$*$, $epsilon$}
FIRST(F)={ (, id }
Non ho capito che domande ti poni quando fai il follow di E ad esempio; sicuramente ci metti & perchè va nel follow del simbolo iniziale,
poi controlli nella grammatica dove riappare E,($F->(E)|id$) ok a questo punto che hai trovato in quali produzione c'è E che operazioni fai?
FIRST(E)={ (, id }
FIRST(A)={ +, $epsilon$}
FIRST(T)={ (, id }
FIRST(B)={$*$, $epsilon$}
FIRST(F)={ (, id }
Non ho capito che domande ti poni quando fai il follow di E ad esempio; sicuramente ci metti & perchè va nel follow del simbolo iniziale,
poi controlli nella grammatica dove riappare E,($F->(E)|id$) ok a questo punto che hai trovato in quali produzione c'è E che operazioni fai?
Usando gli insiemi $\FIRST$ è molto semplice calcolare gli insiemi $\FOLLOW$, vedi in particolare il link che ti ho postato, faccio una traduzione al volo:
1) per lo start-symbol $S$, metti \$ in $\FOLLOW(S)$
2) per ogni produzione $A -> alpha\ X\ beta$
-- metti i simboli di $\FIRST(beta)$ in $\FOLLOW(X)$
-- se da $beta$ si può derivare la stringa vuota $epsilon$, metti i simboli di $\FOLLOW(A)$ in $\FOLLOW(X)$
dove \$ indica il simbolo di fine stringa.
Il metodo che uso io, "ad occhio", è forse più veloce, ma solo secondo me; e ovviamente dipende da quanti esercizi fai o devi fare.
[ Nel tuo esempio in $\FOLLOW(E)$ ci va sicuramente '\$' ($E$ è iniziale) e anche ')', infatti esiste una derivazione $F->(E)$ ed in questa derivazione dopo il simbolo 'E' c'è il simbolo ')'. Poi noto che esiste $E->TA$ e quindi ')' è un "seguente" anche del simbolo $A$, e quindi lo aggiungo a $\FOLLOW(A)$ e proseguo... ]
Senza volerti complicare la vita, se usi l'algoritmo illustrato sopra non puoi sbagliare.
1) per lo start-symbol $S$, metti \$ in $\FOLLOW(S)$
2) per ogni produzione $A -> alpha\ X\ beta$
-- metti i simboli di $\FIRST(beta)$ in $\FOLLOW(X)$
-- se da $beta$ si può derivare la stringa vuota $epsilon$, metti i simboli di $\FOLLOW(A)$ in $\FOLLOW(X)$
dove \$ indica il simbolo di fine stringa.
Il metodo che uso io, "ad occhio", è forse più veloce, ma solo secondo me; e ovviamente dipende da quanti esercizi fai o devi fare.
[ Nel tuo esempio in $\FOLLOW(E)$ ci va sicuramente '\$' ($E$ è iniziale) e anche ')', infatti esiste una derivazione $F->(E)$ ed in questa derivazione dopo il simbolo 'E' c'è il simbolo ')'. Poi noto che esiste $E->TA$ e quindi ')' è un "seguente" anche del simbolo $A$, e quindi lo aggiungo a $\FOLLOW(A)$ e proseguo... ]
Senza volerti complicare la vita, se usi l'algoritmo illustrato sopra non puoi sbagliare.
allora incominciamo dal FOLLOW(E)
è il simbolo iniziale ci va &, poi controllo in che produzione appare.
$F->(E)|id$ dunque la regola da applicare è
quindi in questo caso )
non è questo il caso quindi FOLLOW(E)={&,)}
FOLLOW(A)
Lo ritrovo nelle produzioni:
$E->TA
$A->+TA|epsilon
La regola non la posso applicare perchè non c'è nè un terminale ne una variabile a seguire la A, come mi comporto?
è il simbolo iniziale ci va &, poi controllo in che produzione appare.
$F->(E)|id$ dunque la regola da applicare è
per ogni produzione $A-> alpha X beta$ metti $FIRST(beta)$ in $FOLLOW(X)$
quindi in questo caso )
se da $beta$ puoi derivare la stringa vuota $epsilon$ metti i simboli di $FOLLOW(A)$ in $FOLLOW(X)$
non è questo il caso quindi FOLLOW(E)={&,)}
FOLLOW(A)
Lo ritrovo nelle produzioni:
$E->TA
$A->+TA|epsilon
La regola non la posso applicare perchè non c'è nè un terminale ne una variabile a seguire la A, come mi comporto?
Forse si capisce meglio qui, fra l'altro è in italiano (e redatto bene):
http://www.cs.unicam.it/tesei/didattica ... 4Total.pdf
vedi a pagina 86 e seguenti.
Nel tuo caso: tutto ciò che è in $\FOLLOW(E)$ va in $\FOLLOW(A)$, quindi $\FOLLOW(A)={'&', ')'}$ (uso la tua notazione con & per fine-stringa).
PS. Ma fai sta roba sempre a notte fonda?
http://www.cs.unicam.it/tesei/didattica ... 4Total.pdf
vedi a pagina 86 e seguenti.
Nel tuo caso: tutto ciò che è in $\FOLLOW(E)$ va in $\FOLLOW(A)$, quindi $\FOLLOW(A)={'&', ')'}$ (uso la tua notazione con & per fine-stringa).
PS. Ma fai sta roba sempre a notte fonda?
Ok ho capito dove sbagliavo,
1)se la variabile di cui faccio il follow è iniziale ci metto il & o il dollaro
2)controllo in che produzioni appare il simbolo in questione (X), se è in una produzione $A->alpha X beta$
metto in follow di X il first di $beta$ ma non il simbolo $epsilon$, se poi nel first di $beta$ c'è effettivamente $epsilon$ aggiungo al follow di X il Follow di A
se invece la produzione appare come $A->alpha X$ metto nel follow di X il follow di A.
quindi risulta
FOLLOW(E)={&,)}
FOLLOW(A)={&)}
FOLLOW(T)={+,&,)}
FOLLOW(B)={+,&,)}
FOLLOW(F)={*,+,&,)}
Perchè rimando sempre all'ultimo momento, e di notte si studia meglio.
1)se la variabile di cui faccio il follow è iniziale ci metto il & o il dollaro
2)controllo in che produzioni appare il simbolo in questione (X), se è in una produzione $A->alpha X beta$
metto in follow di X il first di $beta$ ma non il simbolo $epsilon$, se poi nel first di $beta$ c'è effettivamente $epsilon$ aggiungo al follow di X il Follow di A
se invece la produzione appare come $A->alpha X$ metto nel follow di X il follow di A.
quindi risulta
FOLLOW(E)={&,)}
FOLLOW(A)={&)}
FOLLOW(T)={+,&,)}
FOLLOW(B)={+,&,)}
FOLLOW(F)={*,+,&,)}
"Rggb":
PS. Ma fai sta roba sempre a notte fonda?
Perchè rimando sempre all'ultimo momento, e di notte si studia meglio.
Mi sembra torni tutto 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo