Compilatori, interpreti e catena di traduzione

Come il testo di un programma diventa codice eseguibile

Questa lezione conclusiva del corso mostra come tutti i concetti teorici e le strutture dati che abbiamo studiato — dalle Grammatiche Formali e gli Automi dell’Unità 1, alla Ricorsione e allo Scope dell’Unità 4, fino ad Alberi, Grafi e Tabelle di Hash dell’Unità 6 — convergano armoniosamente all’interno del programma più affascinante dell’informatica: il Compilatore.

Un processore (CPU) è in grado di eseguire esclusivamente istruzioni elementari codificate in binario nel proprio linguaggio macchina. Per eseguire un programma scritto in un linguaggio ad alto livello (, come C, Java o Python), il programma deve essere tradotto in istruzioni macchina oppure elaborato da un interprete eseguito dalla CPU.


Compilazione pura vs Interpretazione vs Approccio Ibrido (Bytecode + JIT)

Esistono tre modelli architetturali principali per tradurre ed eseguire un linguaggio di programmazione:

flowchart TD
    subgraph Compilato["1. Compilazione Pura (C, C++, Rust)"]
        S1["Codice Sorgente (.c)"] --> C1["<b>Compilatore + Linker</b><br/>(Traduzione offline anticipata)"]
        C1 --> EXE["Eseguibile Macchina Nativo (.exe / ELF)"]
        EXE --> CPU1["<b>Esecuzione diretta su CPU</b> + Input ➔ Output"]
    end
    subgraph Interpretato["2. Interpretazione Pura (Bash, Python classico)"]
        S2["Codice Sorgente (.py / .sh) + Input"] --> INT["<b>Interprete</b><br/>(Legge, analizza ed esegue riga per riga a runtime)"]
        INT --> OUT2["Output"]
    end
    subgraph Ibrido["3. Modello Ibrido Bytecode + VM/JIT (Java JVM, C# .NET)"]
        S3["Sorgente (.java)"] --> JAVAC["<b>Compilatore Front-End</b> (javac)"]
        JAVAC --> BC["<b>Bytecode</b> (.class)<br/>Indipendente dall'hardware"]
        BC --> JVM["<b>Macchina Virtuale (JVM) + Compilatore JIT</b>"]
        JVM --> OUT3["Output"]
    end
CaratteristicaCompilazione Pura (C, C++, Rust, Go)Interpretazione (Shell, Python standard)Modello Ibrido su VM / JIT (Java, C#)
Come funzionaTraduce prima dell’esecuzione l’intero sorgente in codice macchina nativo per una specifica architettura CPU + OS.Un programma (Interprete) legge il sorgente (o una sua rappresentazione interna) e lo esegue istantaneamente istruzione per istruzione.Compila il sorgente in un linguaggio intermedio astratto (Bytecode), eseguito poi da una Virtual Machine dotata di compilatore JIT (Just-In-Time) che traduce a caldo i tratti più usati in codice nativo.
Velocità di esecuzioneMassima (esecuzione diretta sull’hardware, ottimizzazioni globali spinte).Più lenta (overhead di analisi e decodifica a runtime).Molto alta (vicina al nativo dopo il “riscaldamento” del JIT).
Portabilità dell’eseguibileBassa: bisogna ricompilare il sorgente per ogni combinazione di CPU (x86_64, ARM) e Sistema Operativo.Altissima: lo stesso script gira ovunque sia installato l’interprete.Altissima (“Write Once, Run Anywhere”): lo stesso file .class gira su qualsiasi piattaforma dotata di JVM.
Scoperta degli erroriErrori sintattici e di tipo scoperti tutti prima dell’esecuzione (compile-time).Gli errori in un ramo if vengono scoperti solo se e quando quel ramo viene eseguito a runtime.Controllo statico completo dei tipi a compile-time + controlli di sicurezza a runtime nella VM.

Architettura interna di un Compilatore

Un compilatore moderno (come gcc o clang) non traduce il testo C in codice macchina in un solo colpo, ma è strutturato come una pipeline di fasi divisa in due grandi blocchi collegati a una Tabella dei Simboli (Symbol Table) centrale:

  • Front-End (dipendente dal linguaggio sorgente, indipendente dalla CPU target): Analisi Lessicale Analisi Sintattica Analisi Semantica Generazione del Codice Intermedio (IR).
  • Back-End (indipendente dal linguaggio sorgente, dipendente dall’architettura hardware target): Ottimizzazione del Codice Generazione del Codice Macchina/Assembly.
flowchart TD
    SRC["<b>Codice Sorgente</b><br/><code>int ris = a + b * 2;</code>"]
    LEX["<b>1. Analizzatore Lessicale (Lexer / Scanner)</b><br/><i>Usa Espressioni Regolari e Automi a Stati Finiti (DFA)</i>"]
    TOK["Sequenza di <b>Token</b><br/><code>[KW_INT] [ID:'ris'] [ASSIGN] [ID:'a'] [PLUS] [ID:'b'] [MUL] [NUM:2] [SEMI]</code>"]
    PAR["<b>2. Analizzatore Sintattico (Parser)</b><br/><i>Usa Grammatiche Libere dal Contesto (CFG)</i>"]
    AST["<b>Albero Sintattico Astratto (AST)</b>"]
    SEM["<b>3. Analizzatore Semantico</b><br/><i>Controllo dei tipi (Type Checking) e dello Scope</i>"]
    IR["<b>4. Generatore di Codice Intermedio (IR / Three-Address Code)</b>"]
    OPT["<b>5. Ottimizzatore del Codice</b><br/><i>Analisi sul Grafo di Flusso di Controllo (CFG)</i>"]
    GEN["<b>6. Generatore di Codice Target (Assembly / Macchina)</b><br/><i>Allocazione dei registri tramite Colorazione di Grafi</i>"]
    ST[("<b>Symbol Table</b><br/><i>Tabella di Hash</i><br/>(Nomi, Tipi, Scope,<br/>Offset di memoria)")]

    SRC --> LEX --> TOK --> PAR --> AST --> SEM --> IR --> OPT --> GEN
    LEX & PAR & SEM & IR & GEN <--> ST

Le Fasi di Compilazione nel dettaglio

Seguiamo passo passo come viene trasformata l’istruzione C:

totale = prezzo + tasse * 2;

Fase 1: Analisi Lessicale (Lexer / Scanner)

Lo Scanner legge il file sorgente come un flusso grezzo di caratteri, elimina gli spazi bianchi e i commenti, e raggruppa i caratteri in unità minime dotate di significato chiamate Lessemi (Lexemes), classificandole in Token della forma :

  1. <ID, "totale">
  2. <ASSIGN, "=">
  3. <ID, "prezzo">
  4. <PLUS, "+">
  5. <ID, "tasse">
  6. <MUL, "*">
  7. <INT_LIT, 2>
  8. <SEMICOLON, ";">
  • Strumento teorico: Le regole che definiscono gli identificatori ([a-zA-Z_][a-zA-Z0-9_]*), i numeri e gli operatori sono Linguaggi Regolari (Tipo 3 di Chomsky), specificati tramite Espressioni Regolari e riconosciuti in tempo lineare da Automi a Stati Finiti Deterministici (DFA)!
  • Errori lessicali: sequenze di caratteri che non appartengono a nessun token valido del linguaggio (es. un carattere illegale @ fuori da una stringa o una costante numerica malformata 123abc).

Fase 2: Analisi Sintattica (Parser)

Il Parser riceve la sequenza lineare di Token prodotta dal Lexer e verifica se essa rispetta le regole grammaticali del linguaggio, costruendo una struttura gerarchica ad albero chiamata Albero di Derivazione (Parse Tree) o, nella sua forma compatta priva di punteggiatura superflua, Albero Sintattico Astratto (AST — Abstract Syntax Tree).

flowchart TD
    ASS["<b>= (Assegnamento)</b>"]
    ID1["ID: <b>totale</b>"]
    PLUS["<b>+ (Somma)</b>"]
    ID2["ID: <b>prezzo</b>"]
    MUL["<b>* (Moltiplicazione)</b>"]
    ID3["ID: <b>tasse</b>"]
    NUM["INT_LIT: <b>2</b>"]

    ASS --> ID1
    ASS --> PLUS
    PLUS --> ID2
    PLUS --> MUL
    MUL --> ID3
    MUL --> NUM

Osserva come l’AST catturi automaticamente la precedenza degli operatori: il nodo * è figlio del nodo +, quindi in una visita Post-Order dell’AST verrà valutato prima tasse * 2 e poi la somma con prezzo!

  • Strumento teorico: La sintassi dei linguaggi di programmazione (con parentesi bilanciate e blocchi annidati { ... } a profondità arbitraria) non può essere descritta da automi a stati finiti, ma richiede Grammatiche Libere dal Contesto (CFG — Tipo 2 di Chomsky) e Automi a Pila. I parser si dividono in:
    • Parser Top-Down (es. / Discesa Ricorsiva): costruiscono l’albero dalla radice (simbolo iniziale ) scendendo verso le foglie (i token);
    • Parser Bottom-Up (es. / Shift-Reduce): partono dalle foglie (i token) e le riducono progressivamente fino alla radice .
  • Errori sintattici: sequenze di token valide lessicalmente ma disposte in modo grammaticalmente errato (es. int a = * + 5;, parentesi non chiusa o ; mancante).

Fase 3: Analisi Semantica e la Symbol Table

Un programma può essere lessicalmente e sintatticamente perfetto, ma privo di senso rispetto alle regole di tipo e di visibilità del linguaggio (es. in C: sommare una struct a un float, chiamare una funzione con 2 argomenti invece di 4, o usare una variabile mai dichiarata).

L’Analizzatore Semantico visita l’AST consultando la Tabella dei Simboli (Symbol Table) — implementata concretamente tramite Tabelle di Hash annidate per gestire lo Scope dei blocchi — ed effettua:

  1. Controllo dello Scope e delle dichiarazioni: verifica che ogni identificatore usato sia stato dichiarato nello scope corrente o in uno scope esterno visibile, e che non vi siano doppie dichiarazioni nello stesso blocco.
  2. Type Checking (Controllo dei Tipi) e conversioni implicite (coercions): se nell’esempio prezzo è double e tasse è int, l’analizzatore semantico inserisce nell’AST un nodo di conversione int_to_double(tasse * 2) prima di sommarlo a prezzo.

Fase 4, 5 e 6: Codice Intermedio (IR), Ottimizzazione e Codice Macchina

  1. Generazione del Codice Intermedio (IR — Three-Address Code):
    L’AST annotato viene linearizzato in una sequenza di istruzioni elementari con al più un operatore e variabili temporanee t1, t2:
    t1 = tasse * 2
    t2 = int_to_double(t1)
    t3 = prezzo + t2
    totale = t3
  2. Ottimizzazione del Codice:
    Trasforma il codice intermedio in una versione semanticamente equivalente ma più veloce o più compatta:
    • Constant Folding: calcola a compile-time espressioni costanti (x = 3 * 4; diventa direttamente x = 12;);
    • Dead Code Elimination: rimuove codice irraggiungibile (es. dopo un return) o variabili calcolate ma mai lette;
    • Strength Reduction: sostituisce operazioni costose con operazioni più veloci (es. tasse * 2 su interi diventa uno shift a sinistra di 1 bit: tasse << 1!).
  3. Generazione del Codice Target (Assembly):
    Assegna le variabili ai limitati registri fisici della CPU (risolvendo un problema di colorazione di un grafo di interferenza!) ed emette le istruzioni Assembly dell’architettura target.

La Catena Completa di Traduzione del C: Preprocessore, Compilatore, Assembler e Linker

Quando eseguiamo gcc main.c modulo.c -o programma, dietro le quinte vengono invocati in sequenza 4 programmi distinti:

flowchart LR
    C["<b>Sorgente C</b><br/><code>main.c</code>"]
    CPP["<b>1. Preprocessore (cpp)</b><br/>Espande <code>#include</code>,<br/><code>#define</code>, <code>#ifdef</code>"]
    I["<b>Sorgente Espanso</b><br/><code>main.i</code>"]
    CC["<b>2. Compilatore (cc1)</b><br/>Lexer, Parser, Semantica,<br/>Ottimizzazione, CodeGen"]
    S["<b>Codice Assembly</b><br/><code>main.s</code>"]
    AS["<b>3. Assembler (as)</b><br/>Traduce Assembly<br/>in binario rilocabile"]
    O["<b>File Oggetto</b><br/><code>main.o</code>"]
    LD["<b>4. Linker (ld)</b><br/>Unisce più <code>.o</code> e librerie,<br/>risolve i simboli <code>extern</code>"]
    LIB["Librerie (es. <code>libc</code>,<br/><code>modulo.o</code>)"]
    EXE["<b>Eseguibile Finale</b><br/><code>programma</code>"]

    C --> CPP --> I --> CC --> S --> AS --> O --> LD --> EXE
    LIB --> LD
  • Linking Statico vs Dinamico:
    • Nel Linking Statico, il Linker copia fisicamente il codice macchina delle funzioni di libreria usate (es. printf) dentro il file eseguibile finale (eseguibile più grande ma autonomo).
    • Nel Linking Dinamico (default nei sistemi moderni con librerie .so su Linux o .dll su Windows), il Linker inserisce nell’eseguibile solo un riferimento alla libreria condivisa di sistema, che verrà collegata in RAM al momento del caricamento da parte del Dynamic Loader del sistema operativo.

Il Quadro Unificante: tutte le strutture dati del corso dentro un Compilatore!

Fase / Componente del CompilatoreStruttura Dati o Modello del Corso utilizzato
Analisi Lessicale (Lexer)Espressioni Regolari e Automi a Stati Finiti (DFA) (Unità 1)
Analisi Sintattica (Parser)Grammatiche Libere dal Contesto (CFG) (Unità 1), Pila (Stack) e Ricorsione (Unità 4 e 6)
Rappresentazione del Programma (AST)Alberi N-ari e Alberi Binari con visite ricorsive Pre/Post-Order (Unità 6.2)
Tabella dei Simboli (Symbol Table)Tabelle di Hash (Unità 6.5) collegate in una Pila di Scope (Unità 4.4 e 6.2)
Ottimizzazione e Allocazione dei RegistriGrafi orientati (Control Flow Graph, Dependency DAG) e Grafi non orientati (Unità 6.4)

Leggere un diagnostico nella fase giusta

Usiamo l’espressione 2 * (3 + 4) per collegare le fasi. Il lexer separa i token. Il parser costruisce la struttura secondo la grammatica. Nell’AST, il prodotto ha come secondo operando la somma. La nota sui linguaggi formali mostra la stessa espressione nell’albero di derivazione e nell’AST. Le fasi successive possono controllare i tipi e rappresentare il calcolo in una forma intermedia. Un’ottimizzazione può sostituire il calcolo costante con 14 quando conserva la semantica.

In un progetto con più file, il frontend può accettare un prototipo dichiarato in un header. Il linker deve comunque trovare la definizione per i riferimenti esterni che il codice oggetto richiede. La panoramica del C mostra come isolare le fasi. Una tabella dei simboli può essere implementata tramite tabelle hash. La dispensa sulle strutture dinamiche è un riferimento per il funzionamento della struttura dati.


Esempi guidati

Esempio 1: Traccia completa dall’istruzione C al Codice Intermedio

Problema: Mostrare i Token, l’AST, i controlli semantici e il Three-Address Code per l’istruzione C:

while (i < 10) a = a + i;

assumendo int i; float a;.

  1. Analisi Lessicale (10 Token):
    [KW_WHILE], [LPAREN], [ID, "i"], [LT, "<"], [INT_LIT, 10], [RPAREN], [ID, "a"], [ASSIGN, "="], [ID, "a"], [PLUS, "+"], [ID, "i"], [SEMI].
  2. Analisi Sintattica (AST):
    Radice WHILE con due figli:
    • Figlio sinistro (Condizione): nodo < con figli ID("i") e INT_LIT(10).
    • Figlio destro (Corpo): nodo = con figlio sinistro ID("a") e figlio destro + (che ha figli ID("a") e ID("i")).
  3. Analisi Semantica:
    • Cerca "i" e "a" nella Symbol Table: entrambi dichiarati (i: int, a: float).
    • Nella condizione i < 10: entrambi gli operandi sono int tipo booleano/int valido.
    • Nella somma a + i: a è float, i è int inserisce una conversione implicita int_to_float(i).
  4. Codice Intermedio (con etichette di salto):
    L_inizio:
        t1 = i < 10
        if_false t1 goto L_fine
        t2 = int_to_float(i)
        t3 = a + t2
        a  = t3
        goto L_inizio
    L_fine:

Esempio 2: Classificare il tipo di errore (Lessicale, Sintattico, Semantico o di Linking)

Individuiamo la fase che può segnalare il problema. Se il codice è valido e produce un risultato sbagliato, lo confrontiamo con la specifica.

Frammento di codice C erratoFase che rileva l’erroreSpiegazione tecnica
int prezzo@ = 10;1. Analisi lessicaleIn quella posizione @ non forma un token valido del C standard.
if (x > 0 { x++; }2. Analizzatore Sintattico (Parser)Tutti i token sono validi, ma manca la parentesi tonda chiusa ) richiesta dalla produzione grammaticale dell’if.
int x = 5; x = "ciao" + 3.5;3. Analizzatore SemanticoLa sintassi id = expr + expr; è corretta, ma i tipi (const char * sommato a un double) sono incompatibili per il Type Checker!
extern void foo(void); int main(void) { foo(); } (senza definire foo in nessun .c)4. Linker (ld)main.c compila grazie al prototipo, ma il linker non trova la definizione di foo.
int perimetro = lato * lato; con lato intero e prodotto rappresentabileErrore di logicaCon lato = 3 otteniamo 9. La specifica del perimetro richiede 12. Un test con risultato atteso evidenzia la differenza.

Errori frequenti

Errori da evitare

  1. Confondere un errore Semantico a compile-time con un errore di Logica/Runtime:
    • Un errore semantico statico (es. assegnare una struct a un int o usare una variabile non dichiarata) viene bloccato dal compilatore prima dell’esecuzione.
    • Un errore a runtime (es. divisione per zero x / y con y letto da input uguale a 0, o dereferenziazione di NULL) si verifica invece durante l’esecuzione del programma già compilato.
  2. Pensare che un file .h venga compilato da solo:
    I file header .h non vengono passati direttamente al compilatore: è il Preprocessore che, incontrando #include "mioheader.h" dentro un file .c, copia testualmente il contenuto del file .h dentro il file .c prima che inizi l’analisi lessicale!
  3. Confondere errore del Compilatore ed errore del Linker (undefined reference):
    Se si dimentica di includere <math.h> (o si sbaglia la sintassi di una chiamata), l’errore è del compilatore. Se invece si include correttamente <math.h> ma su Linux si dimentica di passare il flag -lm a gcc, la compilazione in .o riesce e l’errore undefined reference to 'sqrt' viene emesso dal Linker!

Esercizi di prova

Esercizio 1. Scansione Lessicale e conteggio dei Token (Base)

Elenca esattamente tutti i Token individuati dall’Analizzatore Lessicale (Scanner) sulla seguente riga di codice C (ignorando spazi e commenti):

/* Calcolo indice */
vett[i + 1] = max_val * 20;

Quanti token vengono prodotti in totale?

Esercizio 2. Classificazione degli errori nella pipeline di traduzione (Base)

Per ciascun caso individua se il problema riguarda l’analisi lessicale, la sintassi, la semantica statica, il linking, il comportamento durante l’esecuzione o la correttezza rispetto alla specifica.

  1. int a = 10 / x; con x = 0 ricevuto in input;
  2. while (a == 5) else a++;
  3. int 99bottiglie = 10;
  4. void f(int a, int b); chiamata come f(10); (numero errato di argomenti);
  5. Scrivere int main(void) come int mian(void) (errore di battitura nel nome di main).
  6. Con lato = 5, usare int perimetro = lato * lato; per calcolare il perimetro del quadrato.

Esercizio 3. Costruzione dell’AST e valutazione di un’espressione (Intermedio)

Disegna (o descrivi i nodi padre/figli) l’Albero Sintattico Astratto (AST) per l’espressione aritmetica:

e scrivi la sequenza di istruzioni di Codice Intermedio a 3 indirizzi (Three-Address Code) prodotta da una visita Post-Order dell’AST.

Esercizio 4. Perché le Espressioni Regolari non bastano per il Parser? (Intermedio)

Spiega facendo riferimento alla Gerarchia di Chomsky (Automi a Stati Finiti vs Grammatiche Libere dal Contesto) perché l’Analizzatore Lessicale può usare un Automa a Stati Finiti (DFA), mentre l’Analizzatore Sintattico non può usare un DFA per verificare che le parentesi tonde (((a + b))) o i blocchi { { ... } } siano bilanciati.

Esercizio 5. Ottimizzazioni del Compilatore (Avanzato)

Dato il seguente frammento di codice C:

int calcola(int x) {
    int sec_in_giorno = 60 * 60 * 24;
    int y = x * 8;
    return y + sec_in_giorno;
    printf("Calcolo terminato!\n");
}

Individua le 3 ottimizzazioni che il Back-End del compilatore può applicare automaticamente a questo codice senza cambiarne la semantica osservabile.

Esercizio 6. Gestione dello Scope annidato nella Symbol Table (Avanzato)

Spiega come un compilatore C organizza la Symbol Table per gestire correttamente il Variable Shadowing quando entra ed esce da blocchi annidati { int x = 1; { double x = 2.5; } } in tempo medio per ogni ricerca di identificatore.


Provenienza del materiale

  • Dispense ufficiali del corso:
    • C1PROG1U6_Fine_Unita_Dispensa_Compilatori.pdf (Unità 6, Dispensa di fine unità — Compilatori e interpreti)
    • Marco Anisetti, Algoritmi e strutture dati dinamiche, C1PROG1_Appunti_di_fine_unità_6.pdf, cap. 5 (tabelle hash come struttura dati).
  • Dispensa del corso, C1PROG1B1L3_Semantica_grammatica_algoritmo.pdf (Lessico, sintassi, semantica e introduzione agli algoritmi).