Post on 12-Mar-2020
Definizioni Definizioni syntaxsyntax--directeddirected
Esempio:Notazione infissa → Notazione postfissa
ProduzioniE → E1 + TE → E1 – TE → TT → 0T → 1T → 2. . . T → 9
Regole semanticheE.t := E1.t _T.t _‘+’E.t := E1.t _T.t _‘-’E.t := T.tT.t := ‘0’T.t := ‘1’T.t := ‘2’
T.t := ‘9’
Movimenti di un robot
Seq → Seq Istr | beginIstr → est | ovest | nord | sud
begin ovest sud est est sud
Traduciamo la sequenza in una posizione relativa al punto di partenza:
(0,0)(-1,0)
(-1,-1) (1,-1)(0,-1)
(1,-2)
Produzioni
Seq → begin
Seq → Seq1 Istr
Istr → est
Istr → ovest
Istr → nord
Istr → sud
Regole semanticheSeq.x := 0Seq.y := 0
Seq.x := Seq1.x + Istr.dxSeq.y := Seq1.y + Istr.dy
Istr.dx := ‘1’, Istr.dy := ‘0’
Istr.dx := ‘-1’, Istr.dy := ‘0’
Istr.dx := ‘0’, Istr.dy := ‘1’Istr.dx := ‘0’, Istr.dy := ‘-1’
Attributi ereditati
Dichiarazioni: int NUM, ELEM, K
Regole semanticheProduzioniD → T LL → L1, idL → idT → intT → real
L.in := T.typeL1.in := L.in, addtype (id.entry, L.in)addtype (id.entry, L.in)T.type := integerT.type := real
D
T L
,int L id3
,L id2
id1
D
T.type = integer
L.in = integer
L.in = integer
,int id3
,L.in = integer id2
id1
Grafo delle dipendenze e ordine di valutazioneGrafo delle dipendenze e ordine di valutazione
for ogni nodo n dell’albero di parsificazione dofor ogni attributo a del simbolo della grammatica
associato ad n docostruisci un nodo per a
for ogni nodo n dell’albero di parsificazione dofor ogni regola semantica b := f(c1,. . . ,ck)
associata alla produzione usata in n dofor i = 1 to k do
costruisci un arco dal nodo ci al nodo b
EsempioEsempio: : costruzionecostruzione di di alberi sintatticialberi sintattici
Funzioni usate:
mknode (op, left, right): crea un nodo operatore con label ope i puntatori agli operandi, restituisce il puntatore al nodo creato.
mkleaf (id, entry): crea un nodo identificatore con label id e un puntatore alla entry per l’identificatore nella symbol-table, restituisce il puntatore al nodo creato.
mkleaf (num, val): crea un nodo numero con label num e ilvalore del numero, restituisce il puntatore al nodo creato.
Definizione syntax-directed per costruire l’albero sintattico
Regole semanticheProduzioniE → E1 + TE → E1 – TE → TT → ( E )T → idT → num
E.nptr := mknode (‘+’, E1.nptr, T.nptr)E.nptr := mknode (‘-’, E1.nptr, T.nptr)E.nptr := T.nptrT.nptr := E.nptrT.nptr := mkleaf (id, id.entry)T.nptr := mkleaf (num, num.val)
E.nptr =
T.nptr =E.nptr = +
T.nptr =
T.nptr =E.nptr = -
id
-
+
idid
id
num num
EsempioEsempio: : Lista delle differenzeLista delle differenze
Definizione syntax-directed per costruire la lista delle differenze
ProduzioniC → N#LL → N;L1
L → NN → 0N → 1. . . N → 9
Regole semanticheC.list := L.list L.elem := N.valL.list := N.val - L.elem, L1.list; L1.elem := L.elem)L.list := N.val - L.elemN.val := 0N.val := 1
N.val := 9
list, eval: sintetizzatielem: ereditato
C
L
N
N
4
6
L;
#
L;N
2N
8
N.val=4
N.val=6
N.val=2
N.val=8
L.elem = 4L.list = 4
L.elem = 4L.list = -2,4
L.elem = 4L.list = 2,-2,4
C.list = 2,-2,4 4#6;2;8 2,-2,4
Definizioni LDefinizioni L--attribuiteattribuite
A → X1 X2 . . . Xn
Ogni attributo ereditato di Xj dipende solo da:• gli attributi dei simboli X1 X2 . . . Xj-1 a sinistra di Xj nella
produzione;• gli attributi ereditati di A.
Schemi di traduzioneSchemi di traduzione
Uno schema di traduzione e’ una grammatica libera in cui gli attributi sono associati ai simboli della grammatica e le azionisemantiche, racchiuse tra parentesi graffe, sono inserite nei membri destri delle produzioni.
Gli schemi di traduzione sono un’utile notazione per specificarela traduzione durante la parsificazione.
E → T RR → addop T {print (addop. lessema)} R1 | εT → num {print (num.val)}
Bisogna assicurare che il valore di un attributo sia disponibilequando un’azione fa ad esso riferimento.
Solo attributi sintetizzati: azioni alla fine del membro destro della produzione associata.
Attributi sintetizzati ed ereditati:
• un attributo ereditato per un simbolo al membro destro di una produzione deve essere calcolato con un’azione prima del simbolo
• un’azione non deve far riferimento a un attributo sintetizzato di un simbolo a destra dell’azione
• un attributo sintetizzato per un non terminale a sinistra puo’ essere calcolato solo dopo che sono stati calcolati tutti gli attributi cui fa riferimento. Le azioni che calcolano questi attributi possono di solito essere posti alla fine del membro destro della produzione.
Definizione non L-attribuita
Regole semanticheProduzioniA → L M
A → Q R
L.i := l (A.i)M.i := m (L.s)A.s := f (M.s)
R.i := r (A.i)Q.i := q (R.s)A.s := f (Q.s)
Schema di traduzione che non soddisfa le condizioni:
S → A1 A2 {A1.in := 1; A2.in := 2}A → a {print (A.in)}
Per una definizione diretta dalla sintassi L-attribuita è sempre possibile costruire uno schema di traduzione che soddisfa le tre condizioni precedenti.
S → {A1.in := 1}A1 {A2.in := 2}A2
A → a {print (A.in)}
Ricorsione sinistraRicorsione sinistra
{E.val := E1.val + num.val}E → E1 num
E → num {E.val := num.val}
Equivalente grammatica senza ricorsione sinistra:
E → num R
R → num R | ε
E → E1 numE → num
{E.val := E1.val + num.val}{E.val := num.val}
E → num RR → num R1R → ε
E
numE
numE
num
E
R
R
num R
ε
num
num
E → E1 numE → num
{E.val := E1.val + num.val}{E.val := num.val}
E → numR → numR → ε
{R{R.i := num.val} R {E.val := R.s}
1.i := R.i + num.val} R1 {R.s := R1.s}{R.s := R.i}
E
numE
numE
num 3
3+2
3 2
5+7 E
num R
num
7
R
numR.s := 12
R
ε
.i=3+2
.i=5+7
3 .i=3
5+7
7
2
A → A1YA → X
{A.a := g (A1.a, Y.y)}{A.a := f (X.x)}
A → X RR → YR | ε
A → X R
R → YR1
R → ε
{R.i := f (X.x)}{A.a := R.s}
{R1.i := g (R.i, Y.y)}{R.s := R1.s}
{R.s := R.i}
Eliminazione ricorsione sinistraEliminazione ricorsione sinistra: : EsempioEsempio
{E.val := E1.val + T.val}E → E1 + T
E → E1 - T
E → T
T → ( E )
T → num
{E.val := E1.val - T.val}
{E.val := T.val}
{T.val := E.val}
{T.val := num.val}
La grammatica non è LL(1)
{R.i := T.val}E → TR
R → +TR1
R → -TR1
R → ε
T → ( E)
T → num
{E.val := R.s}
{R1.i := R.i + T.val}{R.s := R1.s}
{R1.i := R.i - T.val}{R.s := R1.s}
{R.s := R.i}
{T.val := E.val}
{T.val := num.val}
R
E
R
num
εnum
Rnum
T-
T
T+
9
9 9
4+3=7
3
3
7
7
7
7
9-5=4
5
5
E
TE
num
+
T-E
num
num
T
9
9
9
5
5
9-5=4
3
3
4+3=7
R.i e R.s sono gli attributi, ereditato e sintetizzato rispettivamente, che giocano il ruolo di E.val nella grammatica con ricorsione sinistra.
Eliminazione ricorsione sinistraEliminazione ricorsione sinistra: : EsempioEsempio
ProduzioniProduzioni Regole semanticheRegole semantiche
E → E1 + T
E → E1 – T
E → T
T → ( E )
T → id
T → num
E.nptr := mknode (‘+’, E1.nptr, T.nptr)
E.nptr := mknode (‘-’, E1.nptr, T.nptr)
E.nptr := T.nptr
T.nptr := E.nptr
T.nptr := mkleaf (id, id.entry)
T.nptr := mkleaf (num, num.val)
{R.i := T.nptr}E → TR
R → +TR1
R → -TR1
R → ε
T → ( E)
T → num
{E.nptr := R.s}
{R1.i := mknode (‘+’, R.i, T.nptr)}{R.s := R1.s}
{R1.i := mknode (‘-’, R.i, T.nptr)}{R.s := R1.s}
{R.s := R.i}
{T.nptr := E.nptr}
{T.nptr := mkleaf (num, num.val)}
{T.nptr := mkleaf (id, id.entry)}T → id
-
T.nptr =
num
id
id
-
+
R.s =
R.s =
R.i =T.nptr =num
idR.i
+
R.i =T
T.nptr =
id ε
= R.s =
E.nptr =
E.nptr =
+
- id
idnum
Valutazione topValutazione top--down di grammatiche Ldown di grammatiche L--attribuiteattribuite
L’analizzatore a discesa ricorsiva per grammatiche LL(1) può essere modificato in modo da valutare gli L-attributi.
Ad ogni non terminale si associa una funzione che ha come parametri i valori degli attributi ereditati della variabile e restituisce i valori dei suoi attributi sintetizzati.
La funzione per un non terminale ha una variabile locale per ogni attributo ereditato o sintetizzato per i simboli che compaiono nelle parti destre delle produzioni dal non terminale.
Codice per le parti destre delle produzioni:
• Per ogni non terminale B si genera un’assegnazione <c1, . . ., ck> := B(b1, . . . Bn), che è una chiamata alla funzione associata a B.
• Per ogni terminale a i valori degli attributi sintetizzati vengono assegnati alle corrispondenti variabili e l’esame passa al simbolo successivo.
• Le azioni semantiche vengono ricopiate dopo aver sostituito i riferimenti agli attributi con le variabili corrispondenti.
Valutazione topValutazione top--down di grammatiche Ldown di grammatiche L--attribuiteattribuite
function A(e1, . . . en)var s1, . . . , sm, X1_x1, . . . , X1_xk, . . . , Xh_x1, . . . , Xh_xrbegin if cc ∈ Gui(A → α1) then body (α1)
else if cc ∈ Gui(A → α2) then body (α2)….else if cc ∈ Gui(A → αk) then body (αk)else ERRORE(…)
return < s1, . . . , sm>end
Regole semanticheProduzioniC → N#LL → N;L1
L → NN → 0. . . N → 9
ε
C.list := L.list; L.elem := N.valL.list := N.val - L.elem, L1.list;L1.elem := L.elem
L.list := N.val - L.elem L.list := null
L.list := cons (N.val - L.elem, L1.list);
N.val := 0
N.val := 9
C → N#LL → N;L1
L → εN → 0. . . N → 9
Insiemi guida{0, 1, . . . , 9}{0, 1, . . . , 9}{⊣}{0}
{9}
Schema di Schema di traduzionetraduzione
C → N# {L.elem := N.val} L {C.list := L.list}
L → N; {L1.elem := L.elem} L1 {cons (N.val - L.elem, L1.list)}
L → ε {L.list := null}N → 0 {N.val := 0}. . . N → 9 {N.val := 9}
N → 0 {N.val := 0}. . . N → 9 {N.val := 9}
function Nvar val begin if cc = 0 then cc := PROSS
val := 0else if cc = 1 then cc := PROSS
val := 1….else if cc = 9 then cc := PROSS
val := 9else ERRORE(…)
return < s1, . . . , sm>end
L → N; {L1.elem := L.elem} L1 {L.list := cons (N.val - L.elem, L1.list)}
L → ε {L.list := null}
function L (elem)var list, N_val, L_elem, L_list begin if cc ∈ {0, 1, . . . , 9}
then N_val := Nif cc = ; then cc := PROSS
L_elem := elemL_list := L (L_elem)list := cons (N_val - L_elem, L_list)
else ERRORE(…)else if cc = ⊣ then list := nullelse ERRORE(…)
return listend
C → N# {L.elem := N.val} L {C.list := L.list}
function Cvar list, N_val, L_elem, L_list begin if cc ∈ {0, 1, . . . , 9}
then N_val := Nif cc = # then cc := PROSS
L_elem := N_valL_list := L (L_elem)list := L_list
else ERRORE(…)else ERRORE(…)
return listend