:: Traduttori - Lezione del 3 marzo 2009 ::
Cos'è un Linguaggio di Programmazione?
Un Linguaggio di Programmazione, d'ora in poi abbreviato con LDP, non è facilmente definibile così, a ufo. Una definizione un po' più formale è questa:
Un LDP è una definizione di come devono essere scritte le istruzioni
per fare eseguire delle funzioni all'elaboratore.
Oppure:
Un LDP è uno strumento per fare eseguire all'elaboratore funzioni
ad 1 livello più elevato rispetto all'hw sottostante.
Perché c'è la necessità di un livello intermedio tra programmatore e elaboratore? L'elaboratore ragiona in termini di 0 e 1 e, quando va bene, di linguaggio macchina (chi avesse nostalgia di queste cose vada a vedere il MIXAL). Dagli esiti dell'esame di Programmazione degli Elaboratori si può comprendere come scrivere in linguaggio macchina non solo sia difficile, ma porta anche a commettere un sacco di errori. Un linguaggio a più alto livello permette di specificare bene il problema senza diventare matti.
Per essere ancora più formali, possiamo dire che un LDP è un
insieme di regole che definiscono un insieme di stringhe legali,
dando ad ognuna di esse un preciso significato.
Questo insieme di stringhe è detto programma: un LDP definisce quindi che cosa è un programma valido, e che cosa invece no.
Notiamo subito che in questa definizione non c'entra niente l'hardware sottostante: un LDP di per sé prescinde dall'hw.
Ma non sarà del tutto indipendente da esso: alcune fasi di traduzione da LDP a linguaggio macchina saranno diverse a seconda dell'architettura dell'HW. Pensiamo ad esempio alla rappresentazioni dei valori: alcuni processori partono dal bit più significativo, altri da quello meno significativo. Alcuni processori permettono un certo valore massimo agli interi, altri processori un altro etc.
Compare subito un problema: le combinazioni di stringhe possibili sono potenzialmente infinite. Come fa un programma finito a stabilire se una qualsiasi tra queste combinazioni infinite è accettabile?
Due approcci
Quest'ultima domanda apre la strada ad una nuova visione del problema. Ci sono due approcci, che si sono mixati finora: l'approccio generativo e l'approccio riconoscitivo.
L'approccio generativo mi dice come costruire istruzioni valide. Lo si può intendere come il manuale di un linguaggio di programmazione, che mi dice come scrivere espressioni e così via.
L'approccio riconoscitivo invece sta dall'altra parte della barricata: dato un insieme di stringhe, mi deve dire se sono valide o meno.
Le grammatiche formali, che vedremo nelle prossime lezioni, permettono un approccio a questi approcci.
I traduttori
L'interprete
Fermo restando che un programma è un input, che deve produrre un output nel mio elaboratore, e che quindi tra input e output ci sta la macchina, l'interprete si pone come layer intermedio tra l'input, l'output e la macchina.
In pratica, un interprete prende le frasi del linguaggio di programmazione, una alla volta, le traduce e le dà in pasto all'elaboratore per produrre l'output.
Il compilatore
Il compilatore invece non prende le frasi una alla volta: prende tutto il programma, e attraverso una sequenza di fasi più complesse porta al codice eseguibile.
In particolare, deve tradurre il tutto in linguaggio macchina, collegare questa rappresentazione di linguaggio macchina alle librerie utilizzate, e generare l'eseguibile. Qualche passaggio in più.
Front-End e Back-End
Interprete e Traduttore si comportano in modo diverso, ma la prima parte è uguale per tutti e due: devono riconoscere una stringa valida. Ecco quello che deve fare un traduttore:
- occorre una definizione di un LDP (una sequenza di simboli appartenenti ad un alfabeto)
- occorre una grammatica per vedere se le combinazioni di simboli sono legittime
- occorre stabilire se queste combinazioni hanno senso o no
- occorre vedere se ci sono errori semantici e poterli notificare all'utente
Tutte queste cose assumeranno maggiore chiarezza in futuro, ma quello che già ora possiamo dire è che un traduttore traduce da un codice sorgente scritto in un certo LDP in un codice macchina semanticamente equivalente. Semanticamente equivalente vuol dire che fa quello che gli ho detto di fare:)
Possiamo quindi dividere un traduttore in due parti: un frontend ed un backend.
Frontend: deve fare analisi lessicale, sintattica e semantica.
Backend: genera il codice macchina.
Il frontend è la parte "uguale" per tutti i traduttori, mentre il backend è la parte che dipende dalla macchina su cui eseguire il codice.
Analisi lessicale
L'analisi lessicale è eseguita dallo scanner. Questo prende il programma, lo scandisce carattere per carattere, e raggruppa i caratteri in parole, numeri e simboli.
Gli elementi lessicali sono detti lessemi, e sono i raggruppamenti di simboli riconosciuti.
La categoria cui appartiene un dato lessema è detta invece token.
Per fare un esempio, prendiamo la stringa
a = b + c;
Gli elementi lessicali saranno i seguenti: a, =, b, +, c, ;.
Poi, a ciascun lessema verrà associato un token, cioè una categoria:
- a, b e c sono identificatori
- = e + sono operatori
- ; è un segno di punteggiatura
Ogni linguaggio in genera avrà delle regole a questo livello. Ad esempio, gli identificatori non possono essere più lunghi di 30 caratteri, non possono cominciare per un numero e così via.
Analizzatore sintattico
L'analizzatore sintattico mi dice se la struttura del programma sia ammissibile nel mio LDP.
Ad esempio, una stringa come a b c = +; può essere digerita dallo scanner, il quale troverà tranquillamente tre identificatori, due operatori e un segno di punteggiatura.
Ma, se stiamo scrivendo in C, questa roba non ha senso, e sarà l'analizzatore sintattico a scoprirlo.
Quello che produce è l' albero sintattico, anche detto parse tree. In quest'albero, le foglie sono i lessemi, mentre i nodi intermedi sono i token, ovvero le categorie qui il lessema appartiene.
Questo parse tree mi permette anche di stabilire proprietà strane come la precedenza e l'associatività degli operatori. Appena ho un disegno lo posto, così si capisce bene questa faccenda.
Analizzatore semantico
Una volta stabilita la mia struttura sintattica, devo capire che significato ha. La tabella dei simboli, generata precedentemente, viene arricchita con nuove informazioni, e si produce del codice intermedio (già passibile di eventuale ottimizzazione).
Ad esempio, prendiamo la riga C:
int a, b, v, x, y;
L'analizzatore sintattico dice che è tutto OK. Quello semantico invece fa un ulteriore controllo: deve vedere se è lecito, in quel punto del programma, definire dei nuovi interi con quei nomi (se sono già stati definiti nello stesso scope, non si può fare).
Nella stringa
x = y + a * b * 2;
invece controllerà se i tipi degli identificatori sono compatibili tra di loro e con gli operatori segnati.
Ecco come compare una tabella dei simboli, cui si fa appello per vedere chi è cosa:
| nome
| tipo
| offset
|
| a
| int
| 0
|
| b
| int
| 4
|
| v
| int
| 8
|
| x
| int
| 12
|
| y
| int
| 16
|
La colonna offset mi dice l'indirizzo dell'identificatore a partire dal primo blocco di memoria allocata.
Ed ecco invece che aspetto può avere il codice intermedio. Prendiamo queste due righe:
x = y + a * b * 2;
v = x;
Il codice intermedio sarà così:
t1 = a * b
t2 = t1 * 2
t3 = y * t2
x = t3
v = x
Rispetta la precedenza tra operatori, e questo dipende dalla bontà con cui è stato costruito il parse tree.
Per dare un'idea delle ottimizzazioni già possibili a questo livello, l'analizzatore semantico potrebbe vedere che la variabile x non viene più usata, dopo quella riga. Pertanto, il codice intermedio salterebbe l'associazione x = t3, e metterebbe invece v = t3.
Torna alla pagina di Traduttori
