gianfranco-lamperti.unibs.it...Esercizio 2 Specificare la semantica denotazionale della seguente...

Esercizio 1

Data la seguente BNF relativa alla descrizione di numeri in base cinque:

definire la semantica denotazionale che esprime il valore di una frase (sequenza di cifre).

Linguaggi di Programmazione Esercizi Semantica Denotazionale 1

pentanum pentanum 0 | pentanum 1 | pentanum 2 | pentanum 3 | pentanum 4 | 0 | 1 | 2 | 3 | 4

Esercizio 1

Data la seguente BNF relativa alla descrizione di numeri in base cinque:

definire la semantica denotazionale che esprime il valore di una frase (sequenza di cifre).


pentanum pentanum 0 | pentanum 1 | pentanum 2 | pentanum 3 | pentanum 4 | 0 | 1 | 2 | 3 | 4

N = { naturali } = dominio degli oggetti matematici associati

M = funzione di mapping:

M(‘0’) = 0 M(pentanum ‘0’) = 5 * M(pentanum)M(‘1’) = 1 M(pentanum ‘1’) = 5 * M(pentanum) + 1M(‘2’) = 2 M(pentanum ‘2’) = 5 * M(pentanum) + 2M(‘3’) = 3 M(pentanum ‘3’) = 5 * M(pentanum) + 3M(‘4’) = 4 M(pentanum ‘4’) = 5 * M(pentanum) + 4

Esercizio 2

Specificare la semantica denotazionale della seguente istruzione (ciclo a condizione finale):

in cui la lista L di istruzioni viene ripetuta (almeno una volta) finchè la condizione booleana B risulta vera (il ciclo termina quando B = true). Specificatamente, si definisca la funzione Mr(repeat L until B, s), in cui s rappresenta lo stato del programma, assumendo di aver a disposizione le seguenti funzioni:

Mb(B, s) : espressione booleana {true, false, errore} Ml(L, s): lista di istruzioni nuovo stato o errore.


repeat L until B

Esercizio 2

Specificare la semantica denotazionale della seguente istruzione (ciclo a condizione finale):

in cui la lista L di istruzioni viene ripetuta (almeno una volta) finchè la condizione booleana B risulta vera (il ciclo termina quando B = true). Specificatamente, si definisca la funzione Mr(repeat L until B, s), in cui s rappresenta lo stato del programma, assumendo di aver a disposizione le seguenti funzioni:

Mb(B, s) : espressione booleana {true, false, errore} Ml(L, s): lista di istruzioni nuovo stato o errore.


repeat L until B

Mr(repeat L until B, s) = if Ml(L, s) = errore then

erroreelsif Mb(B, Ml(L, s)) = errore then

erroreelsif Mb(B, Ml(L, s)) = true then

Ml(L, s)else Mr(repeat L until B, Ml(L, s)).

Esercizio 3Specificare la semantica denotazionale di una espressione logica definita dalla seguente grammatica:

Si assume che:

• id rappresenti il nome di una variabile logica;• la valutazione di and-expr sia in corto circuito, con valutazione degli operandi da sinistra a destra;• sia disponibile una funzione (id, s) che restituisce il valore della variabile id nello stato s;• (id, s) = ?, qualora il valore della variabile id non sia definito;• il linguaggio di specifica denotazionale non disponga della congiunzione logica (and).


expr true | false | id | and-exprand-expr expr1 and expr2


Si assume che:

• id rappresenti il nome di una variabile logica;• la valutazione di and-expr sia in corto circuito, con valutazione degli operandi da sinistra a destra;• sia disponibile una funzione (id, s) che restituisce il valore della variabile id nello stato s;• (id, s) = ?, qualora il valore della variabile id non sia definito;• il linguaggio di specifica denotazionale non disponga della congiunzione logica (and).


expr true | false | id | and-exprand-expr expr1 and expr2

Me(true, s) = true.Me(false, s) = false.Me(id, s) = if (id, s) == ? then errore else (id, s) endif.Me(and-expr, s) = Mand(and-expr, s).Mand(and-expr, s) = if Me(expr1, s) == errore then errore elsif Me(expr1, s) == true then Me(expr2, s) else false endif.


sulla base delle seguenti assunzioni:

• id rappresenta il nome di una variabile logica;• la valutazione degli operatori and ed or è in corto circuito;• la valutazione degli operandi dell’operatore and è da sinistra a destra;• la valutazione degli operandi dell’operatore or è da destra a sinistra;• è disponibile una funzione (id, s) che restituisce il valore della variabile id nello stato s;• (id, s) = UNDEF, qualora il valore della variabile id non sia definito;• il linguaggio di specifica denotazionale non dispone di operatori logici.


expr true | false | id | expr1 and expr2 | expr1 or expr2



• id rappresenta il nome di una variabile logica;• la valutazione degli operatori and ed or è in corto circuito;• la valutazione degli operandi dell’operatore and è da sinistra a destra;• la valutazione degli operandi dell’operatore or è da destra a sinistra;• è disponibile una funzione (id, s) che restituisce il valore della variabile id nello stato s;• (id, s) = UNDEF, qualora il valore della variabile id non sia definito;• il linguaggio di specifica denotazionale non dispone di operatori logici.


expr true | false | id | expr1 and expr2 | expr1 or expr2

Me(true, s) = TRUE.Me(false, s) = FALSE.

Me(id, s) = if (id, s) == UNDEF then ERRORE else (id, s) endif.

Me(expr1 and expr2, s) = if Me(expr1, s) == ERRORE then ERRORE elsif Me(expr1, s) == TRUE then Me(expr2, s) else FALSE endif.

Me(expr1 or expr2, s) = if Me(expr2, s) == ERRORE then ERRORE elsif Me(expr2, s) == TRUE then TRUE else Me(expr1, s) endif.

Esercizio 5Specificare la semantica denotazionale di una espressione aritmetica che coinvolge gli operatori di moltiplicazione ed esponenziazione:


• num rappresenta una costante intera;• id rappresenta il nome di una variabile intera;• la valutazione degli operandi è da destra a sinistra;• la valutazione degli operatori è in corto circuito, secondo le seguenti regole:• expr1 * expr2 = 0 quando expr2 = 0• expr1 ^ expr2 = 1 quando expr2 = 0• è disponibile una funzione (id, s) che restituisce il valore della variabile id nello stato s;• (id, s) = UNDEF, qualora il valore della variabile id non sia definito;• è disponibile una funzione Mn(num) che restituisce il valore di num;• il linguaggio di specifica denotazionale dispone degli operatori * e ^.


expr expr1 * expr2 | expr1 ^ expr2 | id | num

Esercizio 5Specificare la semantica denotazionale di una espressione aritmetica che coinvolge gli operatori di moltiplicazione ed esponenziazione:


• num rappresenta una costante intera;• id rappresenta il nome di una variabile intera;• la valutazione degli operandi è da destra a sinistra;• la valutazione degli operatori è in corto circuito, secondo le seguenti regole:• expr1 * expr2 = 0 quando expr2 = 0• expr1 ^ expr2 = 1 quando expr2 = 0• è disponibile una funzione (id, s) che restituisce il valore della variabile id nello stato s;• (id, s) = UNDEF, qualora il valore della variabile id non sia definito;• è disponibile una funzione Mn(num) che restituisce il valore di num;• il linguaggio di specifica denotazionale dispone degli operatori * e ^.


expr expr1 * expr2 | expr1 ^ expr2 | id | num

Me(num, s) = Mn(num).

Me(id, s) = if (id, s) == UNDEF then ERRORE else (id, s) endif.

Me(expr1 * expr2 , s) = if Me(expr2, s) == ERRORE then ERRORE elsif Me(expr2, s) == 0 then 0 elsif Me(expr1, s) == ERRORE then ERRORE else Me(expr1, s) * Me(expr2, s) endif.

Me(expr1 ^ expr2 , s) = if Me(expr2, s) == ERRORE then ERRORE elsif Me(expr2, s) == 0 then 1 elsif Me(expr1, s) == ERRORE then ERRORE else Me(expr1, s) ^ Me(expr2, s) endif.

Esercizio 6

È dato il seguente frammento di grammatica BNF, relativo alla specifica di una lista di istruzioni di un linguaggio imperativo:

Si richiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio assumendo che siano disponibili le seguenti funzioni di mapping, che mappano una istruzione ed un certo stato s in un nuovo stato (eventualmente errore):

Massign(assign-stat, s) Mif(if-stat, s) Mwhile(while-stat, s)

In particolare, si richiede la specifica delle seguenti funzioni (che computano il nuovo stato, eventualmente errore):

Mstat(stat, s) Mlist(stat-list, s)


stat-list stat stat-list | statstat assign-stat | if-stat | while-stat

Esercizio 6


stat-list stat stat-list | statstat assign-stat | if-stat | while-stat

Mstat(assign-stat, s) = Massign(assign-stat, s).

Mstat(if-stat, s) = Mif(if-stat, s).

Mstat(while-stat, s) = Mwhile(while-stat, s).

Mlist(stat, s) = Mstat(stat, s).

Mlist(stat stat-list2, s) = if Mstat(stat, s) = errore then errore else Mlist(stat-list2, Mstat(stat, s)).

Esercizio 7Specificare la semantica denotazionale della seguente istruzione (ciclo for C-like):

la cui semantica operazionale può essere espressa mediante il ciclo while nel seguente modo:

dove I1 ed I2 sono istruzioni, B è una espressione booleana ed L è una lista di istruzioni (corpo del ciclo). Si assume che siano disponibili le seguenti funzioni semantiche (di cui non è richiesta l’implementazione):

Mstat(I, s), che computa il nuovo stato (eventualmente ERRORE) dopo l’esecuzione della istruzione I nello stato s;

Mbool(B, s), che computa il valore dell’espressione booleana B (eventualmente ERRORE) nello stato s; Mlist(L, s), che computa il nuovo stato (eventualmente ERRORE) dopo l’esecuzione della lista L di

istruzioni nello stato s.


for (I1; B; I2) L

I1;

while B do L; I2 end.

Esercizio 7Specificare la semantica denotazionale della seguente istruzione (ciclo for C-like):

la cui semantica operazionale può essere espressa mediante il ciclo while nel seguente modo:

dove I1 ed I2 sono istruzioni, B è una espressione booleana ed L è una lista di istruzioni (corpo del ciclo). Si assume che siano disponibili le seguenti funzioni semantiche (di cui non è richiesta l’implementazione):

Mstat(I, s), che computa il nuovo stato (eventualmente ERRORE) dopo l’esecuzione della istruzione I nello stato s;

Mbool(B, s), che computa il valore dell’espressione booleana B (eventualmente ERRORE) nello stato s; Mlist(L, s), che computa il nuovo stato (eventualmente ERRORE) dopo l’esecuzione della lista L di

istruzioni nello stato s.


Mfor(for(I1 ; B ; I2) L, s) = if Mstat(I1, s) == ERRORE then ERRORE

else Mwhile(B, L, I2, Mstat(I1, s)).

Mwhile(B, L, I2, s) = if Mbool(B, s) == ERRORE then ERRORE

else if Mbool(B, s) == FALSE then s

else if Mlist(L, s) == ERRORE then ERRORE

else if Mstat(I2, Mlist(L, s)) == ERRORE then ERRORE

else Mwhile(B, L, I2, Mstat(I2, Mlist(L, s))).

for (I1; B; I2) L

I1;

while B do L; I2 end.

Esercizio 8E’ dato il seguente frammento di grammatica BNF relativo alla specifica del ciclo a condizione iniziale in un linguaggio imperativo:

Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio assumendo che:

id rappresenti il nome di una variabile logica; la valutazione dell’operatore and sia in corto circuito, con valutazione degli operandi da sinistra a

destra; sia disponibile una funzione Mid(id, s) che restituisce il valore della variabile id nello stato s; Mid(id, s) = ERRORE, qualora il valore della variabile id non sia definito; sia disponibile una funzione Massign(assign-stat, s) che restituisce il nuovo stato (eventualmente ERRORE); il linguaggio di specifica denotazionale non disponga di operatori logici.

In particolare, si richiede la specifica della seguenti funzioni semantiche:

Mwhile(while-stat, s)Mexpr(expr, s)Mstat(stat, s)


while-stat while expr do statexpr true | false | id | expr and expr | ( expr )stat assign-stat | while-stat

Esercizio 8


Mwhile(while-stat, s) =

if Mexpr(expr, s) == ERRORE then ERRORE

elsif Mexpr(expr, s) == false then s

elsif Mstat(stat, s) == ERRORE then ERRORE

else Mwhile(while-stat, Mstat(stat, s))

endif.

Mexpr(true, s) = TRUE.

Mexpr(false, s) = FALSE.

Mexpr(id, s) = Mid(id, s). Mexpr(expr1 and expr2, s) = if Mexpr(expr1, s) == ERRORE then ERRORE

elsif Mexpr(expr1, s) == TRUE then Mexpr(expr2, s) else FALSE

endif.

Mexpr(( expr1 ), s) = Mexpr(expr1, s).

Mstat(assign-stat, s) = Massign(assign-stat, s). Mstat(while-stat, s) = Mwhile(while-stat, s).

while-stat while expr do statexpr true | false | id | expr and expr | ( expr )stat assign-stat | while-stat

Esercizio 9

Specificare la semantica denotazionale della seguente istruzione (ciclo a conteggio):

in cui n è una costante intera. L’esecuzione della lista L di istruzioni viene ripetuta n volte (zero volte se n 0). Specificatamente, si definisca la funzione semantica

Mfor(for n do L, s)

in cui s rappresenta lo stato del programma, assumendo di avere a disposizione la funzione

Mlist(L, s) : lista di istruzioni nuovo stato o errore.


for n do L

Esercizio 9

Specificare la semantica denotazionale della seguente istruzione (ciclo a conteggio):

in cui n è una costante intera. L’esecuzione della lista L di istruzioni viene ripetuta n volte (zero volte se n 0). Specificatamente, si definisca la funzione semantica

Mfor(for n do L, s)

in cui s rappresenta lo stato del programma, assumendo di avere a disposizione la funzione

Mlist(L, s) : lista di istruzioni nuovo stato o errore.


Mfor(for n do L, s) = Mf(n, L, s).

Mf(n, L, s) = if n 0 then s

else if Mlist(L, s) = errore then errore

else Mf(n-1, L, Mlist(L, s)).

for n do L

Esercizio 10Specificare la semantica denotazionale di una espressione aritmetica con operatori di addizione ed assegnamento:


num rappresenta una costante intera; id rappresenta il nome di una variabile intera; la valutazione degli operandi della addizione è da sinistra a destra; è disponibile una funzione (id, s) che restituisce il valore della variabile id nello stato s (eventualmente UNDEF); è disponibile una funzione Mn(num) che restituisce il valore di num.


expr num | id | expr + expr | (id = expr)

Esercizio 10Specificare la semantica denotazionale di una espressione aritmetica con operatori di addizione ed assegnamento:


num rappresenta una costante intera; id rappresenta il nome di una variabile intera; la valutazione degli operandi della addizione è da sinistra a destra; è disponibile una funzione (id, s) che restituisce il valore della variabile id nello stato s (eventualmente UNDEF); è disponibile una funzione Mn(num) che restituisce il valore di num.

Dominio associato = (Z S) { errore }, in cui


Z = { interi }

S = { stati }

Me(num, s) = (Mn(num), s).

Me(id, s) = if (id, s) == UNDEF then errore else ((id, s), s) endif.

Me(expr1 + expr2, s) =

if Me(expr1, s) == errore then errore elsif Me(expr2, s1) == errore , where (_, s1) = Me(expr1, s), then errore else (v’, s’), where v’ = v1+v2, (v1, s1) = Me(expr1, s), (v2, s’) = Me(expr2, s1) endif.

Me((id = expr), s) =

if Me(expr, s) == errore then errore else (v’, s’’), where Me(expr, s) = (v’, s’), s’’ = {(i1, v1’’),…, (in, vn’’)}, k [1 .. n] vk’’ = endif.

(ik, s’) if ik id

v’ otherwise

expr num | id | expr + expr | (id = expr)

Esercizio 11Specificare la semantica denotazionale di una espressione relazionale di selezione:

in cui relexpr rappresenta una operazione di selezione, pred un predicato di selezione, ed id il nome di una tabella. Si assume che l’istanza (anche vuota) della tabella sia rappresentata da una lista (anche vuota) di tuple. Il risultato della selezione è costituito dalla sottolista di tuple della tabella per le quali il predicato di selezione risulta vero. In particolare, si chiede di specificare la funzione semantica Mr(relexpr, s), in cui s rappresenta lo stato del programma, assumendo di avere a disposizione le seguenti funzioni ausiliarie (di cui non è richiesta la specifica): (id, s): computa la lista di tuple della tabella di nome id (se è definita) oppure error (se non è definita). (p, t): computa il valore booleano del predicato p applicato alla tupla t. head(lista): restituisce la testa di lista. tail(lista): restituisce la coda di lista. cons(testa,coda): restituisce la lista (testa:coda), in cui testa è una tupla e coda una lista.


relexpr select [ pred ] relexpr | id

Esercizio 11Specificare la semantica denotazionale di una espressione relazionale di selezione:

in cui relexpr rappresenta una operazione di selezione, pred un predicato di selezione, ed id il nome di una tabella. Si assume che l’istanza (anche vuota) della tabella sia rappresentata da una lista (anche vuota) di tuple. Il risultato della selezione è costituito dalla sottolista di tuple della tabella per le quali il predicato di selezione risulta vero.


Mr(id, s) = (id, s).

Mr(select [ pred ] relexpr, s) = Msel(pred, Mr(relexpr, s)).

Msel(_, error) = error.Msel(_, [ ]) = [ ].Msel(p, T ) = if (p, head(T )) then cons(head(T ), Msel(p, tail(T ))) else Msel(p, tail(T )).

relexpr select [ pred ] relexpr | id

Esercizio 12Specificare la semantica denotazionale di una espressione relazionale di intersezione definita dalla seguente BNF:

in cui intexpr rappresenta l’operazione insiemistica di intersezione e table il nome di una tabella. Si assume che l’istanza (anche vuota) di ogni tabella sia rappresentata da una lista (anche vuota) di tuple senza duplicati. In particolare, si chiede di specificare la funzione semantica Mint(intexpr) assumendo di avere a disposizione la funzione ausiliaria Mid(table), di cui non è richiesta la specifica, che restituisce la lista di tuple della tabella di nome table (se è definita) oppure errore (se non è definita). Si richiede che la specifica denotazionale sia definita mediante la notazione di pattern-matching. In particolare, è possibile utilizzare il pattern (testa:coda) per una lista non vuota, ed il pattern [] per una lista vuota. Il linguaggio di specifica denotazionale non contiene operatori insiemistici, ad eccezione dell’appartenenza, . Non è richiesto il controllo di compatibilità dei due operandi.


intexpr ( intexpr intexpr ) | table

Esercizio 12Specificare la semantica denotazionale di una espressione relazionale di intersezione definita dalla seguente BNF:

in cui intexpr rappresenta l’operazione insiemistica di intersezione e table il nome di una tabella. Si assume che l’istanza (anche vuota) di ogni tabella sia rappresentata da una lista (anche vuota) di tuple senza duplicati. In particolare, si chiede di specificare la funzione semantica Mint(intexpr) assumendo di avere a disposizione la funzione ausiliaria Mid(table), di cui non è richiesta la specifica, che restituisce la lista di tuple della tabella di nome table (se è definita) oppure errore (se non è definita). Si richiede che la specifica denotazionale sia definita mediante la notazione di pattern-matching. In particolare, è possibile utilizzare il pattern (testa:coda) per una lista non vuota, ed il pattern [] per una lista vuota. Il linguaggio di specifica denotazionale non contiene operatori insiemistici, ad eccezione dell’appartenenza, . Non è richiesto il controllo di compatibilità dei due operandi.


Mint(table) = Mid(table).

Mint(intexpr1 intexpr2 ) = Inter(Mint(intexpr1 ), Mint(intexpr2 ))

Inter( _, errore ) = errore.Inter( errore, _ ) = errore.Inter( [ ], _ ) = [ ].Inter(testa:coda, T) = if testa T then testa:(Inter(coda,T)) else Inter(coda, T).

intexpr ( intexpr intexpr ) | table

Esercizio 13Specificare la semantica denotazionale di una espressione insiemistica che coinvolge operatori di unione () e differenza (), il cui linguaggio è definito dalla seguente BNF:

in cui expr rappresenta una espressione insiemistica e set il nome di un insieme. Si assume che l’istanza (anche vuota) di ogni insieme sia rappresentata da una lista (anche vuota) di elementi senza duplicazioni. In particolare, si chiede di specificare la funzione semantica Me(expr) assumendo di avere a disposizione la funzione ausiliaria Mid(set), di cui non è richiesta la specifica, che restituisce la lista di elementi dell’insieme di nome set (se è definito) oppure errore (se non è definito). Si richiede che la specifica denotazionale sia definita mediante la notazione di pattern-matching. In particolare, è possibile utilizzare il pattern (testa:coda) per una lista non vuota, ed il pattern [] per una lista vuota. Il linguaggio di specifica denotazionale non contiene operatori insiemistici, ad eccezione dell’appartenenza, . Non è richiesto il controllo di compatibilità dei due operandi.


expr ( expr expr ) | ( expr expr ) | set

Esercizio 13Specificare la semantica denotazionale di una espressione insiemistica che coinvolge operatori di unione () e differenza (), il cui linguaggio è definito dalla seguente BNF:


Me(set) = Mid(set).

Me(expr1 expr2 ) = Union(Me(expr1 ), Me(expr2 ))Me(expr1 expr2 ) = Diff(Me(expr1 ), Me(expr2 ))

Union( _, errore ) = errore.Union( errore, _ ) = errore.Union( [ ], S ) = S.Union(testa:coda, S) = if testa S then testa:(Union(coda,S)) else Union(coda, S).

Diff( _, errore ) = errore.Diff ( errore, _ ) = errore.Diff ( [ ], S ) = [ ].

Diff (testa:coda, S) = if testa S then testa:(Diff (coda,S)) else Diff(coda, S).

expr ( expr expr ) | ( expr expr ) | set

Esercizio 14È dato il seguente frammento di grammatica BNF relativo alla specifica di una istruzione condizionale in un linguaggio imperativo:

Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio assumendo la disponibilità delle seguenti funzioni ausiliarie (di cui non è richiesta la specifica):

• Mexpr(expr, s): restituisce il valore logico di expr allo stato s oppure ERRORE;• Mstat(stat, s): restituisce il nuovo stato oppure ERRORE dopo l’esecuzione di stat.

In particolare, si richiede la specifica della seguente funzione semantica:

Mif-stat(if-stat, s).


if-stat if expr then stat elsif-part else stat endifelsif-part elsif expr then stat elsif-part |

Esercizio 14È dato il seguente frammento di grammatica BNF relativo alla specifica di una istruzione condizionale in un linguaggio imperativo:


• Mexpr(expr, s): restituisce il valore logico di expr allo stato s oppure ERRORE;• Mstat(stat, s): restituisce il nuovo stato oppure ERRORE dopo l’esecuzione di stat.

In particolare, si richiede la specifica della seguente funzione semantica:

Mif-stat(if-stat, s).


if-stat if expr then stat1 elsif-part else stat2 endifelsif-part elsif expr then stat elsif-part2 |

Mif-stat(if-stat, s) = if Mexpr(expr, s) == ERRORE then ERRORE elsif Mexpr(expr, s) == TRUE then Mstat(stat1, s) elsif Melsif-part(elsif-part, s) == NULL then Mstat(stat2, s) else Melsif-part(elsif-part, s).

Melsif-part(elsif expr then stat elsif-part2, s) = if Mexpr(expr, s) == ERRORE then ERRORE elsif Mexpr(expr, s) == TRUE then Mstat(stat, s) else Melsif-part(elsif-part2, s).Melsif-part(, s) = NULL.

Esercizio 15Specificare la semantica denotazionale di una istruzione condizionale a due vie definita dalla seguente grammatica:

Si assume che:

• id rappresenti il nome di una variabile logica;

• la valutazione degli operandi nelle operazioni logiche sia da sinistra a destra;

• la valutazione della disgiunzione (or) sia in corto circuito;

• la valutazione della congiunzione (and) non sia in corto circuito;

• il linguaggio di specifica denotazionale disponga degli operatori logici Ù (congiunzione), Ú (disgiunzione), Ø (negazione), e degli operatori aritmetici +, -, *, /, applicabili unicamente ad operandi semanticamente corretti;

• siano disponibili le seguenti funzioni ausiliarie (di cui non è richiesta la specifica):

(id, s): restituisce il valore della variabile id nello stato s (o errore nel caso id non sia istanziata);Mstat(stat, s): restituisce lo stato raggiunto dalla esecuzione di stat allo stato s (eventualmente errore).


if-stat if expr then stat-list1 else stat-list2

stat-list stat stat-list1 | statexpr true | false | id | expr1 and expr2 | expr1 or expr2 | not expr1

Esercizio 15Specificare la semantica denotazionale di una istruzione condizionale a due vie definita dalla seguente grammatica:


if-stat if expr then stat-list1 else stat-list2

stat-list stat stat-list1 | statexpr true | false | id | expr1 and expr2 | expr1 or expr2 | not expr1

Mif-stat(if-stat, s) = if Me(expr, s) == errore then errore elsif Me(expr, s) == true then Mlist(stat-list1, s) else Mlist(stat-list2, s).

Mexpr(true, s) = true.Mexpr(false, s) = false.Mexpr(id, s) = (id, s).

Mexpr(expr1 and expr2, s) = if Me(expr1, s) == errore then errore elsif Me(expr2, s) == errore then errore else Me(expr1, s) Ù Me(expr2, s);

Mexpr(expr1 or expr2, s) = if Me(expr1, s) == errore then errore elsif Me(expr1, s) == true then true else Me(expr2, s) endif.

Mexpr(not expr1, s) = if Me(expr1, s) == errore then errore else ØMe(expr1, s) endif.

Mlist(stat stat-list1, s) = if Mstat(stat, s) == errore then errore else Mlist(stat-list1, Mstat(stat, s)) endif.

Mlist(stat, s) = Mstat(stat, s).

Esercizio 16Specificare la semantica denotazionale di una funzione Haskell-like definita dalla seguente grammatica (mediante il costrutto a guardie):

Si richiede la specifica del valore computato dalla funzione, assumendo che:

• non ci siano errori semantici nella valutazione delle condizioni (guardie) e delle espressioni;

• i parametri della funzione abbiano un valore intero;

• siano disponibili le seguenti funzioni ausiliarie (di cui non è richiesta la specifica):

Mexpr(expr): restituisce il valore (intero) di expr,Mcond(cond): restituisce il valore (booleano) di cond;

• il valore computato dalla funzione corrisponda alla prima espressione la cui condizione (guardia) risulti vera.

• nel caso in cui nessuna condizione (guardia) risulti vera, il valore computato sia nil.


function id param-list equation-listparam-list id param-list1 | idequation-list equation equation-list1 | equationequation '|' cond = expr

alfa x y z | x > y = x + y | x == z = z 1 | y < z = x * (y z)

esempio di frase

Esercizio 16Specificare la semantica denotazionale di una funzione Haskell-like definita dalla seguente grammatica (mediante il costrutto a guardie):


function id param-list equation-listparam-list id param-list1 | idequation-list equation equation-list1 | equationequation '|' cond = expr

alfa x y z | x > y = x + y | x == z = z 1 | y < z = x * (y z)

esempio di frase

Mf(id param-list equation-list) = Meq-list(equation-list).

Meq-list(equation equation-list1) = if Meq(equation) == (true, val) then val else Meq-list(equation-list1) endif.

Meq-list(equation) = if Meq(equation) == (true, val) then val else nil endif.

Meq(equation) = if Mcond(cond) == false then (false, _) else (true, Mexpr(expr) ) endif.

Esercizio 17

Specificare la semantica denotazionale di un frammento di codice definito dalla seguente BNF:

Il frammento è costituito da due operazioni: istanziazione di una lista di interi e appartenenza di un intero a tale lista. La lista non deve contenere duplicati e il nome della lista nella espressione di appartenenza deve coincidere con il nome della lista istanziata precedentemente. In particolare, si richiede la specifica delle seguenti funzioni semantiche:

• Mf(frammento): restituisce il risultato della operazione di appartenenza in frammento, (eventualmente error);

• Mnl(num-list): restituisce la lista di interi relativa a num-list, (eventualmente error).

Nel linguaggio di specifica denotazionale, è possibile esprimere l'operazione di appartenenza mediante il simbolo . Sono inoltre disponibili le seguenti funzioni ausiliarie (di cui non è richiesta la specifica):

• name(id): restituisce il valore lessicale (nome) di id;• value(num): restituisce il valore lessicale (valore) di num.


frammento id = [ num-list ] ; num in id.num-list num , num-list | num

S = [1,3,6,9,24];4 in S.

Esercizio 17



frammento id = [ num-list ] ; num in id.num-list num , num-list | num

S = [1,3,6,9,24];4 in S.

Mf(id1 = [ num-list ] ; num in id2.) = if name(id1) != nome(id2) then error elsif Mnl(num-list) == error then error else value(num) Mnl(num-list) endif.

Mnl(num) = [ value(num) ].Mnl(num , num-list) = if Mnl(num-list) == error then error elsif value(num) Mnl(num-list) then error else (value(num) : Mnl(num-list)) endif.

Esercizio 18

Specificare la semantica denotazionale del ciclo a conteggio definito dalla seguente BNF:

in cui [num1 .. num2] costituisce il range di valori interi per la variabile di conteggio id. In particolare, si richiede la specifica delle funzione semantica Mloop(loop-stat, s), in cui s rappresenta lo stato del programma. Sono disponibili le seguenti funzioni ausiliarie (di cui non è richiesta la specifica):

• name(id): restituisce il nome (attributo lessicale) di id;• value(num): restituisce il valore (attributo lessicale) di num.• value(nome, s): restituisce il valore della variabile nome nello stato s.• inscope(nome, s): restituisce un booleano, vero quando la variabile nome è visibile nello stato s.• Massign(nome, val, s): restituisce lo stato raggiunto (eventualmente error) dopo l'assegnamento della

variabile nome (nello stato s) con il valore val.• Mstat(stat, s): restituisce lo stato raggiunto (eventualmente error) dopo l'esecuzione di stat.


loop-stat for id = num1 to num2 do stat

Esercizio 18

Specificare la semantica denotazionale del ciclo a conteggio definito dalla seguente BNF:

in cui [num1 .. num2] costituisce il range di valori interi per la variabile di conteggio id. In particolare, si richiede la specifica delle funzione semantica Mloop(loop-stat, s), in cui s rappresenta lo stato del programma.


loop-stat for id = num1 to num2 do stat

Mloop(loop-stat, s) = if not inscope(name(id), s) then error else Mf(name(id), value(num2), stat, Massign(name(id), value(num1), s)) endif.

Mf(nome, val, stat, s) = if value(nome, s) > val then s elsif Mstat(stat, s) == error then error else Mf(nome, val, stat, Massign(nome, value(nome)+1, Mstat(stat, s))) endif.

Esercizio 19


Il frammento è costituito da due operazioni: assegnamento di un vettore di stringhe e indicizzazione di tale vettore. Il nome del vettore nella espressione di indicizzazione deve coincidere con il nome del vettore assegnato precedentemente. Inoltre, il valore dell'indice non deve uscire dai limiti di indicizzazione [0 .. n-1], in cui n è la dimensione del vettore. Si richiede la specifica delle seguenti funzioni semantiche:

• Mc(codice): restituisce il risultato della operazione di indicizzazione in codice, (eventualmente errore);• Msl(string-list): restituisce la lista di stringhe relativa a string-list.

Nel linguaggio di specifica denotazionale sono disponibili le seguenti funzioni ausiliarie (di cui non è richiesta la specifica):

• name(id): restituisce il valore lessicale (nome) di id;• ivalue(num): restituisce il valore lessicale (valore) di num.• svalue(string): restituisce il valore lessicale (valore) di string.• length(L): restituisce la lunghezza della lista L.• elem(L,i): restituisce l'elemento i-esimo della lista L.• cons(e,L): restituisce la lista (e:L).


codice id = [ string-list ] ; id [ num ].string-list string , string-list | string

v = ["alfa","beta","gamma","delta","epsilon"];v[3].

Esercizio 19



codice id = [ string-list ] ; id [ num ].string-list string , string-list | string

v = ["alfa","beta","gamma","delta","epsilon"];v[3].

Mc(id1 = [ string-list ] ; id2[num].) = if name(id1) != name(id2) then errore elsif ivalue(num) < 0 or ivalue(num) >= length(Msl(string-list)) then errore else elem(Msl(string-list), ivalue(num)) endif.

Msl(string) = [ svalue(string) ].Msl(string , string-list) = cons(svalue(string), Msl(string-list)).

Esercizio 20

È dato un linguaggio delle espressioni logiche definito dalla seguente grammatica BNF:

in cui:

• id rappresenta il nome di una variabile logica;• entails rappresenta l'operatore di implicazione logica;• la valutazione dell'operatore di implicazione è in corto circuito (da sinistra a destra).

Si chiede di:

• rappresentare la tabella di verità dell'operatore entails;• sulla base della relativa tabella di verità, definire la regola di corto circuito per l'operatore entails;• specificare la semantica denotazionale di una espressione logica.

Si assume che:

• sia disponibile una funzione value(id, s) che restituisce il valore della variabile id nello stato s; (nel caso in cui la variabile non abbia un valore, value restituisce ERRORE);

• il linguaggio di specifica denotazionale non disponga di alcun operatore logico.


expr true | false | id | expr1 entails expr2

Esercizio 20

È dato un linguaggio delle espressioni logiche definito dalla seguente grammatica BNF:


expr true | false | id | expr1 entails expr2

Me(true, s) = TRUE.

Me(false, s) = FALSE.

Me(id, s) = value(id, s).

Me(expr1 entails expr2, s) = if Me(expr1, s) == ERRORE then ERRORE elsif Me(expr1, s) == TRUE then Me(expr2, s) else TRUE endif.

A B A entails BF F TF T TT F FT T T

A entails B º (A ? B : true)

Esercizio 21

È dato un linguaggio delle espressioni logiche definito dalla seguente grammatica BNF :

in cui:

• id rappresenta il nome di una variabile logica;• xor rappresenta l'operatore di disgiunzione logica esclusiva (vero se e solo se un solo operando è

vero);• la valutazione dell'operatore xor è da sinistra a destra.

Si chiede di:

• rappresentare la tabella di verità dell'operatore xor;• sulla base della relativa tabella di verità, specificare l'espressione condizionale (non triviale) che

definisce l'operatore xor;• specificare la semantica denotazionale di una espressione logica sulla base della espressione

condizionale.

Si assume che:

• sia disponibile una funzione value(id, s) che restituisce il valore della variabile id nello stato s; (nel caso in cui la variabile non abbia un valore, value restituisce ERRORE);

• il linguaggio di specifica denotazionale non disponga di alcun operatore logico ad eccezione della negazione (!).


expr true | false | id | expr1 xor expr2

Esercizio 21

È dato un linguaggio delle espressioni logiche definito dalla seguente grammatica BNF :


expr true | false | id | expr1 xor expr2

A B A xor BT T FT F TF T TF F F

Me(true, s) = TRUE.


Me(id, s) = value(id, s).

Me(expr1 xor expr2, s) = if Me(expr1, s) == ERRORE then ERRORE elsif Me(expr1, s) == TRUE then if Me(expr2, s) = ERRORE then ERRORE else ! Me(expr2, s) endif else Me(expr2, s) endif.

A xor B º (A ? ØB : B)

Esercizio 22

È dato il seguente frammento di grammatica BNF relativo alla specifica di una istruzione case in un linguaggio imperativo:


• Mexpr(expr, s): restituisce il valore di expr (eventualmente ERROR) allo stato s;

• Mstat-list(stat-list, s): restituisce il nuovo stato (eventualmente ERROR) dopo l'esecuzione delle istruzioni in stat-list allo stato s;

• Mconst(const): restituisce il valore della costante const.


case-stat case expr of case-list default endcase-list case case-list | casecase const : stat-listdefault otherwise stat-list |

Esercizio 22

È dato il seguente frammento di grammatica BNF relativo alla specifica di una istruzione case in un linguaggio imperativo:


case-stat case expr of case-list default endcase-list case case-list | casecase const : stat-listdefault otherwise stat-list |

Mcase-stat(case-stat, s) = if Mexpr(expr, s) == ERROR then ERROR elsif Mcase-list(case-list, Mexpr(expr, s), s) NULL then Mcase-list(case-list, Mexpr(expr, s), s) else Mdefault(default, s) endif.

Mcase-list(case case-list, val, s) = if Mcase(case, val, s) NULL then Mcase(case, val, s) else Mcase-list(case-list, val, s) endif.

Mcase(case, val, s) = if Mconst(const) == val then Mstat-list(stat-list, s) else NULL endif.

Mcase-list(case, val, s) = Mcase(case, val, s).

Mdefault(otherwise stat-list, s) = Mstat-list(stat-list, s).

Mdefault(, s) = s.

Esercizio 23

È dato il seguente frammento di grammatica BNF, relativo alla specifica di un insieme di numeri:

Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio, definita come la somma di tutti i numeri positivi nell'insieme. Si assume la disponibilità della funzione ausiliaria Mn(num), che restituisce il valore lessicale di num.


set { numbers }numbers num , numbers | num

Esercizio 23


Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio, definita come la somma di tutti i numeri positivi nell'insieme. Si assume la disponibilità della funzione ausiliaria Mn(num), che restituisce il valore lessicale di num.


set { numbers }numbers num , numbers | num

Ms(set) = Msum(numbers).

Msum(num) = if Mn(num) > 0 then Mn(num) else 0 endif.

Msum(num , numbers) = Msum(num) + Msum(numbers).

Esercizio 24

È dato il seguente frammento di grammatica BNF, relativo alla specifica di una espressione di tipo intero in un linguaggio funzionale, che coinvolge costanti (num), identificatori (id) che hanno un binding con un valore intero, somme e chiamate di funzioni unarie (id(expr)):

Assumendo che l'esecuzione di una funzione possa generare errore, si chiede di specificare la funzione semantica Me(expr), relativa al corrispondente frammento di linguaggio, assumendo la disponibilità delle seguenti funzioni ausiliarie (di cui non è richiesta la specifica):

• Mn(num), che restituisce il valore lessicale (intero) di num;

• Mid(id), che restituisce il valore lessicale (stringa) di id;

• Ms(s), che restituisce il valore intero associato alla costante simbolica di nome s, oppure errore (nel caso in cui s non sia definita).

• Mf(f), che restituisce la l-espressione associata al nome f, oppure errore (nel caso in cui f non sia definito).


expr num | id | expr + expr | id(expr)

Esercizio 24

È dato il seguente frammento di grammatica BNF, relativo alla specifica di una espressione di tipo intero in un linguaggio funzionale, che coinvolge costanti (num), identificatori (id) che hanno un binding con un valore intero, somme e chiamate di funzioni unarie (id(expr)):

Assumendo che l'esecuzione di una funzione possa generare errore, si chiede di specificare la funzione semantica Me(expr), relativa al corrispondente frammento di linguaggio, assumendo la disponibilità delle seguenti funzioni ausiliarie (di cui non è richiesta la specifica):

• Mn(num), che restituisce il valore lessicale (intero) di num;

• Mid(id), che restituisce il valore lessicale (stringa) di id;

• Ms(s), che restituisce il valore intero associato alla costante simbolica di nome s, oppure errore (nel caso in cui s non sia definita).

• Mf(f), che restituisce la l-espressione associata al nome f, oppure errore (nel caso in cui f non sia definito).


expr num | id | expr + expr | id(expr)

Me(num) = Mn(num).

Me(id) = Ms(Mid(id)).

Me(expr1 + expr2) = if Me(expr1) == errore then errore elsif Me(expr2) == errore then errore else Me(expr1) + Me(expr2).

Me(id(expr)) = if Me(expr) == errore then errore elsif Mf(Mid(id)) == errore then errore else Mf(Mid(id))(Me(expr)).

Esercizio 25


Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio, definita come la media aritmetica dei numeri nell'insieme. Si assume la disponibilità della funzione ausiliaria Mn(numero), che restituisce il valore lessicale di numero.


insieme { numeri }numeri numero , numeri | numero

Esercizio 25


Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio, definita come la media aritmetica dei numeri nell'insieme. Si assume la disponibilità della funzione ausiliaria Mn(numero), che restituisce il valore lessicale di numero.


Mmedia(insieme) = Msomma(numeri) / Mcard(numeri)

Msomma(numero) = Mn(numero).Msomma(numero , numeri) = Mn(numero) + Msomma(numeri).

Mcard(numero) = 1.Mcard(numero , numeri) = 1 + Mcard(numeri).

insieme { numeri }numeri numero , numeri | numero

Esercizio 26

È dato il seguente frammento di grammatica BNF, relativo a una lista di istruzioni di un linguaggio imperativo:

Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio assumendo la disponibilità delle seguenti funzioni ausiliarie, che mappano una istruzione ed un certo stato in un nuovo stato (eventualmente errore):

• Md(declaration, s);

• Mc(conditional, s);

• Mi(iteration, s).

In particolare, si richiede la specifica della seguente funzione (che computa il nuovo stato, eventualmente errore):

• Mlist(instruction-list, s).


instruction-list instruction instruction-list instruction | instructioninstruction declaration | conditional | iteration

Esercizio 26

È dato il seguente frammento di grammatica BNF, relativo a una lista di istruzioni di un linguaggio imperativo:

Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio assumendo la disponibilità delle seguenti funzioni ausiliarie, che mappano una istruzione ed un certo stato in un nuovo stato (eventualmente errore):

• Md(declaration, s);

• Mc(conditional, s);

• Mi(iteration, s).

In particolare, si richiede la specifica della seguente funzione (che computa il nuovo stato, eventualmente errore):

• Mlist(instruction-list, s).


Minst(declaration, s) = Md(declaration, s).

Minst(conditional, s) = Mc(conditional, s).

Minst(iteration, s) = Mi(iteration, s).

Mlist(instruction, s) = Minst(instruction, s).

Mlist(instruction1 instruction-list instruction2, s) = if Minst(instruction1, s) = errore then errore elsif Mlist(instruction-list, Minst(instruction1, s)) = errore then errore else Minst(instruction2, Mlist(instruction-list, Minst(instruction1, s))).

instruction-list instruction instruction-list instruction | instructioninstruction declaration | conditional | iteration

Esercizio 27

È dato il seguente frammento di grammatica BNF:

che corrisponde all'iterazione su tutti gli elementi di un array di nome id2. Ad ogni iterazione, viene eseguita l'istruzione stat (che non altera l'array), in cui id1 rappresenta di volta in volta l'elemento corrente dell'array.

Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio, assumendo la disponibilità delle seguenti funzioni ausiliarie (in cui s rappresenta lo stato del programma):

• (id, s): restituisce la lista di elementi dell'array id, se questo è definito, altrimenti restituisce undef;

• Mstat(stat, s): restituisce lo stato raggiunto dalla computazione di stat (eventualmente errore).

In particolare, si richiede la specifica della funzione Mfor(for-stat, s), che computa il nuovo stato, eventualmente errore. Nella specifica denotazionale è possibile utilizzare il pattern lista vuota [] ed il pattern testa:coda.


for-stat foreach id1 in id2 do stat

Esercizio 27


che corrisponde all'iterazione su tutti gli elementi di un array di nome id2. Ad ogni iterazione, viene eseguita l'istruzione stat (che non altera l'array), in cui id1 rappresenta di volta in volta l'elemento corrente dell'array.

Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio, assumendo la disponibilità delle seguenti funzioni ausiliarie (in cui s rappresenta lo stato del programma):

• (id, s): restituisce la lista di elementi dell'array id, se questo è definito, altrimenti restituisce undef;

• Mstat(stat, s): restituisce lo stato raggiunto dalla computazione di stat (eventualmente errore).

In particolare, si richiede la specifica della funzione Mfor(for-stat, s), che computa il nuovo stato, eventualmente errore. Nella specifica denotazionale è possibile utilizzare il pattern lista vuota [] ed il pattern testa:coda.


for-stat foreach id1 in id2 do stat

Mfor(foreach id1 in id2 do stat, s) = if (id2, s) == undef then errore else iterate((id2, s), stat, s).

iterate([], _, s) = s.

iterate(_:coda, stat, s) = if Mstat(stat, s) == errore then errore

else iterate(coda, stat, Mstat(stat, s)).

Esercizio 28


in cui id è il nome di un vettore di numeri. L'operazione di somma vettoriale genera un nuovo vettore con dimensione pari alla dimensione minore dei due vettori, in cui ogni elemento corrisponde alla somma aritmetica dei due elementi nella nella stessa posizione nei due vettori. Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio, assumendo la disponibilità della funzione ausiliaria instance(id, s), in cui s rappresenta lo stato del programma, la quale restituisce la lista di numeri del vettore id, se questo è definito, altrimenti restituisce errore. Nella specifica denotazionale è possibile utilizzare il pattern lista vuota [] ed il pattern testa:coda.


vexpr vexpr + vexpr | id

Esercizio 28


in cui id è il nome di un vettore di numeri. L'operazione di somma vettoriale genera un nuovo vettore con dimensione pari alla dimensione minore dei due vettori, in cui ogni elemento corrisponde alla somma aritmetica dei due elementi nella nella stessa posizione nei due vettori. Si chiede di specificare la semantica denotazionale del corrispondente frammento di linguaggio, assumendo la disponibilità della funzione ausiliaria instance(id, s), in cui s rappresenta lo stato del programma, la quale restituisce la lista di numeri del vettore id, se questo è definito, altrimenti restituisce errore. Nella specifica denotazionale è possibile utilizzare il pattern lista vuota [] ed il pattern testa:coda.


vexpr vexpr + vexpr | id

Mvexpr(id, s) = instance(id, s).

Mvexpr(vexpr1 + vexpr2, s) = Msum(Mvexpr(vexpr1, s), Mvexpr(vexpr2, s)).

Msum(errore, _) = errore.

Msum(_, errore) = errore.

Msum([], _) = [].

Msum(_, []) = [].

Msum(x:xs, y:ys) = (x+y):Msum(xs, ys)

Esercizio 29

È dato il seguente frammento di grammatica BNF, relativo alla specifica del ciclo a condizione finale in un linguaggio imperativo:

Specificare la semantica denotazionale del corrispondente frammento di linguaggio, assumendo che id rappresenti il nome di una variabile logica, il linguaggio di specifica non disponga di operatori logici, siano disponibili le funzioni ausiliarie Mid(id, s), che restituisce il valore di id allo stato s (eventualmente errore), e Massign(assign-stat, s). In particolare, specificare la funzione semantica Mstat(stat, s).


do-stat do stat while exprexpr not expr | idstat assign-stat | do-stat

Esercizio 29

È dato il seguente frammento di grammatica BNF, relativo alla specifica del ciclo a condizione finale in un linguaggio imperativo:



do-stat do stat while exprexpr not expr | idstat assign-stat | do-stat


Mstat(do-stat, s) = Mdo(do-stat, s).

Mdo(do stat while expr, s) = if Mstat(stat, s) == errore then errore elsif Mexpr(expr, Mstat(stat, s)) == errore then errore elsif Mexpr(expr, Mstat(stat, s)) == false then Mstat(stat, s) else Mdo(do stat while expr, Mstat(stat, s)).

Mexpr(not expr, s) = if Mexpr(expr, s) == errore then errore elsif Mexpr(expr, s) == true then false else true endif.

Mexpr(id, s) = Mid(id, s).

Esercizio 30È dato un linguaggio delle espressioni logiche definito dalla seguente grammatica BNF :

in cui:

• id rappresenta il nome di una variabile logica;• nand rappresenta l'operatore logico binario così definito:

• la valutazione dell'operatore nand è da sinistra a destra.

Si chiede di:

• rappresentare la tabella di verità dell'operatore nand;• sulla base della relativa tabella di verità, specificare l'espressione condizionale (non triviale) che definisce

l'operatore nand;• specificare la semantica denotazionale di una espressione logica sulla base della espressione condizionale.

Si assume che:

• sia disponibile una funzione valore(id, s) che restituisce il valore della variabile id nello stato s; (nel caso in cui la variabile non abbia un valore, valore restituisce ERRORE);

• il linguaggio di specifica denotazionale non disponga di alcun operatore logico ad eccezione della negazione (!).


A nand B = not (A and B)

expr true | false | id | expr1 nand expr2

Esercizio 30È dato un linguaggio delle espressioni logiche definito dalla seguente grammatica BNF :

in cui:

• id rappresenta il nome di una variabile logica;• nand rappresenta l'operatore logico binario così definito:

• la valutazione dell'operatore nand è da sinistra a destra.


expr true | false | id | expr1 nand expr2

A nand B = not (A and B)

A nand B = (not A ? true : not B)

A B A nand BT T FT F TF T TF F T

Me(true, s) = TRUE.


Me(id, s) = valore(id, s).

Me(expr1 nand expr2, s) = if Me(expr1, s) == ERRORE then ERRORE elsif Me(expr1, s) == FALSE then TRUE elsif Me(expr2, s) = ERRORE then ERRORE else ! Me(expr2, s) endif.

Esercizio 31È dato un linguaggio delle espressioni indicizzate definito dalla seguente grammatica BNF :

in cui:

• id2 rappresenta il nome di una variabile intera;

• num rappresenta una costante intera;

• id1 [ expr ] rappresenta l'elemento della lista id1 alla posizione expr (partendo da 1).

Si chiede di specificare la semantica denotazionale del linguaggio sulla base dei seguenti requisiti:

• Se la variabile indicizzata non è una lista o l'indice è minore di 1 o la lunghezza della lista indicizzata è minore dell'indice, la semantica è ERRORE.

• Sia disponibile una funzione valnum(num) che restituisce il valore di num;

• Sia disponibile una funzione valid(id, s) che restituisce il valore della variabile id nello stato s (nel caso in cui la variabile non abbia un valore, valid restituisce ERRORE);

• Sia disponibile una funzione booleana list(id, s) che stabilisce se la variabile id nello stato s sia una lista;

• Nella specifica, è possibile utilizzare il pattern lista, nelle forme [] e (testa:coda).


expr id1 [ expr ] | id2 | num

Esercizio 31È dato un linguaggio delle espressioni indicizzate definito dalla seguente grammatica BNF :

in cui:

• id2 rappresenta il nome di una variabile intera;

• num rappresenta una costante intera;

• id1 [ expr ] rappresenta l'elemento della lista id1 alla posizione expr (partendo da 1).


expr id1 [ expr ] | id2 | num

Me(num, s) = valnum(num).

Me(id, s) = if valid(id, s) == ERRORE then ERRORE elsif list(id, s) then ERRORE else valid(id, s).

Me(id [ expr ], s) = if valid(id, s) == ERRORE then ERRORE elsif list(id, s) == FALSE then ERRORE elsif Me(expr, s) == ERRORE then ERRORE elsif Me(expr, s) < 1 then ERRORE elsif length(valid(id, s)) < Me(expr, s) then ERRORE else get(valid(id, s), Me(expr, s)) endif.

get((testa:_), 1) = testa.get((_:coda), i) = get(coda, i1).

Esercizio 32È dato un linguaggio di espressioni insiemistiche:

in cui id rappresenta il nome di una variabile di tipo lista, mentre rappresenta l'operatore di prodotto cartesiano.Si chiede di specificare la semantica denotazionale del linguaggio sulla base dei seguenti requisiti:

• Sia disponibile una funzione instance(id, s) che restituisce il valore (lista di elementi) della variabile id nello stato s (nel caso in cui la variabile non abbia un valore, instance restituisce ERRORE);

• Nella specifica denotazionale è possibile utilizzare i costrutti Haskell-like per la manipolazione di liste.


expr expr expr | id

Esercizio 32È dato un linguaggio di espressioni insiemistiche:

in cui id rappresenta il nome di una variabile di tipo lista, mentre rappresenta l'operatore di prodotto cartesiano.Si chiede di specificare la semantica denotazionale del linguaggio sulla base dei seguenti requisiti:

• Sia disponibile una funzione instance(id, s) che restituisce il valore (lista di elementi) della variabile id nello stato s (nel caso in cui la variabile non abbia un valore, instance restituisce ERRORE);

• Nella specifica denotazionale è possibile utilizzare i costrutti Haskell-like per la manipolazione di liste.


expr expr expr | id

Me(id, s) = instance(id, s).

Me(expr1 expr2, s) = if Me(expr1, s) == ERRORE then ERRORE elsif Me(expr2, s) == ERRORE then ERRORE else Prod(Me(expr1, s), Me(expr2, s)) endif.

Prod(X,Y) = [(x,y) | x < X, y < Y].

Esercizio 33

È dato il seguente frammento di grammatica BNF, relativo alla specifica del ciclo loop-until in un linguaggio imperativo (il ciclo termina quando la condizione risulta vera):

Specificare la semantica denotazionale del frammento di linguaggio, assumendo che id rappresenti il nome di una variabile logica, la congiunzione logica sia valutata in modo completo (non in corto circuito), il linguaggio di specifica disponga degli operatori logici and ed or, (ma non l'operatore di negazione), siano disponibili le funzioni ausiliarie Mid(id, s), che restituisce il valore di id allo stato s (eventualmente errore), e Massign(assign-stat, s). In particolare, specificare la funzione semantica Mstat(stat, s).


loop-stat loop stat until exprexpr expr and expr | not expr | id | true | falsestat assign-stat | loop-stat

Esercizio 33


loop-stat loop stat until exprexpr expr and expr | not expr | id | true | falsestat assign-stat | loop-stat


Mstat(loop-stat, s) = Mloop(loop-stat, s).

Mloop(loop stat until expr, s) = if Mstat(stat, s) == errore then errore elsif Mexpr(expr, Mstat(stat, s)) == errore then errore elsif Mexpr(expr, Mstat(stat, s)) == true then Mstat(stat, s) else Mloop(loop stat until expr, Mstat(stat, s)).

Mexpr(expr1 and expr2, s) = if Mexpr(expr1, s) == errore or Mexpr(expr2, s) == errore then errore else Mexpr(expr1, s) and Mexpr(expr2, s) endif.



Mexpr(true, s) = true.

Mexpr(false, s) = false.

Esercizio 34

È dato il seguente frammento di grammatica BNF, relativo alla specifica del ciclo foreach in un linguaggio imperativo:

Specificare la semantica denotazionale del frammento di grammatica, assumendo che siano disponibili le funzioni ausiliarie Mid(id, s), che restituisce il valore di id allo stato s (eventualmente errore), Massign(id, val, s), corrispondente all'assegnamento nello stato s della variabile id mediante il valore val, e Mstat(stat, s). In particolare, specificare la funzione semantica Mforeach(foreach-stat, s).


foreach-stat foreach id in id do stat endforforeach num in numeri do print(num)endfor;

Esercizio 34

È dato il seguente frammento di grammatica BNF, relativo alla specifica del ciclo foreach in un linguaggio imperativo:

Specificare la semantica denotazionale del frammento di grammatica, assumendo che siano disponibili le funzioni ausiliarie Mid(id, s), che restituisce il valore di id allo stato s (eventualmente errore), Massign(id, val, s), corrispondente all'assegnamento nello stato s della variabile id mediante il valore val, e Mstat(stat, s). In particolare, specificare la funzione semantica Mforeach(foreach-stat, s).


foreach-stat foreach id in id do stat endforforeach num in numeri do print(num)endfor;

Mforeach(foreach id1 in id2 do stat endfor, s) =

if Mid(id2, s) == errore then errore else Mf(id1, Mid(id2, s), stat, s).

Mf(id, [], stat, s) = s.

Mf(id, ((testa:coda), stat, s) = if Massign(id, testa, s) == errore then errore elsif Mstat(stat, Massign(id, testa, s)) == errore then errore else Mf(id, coda, stat, Mstat(stat, Massign(id, testa, s))).

Esercizio 35

È dato il seguente frammento di grammatica BNF, relativo alla specifica del ciclo repeat-untill in un linguaggio imperativo (il ciclo termina quando la condizione è vera):



repeat-stat repeat stat until exprexpr not expr | idstat assign-stat | repeat-stat

Esercizio 35

È dato il seguente frammento di grammatica BNF, relativo alla specifica del ciclo repeat-untill in un linguaggio imperativo (il ciclo termina quando la condizione è vera):



repeat-stat repeat stat until exprexpr not expr | idstat assign-stat | repeat-stat


Mstat(repeat-stat, s) = Mrepeat(repeat-stat, s).

Mrepeat(repeat stat until expr, s) = if Mstat(stat, s) == errore then errore elsif Mexpr(expr, Mstat(stat, s)) == errore then errore elsif Mexpr(expr, Mstat(stat, s)) == true then Mstat(stat, s) else Mrepeat(repeat stat until expr, Mstat(stat, s)).



Esercizio 36

È dato il seguente frammento di grammatica BNF, relativo alla specifica del ciclo repeat in un linguaggio imperativo:

Specificare la semantica denotazionale del corrispondente frammento di linguaggio, assumendo che siano disponibili le funzioni ausiliarie Mcond(condition, s), Massign(assign-stat, s) e Mif(if-stat, s). In particolare, specificare la funzione semantica Mstat(stat, s).


repeat-stat repeat stat stat until conditionstat assign-stat | if-stat | repeat-stat

Esercizio 36

È dato il seguente frammento di grammatica BNF, relativo alla specifica del ciclo repeat in un linguaggio imperativo:

Specificare la semantica denotazionale del corrispondente frammento di linguaggio, assumendo che siano disponibili le funzioni ausiliarie Mcond(condition, s), Massign(assign-stat, s) e Mif(if-stat, s). In particolare, specificare la funzione semantica Mstat(stat, s).



Mstat(if-stat, s) = Mif(if-stat, s).

Mstat(repeat-stat, s) = Mrepeat(repeat-stat, s).

Mrepeat(repeat stat1 stat2 while condition, s) =

if Mstat(stat1, s) == errore then errore elsif Mstat(stat2, Mstat(stat1, s)) == errore then errore elsif Mc(condition, Mstat(stat2, Mstat(stat1, s))) == errore then errore elsif Mc(condition, Mstat(stat2, Mstat(stat1, s))) == true then Mstat(stat2, Mstat(stat1, s)) else Mrepeat(repeat stat1 stat2 until cond, Mstat(stat2, Mstat(stat1, s))).

repeat-stat repeat stat stat until conditionstat assign-stat | if-stat | repeat-stat

Esercizio 37

È dato il seguente frammento di grammatica BNF, relativo ad una sequenza di costanti booleane:

Specificare la semantica denotazionale del corrispondente frammento di linguaggio, definita come la disgiunzione logica (or) dei valori booleani nella sequenza. Si assume la disponibilità della funzione ausiliaria Mb(boolconst), che restituisce il valore logico di boolconst. Per definizione, nel caso in cui la sequenza contenga un solo elemento, la sua semantica è il valore logico dell'elemento. Nella specifica, non sono disponibili gli operatori logici and, or, not.


sequence [ booleans ] booleans boolconst , booleans | boolconst

Esercizio 37

È dato il seguente frammento di grammatica BNF, relativo ad una sequenza di costanti booleane:

Specificare la semantica denotazionale del corrispondente frammento di linguaggio, definita come la disgiunzione logica (or) dei valori booleani nella sequenza. Si assume la disponibilità della funzione ausiliaria Mb(boolconst), che restituisce il valore logico di boolconst. Per definizione, nel caso in cui la sequenza contenga un solo elemento, la sua semantica è il valore logico dell'elemento. Nella specifica, non sono disponibili gli operatori logici and, or, not.


sequence [ booleans ] booleans boolconst , booleans | boolconst

Mor(sequence) = Mor(booleans).

Mor(boolconst) = Mb(boolconst).

Mor(boolconst , booleans) = if Mb(boolconst) then true else Mor(booleans) endif.

Esercizio 38

È data la seguente grammatica BNF relativa alla specifica di un numero di due cifre con qualifica della base numerica (terminale base che rappresenta una costante intera):

Specificare la semantica denotazionale che esprime il valore di una frase secondo i seguenti requisiti:

• È disponibile una funzione ausiliaria Val(base) che restituisce il valore della base;

• La base non può essere minore di 2 o maggiore di 10.

Ecco alcuni esempi:

14 (8) 12

28 (8) errore (8 non può essere una cifra in base 8)

10 (2) 2

13 (2) errore (3 non può essere una cifra in base 2)

13 (16) errore (16 non può essere una base)


num digit digit ( base ) digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Esercizio 38

È data la seguente grammatica BNF relativa alla specifica di un numero di due cifre con qualifica della base numerica (terminale base che rappresenta una costante intera):

Specificare la semantica denotazionale che esprime il valore di una frase secondo i seguenti requisiti:

• È disponibile una funzione ausiliaria Val(base) che restituisce il valore della base;

• La base non può essere minore di 2 o maggiore di 10.


num digit1 digit2 ( base ) digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

M(num) = if Val(base) < 2 or Val(base) > 10 or M(digit1) ³ Val(base) or M(digit2) ³ Val(base) then errore else M(digit1) * Val(base) + M(digit2).

M(0) = 0.M(1) = 1....

M(9) = 9.

Esercizio 39

É data la seguente grammatica BNF, relativa ad una espressione logica con disgiunzione e quantificatore esistenziale:

Specificare la semantica denotazionale che esprime il valore dell'espressione logica sulla base delle seguenti assunzioni:

• la valutazione degli operandi è da sinistra a destra;• la valutazione della congiunzione (and) è in corto circuito;• exists rappresenta il quantificatore esistenziale, in cui pred è il predicato e id l'identificatore di una lista

di tuple;• è disponibile la funzione value(id, s), che restituisce il valore della lista id nello stato s;• è disponibile la funzione predicate(pred, t, s), che restituisce il valore logico del predicato pred

applicato alla tupla t nello stato s;• se utile, è possibile utilizzare l'operatore || (disgiunzione) ed i pattern lista e costruttore lista di

Haskell;• si assume che non vi siano errori semantici.


relexpr true | false | relexpr and relexpr | exists [ pred ] id

Esercizio 39É data la seguente grammatica BNF, relativa ad una espressione logica con disgiunzione e quantificatore esistenziale:

Specificare la semantica denotazionale che esprime il valore dell'espressione logica sulla base delle seguenti assunzioni:

• la valutazione degli operandi è da sinistra a destra;• la valutazione della congiunzione (and) è in corto circuito;• exists rappresenta il quantificatore esistenziale, in cui pred è il predicato e id l'identificatore di una lista di tuple;• è disponibile la funzione value(id, s), che restituisce il valore della lista id nello stato s;• è disponibile la funzione predicate(pred, t, s), che restituisce il valore logico del predicato pred applicato alla tupla t

nello stato s;• se utile, è possibile utilizzare l'operatore || (disgiunzione) ed i pattern lista e costruttore lista di Haskell;• si assume che non vi siano errori semantici.


relexpr true | false | relexpr and relexpr | exists [ pred ] id

Mr(true, s) = TRUE.Mr(false, s) = FALSE.

Mr(relexpr1 and relexpr2, s) = if Mr(relxpr1, s) then Mr(relxpr2, s) else FALSE endif.

Mr(exists [ pred ] id, s) = Me(value(id, s), pred, s).

Me([], _, _) = FALSE.Me(testa:coda, pred, s) = predicate(pred, testa, s) || Me(coda, pred, s).

Esercizio 40

É data la seguente grammatica BNF, relativa ad una espressione logica:

in cui id indica il nome di una lista ed "empty id" è vero se e solo se la lista id è vuota. Si chiede di specificare la semantica denotazionale del linguaggio mediante una funzione M(logexpr, s) che esprime il valore dell'espressione logica nello stato s sulla base delle seguenti assunzioni:

• la valutazione degli operandi è da destra a sinistra;• la valutazione dell'operatore or è in corto circuito;• è disponibile la funzione val(id, s), che restituisce il valore della lista id nello stato s oppure ERRORE;• è disponibile la funzione length(lista), che restituisce la lunghezza di lista;• nel caso di errore semantico, viene restituito ERRORE.


logexpr true | false | logexpr or logexpr | empty id

Esercizio 40É data la seguente grammatica BNF, relativa ad una espressione logica:

in cui id indica il nome di una lista ed "empty id" è vero se e solo se la lista id è vuota. Si chiede di specificare la semantica denotazionale del linguaggio mediante una funzione M(logexpr, s) che esprime il valore dell'espressione logica nello stato s sulla base delle seguenti assunzioni:

• la valutazione degli operandi è da destra a sinistra;• la valutazione dell'operatore or è in corto circuito;• è disponibile la funzione val(id, s), che restituisce il valore della lista id nello stato s oppure ERRORE;• è disponibile la funzione length(lista), che restituisce la lunghezza di lista;• nel caso di errore semantico, viene restituito ERRORE.


M(true, s) = TRUE.M(false, s) = FALSE.

Mr(logexpr1 or logexpr2, s) = if M(logexpr2, s) == ERRORE then ERRORE elsif M(logexpr2, s) == TRUE then TRUE else M(logexpr1 s) endif.

Mr(empty id, s) = if val(id, s) == ERRORE then ERRORE else length(val(id,s)) == 0 endif.

logexpr true | false | logexpr or logexpr | empty id

gianfranco-lamperti.unibs.it...Esercizio 2 Specificare la semantica denotazionale della seguente...

Documents

Transcript of gianfranco-lamperti.unibs.it...Esercizio 2 Specificare la semantica denotazionale della seguente...