Corso di Laurea in “ITPS” · Vogliamo descrivere il linguaggio delle stringhe palindrome...

1

Linguaggi di ProgrammazioneCorso di Laurea in “ITPS”

Descrizione dei Linguaggi di programmazione

Valeria Carofiglio

(Questo materiale è una rivisitazione del materiale prodotto da Nicola Fanizzi)

2

Argomenti

• Introduzione• Sintassi e Lessico

– Grammatiche, derivazioni, alberi, ambiguità• Semantica• Pragmatica• Implementazione

3

Definireun Linguaggio di Programmazione

Linguaggio di programmazioneUna notazione (linguaggio artificiale)

per descrivere algoritmi e strutture datidestinatario della comunicazione = calcolatore

• Linguistica => per poter descrivere un linguaggio:– Sintassi

• Lessico • (Morfologia)

– Semantica– Pragmatica

Studio dei Livelli di descrizione di

un linguaggio

4

Definireun Linguaggio di Programmazione

Linguaggio di programmazioneUna notazione (linguaggio artificiale)

per descrivere algoritmi e strutture datidestinatario della comunicazione = calcolatore

• Linguistica => per poter descrivere un linguaggio:– Sintassi

• Lessico • (Morfologia)

– Semantica– Pragmatica

• In informatica c'è un altro livello:– Implementazione

Studio dei Livelli di descrizione di

un linguaggio

5

Sintassi: Una relazione tra segni“quali sono le frasi corrette ?”

6

Sintassi: Una relazione tra segni“quali sono le frasi corrette ?”

Dato un alfabeto:

I°Stadio: Lessico“quali sequenze di simbolicostituiscono le parole del

linguaggio ?”

•

Esempio: il caso del linguaggio naturale (Italiano)

Alfabeto latino su 22 lettere:{A..Z }

Livello lessicaleParole legali in italiano:

sequenze corrette di lettere

7

Sintassi: Relazione tra segni“quali sono le frasi corrette ?”

Dato un alfabeto:

I°Stadio: Lessico“quali sequenze di simbolicostituiscono le parole del

linguaggio ?”

• Relazione tra simbolidell'alfabeto

II°Stadio“quali sequenze di parole

costituiscono le frasidel linguaggio ?”

Esempio: il caso del linguaggio naturale (Italiano)

Alfabeto latino su 22 lettere:{A..Z }

Livello lessicaleParole legali in italiano:

sequenze corrette di lettere

Frasi legali in Italiano: sequenze corrette di parole

Livello morfologico

8

Semantica: Relazione tra segni e significati

“cosa significa una frase corretta ?”Difficile in linguaggio naturale/ Più semplice nei linguaggi artificiali

Esempio:

Il significato di un programma potrebbe essere la funzione matematica che quel programma computa

9

Pragmatica:“Come usare una frase corretta e sensata?”

Punto di vista del programmatore:

Frasi con lo stesso significato possono essere usate da due persone in modo diverso

Contesti linguistici diversi possono richiedere l’uso di frasi diverse

10

Implementazone: Livello esistente solo per i LdP

“Come eseguire una frase correttarispettandone la semantica?”

Punto di vista del progettista (Software o del linguaggio)

Mediante quale processo le frasi operative del linguaggio realizzano lo stato di cose di cui parlano

(descritto dall’implementazione del linguaggio)

11

SintassiL= { stringhe di caratteri su un certo alfabeto}

Regole sintattiche

specificano quali stringhe appartengono ad L

L Naturale

Artificiale

Numerose

complesse

Poche regole

Se L è finito: possiamo elencare tutte le parole di L (es: Il vocabolario di italiano è un volume finito)

I LdP possono essere costituiti anche da un numero infinito di parole(lessico infinito)

12

Sintassi: gli elementi che ci servnoElementi lessicali di un LdP (lessemi)

(unità del livello sintattico più basso (lessico) di un linguaggio )Identificatori costanti operatori punteggiatura

Token (simboli)(categorie (astrazioni) di lessemi )

Index := 3 * count + 5;

semicolon;num5plus+idcounttimes*num3assign:=idindex

TokenLessemiEsempio

Programma: frase di LdP (visto come <lessemi>)

13

SintassiDefinizione formale di un linguaggio

Per generazioneL definito su alfabeto ∑

Rfrase verdetto

R è lo strumento per riconoscere le frasi di L

frase ∈∉ L

Per riconoscimento

Se L è infinito

R non è adatto per enumerare le frasi di L

Usato per verificare la correttezza sintattica di un

programma scritto in L

14


Per riconoscimento Per generazioneL definito su alfabeto ∑

Rfrase verdetto


Se L è infinito




L definito su alfabeto ∑

G

Push

Frase (qulaunque)

G è lo strumento per generarele frasi di L

frase ∈∉ L

15



Rfrase verdetto


Se L è infinito





G

Push

Frase (qulaunque)


frase ∈∉ L

R: funziona per tentativi

G: aleatorietà della definizione della frase

16



Rfrase verdetto


Se L è infinito





G

Push

Frase (qulaunque)


frase ∈∉ L

R: funziona per tentativi

G: aleatorietà della definizione della frase

Importante scoperta:

Stretta connessione tra R e G:

Il meccanismo di R è basato su quello di G

17

Metodi formaliper la definizione della sintassi

(strumenti generativi)J.Backus

N.Chomsky1950: Inventano la stessa notazione anche se in

contesti diversi

18


(strumenti generativi)

(Linguistica) Chomsky:Specifica 4 classi di strumenti

generativi (grammatiche)

10

23

4 classi di linguaggi

Classe 2 Gram.non-contestualià sintassi

Classe 3 Gram. Regolarià lessico

J.Backus


contesti diversi

19


(strumenti generativi)



10

23


(Informatica) Backus:Presenta Algol 60

(sintassi specificata in BNF)

BNF (Backus Naur Form)

Quasi equivalente allo strumento di tipo 2 di chomsky


Classe 3 Gram. Regolarià lessicometalinguaggio

J.Backus


contesti diversi

20

EsempioVogliamo descrivere il linguaggio delle stringhe palindrome

costruite a partire dai simboli a e b

A= {a,b} L={a,b, aa, bb, aaa, …, abba, aabaa}Definizione ricorsiva:

21




• a e b sono palindrome (base)• Se s è palindroma (passo)

– asa e bsb sono palindrome

22





– asa e bsb sono palindromea, aaa, aba, ababa, …. Stringhe di lunghezza

dispari su A

23





– asa e bsb sono palindrome• Stringa vuota

a, aaa, aba, ababa, …. Stringhe di lunghezza

dispari su A

Per stringhe di lunghezza pari

24





– asa e bsb sono palindrome• Stringa vuota

a, aaa, aba, ababa, …. Stringhe di lunghezza

dispari su A

Per stringhe di lunghezza pari

Se s è una stringa palindroma Esiste una

successione di regole sintattiche che la costruisce

25

Grammatiche non contestuali(o libere da contesto)

Dato un alfabeto A (finito e non vuoto) si costruisce l'insieme (infinito) A* di tutte le stringhe su A

– A* contiene anche la Stringa vuota (senza simboli di A) denotata con ε (un linguaggio formale è un sottoinsieme di A*)

• Grammatica G = (NT,T,R,S)– NT insieme di simboli non terminali o variabili– T insieme dei simboli terminali

• (es., A oppure A*)– R insieme di regole di produzione V → W con

• V ∈ NT• W ∈ (T ∪ NT)*

– S ∈ NT (scopo, simbolo distintivo, iniziale o di partenza)

26

EsempioGrammatica per stringhe di palindrome su

A={a,b}• G = ({P}, A, R, P) con

R = {P → εP → aP → bP → aPaP → bPb}

27

Esempio2Grammatica per descrivere le espressioni aritmetiche tra identificatori

costituiti da sequenze finite di “a” e “b” (su op. unari e binari)

• G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {

1. E → Ι2. E → E+E3. E → E*E4. E → E-E5. E → -E6. E → (E)7. I → a8. I → b9. I → Ιa10. I → Ιb}

28


costituiti da sequenze finite di “a” e “b” (su op. unari e binari)

• G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {


Per definire una espressione aritmetica

Per definire un Identificatore

29

Derivazione: aspetto operativo delle grammatiche

Una derivazione consiste nella ripetuta applicazione di regole di una grammatica

Grammatica per descrivere le espressioni aritmetiche

G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {


La stringa

ab*(a+b)È coprretta secondo la

grammatica data

Applicazione ripetuta regole di produzione

ßàregole di riscrittura

(NOT: ⇒)

30




G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {


La stringa ab*(a+b)È corretta secondo la grammatica

Applicazione ripetuta

(E ⇒3E*E ⇒1I *E

⇒10Ib *E⇒7 ab *E⇒6 ab*(E)

⇒2 ab*(E+E)⇒1 ab *(I+E)⇒7 ab*(a+E)⇒1 ab*(a+I)⇒8 ab*(a+b)

31




G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {




(E ⇒3E*E ⇒1I *E

⇒10Ib *E⇒7 ab *E⇒6 ab*(E)


Notazione

E ⇒∗

(ab*(a+b))

32

DerivazioneFissata una grammatica

G = (NT,T,R,S) Assegnate due stringhe

“v” e “w” su NT ∪ T------------------

• Da v si deriva direttamente w (v ⇒ w)– Se w si ottiene da v sostituendo ad un simbolo non

terminale V di v il corpo di una regola di produzione di R la cui testa sia V

• Da v si deriva w (v ⇒∗ w) – Se esiste una sequenza finita (anche vuota) di

derivazioni dirette: v ⇒ wo ⇒ w1 ⇒ … ⇒ w

33

Linguaggio generato da una grammatica

Il linguaggio generato da una grammaticaG = (NT,T,R,S) è costituito

dall'insieme delle stringhe derivabili dal simbolo iniziale di G

Formalmente: L(G) = { ω ∈ Τ∗ | S ⇒∗ ω}

Definisce un linguaggio su T*

34

Backus-Naur Form (BNF)Idea di fondo:

astrazione per definire le strutture sintattiche(Token-Simboli)

Es (C):Istruzione di assegnazioneAssignà var = Expr

L’astrazione assign è definita come una istanza dell’astrazione varseguita dal lessema = seguita da una istanza dell’astrazione Expr

35

Backus-Naur Form (BNF)Idea di fondo:

astrazione per definire le strutture sintattiche(Token-Simboli)

Es (C):Istruzione di assegnazioneAssignà var = Expr

L’astrazione assign è definita come una istanza dell’astrazione varseguita dal lessema = seguita da una istanza dell’astrazione Expr

Astrazione ≡ simbolo non terminale

Struttura sintattica/Token/lessema ≡simbolo terminale

Grammatica ≡ insieme di regole

36

Regole BNF• Una regola ha una parte sinistra (left-hand

side: LHS) e una parte destra (right-hand side: RHS), che consistono di simboli terminali e non-terminali

LHS ::= RHSEs:Istruzione di assegnazione

<Assign >::= <var> = <Expr>• Una regola per un simbolo non-terminale può

avere più d'una parte destra, separate dal simbolo “ | “

37

Regole BNF• La freccia “à” è sostituita da “::=”• I simboli non terminali sono scritti tra parentesi

angolari <…> – (maiuscoli nelle grammatiche di Chomsky)

38


costituiti da sequenze finite di “a” e “b” (su op. + * unario e binario)

• G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {


BNF<E> ::= <I> | <E> + <E> |

<E>*<E>|<E>-<E> |-<E>| (<E>)

39

Esempio4

<program> ::= <stmts><stmts> ::= <stmt> | <stmt> ; <stmts><stmt> ::= <var> = <expr><expr> ::= <term> + <term> | <term> - <term><term> ::= <var> | const <var> ::= a | b | c | d

40

Osserviamo che..La derivazione di una stringa

è un processorigidamente sequenziale

Alcuni passi devonoessere effettuatiin un certo ordine

Altri passi possonoessere scambiatid’ordine



(E ⇒3E*E ⇒1I *E

⇒10Ib *E⇒7 ab *E⇒6 ab*(E)


41

Derivazioni canoniche• Una derivazione sinistra (leftmost

derivation) è una derivazione nella quale si espande il non-terminale più a sinistra in ogni forma di frase intermedia

• Analogamente si definisce la derivazione destra(rightmost derivation)

NB: Ci sono derivazioni che non sono né destre né

sinistre

42

Alcuni passi della derivazionepossono essere scambiati

App.ripetuta

(E ⇒3E*E ⇒1I *E

⇒10Ib *E⇒7 ab *E⇒6 ab*(E)


App.ripetuta

(E ⇒3E*E ⇒6E *(E)

⇒2 E * (E+E)⇒1 E *(E+I)⇒8 E * (E+b) ⇒1 E * (I+b)⇒7 E * (a+b)

⇒1 I*(a+b)⇒10 Ib*(a+b)⇒7 ab*(a+b)


G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {


43

Alcuni passi della derivazionepossono essere scambiati

App.ripetuta

(E ⇒3E*E ⇒1I *E

⇒10Ib *E⇒7 ab *E⇒6 ab*(E)


App.ripetuta

(E ⇒3E*E ⇒6E *(E)


⇒1 I*(a+b)⇒10 Ib*(a+b)⇒7 ab*(a+b)


G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {


Utilità della dervazione in forma

di albero

Deriv. destra Deriv. sinistra

44

Derivazione in Forma di albero(un esempio)

App.ripetuta

(E ⇒3E*E ⇒6E *(E)


⇒1 I*(a+b)⇒10 Ib*(a+b)⇒7 ab*(a+b)

EEE

I

I b

a

*

(

E

E E

I

)E

+

I

a b

45

AlberiStruttura costituita da un insieme

di nodi NSe non vuota si distinguono:• La radice r• Un partizionamento (S1,S2,...,Sn)

dei nodi di N \ {r}dove ogni Si è strutturato ad albero

EEE

I

I b

a

*

(

E

E E

I

)E

+

I

a b

46




EEE

I

I b

a

*

(

E

E E

I

)E

+

I

a b

47




EEE

I

I b

a

*

(

E

E E

I

)E

+

I

a b

Grafo connesso T = (N,A)N = insieme dei nodi;

A = insieme degli archi (ni, nj) – |N| = |A|+1– un Nodo n padre di tutti i nodi figli

(ordinati) m1,...,mp, tali che (n, mj) ∈ Α– radice r, livello(r) = 0– Se livello(n) = i

allora m tale che (n,m) ∈ A: livello(m) = i+1

48

Albero di derivazione

Rappresentazione gerarchica di una derivazione:

• I nodi sono etichettati con elementi di T ∪ NT ∪ {ε}

– Nodo radice = S– Nodo interno (con figli) è un A ∈ NT:

• Se i figli di A sono etichettati X1...Xndove ∀Xi ∈ T ∪ NT, allora deve esistere in R la regola

A → X1...Xn

• Se ε è l'unico figlio di A, allora deve esistere in R la regola

A → ε– Nodi foglia (senza figli) sono simboli

di T ∪ {ε}

Data una grammatica G = (NT,T,R,S)

EEE

II b

a

*

(

EE E

I

)E

+

I

a b

50

Osserviamo che…

App.ripetuta

(E ⇒3E*E ⇒1I *E

⇒10Ib *E⇒7 ab *E⇒6 ab*(E)


App.ripetuta

(E ⇒3E*E ⇒6E *(E)


⇒1 I*(a+b)⇒10 Ib*(a+b)⇒7 ab*(a+b)

Albero della derivazione uguale


EEE

II b

a

*

(

EE E

I

)E

+

I

a b

51

Osserviamo che…

App.ripetuta

(E ⇒3E*E ⇒1I *E

⇒10Ib *E⇒7 ab *E⇒6 ab*(E)


App.ripetuta

(E ⇒3E*E ⇒6E *(E)


⇒1 I*(a+b)⇒10 Ib*(a+b)⇒7 ab*(a+b)

Albero della derivazione uguale


EEE

II b

a

*

(

EE E

I

)E

+

I

a b

IMPORTANTE PER L’ANALISI SINTATTICA DI UN LdPLa struttura dell’albero (attraverso i sottoalberi) esprime la

struttura logica che la grammatica assegna alla stringa

52

Osserviamo che…

App.ripetuta

(E ⇒2E+E ⇒3 E*E +E ⇒1 I * E +E⇒7 a * E+ E⇒1 a * I+E ⇒8 a * b+E

⇒1 a * b + I⇒7 a* b +a

Deriv. destra




G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {


53

Osserviamo che…

Deriv. destra



App.ripetuta


⇒1 a * b + I⇒7 a* b +a

E

EE +

E E

I

*

I

a b

I

a

54

Osserviamo che…

Deriv. destra



App.ripetuta


⇒1 a * b + I⇒7 a* b +a

E

EE +

E E

I

*

I

a b

I

a

Moltiplica a per b poi somma a

55

Ambiguità nelle grammatiche(esempio)

Alberi di derivazione per la stringa a * b + a

E

EE +

E E

I

*

I

a b

I

a

E

EE

+I

a

E E

I

*

I

b a

Due alberi diversi producono la stessa stringa

56

Ambiguità nelle grammatiche(esempio)

Alberi di derivazione per la stringa a * b + a

E

EE +

E E

I

*

I

a b

I

a

E

EE

+I

a

E E

I

*

I

b a

Due alberi diversi producono la stessa stringaA seconda di come la derivazione è costruita

cambia la precedenza tra i due operatori aritmetici cambia

57

Ambiguità nelle grammatiche

Una grammatica è ambigua se e solo se essa genera (almeno) una stringa (forma di

frase) che abbia due o più alberi di derivazione distinti

NB: ma una stringa può però avere più derivazioni distinte senza che la grammatica sia ambigua

58

Disambiguità nelle grammatiche(esempio)

Grammatica AMBIGUA per descriverele espressioni aritmetiche

G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {E ::= I | E+E |E*E |E-E|

-E| (E)I ::= a| b| Ia |Ib}

Grammatica NON AMBIGUA per descrivere le espressioni

aritmetiche

G = ({E,T,A,I}, {a,b,+,*,-,(,)}, R’, E) con

R = {E ::= T | T + E | T - ET ::= A | A * T | A ::= I | -A | ( E ) I ::= a | b | Ia | Ib

59




-E| (E)I ::= a| b| Ia |Ib}


aritmetiche

G = ({E,T,A,I}, {a,b,+,*,-,(,)}, R’, E) con


Rappresenta la nozione di precedenza degli operatori

60




-E| (E)I ::= a| b| Ia |Ib}


aritmetiche

G = ({E,T,A,I}, {a,b,+,*,-,(,)}, R’, E) con



Gli operatori dello stesso livello di precedenza vengono

associati a destra:

a + b +a ßà a + (b + a)

61




-E| (E)I ::= a| b| Ia |Ib}


aritmetiche

G = ({E,T,A,I}, {a,b,+,*,-,(,)}, R’, E) con



Gli operatori dello stesso livello di precedenza vengono

associati a destra:

a + b +a ßà a + (b + a)

Osserviamo che:

La disambiguazione della grammatica è pagata in termini di

complessità

LdP a volte molto contorti

62

Caso dell'istruzione condizionaleGrammatica ambigua per il costrutto

“if” in Java<istruzione> ::= ... <if-else> | <altra><altra> ::= ... <blocco> | <vuota> | <return><if-else> ::= if (<espressione>) <istruzione> |

| if (<espressione>) <istruzione> else <istruzione>

63




Quanti alberi per la stringa seguente ?if (<espressione>) if(<espressione>) <istruzione> else <istruzione>

64




Quanti alberi per la stringa seguente ?if (<espressione>) if(<espressione>) <istruzione> else <istruzione>

if (<espressione>) if(<espressione>)

<istruzione>

else <istruzione>

if (<espressione>) if(<espressione>)

<istruzione>

else <istruzione>

65

Caso dell'istruzione condizionale

Grammatica non ambigua per il costrutto“if” in Java

<istruzione> ::= ... <if> | <if -else> | <altra><altra> ::= ... <blocco> | <vuota> | <return><no-if-breve> ::= <altra> | <if-else2><if> ::= if (<espressione>) <istruzione><if-else> ::= if (<espressione>) <no-if-breve> else <istruzione> <if-else2> ::= if (<espressione>) <no-if-breve> else <no-if-breve>

Il ramo else appartiene all’if più vicino

66

Metodi Formali perDescrivere la Sintassi

• Grammatiche e riconoscitori• Backus-Naur Form e Grammatiche libere

da contesto– Metodi più diffusi per descrivere la sintassi

dei linguaggi di programmazione• Extended BNF

– Migliora la leggibilità e la scrivibilità della BNF

67

Extended BNF(EBNF)

• Opzionalità– Le parti opzionali sono poste tra parentesi quadre [ ]– <proc_call> ::= ident [(<expr_list>)]

• Disgiunzione– Le parti destre alternative sono poste tra parentesi tonde () e

separate con barre verticali |– <term> ::= <term> (+|-) const

• Ripetizione– Ripetizioni (di 0 o più elementi) sono poste tra parentesi graffe {

}– <ident> ::= letter {letter | digit}

Estensioni della BNF

68

BNF e EBNF• BNF

<expr> ::= <expr> + <term>| <expr> - <term>| <term>

<term> ::= <term> * <factor>| <term> / <factor>| <factor>

• EBNF<expr> ::= <term> {(+ | -) <term>}<term> ::= <factor> {(* | /) <factor>}


aritmetiche

G = ({E,T,A,I}, {a,b,+,*,-,(,)}, R’, E) con


69

Vincoli contestualiCorrettezza di una frase può dipendere dal

contesto nel quale la frase si trova:

– Identificatore da dichiarare prima dell'uso– Numero dei parametri effettivi pari al numero di

parametri formali– Espressione nella parte destra di un assegnazione di

tipo compatibile con quello della variabile nella parte sinistra

– Non modificabilità della variabile che controlla l'istruzione for

– Inizializzare ogni variabile prima dell'uso– Metodi sovrascritti da metodi con firma uguale (o

compatibile)

70

Vincoli contestualiCorrettezza di una frase può dipendere dal

contesto in cui la frase si trova:– Identificatore da dichiarare prima dell'uso– Numero dei parametri effettivi pari al numero di

parametri formali– Espressione nella parte destra di un assegnazione di

tipo compatibile con quello della variabile nella parte sinistra

– Non modificabilità della variabile che controlla l'istruzione for

– Inizializzare ogni variabile prima dell'uso– Metodi sovrascritti da metodi con firma uguale (o

compatibile)

NON si possono esprimere

con unagrammatica

Non Contestuale

71

Grammatiche contestuali e Vincoli contestuali

Grammatiche contestuali per descrivere i vincoli contestualiDovere di cronaca

Le grammatiche contestuali hanno regole di produzione del tipo:

uAv à uwv con u,v,w ∈ T ∪ NT

Il simbolo non terminale A può essere riscritto come w solo se appare in un certo contesto (definito da u e v)

72

Grammatiche contestuali e Vincoli contestuali

Grammatiche contestuali per descrivere i vincoli contestualiDovere di cronaca

Le grammatiche contestuali hanno regole di produzione del tipo:

uAv à uwv con u,v,w ∈ T ∪ NT

Il simbolo non terminale A può essere riscritto come w solo se appare in un certo contesto (definito da u e v)

Perche tali grammatiche non vengono di fatto utilizzate

• Grammatiche molto pesanti

• Per le quali non esistono tecniche automatiche di generazione d i traduttori efficienti (che invece esistono per le grammatiche libere da contesto)

73

Vincoli contestuali esemantica statica

La necessità di gestire i vincoli della sintassi contestuale

porta alla nozione di semantica statica

– ossia verificabile sul testo del programma sorgente– Diversa dalla semantica dinamica

(che riguarda il significato del programma mentre gira)

Es. grammatiche con attributiGrammatiche libere + vincoli ed azioni

74

Sintassi o semantica?I vincoli contestuali appartengono alla

sintassi– Identificatore da dichiarare prima dell'uso– Numero dei parametri effettivi pari al numero di parametri

formali– Espressione nella parte destra di un assegnazione di tipo

compatibile con quello della variabile nella parte sinistra– ......

Tradizionalmente nei LdP si intende- sintassi: tutto ciò che si descrive mediante BNF

- Semantica: tutto il resto

I vincoli contestuali sono dunque vincoli semantici....

75

Controlli di tipo semanticoSemantica statica

vincoli contestuali determinabili al monentodella compilazione

- Var A: integer tipo e allocazione di memoria per A- int B[10] tipo e allocazione di memoria per il vettore B- Float myProgram(float x, integer y) {...} parametri- X=3.5 che tipo è x?

Semantica dinamicavincoli determinabili in fase di esecuzione del

programma- z=x/y errore se y=0- ....

76

CompilatoriAnalisi

Lessicale

AnalisiSintattica

AnalisiSemantica

GenerazioneForma Intermedia

Ottimizzazione

GenerazioneCodice

Tavoladei simboli

Gestioneerrori

programma sorgente

lista token

albero sintattico

codice intermedio

albero aumentato

codice intermedio

codice oggetto

77

Compilazione:analisi lessicaleDetta anche scanning o lexing

Da cui scanner (o lexer) è il (sotto)programma che la implementa

Lettura dei caratteri dal sorgente (da sinistra a destra in una passata) e costruzione di una lista di token

(le parole del linguaggio)es. la stringa a = 12 * indice++; genera 7 token:• id, assign, const, star, id, incremento,semicolon

78




(le parole del linguaggio)es. la stringa a = 12 * indice++; genera 7 token:

– id, assign, const, star, id, incremento, semicolon

Per descrivere gli elementi del lessico basta una sottoclasse delle grammatiche libere detta delle

grammatiche regolari (o lineari)

79




(le parole del linguaggio)es. la stringa a = 12 * indice++; genera 7 token:• a, =, 12, *, indice, ++

Per descrivere gli elementi del lessico basta una sottoclasse delle grammatiche libere detta delle

grammatiche regolari (o lineari)



10

23



Classe 3 Gram. Regolarià lessico

80

Analisi lessicale e Grammatiche regolari

Grammatiche regolari per descrivere il lessico di un LdPDovere di cronaca

Le grammatiche regolari hanno regole di produzione del tipo:

A à uB AàBucon u ∈ T* e A,B ∈ NT

81




A à uB AàBu con u ∈ T* e A,B ∈ NT


G = ({E,I}, {a,b,+,*,-,(,)}, R, E) conR = {


82




A à uB AàBucon u ∈ T* e A,B ∈ NT

Potere espressivo limitato

Es: non è possibile contare un numero arbitrario di caratteri (bilanciamento parentesi???)

Analisi lessicale: Verifica che la stringa in ingresso possa essere decomposta in token (ognuno descritto da una

grammatica regolare)

83

CompilatoriAnalisi

Lessicale

AnalisiSintattica

AnalisiSemantica


Ottimizzazione

GenerazioneCodice

Tavoladei simboli

Gestioneerrori

programma sorgente

lista token

albero sintattico

codice intermedio

albero aumentato

codice intermedio

codice oggetto

Grammatiche libere da contesto con insieme dei terminali = lista dei tokenottenuta

84

Compilazione: analisi sintatticaDetta anche parsing

Da cui parser è il (sotto)programma che la implementa

Lettura dei token dalla listae costruzione dell'albero di derivazione

(i token sono le foglie)Stringa non corretta nel linguaggio:se non si è in grado di costruire l'albero

Spesso lo scanner è un sottoprogramma chiamato dal parser

(lo scanner restituisce un token ad ogni invocazione del parser)

85

CompilatoriAnalisi

Lessicale

AnalisiSintattica

AnalisiSemantica


Ottimizzazione

GenerazioneCodice

Tavoladei simboli

Gestioneerrori

programma sorgente

lista token

albero sintattico

codice intermedio

albero aumentato

codice intermedio

codice oggetto

86

Compilazione: analisi semantica

Vengono effettuati i controlli dei vincoli contestuali

(ossia di semantica statica)

L'albero viene aumentatovia via con queste nuove informazioni

es. variabile: tipo, punto di dichiarazione, scope, ...

Per gli identificatori esse sono anche registrate nella tabella dei simboli

87

CompilatoriAnalisi

Lessicale

AnalisiSintattica

AnalisiSemantica


Ottimizzazione

GenerazioneCodice

Tavoladei simboli

Gestioneerrori

programma sorgente

lista token

albero sintattico

codice intermedio

albero aumentato

codice intermedio

codice oggetto

88

Compilazione: fasi finali• Generazione della forma intermedia

– Visita dell'albero per generare codice– Forma intermedia

• Ottimizzabile• Portabile

• Ottimizzazione– Rimozione codice inutile, espansione inline delle

chiamate di sottoprogrammi, fattorizzazione espressioni, ottimizzazione dei cicli

• Generazione del codice oggetto– Segue spesso un'altra fase di ottimizzazione

• es. assegnamento di variabili molto usate a registri

89

Sintassi e Semantica

NOGrandeSemantica

SIPiccolaSintassi

StandardizzazioneComplessità

Separate nella descrizione ma intimamente collegate

La sintassi dovrebbe suggerire la semantica

La semantica è guidata dalla sintassi

90

Semantica (dinamica)

• Specifica del linguaggio in modo da bilanciare– Esattezza

• (specifica non ambigua, a priori, di cosa ci si debba aspettareda costrutti sintatticamente corretti, indipendentemente dall’architettura della macchina cheesegue il programma)

– Flessibilità• (le molteplici implementazioni del LdP non devono essere

impedite.)

Per descrivere il significato dei programmi. E’ complessa:

91


• Specifica del linguaggio in modo da bilanciare– Esattezza

• (specifica non ambigua, a priori, di cosa ci si debba aspettareda costrutti sintatticamente corretti, indipendentemente dall’architettura della macchina cheesegue il programma)

– Flessibilità• (le molteplici implementazioni del LdP non devono essere

impedite.)

Per descrivere il significato dei programmi. E’ complessa:

Uso di metodi formaliper descrivere

il significato dei programmi(derivati e adattati dai linguaggi artificiali della logica matematica)

92


Semantica denotazionale(applicazione ai linguaggi di programmazione di tecniche

sviluppate per la semantica dei linguaggi logico-matematici)

I metodi formali: due grandi famiglie (ma ce ne sono altre)

Significato di un programma ßà Uso di funzione: descrive I/O del programma

Dominio e codominio della funzione sono strutture matematiche (I/O, ambienti, memoria)

93


Semantica denotazionale(applicazione ai linguaggi di programmazione di tecniche

sviluppate per la semantica dei linguaggi logico-matematici)

I metodi formali: due grandi famiglie (ma ce ne sono altre)

Significato di un programma ßà Uso di funzione: descrive I/O del programma

Dominio e codominio della funzione sono strutture matematiche (I/O, ambienti, memoria)

Semantica operazionale(specifica del comortamento della macchina astratta, tramiteun formalismo a basso livello: Automi Assiomi algebrico-logici

Stati e transizioni (SOS))

Significato di un programma ßà Uso di formalismo di basso livello: descrive il comportamento dell ’interprete della macchina astratta

94

Semantica operazionaleOttenuta definendo un interprete del linguaggio L

su di una macchina ospite i cui componenti sono descritti in modo matematico

L’idea alla base:Dare la semantica di un linguaggio L

mediante la definizione del comportamento dell’interprete

(della macchina astratta che riconosce L) in corrispondenza di programmi scritti in linguaggio L

Ricordiamo il nostro obbiettivo:

Descrivere il significato di un programma scritto in linguaggio L in termini

di cosa ci si debba aspettare dall’uso dei costrutti corretti del linguaggio L

COSA FA IL PROGRAMMA?

95

Semantica operazionaleOttenuta definendo un interprete del linguaggio L

su di una macchina ospite i cui componenti sono descritti in modo matematico

L’idea alla base:Dare la semantica di un linguaggio L

mediante la definizione del comportamento dell’interprete

(della macchina astratta che riconosce L) in corrispondenza di programmi scritti in linguaggio L

Utile perché fornisce direttamente un modello di implementazione

Definibile in modo formale a partire dalla sintassi (Semantica Operazionale Strutturata)

96

Sintassi astratta per definire la semantica

Una descrizione sintattica che evidenzia la struttura sintattica essenziale dei vari costrutti del linguaggio

Alberi di derivazione che rispettano i vincoli contestuali

Strumento utile per chi pensa a come sia possibile manipolare un linguaggio

98

Semantica Operazionale Srutturata(SOS)

Definizione della semantica in modo guidato dalla sintassi

Si definiscono delle regole di transizioneche specificano

i passi della computazione di costrutti complessi del linguaggio

(es: Exp + Exp’) in termini dei passi della computazione di

costrutti componenti (es: Exp e Exp’)

99

I costrutti cui siamo interessati modificano una qualche nozione di stato

(in cui la macchina astratta si trova durante la computazione)

Regole definite su configurazioni del tipo

<Comando, Stato>

Not. ⟨C,σ⟩

Configurazioni ßà Stati in cui la macchina si trova durante il suo funzionamento (mentre l’interprete del linguaggio computa)


100

Regole sono definite su configurazioni del tipo…

<Comando, Stato>

⟨C,σ⟩

Una sequenza finita di coppie (X,n):Stato σ:

“nello stato σ la variabile X ha valore n”

(tutte le variabili su cui il comandoagisce)

Un albero di derivazione corretto

(sintassi astratta)

(es. una istruzione corretta e che rispetti i

vincoli contestuali in un programma scritto

in un LdP)

E’ definito con riferimento al modello di memoria adottato

(mantiene i valori delle variabili coinvolte nel

comando)


101

Semantica Operazionale Strutturata (SOS)

Tipi di transizioni tra configurazioni

Forma semplice di una transizione: in un solo passo

<Comando, Stato> → Stato’⟨c,σ⟩ → τ

σ: stato di partenzaτ: stato d'arrivo

es. comando nullo:⟨skip, σ⟩ → σ

102


Tipi di regole per la specifica di transizioni tra configurazioni

Forma composta di una transizione: in tanti piccoli passi

<Comando, Stato> → <Comando’, Stato’>⟨c,σ⟩ → ⟨c',τ⟩

σ: stato di partenzaτ: stato di arrivo

es. Comando “if then else”: ⟨if tt then C1 else C2 ,σ⟩ → ⟨C1,σ⟩

103


forma condizionale

Le premesse sono i prerequisiti della transizione (conseguenza)

premessa -----------------conseguenza

⟨c1,σ1⟩ → ⟨c'1,σ'1⟩ ⟨c2,σ2⟩ → ⟨c'2,σ'2⟩⟨c,σ⟩ → ⟨c',σ'⟩

Se c1, partendo dallo stato σ1, può fare un passo trasformandosi in c'1, nello stato σ'1

e c2 partendo da σ2 può fare un passo trasformandosi in c'2, nello stato σ'2

Allorail comando c partendo da σ può fare un passo trasformandosi in c' nello

stato σ'

104

Semantica delleespressioni aritmetiche

Le configurazioni

rappresentano gli stati in cui il sistema si trova ad operare mentre esegue il calcolo di una espressione

<Comando, Stato> ⟨C,σ⟩

Configurazioni ßà Stati in cui la macchina si trova durante il suo funzionamento

105


Le transizioni

rappresentano il procedere del calcolo stesso dell’espressione

Una configurazione finale rappresenta il risultato del calcolo

<Comando, Stato> → <Comando’, Stato’>⟨C,σ⟩ → ⟨C',σ'⟩

“à” (relazione di transizione), ovvero come si passa da una configurazione all ’altra

106


(semplificate)<AExpr> ::= <AExpr> + <AExpr> | <Num>

Come si calcola il valore di una espressione in questo linguaggio?In linguaggio naturale:

107


(semplificate)

Come si calcola il valore di una espressione in questo linguaggio?

In linguaggio naturale:

R1: Il valore di una espressione costituita da un numero n è il valore rappresentato da n (not. n)

es: il valore di 10 è 2

<AExpr> ::= <AExpr> + <AExpr> | <Num>Come si calcola il valore di una espressione in questo linguaggio?

108


(semplificate)





R2: Il valore di una espressione E + E’ si ottiene sommando n ed m (dove n è il valore di E ed m è il valore di E’)


109


(semplificate)







OSSERVIAMO CHE:

R1 ed R2 corrispondono alle due alternative nella definizione si ntattica di <AExpr>

R2 suggerisce il modo per calcolare una espressione complessa: calcolare il valore delle due espressioni di cui si compone e sommare i valori

110


(semplificate)


CALCOLIAMO 10+11 applicando le regole R1 ed R2:

R2: Il valore di 10+11 è n + m, dove n è il valore di 10 ed m è il valore di 11

ABBIAMO RIDOTTO IL PROBLEMA ALLA RICERCA DEI VALORI n ed m

R1: il valore di 10 è 2

R1: il valore di 11 è 3

Sappiamo che la somma di 2 e 3 è 5

Il valore di 10 +11 è 5

111


(semplificate)


Riprendiamo le regole in linguaggio naturale:


Le transizioni rappresentano il procedere del calcolo (scrivere Eàn significa dire che il valore di E è il numero naturale rappresentato da n)

112


(semplificate)





R2 è vista come regola per determinare la transizione

dalla configurazione del tipo E + E’ alla configurazione che rappresenta il valore di E + E’

transizioni: se Eàn e E’àm allora E+E’àk con k = n+m

113


(semplificate)

<AExpr> ::= <AExpr> + <AExpr> | <Num>


R1 è vista come regola per determinare il valore n di una espressione semplice n

transizioni: nàn



R1: Il valore di una espressione costituita da un numero n è il val ore rappresentato da n (not. n)

114


(semplificate)

<AExpr> ::= <AExpr> + <AExpr> | <Num>Regole di transizioni

n à n

Eàn E’àm k= n+m

E+E’ à k

Le regole sono guidate dalla sintassi

La prima regola definisce le transizioni per configurazioni cost ituite da un elemento della struttura sintattica <Num>

La seconda regola definisce transizioni per espressioni in cui c ompare +

K=n+m ßà ipotesi di saper calcolare la somma tra numeri naturali (valori)

116

n → n

Eàn E’àm k= n+mE+E’à k

Eàn E’àm n > m k = n-m E-E’à k

Eàn(E) à n

Semantica delle espressioni aritmetichesui numeri naturali

(estensione delle regole precedenti)

Vediamo le configurazioni finali come i valori delle espressioni di partenza

In che senso semantica del linguaggio delle espressioni aritmetiche?

117

Osserviamo che

Che fine ha fatto il concetto di STATO?

Siano a questo punto abbiamo fatto una semplificazione:

le transizioni erano determinate come funzioni che associavano ad una espressione (in termini di struttura astratta) il valore

di questa espressione:

Eàk

118

Grammatica delleespressioni aritmetiche a valori naturali

con identificatori

<AExpr> ::=<Num>|<Var>|<AExpr> +<AExpr>| <AExpr> +<AExpr>

<Num> ::= 1|2|…… <Var>::= X1……

<AExpr>::= <Var> consente di scrivere espressioni in cui compaiono nomi

(identificatori)

119

Semantica delleespressioni aritmetiche a valori naturali

con identificatoriIl significato di una espressione

x+2 dipende dal significato di x (valore associato ad x)

In questo contesto serve una qualche nozione di STATO

120

Semantica delleespressioni aritmetiche a valori naturale

con identificatoriIl significato di una espressione

x+2 dipende dal significato di x (valore associato ad x)

In questo contesto serve una qualche nozione di STATO

Le transizioni sono del tipo

Scrivo:

⟨E,σ⟩ → n

Leggo: Il valore di E date le associazioni di σ è n

121

StatoE’ definito con riferimento al

modello di memoria della nostra macchina astratta(mantiene i valori delle variabili)

Stato σ : sequenza finita di coppie (X,n)

Nello stato σ la variabile X ha il valore n (not. n = σ(X))

122


σ(X) = n

<n, σ> → n

<E, σ>àn <E’, σ> à m k= n+m<E +E’,σ> à k

<E, σ>àn <E’, σ> à m n>m k= n-m<E-E’,σ> à k

<E, σ>àn<(E), σ> à n

123


σ(X) = n

<n, σ> → n

<E, σ>àn <E’, σ> à m k= n+m<E+E’,σ> à k

<E, σ>àn <E’, σ> à m n>m k= n-m<E-E’,σ> à k

<E, σ>àn<(E), σ> à n

<AExpr> ::=<Var>

124

Esempio Completo

<AExpr> ::= <Num>|<Var>|<AExpr> +<AExpr>| <AExpr> -<AExpr><Num> ::= 1|2|…… <Var>::= X1 ,X2……

Tramite la seguente grammatica …

Generiamo la stringa sintatticamente corretta X1+8 – X2 (con struttura astratta )

<AExpr>

<AExpr> + <AExpr>

<Var>

X1

<AExpr> - <AExpr>

<Num>

8

<Var>

X2

125

Esempio Completo

Ricordate che la stringa, in realtà è l’albero di derivazione

Valutiamo la semantica della struttura astratta X1 + 8 -X2 a partire da uno stato σ che associa a X1 il valore 5 e ad X2 il valore 3

<X1 + 8 – X2, σ> à{…} 10

<X1 + 8 –X2, σ> à k

126

Esempio Completo



<X1 + 8 – X2, σ> à{…} 103:

3

<E, σ>àn <E’, σ> à m k= n+m<E + E’,σ> à k

<X1, σ>àn <8-X2, σ> àm k= n+m

<X1 + 8 –X2, σ> à k

127

Esempio Completo



<X1 + 8 – X2, σ> à{…} 101:

3

σ(X) = n

1<X1, σ>à5 <8-X2, σ> àm k= 5+m

<X1 + 8 –X2, σ> à k

128

Esempio Completo



<X1 + 8 – X2, σ> à{…} 104:

3

1<X1, σ>à5 k= 5+m

<E, σ>àn <E’, σ> à m n>m k= n-m

<X2, σ> àm2 n1>m2 m= n1-m24:

<X1+ 8 –X2, σ> à k

<E-E', σ>àk

<8, σ>àn1

<8-X2, σ>àm

129

Esempio Completo



<X1 + 8 – X2, σ> à{…} 10

3

1<X1, σ>à5 k= 5+m

2: <n, σ> → n

2<8, σ>à8 <X2, σ> àm2 8>m2 m= 8-m2 4:

<X1 + 8 –X2, σ> à k

130

Esempio Completo



<X1 + 8 – X2, σ> à{…} 10

3

1<X1, σ>à5 10= 5+5

1: σ(X) = n

2 1<8, σ>à8 <X2, σ> à 3 8>3 5= 8-3 4:

<X1+ 8 –X2, σ> à 10

<8-X2, σ>à5

131

Un semplice L

<Exp> ::= <Const> | <Var> | (<Exp>) | <Exp> <Op> <Exp> | <!Exp>

<Op> ::= + | - | * | / | % | == | != | < | <= | > | >= | && | ||<Const> ::= <Num> | <Bool><Bool> ::= true | false<Num> ::= ...

La sintassi

3

132

Semantica delleespressioni logiche

⟨true, σ⟩ → tt⟨false, σ⟩ → ff

secondo la tavola di verità

bv indica un valore booleano tt o ff

Op.elementari

<E, σ>àbv <E’, σ> à bv’ bv’’= bv ∨ bv’<E || E’,σ> à bv’’

<E, σ>àbv <E’, σ> à bv’ bv‘’= bv ∧ bv’<E&&E’,σ> à bv’’

<E, σ>àbv bv’ = ¬bv<!E, σ> à bv’

133

Semantica delleespressioni logiche

Rel indica uno qualunque degli operatori di confronto

<E, σ>àn <E’, σ> à m bv = n rel m<E rel E’,σ> à bv

134

I comandiStato σ :

sequenza finita di coppie (X,n)Nello stato σ la variabile X ha il valore n

La soluzione ad un problema di programmazione consistenella individuazione di una sequenza di azioni che

modifcano lo stato iniziale fino a trasformarlo nellostato finale desiderato

Modifica di uno stato

σ[X ← v]: nuovo stato simile a σ dove la variabile X prende il nuovo valore v

136

Semantica dei comandiLe transizioni sono del tipo

Scrivo:

⟨C,σ⟩ → τ

Leggo: Il comando C, date le associazioni di σ, porta nello stato σ‘

137

Semantica dei comandi

⟨E, σ⟩ → n⟨X := E, σ⟩ → σ[X ← n]

⟨c1, σ⟩ →σ’ ⟨c2, σ’⟩→ τ⟨c1 ; c2, σ⟩ → τ

⟨skip, σ⟩ → σ Com nullo

Com assegnazione

Com blocco di istruzioni da eseguire in ordine

138


⟨E, σ⟩ → tt ⟨c1, σ⟩ → τ⟨if E then c1 else c2, σ⟩ → τ

⟨E, σ⟩ → ff ⟨c2, σ⟩ → τ⟨if E then c1 else c2, σ⟩ → τ

139

⟨while E do C, σ⟩ → σ


⟨E, σ⟩ → ffSe la condizione è falsa lo stato non viene modificato (eq. Com nullo)

⟨while E do C, σ⟩ → τ

⟨E, σ⟩ → tt <C, σ>

Se la condizione è vera C viene ripetutamente eseguito

⟨while E do C, σ’⟩ → τ

140

Esempio


<x=2; y=3; x=x-1, σ0> à{…} σ0[xß1, yß3]

<x=2; y=3; x=x-1;, σ0> à σf

Valutiamo la semantica della struttura astratta x=2; y=3; x=x-1 a partire da uno stato σ0 che associa a x e y il valore 0

141

Esempio


<x=2; y=3; x=x-1, σ0> à{…} σ0[xß1, yß3]

<x=2; y=3; x=x-1;, σ0> à σf


⟨c1, σ⟩ →σ’ ⟨c2, σ’⟩→ τ⟨c1 ; c2, σ⟩ → τ

<x=2;, σ0> à σ1 <y=3; x=x-1;, σ1> àσf

142

Esempio


<x=2; y=3; x=x-1, σ0> à{…} σ0[xß1, yß3]

<x=2; y=3; x=x-1;, σ0> à σf


<x=2;, σ0> à σ1 = σ0[xß2] <y=3; x=x-1;, σ1 = σ0[xß2] > àσf

⟨Ε, σ⟩ → n⟨x := Ε, σ⟩ → σ[x← n]

<2, σ0> à 2

143

Esempio


<x=2; y=3; x=x-1, σ0> à{…} σ0[xß1, yß3]

<x=2; y=3; x=x-1;, σ0> à σf


<x=2;, σ0> à σ1 = σ0[xß2] <y=3; x=x -1;, σ1 = σ0[xß2] > àσf

<2, σ0> à 2 <y=3; σ1 = σ0[xß2] > àσ2 <x=x-1; σ2> àσf

⟨c1, σ⟩ →σ’ ⟨c2, σ’⟩→ τ⟨c1 ; c2, σ⟩ → τ

144

Esempio


<x=2; y=3; x=x-1, σ0> à{…} σ0[xß1, yß3]

<x=2; y=3; x=x-1;, σ0> à σf



<2, σ0> à 2 <y=3; σ1 = σ0[xß2] > àσ2= σ0[x=2 yß3] <x=x-1; σ2> àσf

⟨Ε, σ⟩ → n⟨x := Ε, σ⟩ → σ[x← n]

<3, σ1> à 3

145

Esempio


<x=2; y=3; x=x-1, σ0> à{…} σ0[xß1, yß3]

<x=2; y=3; x=x-1;, σ0> à σf



<2, σ0> à 2 <y=3; σ1 = σ0[xß2] > àσ2= σ0[x=2 yß3] <x=x-1; σ2> àσf

⟨Ε, σ⟩ → n⟨x := Ε, σ⟩ → σ[x← n]

<3, σ1> à 3 <x-1, σ2> à 1

σf= σ2[xß1]’ =σ1[yß3] àσ0[xß1 yß3]

146

Esercizio

Valutiamo la semantica della struttura astratta while x>0 do x=x-1 a partire da uno stato σ che associa a x il valore 2

147

Computazione

• Sequenza di transizioni concatenate non ulteriormente estendibile in cui ogni transizione è premessa di qualche regola

• Due tipi di computazioniterminanti: finitedivergenti: infinite (loop)

148

Pragmatica e Implementazione– “a che serve / come

usare un certo un certo costrutto linguistico ?”

• Obiettivo: migliorare il sw

• Fattori in evoluzione– Convenzioni – Stile

• Usare il goto ?• Modificare le variabili

dei cicli for ?• Modalità di passaggio di

parametri• Scelta iterazioni

• Connesso alla realizzazione pratica dei compilatori

– “come vengono implementati ?”

– “a quale costo ?”• Domande di tipo

ingegneristico

Corso di Laurea in “ITPS” · Vogliamo descrivere il linguaggio delle stringhe palindrome...

Documents

Transcript of Corso di Laurea in “ITPS” · Vogliamo descrivere il linguaggio delle stringhe palindrome...