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