Struttura di un compilatore

Visto ad alto livello, un compilatore è un programma che prende in input il codice sorgente di un pogramma e, se questo ha la forma corretta rispetto alle regole del linguaggio, produce in output del codice oggetto eseguibile su una certa macchina (che può anche essere una macchina vrtuale, come ad esempio nel caso di Java).

All’interno di un compilatore si possono identificare due principali componenti:

• il reader, che legge i sorgenti del programma, riconosce al loro interno le strutture del linguaggio, e costruisce una rappresentazione interna (IR, Intermediate Representation) di tali strutture, verificando nel frattempo la correttezza dell’input
• il generatore o traduttore, che a partire dalla IR genera il codice oggetto.

Reader

Si supponga di voler compilare il seguente frammento di codice sorgente in linguaggio C:

double f(int x, int y, double z) {
	double w;
	w = (x + y) * z;
	return w;
}

Gli elementi significativi “più piccoli”, indivisibili, della struttura che il reader deve riconoscere in questo codice, ovvero i simboli del linguaggio, sono i token o lessemi: le parole chiave (double, return, …), gli identificatori (f, x, y, …), gli operatori (=, +, …), i separatori (,, ;, …), ecc. Tuttavia, il codice sorgente viene fornito in input sotto forma di un file di testo, cioè una sequenza di singoli caratteri (d, o, u, b, l, e, spazio, f, …): i simboli della stringa in input non corrispondono ai simboli del linguaggio, sono unità più piccole. Allora, il primo passo per il riconoscimento della struttura è raggruppare i caratteri in token. Poi, i token vengono a loro volta raggruppati in frasi secondo le regole sintattiche del linguaggio, espresse da una grammatica libera dal contesto avente i token come terminali. Infine, queste frasi vengono organizzate nella rappresentazione interna, che in sostanza è l’albero sintattico corrisponde alle frasi identificate, semplificato rimuvendo informazioni ridondanti e arricchito invece con informazioni aggiuntive utili per il generatore. Nel contesto della teoria dei compilatori, gli alberi sintattici sono chiamati alberi di parsing.

Ad esempio, la struttura riconosciuta dal reader per la riga di codice w = (x + y) * z; del frammento mostrato prima potrebbe essere la seguente (qui mostrata in forma semplificata):

Lexer e parser

Le due fasi di “raggruppamento” necessarie per il passaggio dai caratteri all’IR vengono gestite da due diversi componenti del reader:

1. il lexer riceve in input uno stream (flusso) di caratteri, li raggruppa in token, e produce come output uno stream di token
2. il parser riceve in input lo stream di token emesso dal lexer, organizza i token in frasi, e produce in output la rappresentazione interna.

Siccome i token di un tipico linguaggio di programmazione costituiscono un linguaggio regolare, l’implementazione di un lexer si basa solitamente su un DFA (con qualche piccola aggiunta per eseguire l’output dei token riconosciuti). In particolare, esistono degli strumenti che, data una definizione dei token sotto forma di espressioni regolari, generano automaticamente il DFA che li riconosce. Inoltre, questo è uno dei casi “fortunati” in cui la dimensione del DFA rimane sempre proporzionale a quella dell’NFA, ovvero a quella dell’espressione regolare di partenza, senza crescere in modo esponenziale.

Analogamente, siccome le frasi di un tipico linguaggio sono descritte da una CFG, i parser sono implementati mediante vari tipi di riconoscitori per i linguaggi context-free (adattati in modo da costruire l’IR per le frasi riconosciute), che possono essere generati automaticamente, tramite appositi strumenti, a partire da CFG scritte in sintassi BNF o simile. Uno di questi riconoscitori sono gli automi a pila (deterministici), che, come visto in precedenza, corrispondono alle derivazione leftmost su una grammatica, dunque operano in modo top-down (applicano le produzioni partendo dal simbolo iniziale e procedendo verso i terminali). L’approccio basato su di essi (che verrà illustrato a breve) è molto usato al momento, in quanto semplice e intuitivo, ma in passato si preferiva un metodo bottom-up, corrispondente all’inferenza ricorsiva, perchè esso richiede meno memoria. Entrambi questi algoritmi hanno però delle limitazioni sulle grammatiche che sono in grado di gestire.

Symbol table e analizzatore semantico

Le frasi di un linguaggio di programmazione sono soggette non solo alle regole sintattiche, ma anche alle regole di semantica statica, che non vengono espresse tramite una CFG, perchè farlo è in molti casi impossibile, e se anche fosse possibile complicherebbe troppo la grammatica. Due esempi tipici di regole che non possono essere espresse tramite una CFG, ma che devono essere rispettate dalle frasi di un linguaggio staticamente tipizzato, sono le seguenti:

• le variabili devono essere dichiarate prima di essere utilizzate