1

1

Sintassi e semantica

• La sintassi dei linguaggi e la compilazione

(cenni, materia ripresa nel corso di Linguaggi di Programmazione)

• Introduzione alla semantica

• La semantica operazionale di un semplice linguaggio

2

abbiamo visto: Linguaggi (artificiali)

La descrizione di un linguaggio avviene su tre dimensioni (Morris, 1939):

– sintassi

– semantica

– pragmatica

regole di formazione:quando una frase è corretta

relazioni tra segni

attribuzione di significato:cosa significa una frase correttarelazioni tra segni e significato

in qual modo frasi corrette e sensatesono usate

relazioni tra segni, significato e utente

Per un linguaggio eseguibile:

– implementazione

eseguire una frase corretta,rispettandone la semantica

2

3

già visto: Come è descritto un LP in queste tredimensioni?

– Sintassi• formale: grammatiche formali , BNF (Backus Naur Form)

• quasi-formale: tipizzazione, vincoli contestuali

– Semantica• informale: linguaggio naturale, manuale

• formale: denotazione, operazionale

– Pragmatica• informale: esempi

• semi-formale: metodologie di programmazione

– Implementazione• derivazione dalla semantica

• macchina astratta

4

Sintass i e semantica

Sintassi• Definisce quali frasi fanno parte del linguaggio, ovvero quali sequenze di

caratteri costituiscono un programma “legale”• Ci dice come “appare” un programma• Strumenti per descrivere la sintassi:

– grammatiche generative (Chomsky)– automi– BNF

Semantica• Specifica il “significato” di ogni programma legale• Specifica il comportamento del programma al momento dell’esecuzione• Semantica Statica : Semantica che può essere determinata al momento della

compilazione• Semantica Dinamica: Semantica determinata durante l’esecuzione• Metodologie usate per definire la semantica:

– Algebrica - Operazionale– Assiomatica - Denotazionale

3

5

Sintass i

• Ci dice come costruire le frasi corrette del linguaggio:

var A: integer; if a> 0 then C else C’

Var A: intgr; if a> 0 else C’ then C;

Errore lessicale Errore grammaticale

• Stessi costrutti espressi in modo diverso in linguaggi diversi.Es: un vettore di 10 elementi interi

In C: int V[10]

In Pascal: V: array[0..9] of integer

Presumibilmente questi due oggetti hanno lo stesso significato(ovvero la stessa semantica).

6

Sintass i

• Come definire e riconoscere i costrutti corretti del linguaggio ?

• Problema essenziale nella fase di compilazione di un programma

• Enumerazione di tutti i programmi ben formati ? … un po’ lungo

• Vari strumenti:

- grammatiche generative: regole per costruire le frasi del linguaggio

- grammatiche regolari

- grammatiche libere da contesto

- automi: formalismi per riconoscere i costrutti di un linguaggio

- BNF: Backus Naur Form usata la prima volta per Algol in 1958 da Naur (chair di Algol committee) e Backus (segretario)

- stessa cosa della grammatiche libere da contesto

4

7

Fasi nella traduzione di un programma

8

Fasi principali della compilazione

Analisi lessicale (Scanner): Spezza un programma nei componenti sintattici primitvi,chiamati tokens (identificatori, numeri, parole riservate …)

- grammatiche regolari

- automi a stati finiti

Analisi sintattica (Parsing): Crea una rappresentazione ad albero della sintassi delprogramma. Riconosce le frasi ben formate del linguaggio

- grammatiche libere da contetso

- pushdown automata

- BNF

Tabella dei simboli: Memorizza le informazioni sugli oggetti dichiarati (identificatori,procedure … )

Analisi semantica: Esegue dei controlli di semantica staticaper rilevare eventuali errori(vedi pu’ avanti).

Ottimizzazione: Riscrive l’albero sintattico che rappresenta un programma in modo damigliorarne l’efficienza

Generazione del codice: converte il programma analizzato sintatticamente in una versioneeseguibile

Tutto questo (e altro) è argomento di un corso del III Anno: Linguaggi di Programmazione

5

9

Traduzione ed esecuzione

10

Definire un linguaggio: un esempio

Le stringhe delle espressioni aritmetiche formate a partire dalle variabili

A, B

con gli operatori

*, +

e le parentesi (, )

Esempî: A A+B

A+B+A (A+B+A)

A+(A*B) …

Un’espressione può essere:la variabile A oppurela variabile B oppure

un’espressione * un’espressione oppureun’espressione + un’espressione oppure

( un’espressione )

La definizione è ricorsiva…

6

11

Derivare una stringa

A+(A*B) è un’espressione, perché:

un’espressione può essere un’espressione + un’espressione

ovvero può essere A + un’espressione

ovvero può essere A + ( un’espressione )

ovvero può essere A + ( un’espressione * un’espressione )

ovvero può essere A + ( A * un’espressione)

ovvero può essere A + ( A * B )

Un’espressione può essere:la variabile A oppurela variabile B oppureun’espressione * un’espressione oppureun’espressione + un’espressione oppure

( un’espressione )

Distinguiamo:

terminali

non-terminali

ausiliari

Riscriviamo un non-terminale usando unaregola della forma:

non-terminale può esserestringa-di-terminali-e-non-terminali

12

Linguaggi formali

Def.: Un alfabeto A è un qualsiasi insieme (finito, non vuoto) i cui elementi sonodetti caratteri (o simboli)

Def.: Una parola sull’alfabeto A è una sequenza finita o nulla di caratteriappartenenti ad A.

Def.: Un linguaggio (formale) L su A è un qualsiasi insieme di parole su A.

Ovvero L è un qualsiasi sottoinsieme di A*

dove A* = Un>=0 A n e A 0 = {λ} e A n = A A n-1

Indichiamo con la giustapposizione la concatenazione di sequenze, estesa inmodo ovvio agli insiemi

L’operatore * (stella di Kleene) applicato ad un simbolo indica 0 o più ripetizionidel simbolo. Sopra usiamo la sua estensione a un insieme.

7

13

Esempi

L’insieme di tutti i programmi C è un linguaggio (il linguaggio C, in effetti)

L’insieme di tutti gli assegnamenti che si possono scrivere in C è un linguaggio

L’insieme {an b cn | n >1 } è un linguaggio (sull’alfabeto {a,b,c })

Un linguaggio, essendo un insieme, puo’ essere definito:

- In modo estensionale: elencando tutti gli elementi dell’insieme …

- In modo intensionale: definendo delle regole che ci dicono come

sono fatti gli elementi dell’insieme.

14

Le formule aritmetiche con + e *

Alfabeto dei terminali

Alf = {A0, A1, A2,…,+,*, (, ) }Regole per produrre le formule

<fbf> ::= A0 | A1 | A2 | … |(<fbf>+<fbf>) | (<fbf>∗<fbf>)

((A0 ∗ A2) + A0) è una formula:<fbf> ⇒(<fbf> + <fbf> ) ⇒( <fbf> + A0) ⇒(( <fbf> ∗ <fbf> ) + A0) ⇒((A0 ∗ <fbf> ) ) + A0 )⇒((A0 ∗ A2) ) + A0 )

può essere

oppure

8

15

Le fbf del calcolo proposizionale

Alfabeto

Alf = {A0, A1, A2,…, →, ∧, ∨, ⊥, ¬, (, ) }Formule

<fbf> ::= A0 | A1 | A2 | … |⊥ |(<fbf>∧ <fbf>) | (<fbf> ∨ <fbf>) | (<fbf>→<fbf>) | (¬ <fbf> )

((¬(A0 ∧ A2)) ∨ ⊥) è una fbf:<fbf> ⇒(<fbf> ∨ <fbf> ) ⇒( <fbf> ∨ ⊥) ⇒((¬ <fbf> ) ∨ ⊥) ⇒((¬ ( <fbf> ∧ <fbf> ) ) ∨ ⊥) ⇒((¬ (A0 ∧ <fbf> ) ) ∨ ⊥) ⇒ ((¬ (A0 ∧ A2) ) ∨ ⊥)

16

Grammatiche Libere

• Grammatiche generative (introdotte da N. Chomsky, circa 1959)

Def Una grammatica libera da contesto è una quadrupla (NT,T,S, R) dove

- NT è un insieme finito di simboli non terminali

- T è un insieme (finito o numerabile) T di simboli terminali

- S ∈ NT è detto simbolo iniziale- R è un insieme di regole (o produzioni) della forma:

A ---> b dove A ∈ NT e b ∈ (NT ∪ T) *

Il linguaggio L generato da una tale grammatica è definito come

L = { w ∈ T * | S --->* w} dove, dati v, w ∈ (NT ∪ T) * , v ---> w sse

v = xAy, W = xby e A ---> b è una regola della grammatica

9

17

BNF

La Forma di Backus e Naur (BNF) è una notazione per presentare grammatichelibere, utilizzata per la prima volta nella definizione della sintassi Algol 60.

- Si usa la notazione < w > per indicare un simbolo non terminale (w è unasequenza qualsiasi di caratteri

- Si usa la notazione <A> ::= b invece che A ---> b

- Si usa (nella versione estesa) la notazione <A> ::= b | c per indicare due regole <A> ::= b e

<A> ::= c

- Si usa (nelle versione estesa) il simbolo * (stella di Kleene) con il significato già visto

- Operatore di riscrittura ⇒: sostituisce un non-terminale A in una parolacon b se esiste la regola <A> ::= b

18

BNF

Esempio

Non terminali : {<frase>, <soggetto>, <articolo>, <nome>,<verbo>,<comp.oggetto> }

Terminali: {un, cane, gatto, topo, mangia,insegue}

Simbolo Iniziale: <frase>

Regole:

<frase> ::= <soggetto> <verbo><comp.oggetto>

<soggetto> ::= <articolo> <nome>

<verbo> ::= mangia | insegue

<comp.oggetto> ::= <articolo> <nome>

<articolo> ::= un

<nome> ::= cane | gatto | topo

10

19

Esempio di riscrittura

<frase> ⇒ <soggetto > <verbo><comp.oggetto> I regola

⇒ <articolo> <nome> <verbo><comp.oggetto> II regola

⇒ un <nome> <verbo><comp.oggetto> V regola

. ⇒ un gatto <predicato> <verbo><comp.oggetto>

…

un gatto insegue un topo

Ma potremmo derivare anche

un topo mangia un gatto

La sintassi corretta non implica che la semantica sia corretta !

20

Esempio

Letterali numerici in un linguaggio di programmazione

<cifra> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<int_senza_segno> :: = <cifra><cifra>*<numero> :: = <int_senza_segno> <dec> <exp><dec> ::= . <int_senza_segno> | εε<exp> ::= e <segno> <int_senza_segno> | εε<segno> :: = + | - | εε

(In realtà una grammatica regolare, basta fare lo scanning da sinistra a destra)

Espressioni

<exp> :: = <identificatore> | <numero> | - <exp> ( <exp> ) | <exp> + exp> | <exp> *exp>

(il linguaggio generato necessita della piena potenza delle grammatiche libere)

11

21

Esempi di derivazioni

<exp> :: = <identificatore> | <numero> | - <exp>

( <exp> ) | <exp> + <exp> | <exp> *<exp>

<exp> ⇒ <exp>*<exp>

⇒(<exp>)*<exp>

⇒(<exp>+<exp>)*<exp>

⇒(A+<exp>)*<exp>

⇒(A+B)*<exp>

⇒(A+B)*C

<exp> ⇒ <exp>*<exp>⇒<exp>*C

⇒(<exp>)*C

⇒(<exp>+<exp>)*C

⇒(A+<exp>)*C

⇒(A+B)*C

<exp>

<exp> <exp>*

C

BA

( )<exp>

<exp> <exp>+

le due derivazioni distinte corrispondono allo stessoalbero di derivazione

22

Alberi di derivazione

Def. Data una grammatica G = (NT, T, S, R) un albero di derivazione (o di parsing)è un albero in cui:

• ogni nodo è etichettato con un simbolo in NT ∪ T ∪ {ε};• la radice è etichettata con S;

• ogni nodo interno è etichettato con un simbolo in NT;

• se il nodo n:

ha etichetta A

i suoi figli sono m1, … ,mk etichettati con X1,…,Xk

(dunque A è in NT; X1,…,Xk sono in NT ∪ T ∪ {ε}) allora A ::= X1…Xk è una regola in R;

• se il nodo n ha etichetta ε, allora n è una foglia ed è figlio unico.

Teor. Una stringa (di terminali) w appartiene al linguaggio di G sse ammette unalbero di derivazione (cioè un albero di derivazioni le cui foglie, lette da sin adestra, diano la stringa w).

12

23

Alberi di derivazione e precedenze

La struttura dell’albero di derivazione di una buona grammatica dovrebberispecchiare la struttura “intesa” della stringa:

<exp>

<exp> <exp>+

C

BA

<exp> <exp>*

L’albero “dice”: fai prima A*B e poi somma il risultato per C.

L’albero è la rappresentazione interna della stringa (del programma) usatadall’interprete o dal compilatore:

la struttura dell’albero rappresenta la semantica della stringa.

24

Ambiguità

<exp> :: = <identificatore> | <numero> | - <exp>

( <exp> ) | <exp> + <exp> | <exp> * <exp>

<exp>

<exp> <exp>+

C

BA

<exp> <exp>*

<exp>

<exp> <exp>*

A

CB

<exp> <exp>+

in questa grammatica la stessa stringa hapiù di un albero di derivazione: la grammatica è ambigua.Inutilizzabile come rappresentazione della semantica!

13

25

Grammatiche ambigue

Def . Una grammatica è ambigua se:

esiste almeno una stringa di simboli terminali

che ammette più alberi di derivazione

La grammatica delle espressioni è ambigua, perché A*B+C ha due alberi diderivazione

anche se (A+B)*C ha un solo albero (e più derivazioni).

Alcune grammatiche possono essere modificate in modo da:

- rimuovere l’ambiguità, e

- definire lo stesso linguaggio.

Esistono grammatiche (patologiche) dalle quali non è possibile rimuovere l’ambiguità(i linguaggi generati sono inerentemente ambigui)

26

Rimuovere l’ambiguità

Introduciamo la precedenza di * su +

complicando la grammatica

<exp> :: = <term> | <exp> + <exp>

<term> ::= <atom> | <term>*<term>

<atom> ::= <literal> | - <atom> | (<exp>)

<literal> ::= <identificatore> | <numero>

<exp> :: = <identificatore> | <numero> | - <exp>

( <exp> ) | <exp> + exp> | <exp> *<exp>

<exp>

<exp> <exp>+

<term>

BA

<term> <term>*<atom>

C

<literal>

<term>

<atom>

<literal>

<atom>

<literal>

L’altro albero non è più possibile

La grammatica modificata e’ ancoraambigua ?

14

27

Rimuovere l’ambiguità

Si, la seguente grammatica e’ ambigua

<exp> :: = <term> | <exp> + <exp>

<term> ::= <atom> | <term>*<term>

<atom> ::= <literal> | - <atom> | (<exp>)

<literal> ::= <identificatore> | <numero>

<exp> :: = <identificatore> | <numero> | - <exp>

( <exp> ) | <exp> + exp> | <exp> *<exp>

<exp>

<exp> <exp>+

<term>

BA

<term> <term>*<atom>

C

<literal>

<term>

<atom>

<literal>

<atom>

<literal>

Per disambiguarla dobbiamo introdurreanche la precedenza fra gli operandi:

<exp> :: = <term> | <term> + <exp>

<term> ::= <atom> | <atom>*<term>

<atom> ::= <literal> | - <atom> | (<exp>)

<literal> ::= <identificatore> | <numero>

28

Il dangling else

La dis-ambiguazione spiega alcuni contorcimenti delle grammatiche deiLP.

Esempio in Java:

if (porta - aperta)

if (ne ssuno-in-vista)

ret urn “C’e’ nessuno?”;

else suon a-campanello();

Con quale “ if” si accoppia “ else” ?

Guardiamo alla definizione ufficiale di Java…

15

29

Da Java Language Specificationhttp://java.sun.com/docs/books/jls/index.html

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �! " # " $ % $ & " ' ( " ) * + " , - # ( . ( & / ! + 0 1 " # " $ % $ & " 2

3 4 5 6 7 8 9 4 : ; < = > ? = @ = A ; A B = C D E F G H I J F K F E L E I F M N O P Q R S T U V R W X P Y R UZ [ \ [ ] ^ ] _ [ ` a Z b a c [ d e fg h Z [ \ [ ] ^ ] _ [ i j [ b a k [ l c \ j m j _ n Z k o p [ \ [ ] ^ ] _ [ hd e l b ] _ q m p ] Z [ \ [ ] ^ ] _ [ ` a Z b a c [ d e

d e l b ] _ Z [ \ [ ] ^ ] _ [ fif ( r s t u v w w x y z ) { | } | v ~ v z |� � � � v z r � w v { | } | v ~ v z | �

if ( r s t u v w w x y z ) { | } | v ~ v z | � y { � y u | � �else { | } | v ~ v z |� � � � v z r � w v { | } | v ~ v z | � y { � y u | � � �

if ( r s t u v w w x y z ) { | } | v ~ v z | � y { � y u | � �else { | } | v ~ v z | � y { � y u | � �

Semplice variante di BNF: � � � � � � � per non-terminali (nostro: <Statement>)

: invece di ::=

30

Dunque …

La lettura corretta e’:i f (p or t a- aper ta ) if ( nessuno-i n- v i s t a)

r et ur n “ C’ e’ n essuno?” ;

el se suona- camp( ) ;

“The Java programming language, like C and C++ and many programming languages beforethem, arbitrarily decree that an else clause belongs to the innermost if to which it mightpossibly belong”

Ecco la derivazione:� � � � � � � � � � � � � � � � � � � � � � � � � �⇒ i f ( � � � � � � � � � �

)� � � � � � � � �

⇒ i f ( � � � � � � � � � �)

� � � � � � � � � � � � � � � � � � �⇒ i f ( � � � � � � � � � �

) i f ( � � � � � � � � � �)

� � � � � � � � �   � � � � � � � �el se

� � � � � � � � �⇒ i f ( � � � � � � � � � �

) i f ( � � � � � � � � � �)

� � � � � � � � � ¡ � � � � ¢ � � � � � � � � £ � ¢ ¤ � � � � � � � � �el se

� � � � � � � � �⇒ i f ( � � � � � � � � � �

) i f ( � � � � � � � � � �) ¥ � � ¢ � � � � � � � � � � �

el se� � � � � � � � �

⇒ i f ( � � � � � � � � � �) i f ( � � � � � � � � � �

) r et ur n “ C’ e’ n ess uno?” ; el se� � � � � � � � �

⇒ i f ( � � � � � � � � � �) i f ( � � � � � � � � � �

) r et ur n “ C’ e’ n ess uno?” ; el se� � � � � � � � � ¡ � � � � ¢ � � � � � � � � £ � ¢ ¤ � � � � � � � � �⇒ i f ( � � � � � � � � � �

) i f ( � � � � � � � � � �) r et ur n “ C’ e’ n ess uno?” ; el se ¦ � � � � § � � ¨ � © � � � � �

⇒ i f ( � � � � � � � � � �) i f ( � � � � � � � � � �

) r et ur n “ C’ e’ n ess uno?” ; el se suona- camp( ) ;

16

31

Vincoli sintattici contestuali

Il numero di parametri attuali di una chiamata di procedura deve essere egualeal numero dei parametri formali della dichiarazione.

Vincolo sintattico!

Ma:

lo strumento formale che usiamo (BNF) non è capace di esprimere

vincoli che dipendono dal contesto (delle dichiarazioni).

Soluzioni:

usare strumenti più potenti

per esempio: grammatiche contestuali

riscrittura di un non-terminale solo in un determinato contesto

no: non esistono tecniche automatiche di generazione di riconoscitori

usare controlli ad hoc

32

Sintassi o semantica ?

I vincoli contestuali

per esempio:

numero parametri attuali = parametri formali

un identificatore deve essere dichiarato prima dell’uso

compatibilità dei tipi in un assegnamento

ecc.

appartengono alla sintassi.

Ma tradizionalmente, nel gergo dei LP, si intende:

Sintassi: Quello che si descrive in BNF

Semantica: Il resto…

I vincoli contestuali sono dunque vincoli “semantici”…

17

33

Controlli “ semantici”

• Semantica Statica Vincoli (sintattici contestuali) determinabili al momento dellacompilazione

– var A: integer; tipo e allocazione di memoria per A

– int B[10]; tipo e allocazione di memoria per il vettore B

– float MyProcC(float x,float y){...}; parametri– X = 3.2; in Java errore compilazione se X è int

• Semantica Dinamica Vincoli determinabili durante l’esecuzione del programma:

Z= X/Y errore se Y = 0

Z= V[Y] errore se Y = 11 e V: array[0..9] of integer (Pascal)

Questi errori possono essere rilevati solo a run-time

Non può esistere un compilatore che rileva tutti i possibili errori che si verificheranno arun-time.

(E’ indecidibile sapere staticamente se si verificherà un errore in un programma)

34

Poss ibile?

L’azienda Macrosoft ha rilasciato un’applicazione di debugging H.

Dato un qualsiasi programma P:

H chiamata su P stampa 1 se P termina quando è applicato a se stesso;

H chiamata su P stampa 0 se P cicla quando è applicato a se stesso.

L’azienda Moon sostiene che Macrosoft racconta balle.

Chi ha ragione?

18

35

No!

Macrosoft ha preso una cantonata.

H non può esistere.

Supponiamo che esista. Sfruttando H, costruiamo una nuova applicazione G

che si comporta così:

G(P) = 1 se H(P) = 0

G(P) cicla se H(P) = 1

Scrivere G, sfruttando H come sottoprogramma è un gioco da ragazzi…

Ma cosa succede se chiamiamo G su se stessa?

G(G) = 1 sse H(G) = 0 sse G(G) cicla

G(G) cicla sse H(G) = 1 sse G(G) non cicla

assurdo! dunque G non può esistere, ovvero non può esistere H

36

Ma allora altre applicazioni non esistono…

Esiste un’applicazione T tale che:

T(P,x)=1 se P(x) termina

T(P,x)=0 se P(x) cicla ?

NO: T permetterebbe di costruire H:

H(P) = T(P,P)

Esiste un’applicazione Z tale che:

Z(P)=1 se P(x) è sempre lo stesso output per ogni x

Z(P)=0 in caso contrario ?

NO: Z permetterebbe di costruire H:

costruisci prima un’applicazione F che manipola programmi e si comporta così:

F(P) è un programma che, dato in input un generico x (che non viene usato), provaad eseguire P sull’input P. Se e quando tale esecuzione termina, F(P)(x) stampa 0.Altrimenti (ovviamente) F(P)(x) cicla.

Scrivere F non è problematico se si ha a disposizione un interprete (per eseguire P su P).

Ora, se esistesse Z, si potrebbe definire H:

H(P) = Z ( F (P)).

19

37

H(P) = Z ( F (P)) Infatti

Z(F(P)) = 1 se F(P)(x) e’ lo stesso per ogni input x se P(P) termina

Z(F(P) = 0 se F(P)(x) non e’ lo stesso per ogni input x

se P(P) non termina

38

Ma allora altre applicazioni non esistono…

Esiste un’applicazione Equiv tale che:

Equiv(P,Q)=1 se P e Q hanno la stessa semantica

Equiv(P,Q)=0 se P e Q sono distinti da almeno un input.?

NO: Equiv permetterebbe di costruire Z:

Scriviamo prima un programmino ZERO che stampa sempre 0.

Z(P) = Equiv (P, ZERO)

(suppodniamo per semplicita’ che il valore prodotto da P sia 0).

Il sogno dell’ingegneria del software è destinato a rimanere tale…

20

39

Semantica

• Serve per poter definire con esattezza ``cosa fa‘’ un programma

(e quindi sviluppare tecniche di ottimizzazione, debugging, verifica dicorrettezza, traduzione fra formalismi diversi ecc. ecc.)

• La definizione (semi) formale della semantica fa parte dello standard didefinizione di un linguaggio a partire dagli anni ‘80

• Vari metodi per definire la semantica di un linguaggio di programmazione

- Algebrica

- Assiomatica

- Operazionale

- Denotazionale

• Non esiste una metodologia standard universalmente accettata

40

Semantica Operazionale

• Ottenuta definendo un interprete del linguaggio L su di una macchina ospite i cuicomponenti sono descritti in modo matematico.

• Utile soprattutto perche’ fornisce direttamente un modello di implementazione

• E’ possibile definirla in modo formale e guidato dalla sintassi (SOS)

21

41

Structured Operational Semantics (SOS)

• Definizione della semantica in modo guidato dalla sintassi:

• Si definiscono delle regole di transizione che specificano i passi di computazioneper un costrutto composto A op B in termini di quelli dei componenti A e B

• Regole date nello stile della deduzione naturale:

Premessa

Conseguenza

42

SOS

• Dato che i costrutti che ci interessano in generale modificano una qualchenozione di stato, di solito le regole di transizione sono definite su configurazionidel tipo

<Comando, Stato>

Le regole specificano dunque transizioni del tipo

<C, σ > → <C`, σ`>

• Formalmente le regole definiscono (induttivamente) la relazione→ che dice come una configurazione evolve in un’altra

• L’insieme delle configurazioni e la relazione di transizione costituiscono unSistema di Transizione (TS)

22

43

Sistema di Transizione (TS)

• Un TS e’ definito da una quadrupla (S,I,F, →) dove

– S e’ l’insieme delle configurazioni

– I ⊆ S e’ l’insieme delle configurazioni iniziali

– F ⊆ S e’ l’insieme delle configurazioni finali

– → ⊆ S x S e’ una relazione di transizione

( scriviamo s → s’ per indicare (s,s’) ∈ →)

• Una sequenza di esecuzione e’ una sequenza di configurazioni

C1 C2 ….. Cn tale che:

– C1 ∈I,

– Cn ∈ F,

– Ci → Ci+1 per ogni 0 <= i < n

44

Sistema di Transizione (TS)

• Un TS e’ detto deterministico se per ogni c ∈C

esiste al piu’ un c’ tale che c → c’ .

• La relazione → e’ definita (induttivamente) da un insieme di regole del tipo

c1→ c1’ ……. cn → cn’

op (c1……. cn ) → op’ (c1’ ……. cn’ )

ovvero e’ il minimo insieme che soddisfa l’insieme delle regole date

23

45

Un mini-linguaggio imperativo

46

Semantica delle espressioni aritmetiche

24

47

Nota sulle regole

• Le regole usano metavariabili (n, X, a0 etc.) sui vari domini sintattici.

Una istanza di una regola si ottiene istanziando queste variabili a particolarinumeri, variabili, espressioni etc.

• Esempio di istanza

48

Nota sulle regole

• Le istanze delle regole si compongono in strutture ad albero dette

alberi di derivazione (o derivazioni) dove:

– tutte le premesse di istanze di regole sono conclusioni

di istanze di regole immediatamente sopra nell’albero;

– alla sommita’ dell’albero ci sono assiomi del tipo

<a,σ >

Esempio di derivazione:

25

49

Semantica delle espressioni booleane

50

Semantica delle espressioni booleane

26

51

Semantica dei comandi

52

Semantica del while