Semantica operazionale dei linguaggi di Programmazione · sempliﬁcando alberi di derivazione In...

Semantica operazionale deilinguaggi di Programmazione

Oggetti sintattici e oggetti semantici

Rosario Culmone, Luca Tesei

Lucidi tratti dalla dispensa

“Elementi di Semantica Operazionale”

R. Barbuti, P. Mancarella e F. Turini

Universita degli Studi di Camerino - Corso di Laurea in Informatica - Programmazione - Semantica - Oggetti sintattici e oggetti semantici – p.1/51

Oggetti sintattici

Nella prima parte del corso abbiamo visto alcunistrumenti per definire formalmente dei linguaggi

Abbiamo visto come le regole di una grammatica liberadal contesto non ambigua diano una struttura benprecisa ad ogni stringa de linguaggio

Tale struttura è ricorsiva se il linguaggio non è banale(finito)

Tale struttura è completamente rappresentatadall’albero di derivazione


Oggetti sintattici

Abbiamo più volte sottolineato il fatto che le stringhe diun linguaggio sono di base oggetti simbolici puri

Non hanno un significato particolare associato, a partequello di essere stringhe formate con certi simboli

Siamo noi che diamo loro un significato a seconda delcontesto in cui le usiamo

Tale significato lo chiameremo semantica del linguaggio

Possiamo assegnare infinite semantiche ad uno stessolinguaggio!


Funzioni di valutazione semantica

In un contesto informale il significato di una parola o diuna frase può essere ambiguo

Nel nostro ambito vogliamo la massima precisione

Assegneremo la semantica in maniera formale

Definiremo in maniera rigorosa delle funzioni cheassociano ad ogni stringa del linguaggio il relativosignificato

Il significato sarà un elemento di un certo dominiosemantico


Domini semantici

Se gli oggetti sintattici sono definiti precisamente,altrettanto vogliamo per gli oggetti semantici

Utilizzeremo come domini semantici gli oggettimatematici:

Insiemi con relative operazioni: numeri naturali con+, ×, . . .

Funzioni parziali o totali fra domini semanticiStrutture: pile di funzioni, alberi, . . .

. . .

Le funzioni di valutazione semantica saranno definite inmaniera formale


Stringhe di cifre

Facciamo il primo esempio di funzione di valutazionesemantica

Consideriamo gli elementi della categoria sintattica Num

Sono stringhe formate da cifre decimali

Qual è il loro significato?

A noi risulta naturale pensare ai numeri naturali, perchéquesta è la semantica che quasi sempre vieneassegnata loro

Ma tali stringhe sono solo una possibile rappresentazionedei numeri naturali!


Stringhe di cifre

Formalmente ciò che lega una stringa di cifre decimali aun numero naturale è una funzione che associa ad ognistringa un certo numero naturale

Questa funzione è un esempio di funzione divalutazione semantica: lega oggetti sintattici a elementidi un certo dominio semantico

Vediamo come può essere definita formalmente talefunzione

Sappiamo che il sistema di numerazione in base diecifunziona in questo modo:La stringa 134 rappresenta il numero1 · 102 + 3 · 101 + 4 · 100 = 1 · 100 + 3 · 10 + 4 · 1


Formalizziamo

Indichiamo con n, n′, . . . elementi della categoriasintattica Num, cioè stringhe generate dalla grammatica

Num ::= Num Cif | CifCif ::= 0 | 1 | ... | 9

Indichiamo con n, n′, . . . numeri naturali:IN = {0, 1, 2, 3, 4, 5, . . .}

Definiamo una funzione η: Num → IN che lega ad ognistringa il numero naturale denotato


Definizione diη

La funzione η può essere convenientemente definita inmaniera ricorsiva utilizzando la struttura ricorsiva asinistra suggerita dalla grammatica:

η(0) = 0

η(1) = 1

. . .

η(9) = 9

η(nc) = (η(n) × 10) + η(c)


Altre rappresentazioni

I numeri naturali possono avere un numero infinito dirappresentazioni sintattiche!

Ad esempio possiamo utilizzare una notazione binariain cui i simboli sono le lettere dell’alfabeto {z, u}

La grammatica che usiamo è:

Binary ::= Bit | Binary BitBit ::= z | u

Possiamo definire in maniera analoga alla precedenteuna funzione che associa a queste stringhe un numeronaturale: η′: Binary → IN


Altre rappresentazioni

Basta associare a z il numero 0, ad u ul numero 1 e poiutilizzare il sistema binario di rappresentazione:zuzz rappresenta 0 · 23 + 1 · 22 + 0 · 21 + 0 · 20 = 4

η′(z) = 0

η′(u) = 1

η′(xb) = (η′(x) × 2) + η′(b)


Applicazione di η′

η′(zuzz) = (η′(zuz) × 2) + η

′(z)

= (η′(zuz) × 2) + 0

= (((η′(zu) × 2) + η′(z)) × 2) + 0

= (((η′(zu) × 2) + 0) × 2) + 0

= (((((η′(z) × 2) + η′(u)) × 2) + 0) × 2) + 0

= (((((0× 2) + 1) × 2) + 0) × 2) + 0

= ((((0 + 1) × 2) + 0) × 2) + 0

= (((1× 2) + 0) × 2) + 0

= ((2 + 0) × 2) + 0

= (2× 2) + 0

= 4 + 0

= 4


Espressioni

Definiamo formalmente l’associazione fra espressioniaritmetiche e loro valore

La definizione formale di questa funzione di valutazionesemantica sarà il primo passo verso il nostro obiettivofinale

Ci concentreremo attentamente su tutte le fasi di questoesempio

Nel seguito infatti lo schema di definizione sarà semprelo stesso


Sintassi

Abbiamo già visto come si scrive una grammatica per leespressioni con operatori a cui è assegnata unaprecedenza e una regola di associatività

Tali regole si riflettono sull’albero di derivazione cherappresenta precisamente la struttura della stringa. Adesempio 9 + 3 ∗ 16:

EE + TT T * FF F Num

Num Num Num CifCif Cif Cif 69 3 1


Sintassi

La risoluzione dell’ambiguità della grammatica e lagestione delle regole di precedenza e di associativitàrendono l’albero di derivazione complesso

In realtà basterebbe una rappresentazione più sempliceper rappresentare la struttura della stringa

Quello che faremo da adesso in poi è utilizzare unalbero di derivazione semplificato chiamato alberosintattico

L’albero sintattico non è dettagliato come l’albero diderivazione ed esprime solo ciò che serve ai fini delladefinizione della semantica


Albero sintattico

Ad esempio l’albero sintattico corrispondente all’alberodi derivazione della stringa 9 + 3 ∗ 16 introdotta prima è:

Exp

Exp + Exp

9 Exp * Exp

3 16


Albero sintattico

Nell’albero sintattico sono indicati solo gli operandi e glioperatori

La struttura dei sottoalberi esprime le regole diprecedenza e associatività

Tutto il resto è omesso

Da un albero di derivazione è semplice ottenere ilcorrispondente albero sintattico

Si può dire che l’albero sintattico è unarappresentazione compatta dell’albero di derivazione


Convenzione

Da ora in poi useremo solo alberi sintattici come oggettisintattici

Assumeremo che ai nostri sistemi di transizionivengano sempre passati alberi sintattici ottenutisemplificando alberi di derivazione

In questo modo semplifichiamo i sistemi di transizioniche si concentrano solo sul problema della definizionedella semantica

Chi fornisce gli alberi sintattici si occuperà dei problemirelativi alla scrittura della grammatica giusta, problemiprettamente sintattici


Grammatiche semplici

Alla luce di questa convenzione facciamo ancheun’altra operazione di semplificazione

Non usiamo grammatiche complicate introdotte pergestire i problemi di ambiguità eprecedenza/associatività

Per specificare la sintassi ci basterà scriveregrammatiche semplici, anche ambigue

Questo perché comunque i problemi di questegrammatiche sono risolti alla fonte: ci viene passato unalbero sintattico


Grammatica semplice

Daremo semantica precisamente all’albero sintattico,considerando solamente gli operandi, gli operatori e lastruttura di questo

Quindi per specificare la sintassi delle espressioni cibasterà utilizzare questa grammatica:

Exp ::= Num | (Exp) | Exp Op ExpOp ::= + | - | * | / | %

Chi ci fornisce gli alberi sintattici si sarà preoccupato dieliminare l’ambiguità e di aver espresso nell’alberostesso la struttura della stringa in accordo allaprecedenza/associatività


Convenzione di scrittura

Risulterà comodo, per la chiarezza dell’esposizione,poter rappresentare un albero sintattico in manieralineare, cioè senza disegnare l’albero

Per far questo aggiungeremo alle stringhe delleparentesi quadre che indicheranno la strutturadell’albero...


Convenzioni di scrittura

Ad esempio, per indicare l’albero sintattico:

Exp

Exp + Exp

9 Exp * Exp

3 16

scriveremo la stringa 9 + [3 ∗ 16]


Metavariabili

Utilizzeremo i simboli E, E′, E1, E2, . . . per denotare alberisintattici della categoria sintattica Exp

In questo caso quindi la scrittura E ∈ Exp denota che E èun albero sintattico, non una stringa

Ometteremo queste premesse nelle regole, poichéusiamo metavariabili


Matching

Per il matching bisogna tener conto della struttura: E+E′

fa match con 9 + [3 ∗ 16] ponendo E = 9 ed E′ = 3 ∗ 16

9 + [3 ∗ 16] non fa match con E ∗ E′ poiché l’albero9 + [3 ∗ 16] non ha al primo livello l’operatore ∗

Un albero che fa match con E ∗ E′ potrebbe essere[([9 + 3])] ∗ 16

Si noti che le parentesi hanno al loro interno l’albero9 + 3, che è a tutti gli effetti un sottoalbero dell’albero([9 + 3])


Calcolo del valore

Abbiamo tutti gli ingredienti per definire un sistema ditransizioni che calcola il valore di una espressione

Naturalmente sarà un sistema big-step che utilizzacome base per la ricorsione la relazione di sottoalberodegli alberi sintattici

Le regole saranno guidate dalla sintassi: ogni casosintattico della grammatica semplificata avrà una regolasemantica

Nelle configurazioni non ci saranno stringhe, ma alberisintattici


Configurazioni

Le configurazioni del sistema sono le seguenti

Γexp = {E | E ∈ Exp} ∪

{n | n ∈ IN}

Texp = {n | n ∈ IN}

Come abbiamo visto in precedenza, poiché il sistema èdefinito nello stile big-step non abbiamo bisogno diconfigurazioni intermedie


Configurazioni

Si noti come ad una configurazione contentente unoggetto sintattico (l’albero sintattico) il sistema associauna configurazione terminale formata da un oggetto diun dominio semantico (un numero naturale)

Questo sistema sarà la base con cui definiremo lafunzione di valutazione semantica delle espressioniaritmetiche

Dalla grammatica vediamo che per ora le espressionihanno come operandi solo stringhe di Num

Partiamo con la prima regola che tratta il caso base...


Regole per→exp

Una espressione il cui albero sintattico è formato soloda una stringa di cifre n, elemento della categoriasintattica Num, ha come valore il numero naturaledenotato da n

In questo caso supponiamo che il sistema sia in gradodi ottenere il numero dalla rappresentazione, adesempio usando la funzione η definita sopra

La regola di →exp per questo caso sintattico non hapremesse:

n →exp n (expn)


Regole per→exp

?

E+E′ →exp?

Vediamo la regola (exp+) che gestisce il caso sintatticoExp + Exp

La configurazione di “input” richiede che venga passatoun albero sintattico in cui al primo livello ci sial’operatore + applicato a due sottoalberi E ed E′

Per calcolare il valore di tutta l’espressione abbiamobisogno del valore delle espressioni che sono neisottoalberi...


Regole per→exp

E →exp n ?

E+E′ →exp?

Per calcolare il valore dell’espressione rappresentatadal sottoalbero E applichiamo la ricorsione

L’ipotesi induttiva ci garantisce che il sistema è in gradodi effettuare il calcolo sull’albero E poiché questo è unalbero più piccolo dell’albero che si sta trattando

Inoltre l’ipotesi induttiva garantisce che se il calcoloviene effettuato allora il risultato, che chiamiamo n, ècorretto


Regole per→exp

E →exp n E′ →exp n′

E+E′ →exp?

Facciamo una chiamata ricorsiva anche sul sottoalberodestro E′ per ottenere il valore n′

Non ci resta che applicare l’operatore semantico disomma tra numeri naturali per ottenere il valoredell’espressione E+E′


Regole per→exp

E →exp n E′ →exp n′ m = n + n′

E+E′ →exp m

Chiamiamo m il valore della somma e poniamolo comeconfigurazione di arrivo

Facciamo ora una precisazione sugli operatori e sullaloro rappresentazione


Operatori e loro rappresentazione

Anche per gli operatori, come per i numeri, bisognadistinguere tra rappresentazione sintattica e operatorevero e proprio

Nella regola precedente abbiamo utilizzato il + siacome simbolo di alfabeto che come operatore binariofra numeri naturali

Nell’albero sintattico E + E′ il + è un mero simbolo, lasemantica può assegnargli un qualsiasi significato

Nell’equazione m = n + n′ il + è il ben noto operatore disomma tra numeri naturali


Operatori e loro rappresentazione

Formalmente è buona regola usare due simboli diversio degli accorgimenti tipografici per distinguerli

In questo caso facciamo un’eccezione a questa regola,ma per altri operatori faremo la distinzione

Quando uno stesso simbolo, come in questo caso il +,viene usato per rappresentare diversi oggetti bisognafare attenzione al suo uso

In genere si capisce dal contesto il significato daattribuirgli di volta in volta

Se questo non è vero allora conviene distinguere isimboli o specificare di volta in volta il significato


Regole per→exp

E →exp n E′ →exp n′ m = n× n′

E*E′ →exp m

Questa regola (exp∗) si occupa del caso sintattico

Exp ∗ Exp

Essa opera allo stesso modo di (exp+): fa due chiamatericorsive e un calcolo

In questo caso abbiamo distinto il simbolo ∗dall’operatore di prodotto fra numeri naturali vero eproprio, rappresentato con ×


Regole per→exp

E →exp n E′ →exp n′ ?

E / E′ →exp?

Questa regola (expdiv ) si occupa del caso sintatticoExp/Exp

Come operatore useremo div , che fa la divisione interafra numeri naturali: il risultato è un numero naturale el’operazione ha un resto

Una volta che abbiamo ottenuto i valori delleespressioni dei sottalberi si presenta un problema

Se il valore n′ è 0 l’operatore div non è applicabile!


Regole per→exp

E →exp n E′ →exp n′ n′ 6= 0 m = n div n′

E / E′ →exp m

Dobbiamo inserire nelle premesse una condizionelogica che escluda questo caso, cioè n′ 6= 0

A questo punto possiamo andare avanti e applicarel’operatore div per ottenere il risultato m

Ma cosa succede al sistema se il valore di n′ è proprio0?


Configurazioni Bloccate

Supponiamo di mettere il sistema nella configurazione4/0

Che valore ci aspettiamo per questa espressione?

Chiaramente non possiamo aspettarci nessun numeronaturale se interpretiamo il simbolo / come la divisioneintera!

La regola che abbiamo scritto ha una premessa cheesclude la sua applicabilità nei casi in cui il divisore sia0

Non essendoci altre regole che gestiscono questo casoquello che abbiamo è che il sistema si blocca


Configurazioni Bloccate

Abbiamo visto che una configurazione γ di un sistemadi transizioni si dice bloccata se non è terminale e senon esiste nessuna configurazione γ′ tale che γ → γ′

Questo è proprio il caso di tutte le configurazioni checontengono alberi sintattici in cui in qualche sottoalberoc’è una divisione per un’espressione che ha valore 0

Es: 4/0, 3 + [53/0], 4 ∗ [25/[([2 − 2])]], . . .


Configurazioni bloccate

Alla luce di questo fatto dobbiamo rivedere l’ipotesiinduttiva

Quello che possiamo veramente assumere è che, datoun sottoalbero E dell’albero che stiamo gestendo, lachiamata ricorsiva del sistemase non si bloccaallora è in grado di restituire il valore associato allaespressione rappresentata dal sottoalbero


Configurazioni bloccate

Quindi in ogni regola in cui nelle premesse usiamo laricorsione può succedere che il sistema si blocchiprovocando, a sua volta, il blocco della regola inquestione

Ad esempio il sottoalbero 3/0 dell’albero 2 ∗ [3/0]provocherà il blocco di tutta la configurazione 2 ∗ [3/0]gestita dalla regola (exp

∗)

Anche la regola per %, che rappresenta l’operatore chedà il resto della divisione intera, può provocare deiblocchi...


Regole per→exp

E →exp n E′ →exp n′ n′ 6= 0 m = n mod n′

E % E′ →exp m

In questa regola (expmod) trattiamo il caso sintatticoExp % Exp

L’operatore semantico è rappresentato con mod

Anche in questo caso c’è bisogno della premessa cheesclude i casi in cui il divisore sia 0


Regole per→exp

E →exp n E′ →exp n′ ?

E-E′ →exp?

In questa regola (exp−) si presenta un altro problema:

che succede se n′ è più grande di n?

Tutto dipende dal dominio semantico che vogliamoutilizzare

Se come dominio semantico usiamo l’insieme IN allorain questi casi il sistema si deve bloccare


Regole per→exp

E →exp n E′ →exp n′ n ≥ n′ m = n− n′

E-E′ →exp m

Se invece usassimo l’insieme dei numeri interi allorapotremmo trattare i numeri negativi

Per semplicità prendiamo IN e facciamo bloccare ilsistema

Si noti che, come per +, anche al simbolo − diamo undoppio significato


Regole per→exp

E →exp n

(E) →exp n

Questa regola (exp()) semplicemente esprime il fatto

che il valore di un’espressione tra parentesi è uguale alvalore dell’espressione dentro la parentesi

Si noti che la ricorsione è applicata correttamentepoiché l’albero E è un sottoalbero dell’albero (E)


Derivazione

Facciamo un esempio di derivazione che usa le regoleviste:

25 - 15 / 2

→exp { (exp−),

(expn): 25 →exp 25,(d1): 15 / 2 →exp 7,25 ≥ 7, 25− 7 = 18 }

18

E’ utilizzata una sottoderivazione (d1)...


Derivazione

Vediamo la sottoderivazione (d1) attivata dalladerivazione principale:

(d1):

15 / 2

→exp { (expdiv ),(expn): 15 →exp 15,(expn): 2 →exp 2,2 6= 0, 15 div 2 = 7 }

7


Derivazione ad albero

E’ possibile esprimere una derivazione anchecostruendo un albero in cui le sottoderivazioni sonosottoalberi:

2 → 2(exp

n)

3 → 3(exp

n)

8 → 8((exp

n)

11 = 3 + 8

3 + 8 → 11(exp

+)

13 = 2 + 11

2 + [3 + 8] → 13

(exp+

)

Si noti che l’applicazione di regole senza premessedetermina un nodo foglia (cioè senza figli) dell’albero

Nel seguito, tuttavia, continueremo ad utilizzareprevalentemente le sottoderivazioni


Funzione di valutazione semantica

Possiamo ora definire formalmente la funzione divalutazione semantica E che associa ad un alberosintattico E di Exp il suo valore

Il dominio semantico di riferimento è l’insieme deinumeri naturali IN con le operazioni in esso definite:+,−,×, div ,mod

Il tipo della funzione è il seguente:

E : Exp → IN

La definizione di questa funzione viene data mediante ilsistema di transizione 〈Γexp , Texp ,→exp〉



Per definire E usiamo una notazione speciale che staad indicare che la funzione che stiamo definendo è unafunzione di valutazione semantica:

E [[E]] = k se e solo se E →exp k

Dalla definizione e dalle regole che abbiamo scrittosegue che E , a differenza di η, non è definita per tutte leespressioni

Infatti abbiamo visto che per certe espressioni E ilsistema che abbiamo definito si blocca

In questo caso la definizione “se e solo se” non dànessun valore per E [[E]]



Una funzione si dice totale se è definita per tutti glielementi del suo dominio

Se almeno per un elemento del dominio la funzione nonè definita allora si dice che è parziale

E è quindi una funzione parziale

In particolare E non è definita per ogni E ∈ Exp tale cheE 6→exp

Spesso si usa la seguente notazione per indicare che lafunzione su un certo elemento del dominio non èdefinita: E [[3/0]] = ⊥

⊥ si legge “bottom” o “indefinito”


Semantica operazionale dei linguaggi di Programmazione · sempliﬁcando alberi di derivazione In...

Documents

Transcript of Semantica operazionale dei linguaggi di Programmazione · sempliﬁcando alberi di derivazione In...