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. 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. Derivazioni e alberi sintattici. Grammatiche ambigue. Ricorsione sinistra, diretta e indiretta. Eliminazione della ricorsione sinistra. Fattorizzazione sinistra. Relazione tra grammatiche ed espressioni regolari. 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

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. 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 ed ambienti basati su una pila.