 |
Mauro LEONCINI
Professore Ordinario
Dipartimento di Scienze Fisiche, Informatiche e Matematiche sede ex-Matematica
|
Insegnamento: Linguaggi e compilatori
Informatica (Offerta formativa 2022)
Obiettivi formativi
La progettazione ed implementazione di compilatori e interpreti è un settore della scienza e della tecnologia informatica che ha raggiunto presto un notevole grado di maturità. Ciò è stato possibile grazie anche a importanti e indipendenti studi teorici – alcuni dei quali condotti prima dell’inizio dell’era dei calcolatori –, fra cui vanno ricordati quelli nel campo della teoria dei linguaggi e degli automi nonché in teoria della computabilità e complessità. Al rapido sviluppo ha contribuito poi l’adozione di un modello di computer, pressoché universalmente condiviso, noto come (modello o architettura) di Von Neumann.
Compilatori e interpreti sono lo strumento mediante il quale si “implementano” i linguaggi di programmazione e dunque essi rappresentano la componente fondamentale nel processo di costruzione del software. La tecnologia dei compilatori si è aggiornata nel tempo allo scopo di rendere possibile l’implementazione di meccanismi di astrazione linguistica sempre più sofisticati e lontani dalla macchina (si pensi solo agli aspetti legati alla programmazione orientata agli oggetti). Anche sul versante delle architetture hardware la richiesta di soluzioni compilative avanzate è stata pressante. Nonostante il modello di Von Neumann rimanga un riferimento teorico importante, l’evoluzione dell’hardware è stata ed è tuttora fonte di continui stimoli a produrre compilatori in grado di sfruttare le enormi potenzialità dei sistemi moderni i quali, a loro volta, devono essere in grado di supportare applicazioni sempre più complesse ed esigenti in termini delle risorse spazio/tempo.
Per completare questa panoramica, possiamo rimarcare come la tecnologia dei compilatori abbia altre importanti applicazioni, fra le quali: (1) il progetto di nuove architetture, (2) lo sviluppo di strumenti per il testing e il debugging di software, e (3) lo sviluppo di strumenti per la traduzione automatica.
In questo corso lo studente svilupperà un’approfondita conoscenza della struttura e del funzionamento di un compilatore moderno, nonché delle principali tecniche e degli algoritmi utilizzati nel processo di compilazione. Su un piano squisitamente culturale, anche alla luce dell’ampia premessa, egli/ella sarà condotto ad una comprensione consapevole di alcuni fra i principali fondamenti scientifici alla base della propria disciplina. Sul piano operativo, sarà in grado di utilizzare strumenti automatici di ausilio alla costruzioni di compilatori e di progettare un compilatore completo per un linguaggio semplificato ma con molte caratteristiche che si ritrovano in linguaggi reali. Come ulteriore ricaduta, lo studente avrà più chiara percezione dell’influenza di certe soluzioni programmative sulle prestazioni del programma finale.
Da un punto di vista organizzativo, il corso è suddiviso in due parti, ciascuna di 6 CFU, che si terranno nei due semestri. La suddivisione è necessaria, in primis, per evitare un’eccessiva compressione del periodo di apprendinmento. Tuttiavia essa consegue in modo naturale anche in consideraizone dell’organizzazione dei compilatori in (macro) fasi. La prima fase, costituita dal cosiddetto front-end, sarà oggetto di studio durante il primo semestre. Tale fase, detta anche di analisi, è esclusivamente orientata al linguaggio e produce una rappresentanzione intermedia (IR) che è indipendente dal questo come pure dall’architettura hardware su cui verrà eseguito il codice oggetto. Nel secondo semestre verranno invece affrontate le due fasi di ottimizzazione dell’IR, ancora indipendente dall’architettura (il cosiddetto middle-end), e di sintesi del codice macchina finale (back-end). In conclusione, la modularizzazione del corso segue criteri sia logici sia temporali e di impegno che ci paiono pienamente giustificati.
Prerequisiti
Per il pieno raggiungimento degli obiettivi formativi è fondamentale che lo studente abbia conoscenze ad ampio spettro delle caratteristiche dei linguaggi di programmazione e abbia, in particolare, padronanza della programmazione in C e C++, oltre ad una conoscenza dell’architettura di un computer moderno. Utile è anche una certa maturità algoritmica. Tali requisiti risultano pienamente soddisfatti dagli studenti del CdS che abbiano superato gli esami di Programmazione I e II, Architettura dei calcolarori e Algoritmi e Strutture Dati.
Programma del corso
1. Front end. 48h
a) Compilatori ed interpreti. Struttura di un compilatore, front-, middle- e back-end. Fasi della compilazione. Applicazioni della tecnologia dei compilatori. Richiami su alcuni aspetti dei linguaggi di programmazione. 3h
b) Analisi lessicale. Il lexer. Tokenizzazione dell’input. Symbol table. Linguaggi ed espressioni regolari. Definizione e riconoscimento di token. Automi finiti. Dalle espressioni regolari agli automi. Simulazione e “compilazione” del non determinismo. Strumenti per generare un lexer. LEX con esempi. 10h
c) Analisi sintattica. Il parser. Grammatiche regolari e context-free, derivazioni, parse tree, ambiguità. Progetto di grammatiche. Aspetti demandati all’analisi semantica. Parsing top-down: a discesa ricorsiva e predittivo. Parsing bottom-up. Riduzioni, parsing shft-reduce. Parsing LR. Tabelle SLR e LALR. Gestione dei conflitti. Symbol table e analisi semantica. Strumenti per la generazione automatica di parser. YACC con esempi. 14h
d) Traduzione guidata dalla sintassi. Definizioni guidate dalla sintassi. Attributi e regole. Ordine di valutazione degli attributi. Attributi sintetizzati e attributi ereditati. Applicazioni alla costruzione di Abstract-Syntax Tree (AST). Schemi di traduzione. 7h
e) Interpretazione. Modelli di esecuzione AST (caso del Perl) e bytecode/virtual machne (es. Java). Compilazione Just-In-Time. 4h
f) Generazione di codice intermedio. Codice a tre indirizzi. Variabili Static Single-Assignment (SSA). Rappresentazione intermedia (IR) nel modello LLVM. Cenni su trattamento dei tipi. Espressioni e controllo di flusso. Backpatching. 10h
2. Middle-end e ruolo dell’ottimizzazione. 32h
a) Introduzione. Rappresentazione dei programmi, richiami sulle IR. Sintassi concreta e astratta (AST). Istruzioni (3AC). Rappresentazioni di più alto livello. Control flow graph (CFG): basic block e terminator, successori e predecessori. Costruzione di un CFG di basic block. 3h
b) Analisi e ottimizzazione del codice. Analisi locale, globale e interprocedurale. Esempio di ottimizzazione: dead code elimination (DCE). Identificare le istruzioni “dead” e “killed”. I limiti dell’ottimizzazione locale. 3h
c) Data Flow Analysis. Le reaching definition come esempio di proprietà globale che richiede di ragionare sull’intero CFG. Dominance e liveness analysis. 4h
d) Ottimizzazione dei loop. Forma SSA e ottimizzazione. Esempi notevoli di ottimizzazioni. Loop-Invariant Code Motion (LICM). Induction Variable Elimination. Loop Fission & Fusion. 10h
e) Ottimizzazione interprocedurale. Call graph Inlining e outlining. Link-time optimization. 6h
f) Cenni di ottimizzazione per architetture parallele. Ruolo della gerarchia di memoria. Instruction-level parallelism e thread-level parallelism. Vettorizzazione. 6h
3. Backend. 16h
a) Machine description. Istruzioni, registri, calling convention. 3h
b) Instruction Selection. Da IR machine-agnostic ad equivalente funzionale dell’Instruction Set Archtecture target. 3h
c) Instruction Scheduling. Ordine di esecuzione delle istruzioni per massimizzare la performance. 3h
d) Register Allocation. Dai registri virtuali a quelli fisici. Register spilling. 3h
e) Altre ottimizzazioni machine-specific. 4h
Sono incluse le ore in laboratorio informatico. Nel primo semestre verrà sviluppato il front-end per un sottoinsieme del linguaggio Kaleidoscope con produzione di IR LLVM. Nel secondo semestre verranno sviluppati passi di ottimizzazione della IR LLVM generata dal front-end Kaleidoscope e svolte esercitazioni sullo sviluppo di un back-end LLVM minimale per archtettura RISC.
Metodi didattici
Lezioni frontali per la parte teorica ed esercitazioni in laboratorio informatico.
Testi di riferimento
- Per la prima parte verrà utilizzato il classico testo Compilers: principles, techniques, & tools di A.V. Aho, M.S. Lam. R. Sethi e J.D. Ullman, Pearson/Addison Wesley. Il testo esiste anche nella versione italiana (Pearson, Milano), anche se si consiglia caldamente di utilizzare l’edizione in inglese. Il libro è l’ultima versione del cosiddetto Dragonbook, di Aho e Ullman, testo che è stato per anni un riferimento imprescindibile nella teoria dei linguaggi di programmazione e della compilazione.
- Per la seconda parte il riferimento sarà il seguente testo: K. Cooper, L. Torczon, "Engineering a Compiler" 3rd edition, Elsevier
https://www.elsevier.com/books/engineering-a-compiler/cooper/978-0-12-815412-0
- Per le esercitazioni su LLVM è possibile utilizzare abbondante materiale disponibile in rete (e segnatamente, come è naturale, sul sito http://llvm.org). In particolare, per lo sviluppo del front-end per Kaleidoscope si può (in parte) fare riferimento al tutorial My First Language Frontend with LLVM http://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html.
Verifica dell'apprendimento
Un progetto, che verrà suddiviso in diversi assegnamenti intermedi, e un orale sugli argomenti affrontati nelle due parti in cui è organizzato il corso.
Risultati attesi
- Conoscenza e capacità di comprensione. Al termine del corso lo studente avrà solide conoscenze sulle basi teoriche e la tecnologia alla base della realizzazione di compilatori e interpreti. Conoscerà altresì i formalismi descrittivi (in particolare, espressioni regolari e grammatiche) e gli algoritmi alla base degli strumenti di ausilio alla generazione automatica di (componenti significative di) un compilatore. Le conoscenze sulla generazione del codice lo metteranno in grado di valutare e scegliere, nella scrittura di un programma, costruzioni linguistiche più efficienti.
- Capacità di applicare conoscenza e comprensione. Lezioni ed esercitazioni al computer metteranno lo studente in grado di sviluppare un compilatore (o un interprete) completo per linguaggi non troppo complessi (es. linguaggi embedded), ovvero traduttori da e per linguaggi ad alto livello, ovvero ancora di partecipare in team allo sviluppo di compilatori per linguaggi di complessità paragonabile a quella dei più comuni linguaggi programmativi oggi utilizzati.
- Autonomia di giudizio. I docenti incoraggiano un stile partecipativo di lezioni ed esercitazioni. In questo contesto e, ancora di più, durante la discussione degli elaborati (in sede d’esame), lo studente sarà chiamato a descrivere le soluzioni che utilizzerebbe, o che ha utilizzato, in relazione ad altre possibili alternative, presentando gli argomenti a favore delle scelte indicate.
- Abilità comunicative. Le modalità di esame, in special modo la discussione degli elaborati, costituiscono importanti momenti in cui lo studente, sotto la guida del docente, potrà esercitare e sviluppare la capacità di presentare il risultato del proprio lavoro.
- Capacità di apprendimento. I docenti incoraggiano anche gli approfondimenti, che lo studente sarà chiamato ad effettuare, nello svolgimento degli assegnamenti intermedi. Questa attività, in particolare, consentirà allo studente di progredire nel processo di acquisizione degli strumenti metodologici indispensabili per poter provvedere al proprio aggiornamento continuo; attività, quest’ultima, che risulta particolarmente importante in un settore, quello delle tecnologie informatiche, in rapidissima e continua evoluzione.