Portale di Ateneo - Unibs.it Portale di Ateneo - Unibs.it

Introduzione alle tecniche dei compilatori

Cenni storici. Architettura e contesto di un compilatore. Analisi del programma sorgente: analisi lessicale, analisi sintattica, analisi semantica. Alberi sintattici concreti e astratti. Fasi di un compilatore. Gestione della tabella dei simboli. Trasformazione della rappresentazione interna del programma sorgente. Bootstrapping e porting di un compilatore.

Analisi lessicale

Architettura e ruolo di un analizzatore lessicale. Simboli, stringhe lessicali e pattern. Parole chiave e parole riservate. Attributi lessicali. Gestione degli errori lessicali. Metodi di specifica dei simboli. Alfabeto, stringa e linguaggio. Espressioni e insiemi regolari. Estensione delle espressioni regolari. Specifica dei token dei linguaggi di programmazione mediante espressioni regolari. Ambiguità e delimitatori. Automi finiti deterministici e nondeterministici. Trasformazione di espressioni regolari in automi nondeterministici. Trasformazione di automi nondeterministici in automi deterministici. Lex, un generatore automatico di analizzatori lessicali.

Metodi sintattici

Architettura e ruolo di un analizzatore sintattico. Notazione BNF. Derivazioni. Corrispondenza tra alberi sintattici e derivazioni. Grammatiche ambigue. Ricorsione sinistra, diretta e indiretta. Eliminazione della ricorsione sinistra. Fattorizzazione sinistra. Relazione tra grammatiche ed espressioni regolari. Notazione BNF estesa. Tabella degli operatori e grammatica delle espressioni.

Analisi sintattica top-down

Classificazione. Analisi sintattica a discesa ricorsiva. Analisi sintattica LL(1). Insiemi guida. Costruzione della tabella di parsing. Generazione top-down dell'albero sintattico astratto.

Analisi sintattica bottom-up

Classificazione. Analisi sintattica LR(0). Analisi sintattica SLR(1). Regole di risoluzione dell'ambiguità per conflitti di parsing. Analisi sintattica LR(1). Analisi sintattica LALR(1). Yacc, un generatore automatico di analizzatori sintattici. Generazione bottom-up dell'albero sintattico astratto.

Analisi semantica

Correlazione tra lessico, sintassi e semantica. Architettura e ruolo di un analizzatore semantico. Formalismi per la specifica della semantica statica. Grammatiche ad attributi. Semantica guidata da sintassi. Algoritmi per la computazione degli attributi semantici. Grafi di dipendenza ed ordine di valutazione. Grammatiche ad attributi, circolari e non circolri. Attributi ereditati e sintetizzati. Attributi misti. Tecniche di memorizzazione degli attributi. Type checking: equivalenza strutturale e basata sui nomi.

Generazione di codice intermedio

Rappresentazione intermedia. Codice a quadruple e P-code. Codice intermedio come attributo sintetizzato. Generazione pratica di codice. Cenni di generazione di codice target da codice intermedio: simulazione statica e macro-espansione. Generazione di codice per: referenze, strutture, dati, manipolazione di array, record, puntatori, strutture di controllo, espressioni logiche ed espressioni valutate in corto circuito, sottoprogrammi.

Ambienti runtime

Organizzazione della memoria. Record di attivazione. Sequenza della chiamata. Ambienti pienamente statici. Ambienti basati su una pila: senza procedure locali, con procedure locali, con parametri di tipo procedura.