04/21/23 1

Semantica operazionaleSemantica operazionale

• La semantica ha lo scopo di definire il significato di un programma,

• la semantica operazionale raggiunge tale scopo definendo il comportamento del sistema (calcolatore) mentre esegue il programma.

• Il comportamento del programma viene definito utilizzando un sistema di transizioni in cui – le configurazioni devono permettere di definire lo stato del sistema,

– le configurazioni terminali rappresentano i risultati,

– le transizioni descrivono l’evoluzione del sistema durante la computazione delle istruzioni del programma.

04/21/23 2

Un sistema di transizioni per espressioni Un sistema di transizioni per espressioni semplicisemplici

• Il sistema di transizioni che descrive la semantica di un linguaggio di programmazione (anche se non completo),è piuttosto complesso, per cui verrà introdotto per passi;

• Inizieremo con semplice linguaggio di espressioni che può essere descritto da un sistema di transizione molto semplice

• via via estenderemo il linguaggio, con nuovi meccanismi e di conseguenza il sistema di transizioni verrà anch’esso esteso.

Exp::= Exp Op Exp | Num | ‘(‘Exp’)’Exp::= Exp Op Exp | Num | ‘(‘Exp’)’

Op::= + | - | * | /Op::= + | - | * | /

Num::= ...Num::= ...Espresioni semplici

Il sistema di transizioni per le espressioni Il sistema di transizioni per le espressioni semplicisemplici

Semantica di Exp: Sexp < exp, Texp, exp>

• exp {E | E Exp}

{n | n}

• T exp {n | n}

• exp

Eexp n E’exp n’ n [op] n’ = m

E op E’exp m

Eexp n

(E)exp n

n exp n

(Expop)

(Exp())

(ExpNum)

25 - 3 * 725 - 3 * 7

expexp{ (exp{ (expopop), ),

25 25 expexpnumnum 2525,,

3*73*7

exp exp { (exp{ (expopop), ),

3 3 expexpnum num 33,,

7 7 expexpnum num 77

33 [*] [*] 77 = = 2121 } }

2121

2525 >> 2121 , , 2525 [-] [-] 2121 = = 44 } }

44

Esempio: calcolo di 25-3*7Esempio: calcolo di 25-3*7

Semantica Operazionale: Espressioni con identificatori di costanti

•Riferire una quantità mediante un nome è utile ed è Riferire una quantità mediante un nome è utile ed è prassi comune in molti formalismi.prassi comune in molti formalismi.•Le variabili in matematica sono dei nomi Le variabili in matematica sono dei nomi

(identificatori) ai quali è associato un valore. Nei (identificatori) ai quali è associato un valore. Nei linguaggi funzionali i valori legati agli identificatori sono linguaggi funzionali i valori legati agli identificatori sono costanti.costanti.•Nei linguaggi di programmazione di tipo imperativo Nei linguaggi di programmazione di tipo imperativo

gli identificatori con associato il valore sono un gli identificatori con associato il valore sono un meccanismo fondamentale per la definizione dei meccanismo fondamentale per la definizione dei programmi. Esistono identificatori costanti e modificabiliprogrammi. Esistono identificatori costanti e modificabili

2 * Pigrego * 22= 138,16 = 138,16 allorche’ Pigreco=3,14allorche’ Pigreco=3,14

= 138,226 = 138,226 allorche’ Pigreco=3,1415allorche’ Pigreco=3,1415

04/21/23 6

IdentificatoriIdentificatori

• In ogni linguaggio è necessario definire dei nomi, nei L.P. i nomi vengono chiamati identificatori ed hanno una particolare sintassi, generalmente:

Ide::=Lettera Carattere*

Lettera::=A|B|C|…|Z|a|b|…|z,

Carattere::=Lettera|Cifra|Simbolo,

Cifra::=0|1|2|…|9,

Simbolo::=-|$|%|:|<|…,

Alcuni simboli non sono ammessi

04/21/23 7

Un linguaggio d’espressioni con Un linguaggio d’espressioni con identificatori di costantiidentificatori di costanti

Exp::= Exp Op Exp | Num | ‘(‘ Exp ‘)’ | IdeExp::= Exp Op Exp | Num | ‘(‘ Exp ‘)’ | Ide

Op::= + | - |* | /Op::= + | - |* | /

Num::= …Num::= …

Ide::= ...Ide::= ...

Una grammatica GUna grammatica G

I domini per questa semantica:I domini per questa semantica:Ide: gli identificatori validi del CIde: gli identificatori validi del C

Val: Int Val: Int Float Float

04/21/23 8

FrameFrame

I frame (ii) sono rappresentazioni estensionali di funzioni parziali. Un frame è un insieme di Un frame è un insieme di coppie {(d,c) |dcoppie {(d,c) |d Dom, c Dom, c Cod} Cod}• Per tutti gli elementi d del dominio per cui Per tutti gli elementi d del dominio per cui non esiste (d,c) non esiste (d,c) la funzione è indefinita la funzione è indefinita (cioe vale (cioe vale ). ). • applicazione applicazione (d) = c (d) = c ddDomDom,, c cCodCod• è il frame sempre indefinito (cioè è il frame sempre indefinito (cioè x x Dom Dom (x)= (x)=

04/21/23 9

FrameFrame

In questa semantica i frame sono funzioni Ide ->ValIn questa semantica i frame sono funzioni Ide ->Val

Esempi: Esempi:

1={<Pigreco,3.14>, <Euro,1936>} e 1={<Pigreco,3.14>, <Euro,1936>} e 2={<Pigreco,3.1415>} 2={<Pigreco,3.1415>} Esempi di applicazione delle funzioni Esempi di applicazione delle funzioni 1, 1, 2:2:

1(Pigreco)=3.14 1(Pigreco)=3.14

2(Pigreco)=3.1415 2(Pigreco)=3.1415

1(Euro)= 1936 1(Euro)= 1936

2(Euro)= 2(Euro)=

Semantica di espressioni con Semantica di espressioni con identificatori di costantiidentificatori di costanti

Semantica di ExpSemantica di Exp: S: Sexpexp < < expexp, T, Texpexp, , expexp>>

• expexp {<E, {<E,> | E > | E Exp, Exp, {Ide {Ide Val} Val}

{{nn | | nn} }

• T T expexp { {nn | | nn} }

• expexp <E,<E,>>expexp nn <E’, <E’,> > expexp n’n’ nn [[op1op1]] n’n’ = = mm

<E op1 E’,<E op1 E’,> > expexp mm

<E,<E,> > expexp nn

<(E),<(E),> > expexp nn

<n,<n,> > expexp nn

(x)= (x)= nn

<x,<x,> > expexp nn

(Exp(Exp+|-+|-))

(Exp(Exp()()))

(Exp(ExpNumNum))

(Exp(ExpIdeIde))

In questo caso lo stato è semplicemente un frame

<<2 * Pigreco * 222 * Pigreco * 22, , {Pigreco={Pigreco=33}}>>

expexp{ (exp{ (exp*|/*|/), ),

2 2 expexpnumnum 22 , ,

Pigreco * 22Pigreco * 22

exp exp { (exp{ (exp*|/*|/), ),

Pigreco Pigreco

expexp { (exp{ (expIdeIde), ),

(Pigreco)=(Pigreco)=33 } }

33

22 22 expexpnum num 2222

33 [*] [*] 2222 = = 6666 } }

6666

22 [*] [*] 6666 = = 132132 } }

132132

Esempio:calcolo di 2*Pigreco*22Esempio:calcolo di 2*Pigreco*22