Linguaggi: Semantica Programma in C #include <stdio.h>; Cosa significa? # define bott_vol =2.0; cosa calcola ? # define latt_vol = 0.355; a cosa serve ? int main () è corretto? {int bott_num = 4; int latt_num = 10; double totale = bott_vol * bott_num + latt_vol * latt_num; printf(“volume totale %d litri”, totale); } Linguaggi: Semantica Programma in Caml let bott_vol =2.0 and latt_vol = 0.355 and bott_num = 4 and latt_num = 10 in bott_vol * bott_num + latt_vol * latt_num; Cosa significa? cosa calcola ? a cosa serve ? è corretto? La correttezza sintattica è data dalla Grammatica di C Programma::= Direttive Prototipi int main() {StmtList} FunctDecList Direttive ::= Direttiva Direttive | Direttiva::= #define Ide; | #include <Ide.h>;|... Prototipi::= Prototipo ; Prototipi | Prototipo:= Type Ide(FormalList ) ; FunctDecList::= FunctDecl; FunctDecList | FunctDec::= Type Ide (FormalList) Com La correttezza sintattica è data dalla Grammatica di C StmtList ::= Stmt ; StmtList | Stmt::=Decl | Com Com::=Ide=Exp Assegnamento | if (Exp) Com else Com Condizionale | while (Exp) Com Iteratore | {StmtList} Blocco | Ide(Exp) Invocazione di fun | return Exp Calcolo dei valore Exp::= Ide | Const | Exp Op Exp | Uop Exp | Ide | Ide(Exp) | (Exp)... Decl ::= Type Ide [=Exp] Sintassi e semantica • La sintassi di un linguaggio di programmazione è in genere descritta in modo molto rigoroso. • La semantica viceversa spesso è descritta in modo non formale e quindi poco rigoroso. I vantaggi di una descrizione formale della semantica sono: – è la specifica del compilatore e dell’interprete: • permette di affrontare in modo rigoroso e strutturato il complesso problema dell’implementazione del linguaggio • uno stesso programma, eseguito da implementazioni diverse del linguaggio (macchine diverse), che però rispettano la semantica, danno lo stesso risultato. – aiuta nella definizione di programmi per la soluzione dei problemi, – permette di ragionare sulla correttezza dei programmi, 12/21/2015 5 Semantica Operazionale: Sistemi di Transizioni Sistema di transizioni: S < , T, > • configurazioni (Stati) • T finali • x relazione di transizione Derivazione D: < S , * > * chiusura antisimmetrica, riflessiva, transitiva di • i * k i … k D Regole (R) condizionali per p1 p2 ... pn ’ Le pi sono premesse e sono relazioni tra espressioni che contengono costanti, variabili e operatori del tipo (=, ≠, ). Le variabili sono quelle che permettono di istanziare la regola. Le indichiamo con Vars(R). La copertura delle variabili serve a garantire la fondatezza della regola. Copertura delle variabili Sia R la seguente regola condizionale p1 p2 .. pn ’ Sia x Vars(R), x è coperta in R se e solo se vale una delle seguenti condizioni: 1) x occorre ; 2) esiste in R una premessa pi del tipo y=t tale che y è coperta in R e x Vars(t) 3) esiste in R una premessa pi del tipo x=t tale che tutte le variabili in Vars(t) sono coperte. 4) esiste in R una premessa pi del tipo d ’ d’ tale che tutte le variabili in d sono coperte in R e xVars(d’) Sostituzioni e istanziazioni • Sia V= {x1,...xk} è un insieme di variabili, si dice sostituzione l’insieme di associazioni ={c1/x1,... ck/xk} dove c1,... ck sono costanti. • Dato un termine o espressione E questo può essere istanziato su una sostituzione (E). L’istanza è l’espressione che si ottiene rimpiazzando in E tutte le variabili che occorrono in con i rispettivi valori. – es. V= {x,y} e sia E = x<y+1 l’espressione se ={4/x,2/y} allora (E) = 4<2+1 = 4<3= false – se invece ={2/x, 3/y} allora (E) = 2<3+1 2< 4= true 12/21/2015 9 Derivazione ’ Sia < , T, > un sistema di transizioni con (r1)...(rn) regole condizionali, abbiamo che ’ se e solo se esiste una regola condizionale ri per cui esiste una sostituzione per le variabili in ri tale che: • tutte le premesse di (ri) sono soddisfatte; • la conclusione di (ri) è proprio ’ Le variabili (spesso di seguito denotate con ,,d,) rappresentano generici elementi del dominio del discorso, e si riconoscono perchè, nelle premesse, ne viene definito l’intervallo di variabilità. 12/21/2015 10 Grammatiche LC come sistemi di transizioni Data una G=<,V,s,P>si può definire un sistema di transizioni nel seguente modo: • le configurazioni sono sequenze di simboli in V • le configurazioni terminali sono sequenze di simboli in • la relazione di transizione è definita in base alle produzioni, nel seguente modo: Per ogni produzione A::=h P è definita una regola condizionale. d, (V)* dA dh 12/21/2015 precondizioni/ premesse/ prerequisiti 11 Un esempio Data la grammatica G=<{a,b},{S},S,{S::=ab, S::=aSb}> definiamo un sistema di transizione nel modo seguente: ={ | ({a,b}{S})*} T ={ | {a,b}*} d, ({a,b}{S})} dS dab d, ({a,b}{S})} dS daSb 12/21/2015 12 Un esempio: la reverse di una sequenza di caratteri Rev < Rev, TRev, Rev> • Rev {<,> | , *} • T Rev {<, > | *} • Rev {<x, , * <x,> <, x> Soluzione con solo coppie di sequenze. La configurazione iniziale è <,> 12/21/2015 13 Un’altra soluzione: la reverse Rev < Rev, TRev, Rev> • Rev {<,> | , *} { | *} • TRev { | *} • Rev {<x, , * <x,> <, x> <, > <, > Soluzione con coppie di sequenze, che termina con una singola sequenza 12/21/2015 14 Esempio eliminazione di ripetuti Rem < Rem, TRem, Rem> • Rem {<,x> | *, x {START,STOP} } • TRem {< ,STOP> | * }, • Rem { <,START> <,STOP> (1) x (2) <x,START> <x,STOP> <x, , *, <x,START>*Rem<,STOP> (3) <xx,START> <,STOP> <x,y, x≠y, , *, <y,START>*Rem<,STOP> (4) <xy,START> <x,STOP> } 12/21/2015 15 Eliminazione dei ripetuti:Esempio di applicazione <aacbbb,START> (3)0<0,STOP> < acb,STOP> 0={a/x0,cbbb/0 ,acb /0} 0= acb <acbbb,START> *<0,STOP> < acb,STOP> <acbbb,START> (4) <a1,STOP> <acb,STOP> 1={a/x1,c/y1,bbb/1,cb/1} 1 <cbbb,START> *<1,STOP> <cb,STOP> 1 = cb <cbbb,START> (4)2<c2,STOP> <cb,STOP> 2 ={c/x2,b/y2,bb/2, b/2} 2= b <bbb,START> *<2,STOP> <b,STOP> <bbb,START> (3)3<3,STOP> <b,STOP> <bb,START> *<3,STOP> <b,STOP> <bb,START> (3)4<4,STOP> <b,STOP> <b,START> *<4,STOP> <b,STOP> <b,START> (2)5< b,STOP> 12/21/2015 3 ={b/x3,b/3,b/3} 3 = b 4 ={b/x4,/4, b/4} 4= b 5 ={b/x5} 16 Addizionatore di numeri • Vediamo come esempio un addizionatore di numeri interi, che fa uso di due sistemi di transizione: – un addizionatore di cifre decimali – l’addizionatore di numeri • la grammatica per definire i numeri da addizionare è la seguente: 110 456+ 57= 513 Num::= Num Cif | Cif Cif::= 0|1|2|3|4|5|6|7|8|9 12/21/2015 17 Addizione <456,57> <6,7,0> <3,1>} <45,5,3,1> <5,5,1> <1,1>} <4,0,13,1> <4,0,1> <5,0>} <0,0,513,0> 513 12/21/2015 18 Addizionatore di cifre Addizionatore di cifre: Scr < cr, Tcr, cr> • cr {<c,c’,r> | r{0,1}, c,c’Cif} {<c,r> | r{0,1}, cCif} •Tcr {<c,r> | r{0,1}, cCif} • cr <0,0,0>cr<0,0> <0,1,0>cr<1,0> <0,2,0>cr<2,0> …. <9,8,0>cr<7,1> <9,9,0>cr<8,1> 12/21/2015 <0,0,1>cr<1,0> <0,1,1>cr<2,0> <0,2,1>cr<3,0> ….. <9,8,1>cr<8,1> <9,9,1>cr<9,1> 19 Addizionatore di numeri Addizionatore di Num: S+ < +, T+, +> • + {<n,n’> | n,n’Num} {<n,n’,m,r> | r{0,1}, n,n’,mNum} {n | nNum} • T+ {n | nNum} • + <c,c’,0>cr<c’’,r> <c,c’>+<0,0,c’’,r> <c,c’,0>cr<c’’,r> <nc,c’>+<n,0,c’’,r> <c,c’,0>cr<c’’,r> (i) (ii) (iii) <c,nc’>+<0,n,c’’,r> 12/21/2015 20 Transizioni +(continua) <c,c’,0>cr<c’’,r> (iv) <nc,n’c’>+<n,n’,c’’,r> <0,0,m,0> + m <c,c’,r>cr<c’’,r’> <c,c’,m,r>+<0,0,c’’m,r’> <c,c’,r>cr<c’’,r’> (v) se <c,c’,r>≠<0,0,0> (vi) (vii) <nc,c’,m,r>+<n,0,c’’m,r’> <c,c’,r>cr<c’’,r’> (viii) <c,nc’,m,r>+<0,n,c’’m,r’> <c,c’,r>cr<c’’,r’> (ix) <nc,n’c’,m,r>+<n,n’,c’’m,r’> 12/21/2015 21 Applicazione dell’addizionatore <92,512> +{(iV), <2,2,0> cr<4,0>} <9,51,4,0> +{(iX), <9,1,0> cr<0,1>} <0,5,04,1> +{(vi), <0,5,1> cr<6,0>} <0,0,604,0> +{(v)} 604 12/21/2015 22 Macchina S+ 277 + 9902 Continua 3 <277,9902> <27,990,9,0> <2,99,79,0> <0,9,179,1> <0,0,0179,1> <0,0,10179,0> 10179 10179 Rappresentazione e semantica • I numeri (che indichiamo qui con sulla dispensa sono N) con le loro operazioni sono entità astratte che godono di importanti proprietà. • Per utilizzarli e studiarli gli uomini hanno inventato delle rappresentazioni (concrete) di tali entità: – quella che conosciamo e usiamo normalmente sono i numeri arabi su base decimale, – i Romani ne usavano una diversa (I,II, III, IV, ...X, ..L...) – ne esistono molte altre, ad esempio su basi diverse (2,3,...ecc). • Nel definire la semantica di un linguaggio di programmazione, dove le algebre dei numeri sono rappresentate da tipi predefiniti (int, long, real,..) e importante chiarire la differenza tra valore e rappresentazione. 12/21/2015 24 Correttezza: Rappresentazione e Semantica dei numeri Sia l’insieme dei numeri naturali ={0,1,2,3,...} con le usuali operazioni di somma, sottrazione, ecc., e gli operatori di relazione (=, ≠,>,ecc). Mentre Num sono sequenze di simboli che rappresentano i numeri naturali nella solita rappresentazione decimale. funzione di valutazione h h: Num -> h(0) = 0 …. h(9) = 9 h(nc) = h(n)x10 + h(c) <n,n’> +* m funzione di rappresentazione : -> Num (0) = 0 Num …. (9) = 9 Num (n) = (n 10)(n mod 10) Num, n>9 h(n) + h(n’) = h(m) Rappresentazione binaria • La rappresentazione che utilizza il minimo numero di simboli è la rappresentazione binaria (quella usata dai calcolatori). • Tale rappresentazione è definita dalla seguente funzione di valutazione: h(0) = 0 h(1) = 1 h(yb) = (h(y) 2) + h(b) Si calcoli il valore di h(1100) cioè il numero rappresentato dalla stringa binaria 1100. 12/21/2015 26