Approfondimenti sui linguaggi di programmazione

Lezione 1 - Riepilogo modulo 2 e
approfondimenti
Corso — Programmazione
Linguaggi di programmazione— Approfondimenti sui linguaggi
di programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Ricapitolando M2(1)
• Da programmazione non strutturata a strutturata
• E' utile esercitarsi nella scrittura di codice non strutturato
per comprendere bene quali siano i problemi che introduce
• L'uso di goto espliciti rendono più evidente l'importanza
del flusso e il concetto di salto ad una istruzione
(embrione del salto a sottoprogramma)
• Costrutti di programmazione strutturata - leggibilità e
flusso di esecuzione evidente - confronto con versioni non
strutturate
• Associazione tra flusso del programma e flusso
dell'algoritmo (sequenzialità)
Ricapitolando M2(2)
• Linguaggi pseudoformali per la descrizione di programmi flow chart e pseudocodice
• Flow chart permette di avere ben evidente il flusso
• Pseudocodice si avvicina al codice che dovremo scrivere
permette di esercitarsi sulla logica della programmazione
• Tipi di dato e importanza delle strutture dati - dati ed
algoritmi
• Occupazione in memoria del codice e dei dati (presentata
incrementalmente)
• Relazione tra strutture dati e algoritmi
Ricapitolando M2(3)
• Relazioni di ricorrenza ed invarianti di ciclo - associate ad
errori nel codice
• Associazione tra tipi di dato e iterazioni (array e cicli)
• Operazioni su tipi di dato strutturato - dipendenza dalla
sequenzialità della memorizzazione della struttura
• Modularità, sottoprogrammi e chiamate - associazione tra
logica dei sottoprogrammi e progettazione del programma
• Utilizzo dello stack e motivazioni delle chiamate
• Keep it simple, suddividere in compiti semplici il più
possibile confinati (ad eccezione delle interfacce)
Ricapitolando M2(4)
• Ricorsione e strutture dati dinamiche
• Heap e allocazione dinamica della memoria, vantaggi e
svantaggi
• Gestione di strutture dinamiche
• Strutture dinamiche e valutazioni sulla loro efficacia
• Fasi della programmazione e relazione tra le fasi
• Importanza della raccolta delle specifiche e del modello
• Evitare retroazioni sulla fase di verifica
• Verifica empirica e formale
Lezione 2 - Principi della programmazione
strutturata
Corso — Programmazione
Linguaggi di programmazione— Approfondimenti sui linguaggi
di programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Programmazione strutturata e Top-Down
• Approccio alla progettazione di algoritmi
• Scomposizione gerarchica del problema
• Algoritmi chiari e ben strutturati
• Livelli di dettaglio crescente
• Mantenere, in fase di codifica, chiarezza e strutturazione
dell'algoritmo
• La programmazione strutturata rappresenta la naturale
estensione dell'approccio top-down al processo di scrittura
del codice
Programmazione strutturata e Top-Down
• Al crescere delle dimensioni di un programma, diventa
sempre più difficile per il programmatore contemplarlo nel
suo complesso. “Non si vede la foresta guardando degli
alberi”
• Scomporre il programma in blocchi di dimensione gestibile
• Disciplinare la codifica seguendo rigorosamente delle
convenzioni uniformi
• Limitare al minimo indispensabile le interazioni e le
interferenze tra blocchi distinti
Programmazione strutturata e Top-Down
• La programmazione strutturata è l'estensione dell'analisi
top-down
• Nasce dall'esigenza di gestire la complessità di un
programma al crescere delle sue dimensioni
• La programmazioe evolve perchè trainata da necessità di
leggibilità portabilità e manutenibilità
• Programmi sempre più complessi sviluppati con strumenti
più astratti e riusando codice
Attività di processo e attività di gestione
• Qualsiasi programma comprende due tipi di attività:
processo e gestione
• Attività di processo: dove vengono effettivamente svolti
i calcoli
• Attività di gestione: tutto ciò che è accessorio
all'effettivo svolgimento dei calcoli: prendere decisioni,
trasferire il controllo a un'altra parte del programma
(salti), allocare e deallocare variabili
• La strutturazione modulare mappa requisiti e
sottorequisiti e la struttura è di natura gerarchica
(rapporti chiari tra moduli)
Regole per la modularità(1)
• Ogni modulo dovrebbe avere una dimensione tale da
permettere al programmatore di vederlo tutto in una sola
schermata (tutto il suo flusso)
• Un modulo non dovrebbe contenere più di tre livelli di
strutture di controllo una dentro l'altra, e possibilmente di
meno
• Tutte le attività integrate in un modulo dovrebbero
riguardare la stessa fase concettuale dell'algoritmo che
viene realizzato
• Tutte le attività integrate nello stesso modulo dovrebbero
essere eseguite nelle stesse condizioni
Regole per la modularità(2)
• Tutte le attività integrate nello stesso modulo dovrebbero
lavorare sugli stessi dati (embrione di programmazione
orientata agli oggetti)
• Idealmente, ciascun modulo dovrebbe essere volto ad
ottenere un solo scopo specifico o a realizzare una ben
precisa funzionalità
• La programmazione strutturata pone dei vincoli ai modi in
cui l'esecuzione di attività di processo possa essere
controllata
• Ciascun blocco compresi i blocchi strutturati devono avere
un punto di ingresso e uno di uscita
Lezione 3 - Riepilogo M1 e
approfondimenti
Corso — Programmazione
Linguaggi di programmazione— Approfondimenti sui linguaggi
di programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Ricapitolando M1(1)
• UD1: Significato di programmabile vs. regolabile
• Ruolo del programmatore oggi - spendibilità delle
competenze e importanza delle competenze nel ciclo di
vita del software
• UD2: Concetti matematici di base
• Insiemi di oggetti e proprietà degli insiemi - funzioni su
insiemi di oggetti
• Valutazione di predicati e valori di verità - valutazione di
condizioni
• Induzione matematica per la valutazione di iterazione e
ricorsione
Ricapitolando M1(2)
• UD3: Linguaggio formale - Macchina a stati e architettura
di riferiento per il programmatore
• Definizione di un linguaggio formale e proprietà del
linguaggio e delle parole del linguaggio (riconoscitore e
generatore)
• Macchina a stati per definire comportamenti e soluzioni a
problemi (rapporto con il linguaggio)
Linguaggio regolare e AUTOMA (riconosciuto da qualche
ASFD o ASFND)
Ricapitolando M1(3)
• UD4: Algoritmo - programma - esecutore (insieme di
passi elementari da eseguire in un ordine predefinito)
• Decidibilità - trattabilità - intrattabilità
• Valutazione per il confronto tra algoritmi differenti
• Costosto computazionale e di spazio
• Classe di complessità e MdT deterministica o con oracolo
• UD5: Linguaggio per la descrizione di algoritmi
considerando un elaboratore elettronico come esecutore
• Grammatica sintassi e semantica
• Prima classificazione dei linguaggi di programmazione
dipendenti dalla distanza dall'hardware.
Ricapitolando M1: linguaggi
• Parse tree relativo alla grammatica e ambiguità (più alberi
per la stessa grammatica)
• Una stringa di terminali di una grammatica appartiene al
linguaggio se ammette un albero di derivazione (da sx
verso dx le foglie sono la stringa)
• Posso disambiguare modificando la grammatica (ma non
sempre)
• L'albero è la rappresentazione interna della stringa per un
linguaggio di programmazione
Grammatica ambigua (1)
[Grammatiche ambigue] Una grammatica G si dice ambigua
se esiste una stringa che ammette due o più alberi sintattici
distinti
• Esempio: grammatica G per espressioni aritmetiche:
• S→S |S + S|S − S|S ∗ S|S/S|(0|1|2|3|4|5|6|7|8|9)
• la stringa s = 6 + 5 ∗ 9 ammette due alberi sintattici distinti
Grammatica ambigua (2)
• Una grammatica ambigua non è adatta all'analisi
sintattica e alla traduzione automatica
• Una grammatica è adatta all'analisi sintattica se per tale
grammatica è possibile costruire un algoritmo
deterministico (analizzatore sintattico)
• Se ambigua il problema è inerentemente
non deterministico: esistono più alberi sintattici per la
stessa sequenza di input
• La forma delle regole deve essere tale da evitare il non
determinismo
Grammatica ambigua (3)
• Nel caso non si riesca a fornire una grammatica non
ambigua devono essere definite delle regole per
disambiguare attraverso convenzioni
• Un esempio classico è quello della
Dangling-Else ambiguity
• Consideriamo due produzioni
S ::= if E then S
S ::= if E then S else S
• Con S che è l'istruzione e E che è l'espressione da valutare
• Consideriamo: if E1 then if E2 then S1 else S2
• Questa costruzione genera due alberi ed è quindi ambigua
• Si risolve ad esempio imponendo la convenzione che l'else
appartiene all'if più vicino non chiuso
Ricapitolando M1: disambiguare
• Considerate l'esempio di grammatica ambigua visto in
precedenza:
< expr >::=< identificatore > | < numero > |− < expr >
|(expr)| < expr > + < expr > | < expr > ∗ < expr >
• Scrivere una versione non abigua della stessa grammatica
(introdurre nella grammatica la precedenza di * su +)
• Grammatica più complicata ma non ambigua:
< expr >::=< term > | < term > + < expr >
< term >::=< atom > | < atom > ∗ < term >
< atom >::=< letterale > |− < atom > |(< expr >)
< letterale >::=< identificatore > | < numero >
dove numero e identificatore saranno definiti
conformemente alla loro natura
Vincoli contestuali sintattici
• Esempio: il numero di parametri formali deve essere
uguale a quello dei parametri attuali (chiamata a
sottoprogramma)
• BNF non sa esprimere vincoli che dipendono dal contesto
(dipende dalla dichiarazione)
• Servirebbero grammatiche contestuali (riscrittura di un
non terminale solo in un determinato contesto)
• Esempi: dichiarazione prima di utilizzo, compatibilità tra
tipi
• Soluzione: si intende per sintassi tutto ciò che posso
descrivere in BNF il resto lo delego alla semantica
BNF nei linguaggi di programmazione
• Spesso il BNF di un vero linguaggio di programmazione
viene arricchito da altri elementi (EBNF)
• [] la frase è opzionale, []∗ oppure {} la frase è ripetibile
una, nessuna o più volte (operatore star)
• In alcuni dei libri consigliati trovate la BNF o le carte
sintattiche specifiche del linguaggio
• Si trovano esempi di linguaggi molto semplici in rete (es Il
linguaggio KISS) da cui si può partire per vedere come
vengono rappresentati gli elementi fondamentali del
linguaggio
• Tali elementi sono: espressioni matematiche, espressioni
booleane, costrutti strutturati, come inizia il programma e
come si dichiarano e utilizzano le funzioni.
BNF nei linguaggi di programmazione:
esempio(1)
• Esempio BNF parziale con KISS per la definizione di un
programma:
< program >::= PROGRAM < top − level decl >< main >0 .0
• Un programma è definito come un insieme di dichiarazioni
di primo livello, precedute dalla keyword PROGRAM,
seguite dal main e dal punto (obbligatorio)
< main >::= BEGIN < block > END
< block >::= [< statement >]∗
• Un blocco consiste a sua volta di zero o più statement,
che sono assegnazioni o strutture di controllo
BNF nei linguaggi di programmazione:
esempio(2)
• Come in Pascal le dichiarazioni di variabile sono
identificate dalla keyword VAR:
< top − level decls >::= [< data declaration >]∗
< data declaration >::= VAR < var − list >
• Le sezioni VAR possono essere ripetute, cioè apparire più
volte, a differenza del Pascal standard. Ovviamente la
< var − list > può essere una variabile singola nel caso più
semplice
< var − list >::=< ident > [, < ident >]∗
Programmi di parsing
• Dato un file di input contenente del testo e supponendo
una certa grammatica, controllare che il testo sia stato
generato dalla grammatica
• In aggiunta si chiede di capire come è stato generato quali
regole e quali alternative sono state usate durante la
derivazione
• Questo processo è chiamato parsing o analisi sintattica
• Programmi non semplici da scrivere dato che bisogna
scegliere tra alternative
• L'ideale sarebbe poter vedere in avanti per decidere
meglio (anche solo il simbolo successivo)
• Generatori di parser: genera un parser a partire dalla
descrizione della grammatica e codice associato alle
regole della grammatica (semantica)
Progettazione di un parser(1)
• Analisi di un flusso derivante di solito da un file
contenente un codice (in linea teorica posso parsare
qualsiasi cosa anche non del codice)
• Le funzionalità sono: i)Verificare che il flusso sia valido, ii)
Convertire il flusso in un Abstract Syntax Tree o parse
tree, iii) Agire se si trova un pattern specificato nello
stream (analisi semantica)
• I parser possono essere ottenuti in molti modi.
Inizialmente fatti a mano, ad oggi generati da un tool di
parser generator o compiler compiler
• Fasi di parsing:
Scanner: Legge il flusso ed identifica i token. Esempio
if (x = 5) genera 6 token guardando alle regole della
grammatica e converte in un formato che il parser potrà
più facilmente utilizzare (if ( <id>=<num>))
Parser: Prende i token e fa il match con le regole
grammaticali generando se richiesto un albero
Progettazione di un parser(2)
• Due tipi di algoritmi di parsing dipendenti da come
agiscono: 1) algoritmi top down e 2) algoritmi bottom up
• Top down parsing: reperire i token dal flusso uno alla
volta e confrontarli con le regole grammaticali più in alto
nell'albero delle regole (LL recursive descent, tail
recursive, earleys algorithm)
• Bottom up parsing: fanno l'opposto partendo dalle
regole in basso nella grammatica fino ad arrivare a quelle
sopra (LR, LALR, GLR, recursive ascendent algorithm)
• Alcuni algoritmi controllano avanti i token per evitare di
intraprendere strade errate (look ahead). Esempio LL(k)
con k uguale ai token avanti che si ispezionano. Più è
grande k più è lento il parsing (solito LL(1))
Lezione 4 - Analisi semantica di un
linguaggio di programmazione
Corso — Programmazione
Linguaggi di programmazione— Approfondimenti sui linguaggi
di programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Motivazione per il linguaggio
• Linguaggi facilmente meccanizzabili
• Sintassi univoca e ben definita
• Linguaggio definito formalmente
• Potere espressivo e paradigma implementato dal
linguaggio
• E' buona cosa non affezionarsi troppo ad un linguaggio
Semantica del linguaggio
• La sintassi la sappiamo descrivere e abbiamo appena
rivisto come farlo ed alcuni esempi di concreto utilizzo
(parsing)
• Abbiamo visto che in alcuni casi la sintassi non
contestuale non è in grado di stabilire dei vincoli sintattici
• Vediamo in seguito come fare a demandare questo
controllo alla fase di analisi semantica
Controlli semantici
• La semantica serve generalmente per determinare cosa fa
un programma
• Semantica statica (vincoli statici a compile time)
Controlli che la sintassi non sa fare
E' più sintassi che semantica
• Tre cose vengono aggiunte alla grammatica non
contestuale per formare una grammatica ad attributi:
Attributi: associati a simboli della grammatica con la
possibilità di possedere dei valori
Regola semantica: sequenza di azioni semantiche
Azione semantica: azione in grado di assegnare valori
agli attributi e di avere altri effetti
Semantica statica: attributi
• Per i simboli X della grammatica si associa un set di
attributi A(X ) dati dall'unione di due set disgiunti
• Attibuti sintetizzati usando le informazioni del parse tree
risalendo verso l'altro
• Attibuti ereditati usando le informazioni del parse tree
discendendo verso il basso
• Gli attributi sintetizzati realizzano un flusso informativo
ascendente nell'albero sintattico (dalle foglie verso la
radice)
• Gli attributi ereditati realizzano un flusso informativo
discendente (dalla radice verso le foglie) e laterale (da
sinistra verso destra e viceversa) nell'albero sintattico
Semantica statica(1)
• Le grammatiche ad attributi associano attributi semantici
a simboli sintattici e regole semantiche a regole sintattiche
• Aggiungono annotazioni alle produzioni in modo da dare
significato a cio' che generano.
• Gli attributi rappresentano il significato (valore) dei
simboli sintattici
• Le azioni semantiche sono il meccanismo che effettua il
calcolo di tali valori, ottenendo quindi il significato
• Il valore dell'attributo di un token è fornito
dall'analizzatore lessicale, mentre il valore dell'attributo di
un non-terminale è calcolato da regola semantica
Semantica statica: esempio(1)
• Un parse tree di una grammatica con attributi, è un parse
tree basato sulla grammatica con dei valori per gli attributi
• Se tutti gli attributi hanno valore si parla di albero <fully
attributed>
• Numeri binari calcoliamone il valore:
N → D|ND
D → 0|1
• Grammatica ad attributi con attributo value
D → 0 {D. value := 0}
D → 1 {D. value := 1}
N → D {N. value := D. value}
N1 → −N2 D {N1 . value := 2 ∗ N2 . value + D. value}
Semantica statica: esempio(2)
Semantica statica nel linguaggio di
programmazione
• Esempio: in Ada una procedura è
procedure foo
end foo;
• Come dire che il nome indicato all'inizio sia lo stesso della
fine (questione sintattica)
<procedure> → procedure <proc name>[1] <proc body>
end <proc name>[2]
• Predicato semantico: <proc name>[1].string = <proc
name>[2].string
• Esempio sui tipi:
<assign sum> → <var>[1] = <num>[1] + <num>[2]
• Consideriamo solo 2 tipi possibili
• Regola semantica:
<var>[1].type = (if ((<num>[1].type equal
int)and(<num>[2].type equal int))then int else real)
Semantica dinamica(1)
• Semantica dinamica (vincoli determinati durante
l'esecuzione)
• Esistono vari metodi per definire la semantica di un
linguaggio: algebrica, assiomatica, operazionale,
denotazionale
• Operazionale: Structured Operational Semantics (SOS)
definizione della semantica guidato dalla sintassi
• Si definiscono regole di transizione che specificano i passi
di computazione per un costrutto composto A op B in
termini di quelli dei componenti
• La forma è quella della deduzione naturale (premessa /
conseguenza)
Semantica operazionale
• Solitamente i costrutti del linguaggio modificano una
qualche nozione di stato quindi le regole che si utilizzano
sono regole definite su coppie < comando,stato >
• Una transizione è < comando,stato > →
< comando0 ,stato0 >
• Le regole definiscono induttivamente la relazione →
dicendo come si passa da una configurazione ad un altra
• Configurazioni e relazioni di transizione costituiscono un
Sistema di Transizione (Configurazioni,configurazioni
iniziali, configurazioni finali, relazione di transizione)
• Una sequenza di configurazioni da una iniziale ad una
finale è una sequenza di esecuzioni
Esempio di Semantica di un linguaggio
imperativo(1)
• Sintassi semplificata:
a::= n|X |a0 + a1 |a0 − a1 |a0 ∗ a1
b::= true|false|a0 = a1 |a0 ≤ a1 |¬b|b0 ∧ b1 |b0 ∨ b1
c::=skip|X := a|c0 ; c1 |if b then c0 else c1 |while b do c
endwhile
Esempio di Semantica di un linguaggio
imperativo(2)
• Semantica espressioni:
Numeri: < n,σ >→ n
Locazioni: < X ,σ >→ σ(X )
Somma (n somma di n0 e n1 ):
<a0 ,σ>→n0 <a1 ,σ>→n1
<a0 +a1 ,σ>→n
Esempio di Semantica di un linguaggio
imperativo(3)
• Le regole usano metavariabili a0 , n, X sui domini sintattici
• Posso instanziare queste regole usando particolari valori
espressioni o variabili
• Esempio di una moltiplicazione
<3,σ0 >→3 <2,σ0 >→2
<3∗2,σ0 >→6
• Le istanze delle regole si compongono in alberi di
derivazione: i) tutte le premesse di istanze di regole sono
conclusioni delle regole appena sopra, ii) le radici
dell'albero sono assiomi senza premesse
Esempio di Semantica di un linguaggio
imperativo(4)
• Esempio di albero:
<init,σ0 >→0 <4,σ0 >→4 <8,σ0 >→8 <6,σ0 >→6
<(init+4),σ0 >→4
<8+6,σ0 >→14
<(init+4)+(8+6),σ0 >→18
Esempio di Semantica di un linguaggio
imperativo(5)
• Altri esempi di semantica per la sequenza
<c0 ,σ>→σ 00 <c1 ,σ 00 >→σ 0
<c0 ;c1 ,σ>→σ 0
• Semantica ciclo while:
<b,σ>→false
<while b do c endwhile,σ>→σ
<b,σ>→true <c,σ>→σ 00 <while b do c endwhile,σ 00 >→σ 0
<while b do c endwhile,σ>→σ 0
Compilatore
• Sintassi espressa con grammatica ma semantica più
difficile da esprimere
• Un compilatore genericamente trasforma un linguaggio in
un altro. Se la trasformazione prevede come
linguaggio di target quello della macchina allora tenderà a
produrre un programma che potrà essere eseguito una
volta completo di tutte le sue parti
• Un compilatore lavora a fasi
• Front end: Analisi lessicale (produce token), sintattica
(analizza frasi di token) e semantica
• Back-end: Vedremo i dettagli più avanti nel modulo
Compiler compiler
• Compiler compiler come Yacc o Accent servono per
generare un processatore di linguaggi come un
compilatore, un interprete o un traduttore da una
descrizione di alto livello
• Si specifica la grammatica del linguaggio e il compiler
compiler crea un programma che processa l'input scritto
nel linguaggio
• Il programma generato analizza gerarchicamente l'input e
attacca una semantica ad ogni frase che riconosce data la
grammatica
• Spesso si usano varianti della BNF
• Un esempio il BNFC usa labelled BNF
Compiler compiler: associare la semantica
• Le azioni di associazione semantica avvengono dopo il
controllo sintattico del parser (rifiuta frasi non conformi
alla grammatica)
• Occorre associare le regole semantiche ai pattern sintattici
• Spesso queste regole vengono scritte direttamente nella
grammatica
• A volte è del codice C inserito in parentesi graffe che viene
ricopiato nel programma
Linguaggi di programmazione esoterici(1)
• Un linguaggio di programmazione esoterico è una
tipologia di linguaggi di programmazione particolarmente
complessi e volutamente meno chiari possibile
• Non hanno una vera utilità nel mondo reale, ma sono
generalmente concepiti per mettere alla prova i limiti della
programmazione su computer
• Alcuni, invece, sono concepiti come esercizio per
comprendere meglio il funzionamento di un calcolatore
• Wouter van Oortmerssen ha creato FALSE, un linguaggio
basato sul concetto di macchina a stack dotato di una
sintassi confusa, illeggibile ed estremamente concisa: il
compilatore occupa solamente 1024 byte
Linguaggi di programmazione esoterici(2)
• Questo ha in seguito ispirato Urban Muller a creare un
linguaggio ancora più conciso, il brainfuck, composto da
soli otto caratteri riconosciuti
• Hello word in brainfuck:
++++++++++[>+++++++>++++++++++>+++
>+<<<<-]>++.>+.+++++++.
.+++.>++.<<+++++++++++++++.>.+++.-----.--------.>+.>.
• Shakespeare la frase seguente indica un punto nel listato
che può essere raggiunto tramite un'istruzione simile a
GOTO:
Act I: Hamlet's insults and flattery.
• In RAPTOR è possibile generare un eseguibile o compilare
il programma
• Alla luce di quello che possiamo intuire ad oggi come farà
RAPTOR a generare un eseguibile o ad essere compilato?

Download Report