LABORATORIO DI LINGUAGGI
Anno accademico 2004/2005
An Extension of Earley’s Algorithm
for S-Attributed Grammars
- Nelson Correa -
Massimiliano Barletta 802646
Massimo Rabbi 799761
Introduzione
• L’articolo propone una modifica al classico
algoritmo di Earley (1970): lo scopo è
combinare analisi sintattica e semantica.
• Considerando in particolare il caso di
grammatiche S-attribuite
• Condizione di terminazione dell’algoritmo:
assenza di cicli
Proposte
• Alcune proposte di soluzione al problema
della valutazione di grammatiche attribuite
sono inefficienti dal punto di vista
computazionale:
• Watt, Jones and Madsen (1980)
• Pereira e Warren (1983)
• Shieber (1985)
• Yellin (1988)
Definizione di Grammatica ad Attributi
• Può essere sintetizzata con AG = (G,A,R,B)
I. G = (N,T,P,S) è una grammatica context-free.
II. A insieme finito di attributi A(X) con X simbolo
terminale o non terminale.
III. R insieme finito di regole per gli attributi R(p)
dove p è produzione per la grammatica.
IV. B insieme finito di condizioni per gli attributi B(p)
dove p è produzione per la grammatica.
• Ogni nodo X dell’albero viene etichettato con
l’insieme degli attributi ad esso associati.
Attributi ereditati e sintetizzati
• Attributi sintetizzati:
– Il valore degli attributi sintetizzati ad ogni
nodo x è calcolato a partire dai valori degli
attributi dei nodi figli di x nel parse tree
• Attributi ereditati:
– Il valore degli attributi ereditati è ad ogni
nodo x è calcolato a partire dai valori degli
attributi dei nodi fratelli e del nodo padre di
x
• Una grammatica è S-attribuita se contiene
solo attributi SINTETIZZATI
Richiamo all‘algoritmo di Earley
•
•
•
•
E’ un algoritmo di parsing tabulare
Algoritmo di tipo Top-Down
Input percorso da sinistra verso destra
Possibilità di gestire CFG anche ambigue
• E’ possibile vedere l’algoritmo come un insieme
di chiamate sequenziali a tre funzioni particolari:
• Predictor
• Completer
• Scanner
Nel dettaglio (1)
• PREDICTOR
• Si applica nel caso in cui:
si incontri un suffisso nella forma
Aα·Bβ,i
allora si cerchi tra le produzioni
Bγ
e per ognuno di essi si aggiunga il suffisso
B·γ,j
a meno che questi non sia già presente.
Nel dettaglio (2)
• COMPLETER
• Si applica nel caso in cui:
• si incontri un suffisso nella forma
Aγ·,i
• allora si cerchi nello stato i per un suffisso del tipo
Bα·Aβ,j
e per ogni item trovato si aggiunga il suffisso
BαA·β,j
allo stato corrente.
Nel dettaglio (3)
• SCANNER
• Si applica nel caso in cui:
• si incontri un suffisso nella forma
Bα·aβ,i
(a è terminale)
• allora si aggiunga allo stato corrente
Bαa·β,i
Idea base dell’estensione
• Cambiamento nella rappresentazione degli stati
dell’algoritmo originale
 Rappresentazioni attribuite
Per ciascun simbolo non terminale A nella
grammatica di base si definisce:
A[A.a1 … A.an]
• Risultato:
L’algoritmo esteso in aggiunta al riconoscimento
sintattico della stringa in input valuta gli attributi
associati ai simboli della grammatica
Algoritmo di Earley modificato
Per grammatiche S-attribuite si effettua una modifica della fase
completer come segue:
Inizializzazione:
S0 =    S [S.a1, … , S.an],0
For i = 1 to n do
Begin
//Per ogni stato s in Si ripeti le fasi fino a quando
//non possono essere aggiunti altri stati a Si o Si+1
Begin
1. Predictor
//Applicata su suffissi in cui il punto è seguito da un non
terminale
If s= A X,f //s non finale e X non terminale
Si = Si  {X, i } //stato i è lo stato corrente
Algoritmo di Earley modificato
• 2.
Completer
//Applicata su suffissi in cui il punto è alla fine della sequenza di
simboli
If s= A,f
//Modifica dell’algoritmo originale
//eval_s ritorna il simbolo attribuito Ac identico ad A
//ma le occorrenze sono state valutate secondo le regole semantiche
• a.
• b.
Ac= eval_s(A, ,A)
Si = Si  {XAc, k }
• 3.
Scanner
//Applicata su suffissi in cui il punto è seguito da un terminale
If s= A xi+1,f
Si+1 = Si+1  {X  xi+1,f }
end;
If Si+1 è vuoto, annulla e termina la procedura
end;
if   S [S.a1, … , S.a2] ,0 in Sn+1, ACCETTA
Simulazione dell’algoritmo (1)
Grammatica
S—>A
A—>A
A—>a
Attribuzioni
S.v <-- A.v
A0.v <-- A1.v +1
A.v <–1
Vediamo un caso in cui l’algoritmo non termina
Inizializzazione:
S0 =    S [S.a1, … , S.an],0
S0 =
S.v A[v],0
A.v A[v],0
A.v a,0
Simulazione dell’algoritmo (1)
S1 =
Input = a
S0 =
Aa,0
Si applica il completer quindi si
valutano anche gli attributi secondo
le regole semantiche e si ottiene:
S.vA[v],0
S[v] –> A[1] ,0
A.v A[v],0
A[v] –> A[1] ,0
A.va,0
Si applica ancora il completer. Lo
stato non è ancora completo
S[v] – >A[2] ,0
Si applica lo scanner
A[v] – >A[2] ,0
Si applica ancora il completer. Lo
stato non è ancora completo
S[v] – >A[3] ,0
CICLA
A[v] – >A[3] ,0
ALL’INFINITO
Esempio dell’algoritmo
Grammatica
Regole semantiche
E->T
T->T*F
T->F
F->a
E.v=T.v
T.v=T1.v*F.v
T.v=F.v
F.v=a.lexval
SULL’ INPUT: 3*5
Valutazione espressione
S0=
E.v   T.v,0
T.v   T1.v * F.v,0
T.v   F.v,0
F.v   a.lexval,0
INPUT : 3*5
S1=
F.v  a ,0 completer
T.v  F[3] ,0 completer
E.v  T[3] ,0 completer
T.v  T[3]  * F[v],0
Valutazione espressione (2)
S1=
F.v  a ,0
T.v  F[3] ,0
E.v  T[3] ,0
T.v  T[3]  * F[v],0
INPUT : 3*5
S2=
T.v  T[3]*° F[v],0
F.v   a,2
Valutazione espressione (3)
S2=
T.v  T[3]*  F[v],0
F.v   a,2
S3=
F.v  a ,2 completer
T.v  T[3] * F[5]  ,0
 ,0
T.v  T[15]  * F[v]
E.v  T[15]
INPUT : 3*5
if   S [S.a1, … , S.a2] ,0 in Sn+1, ACCETTA
Note
• A differenza di Earley in cui al massimo veniva
generato un solo stato finale, l’algoritmo
modificato può generare più stati finali, e questo
significa avere valutazioni diverse del valore
degli attributi.
• Per grammatiche S-attribuite la non
terminazione si verifica se la grammatica
contiene cicli ovvero se contiene produzioni del
tipo AA.
Finite Partition
• Per risolvere i problemi precedentemente
•
•
descritti e garantire la corretta terminazione
dell’algoritmo è necessario considerare una
“partizione finita” del dominio degli attributi.
Restringendo il dominio degli attributi,
impediamo che la dimensione degli stati diventi
infinita (come precedentemente visto).
Questo assicura una terminazione dell’algoritmo
anche nei casi di grammatiche ambigue e
cicliche.
Conclusioni e status implementativo
• L’algoritmo esteso per la sua caratteristica di effettuare
•
•
•
anche la valutazione semantica non ha bisogno di essere
ulteriormente esteso.
In grammatiche ad attributi che presentino condizioni
sulle produzioni, il fatto di aver già valutato i valori degli
attributi può semplificare il processo di parsing,
riducendo il numero di stati che devono venir generati
dall’algoritmo.
L’algoritmo esteso è stato scritto in C ed è basato su una
implementazione ottimizzata dell’algoritmo di Earley
(Chamorro e Correa 1990)
L’algoritmo esteso verrà altresì incorporato in un
progetto più ampio: ANDES-1, un ambiente di
programmazione specifico per grammatiche ad attributi.