Corso di Linguaggi di Programmazione - Lezione...

Corso di Linguaggi di ProgrammazioneLezione 5

Chiara [email protected]

Dipartimento di Tecnologie dell’InformazioneUniversità degli Studi di Milano

10 Marzo 2008

C. Braghin, DTI – Univ. di Milano Corso di Linguaggi di Programmazione

Struttura di un compilatore


Semantica di un linguaggio

Definisce il significato di ogni costrutto sintattico legale dellinguaggio;Si divide in semantica statica e semantica dinamica:

la semantica statica specifica le regole di compatibilità ditipo e alcune regole che vincolano la forma di alcunicostrutti legali e descrivono come deve essere scritto ilprogramma.

- Può essere verificata staticamente in fase di compilazione.- Esprime regole legate alla sintassi che la BNF non riesce a

descrivere, ad esempio controllo di etichette, verifica degliargomenti in fase di chiamata di funzione, utilizzo degliidentificatori dopo la dichiarazione, ecc.

la semantica dinamica specifica il comportamento attesodurante l’esecuzione.

- Non può essere verificata in fase di compilazione.


Semantica statica: Grammatica ad attributi

Una grammatica ad attributi è una tripla 〈G, A, E〉 dove:G è una grammatica libera da contestoA è un insieme di attributi associati ai simboli non-terminalie terminali della grammatica GE è un insieme di equazioni per il calcolo dei valori dei variattributi, dette regole semantiche, associate alle regole diproduzione della grammatica G.

Le regole semantiche sono scritte in un’opportunanotazione, detta metalinguaggio semantico, ad esempionotazioni matematiche, logiche o programmative


Grammatica ad attributi - Attributi (1)

Sia X0 → X1 . . . Xn una regola sintattica, ad ogni simbolo nonterminale Xi si associano uno o più attributi, A(Xi).Un attributo di X ha un dominio (ad esempio può assumerevalori interi o stringhe) e può essere:

Sintetizzato S(X0)

il suo valore dipende da X1, . . . , Xn: un attributo del nodopadre è calcolato in funzione dei valori degli attributi deinodi figli.S(X0) = f (A(X1), . . . , A(Xn))il calcolo va dalle foglie alla radice (ascendente)

Ereditato E(Xj)

il suo valore dipende da X0, X1, . . . , Xn: un attributo di unnodo è calcolato in funzione dal valore degli attributi del suonodo padre e dei nodi fratelli (a volte solo quelli left-mostper non avere cicli).E(Xj) = f (A(X0), . . . , A(Xn)), 1 ≤ j ≤ nil calcolo va dalla radice alle foglie (discendente)


Grammatica ad attributi - Attributi (2)

Intrinseco I(X )

prodotto dall’esterno: il valore è calcolato da procedureesterne, ad esempio dall’analizzatore lessicale oppure dauna lettura da tastiera.sono associabili anche ai simboli terminali, quindi alle fogliedell’albero di derivazione.


Grammatica ad attributi - Notazioni

〈A〉.a indica l’attributo a del simbolo non terminale 〈A〉I simboli non terminali che compaiono più volte nella partedestra di una regola di produzione sono indicizzati perdistinguere le occorrenze multiple

〈expr〉 → 〈T 〉+ 〈T 〉 diventa 〈expr〉 → 〈T 〉[1] + 〈T 〉[2]oppure, E → T + T diventa E → T1 + T2


Grammatica ad attributi - Esempi

Vedi lavagna


Grammatica ad attributi - Calcolo degli attributi (1)

Una grammatica è chiamata S-attributed se tutti gli attributisono sintetizzati.

In questo caso per calcolare il valore degli attributi èsufficiente un’attraversamento bottom-up del parse tree.

Nel caso in cui la grammatica ad attributi contenga siattributi sintetici che ereditati, si utilizza un grafo delledipendenze, ovvero si estende il parse tree con dellefrecce che indicano le dipendenze degli attributi:

- Un arco da un nodo A ad un nodo B indica che l’attributo diA è necessario per calcolare l’attributo di B

- E’ buona norma distinguere gli attributi sintetizzati da quelliereditati.


Grammatica ad attributi - Calcolo degli attributi (2)

Una grammatica è chiamata L-attributed se nel grafo delledipendenze tutti gli archi vanno da sinistra a destra

- garantisce l’assenza di cicli all’interno del grafo delledipendenze

- garantisce che esiste un ordine per il calcolo degli attributi- si tratta di una proprietà essenziale per compilatori

one-pass perchè le regole semantiche possono venireapplicate direttamente durante la fase di parsing e quindi ilparse tree non deve venire mantenuto in memoria.


Come definire formalmente la semantica (dinamica) diun linguaggio?

Non esiste uno standard come nel caso della descrizioneformale della sintassi;La descrizione formale rispetto al linguaggio naturalepermette di verificare formalmente la correttezza di unprogramma (vedi theorem prover basati su semanticaassimatica);Principali formalismi utilizzati:

semantica operazionalesemantica assiomaticasemantica denotazionale


Semantica Operazionale

Ottenuta definendo un interprete del linguaggio L su di unamacchina virtuale i cui componenti sono descritti in modomatematico;Il significato di un’istruzione consiste nella variazione dellostato della macchina (registri, program counter, istruzionecorrente, etc.) causato dall’esecuzione dell’istruzionestessa.È possibile definirla in modo più formale guidato daicostrutti sintattici (SOS, Structural Operational Semantics)tramite regole di transizione definite come〈Cmd , State〉 → 〈Cmd ′, State′〉, dove 〈Cmd , State〉 è dettaconfigurazione.


Semantica Denotazionale

Metodo introdotto da Scott e Strachey nel 1971.È il metodo finora più utilizzato.Definisce la semantica di un linguaggio in termini difunzioni ricorsive: per ogni costrutto del linguaggio sidefinisce un oggetto matematico che lo rappresenti e unafunzione che collega istanze di uno stesso costrutto allostesso oggetto matematico.Lo stato delle variabili viene esaminato e modificatotramite funzioni.


Semantica Assiomatica

Introdotta da Floyd nel 1967 e raffinata da Hoare nel 1969.Fondata sulla logica matematica e sul concetto diasserzione, ovvero condizione che deve valere prima edopo l’esecuzione di una certa istruzione.In alcuni casi (programmi piccoli e semplici) permette diprovare formalmente la correttezza di un programma.Poco chiara come strumento di definizione.


Theorem Prover: Tool per la Verifica

Automated theorem proving (ATP) o automateddeduction, consiste nella verifica di teoremi matematici permezzo di un computer.A seconda della logica sottostante, il problema di deciderela validiti. un teorema varia da molto semplice adimpossibile.

Nel caso di logica proposizionale, il problema è decidibile,ma NP-completo (cioè si crede esistano solo algoritmi dicomplessità esponenziale per la soluzione di taleproblema).

Theorem prover famosiACL2: scritto in Common Lisp, usato per verifica di circuitiHW.Isabelle: scritto in Standard ML, interattivo.HOL (Higher-Order Logic): scritto in ML, interattivo.


Lex e Yacc [1975, Lesk e Johnson]

Lex: tool utilizzato per generare un analizatore lessicalescritto in C.

basato sul fatto che data una grammatica regolare èpossibile costruire un riconoscitore del linguaggio in modoalgoritmico (automa a stato finito).

Yacc: tool utilizzato per generare un analizatore sintatticoscritto in C.

basato sul fatto che data una grammatica libera dacontesto è possibile costruire un riconoscitore dellinguaggio in modo algoritmico (automa a pila).


Lex e Yacc

Le regole lessicali del linguaggio da riconoscere sonocontenute nel file bas.l

Le regole sintattiche del linguaggio da riconoscere sonocontenute nel file bas.y


Struttra dei file di input di Lex e Yacc

... definizioni {% dichiarative C %} ...

%%

... regole ...

%%

... subroutines (codice C dell’utente) ...


Lex e Yacc - Esempio

legge_interi (usa solo Lex)legge_numeri_parole (usa solo Lex)esempio di interazione tra i due (calcolatore)esempio di ANSI C


Lex (1)Meta-linguaggio

I linguaggi regolari sono equivalenti alle espressioniregolari e agli automi a stati finiti. Lex utilizza le espressioniregolari per definire le regole lessicali del linguaggio.In Lex ad ogni regola è associata un’azione.


Lex (2)Esempi di uso del meta-linguaggio


Esercizi per casa (1)

1 Provare a definire (anche solo in linguaggio naturale)proprietà non esprimibili mediante BNF, ma esprimibilimediante grammatiche ad attributi.

2 Commentare l’esempio relativo alla regola semantica diAda che si trova nel libro di testo a pagina 133: di che tipodi attributi si tratta, far vedere il parse tree decorato con gliattributi, ecc.


Esercizi per casa (2)

3 Scaricare i file di esempio d’uso di Flex e Bison:1 Descrivere l’output dell’esecuzione di ciascun programma.2 Modificare il programma legge_interi facendogli

tornare un messaggio d’errore nel caso in cui si inseriscaun carattere non numerico.

3 Modificare il programmma legge_numeri_parolefacendogli riconoscere anche i caratteri ; e , , cheappartengono alla categoria PUNTEGGIATURA.


Corso di Linguaggi di Programmazione - Lezione...

Documents

Transcript of Corso di Linguaggi di Programmazione - Lezione...