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 xVars(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) <a1,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<c2,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}, cCif}
•Tcr {<c,r> | r{0,1}, cCif}
• 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’,mNum} 
{n | nNum}
• T+  {n | nNum}
• +
<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