Fasi combustione

Un compilatore è un programma per computer che traduce un programma scritto in un linguaggio di programmazione ad un altro linguaggio di programmazione, di produzione di un programma equivalente che la macchina sarà in grado di interpretare. Solitamente seconda lingua è linguaggio macchina , ma può essere solo testo. Questo processo di traduzione si chiama compilazione . ¹

Un compilatore è un programma in grado di tradurre il codice sorgente di un programma in linguaggio di alto livello ad un altro livello di linguaggio più basso (di solito in linguaggio macchina ). In questo modo uno sviluppatore può progettare un programma in un linguaggio molto più vicino a come si pensa che un essere umano, e quindi compilare ad un più gestibile da un computer.

Processo di generazione

E 'il processo attraverso il quale traduce le istruzioni scritte in un particolare linguaggio di programmazione in linguaggio macchina. Oltre a un traduttore, potrebbe essere necessario altri programmi per creare un eseguibile oggetto del programma. Un programma sorgente può essere suddiviso in moduli memorizzati in file separati. Il compito di assemblare il programma di origine spesso affidata ad un programma separato chiamato il preprocessore . Il preprocessore può anche espandere le abbreviazioni, le chiamate macro, la lingua di dichiarazioni di origine.

Di solito la creazione di un programma eseguibile (un típico.Exe per Microsoft Windows o DOS ) prevede due passaggi. Il primo passo è chiamato compilation (sé stesso) e la fonte traduce il codice scritto in unlinguaggio di programmazione in un file memorizzato in codice di livello basso (di solito in codice oggetto, e non direttamente al linguaggio macchina). Il secondo passo è chiamato vincolato in cui i collegamenti a livello di codice a basso generato per tutti i file e le subroutine che sono stati ordinati per compilare e aggiungere il codice funzione è nelle librerie del compilatore per il file eseguibile di comunicare direttamente sistema operativo, e infine tradurre il codice oggetto di codice macchina e la generazione di un modulo eseguibile.

Questi due passi si può fare separatamente, memorizzare il risultato della fase di compilazione dei file oggetto (o uno típico.Obj per Microsoft Windows, DOS, Unix ) per metterli in seguito, o creare direttamente eseguibile, così la fase di compilazione è memorizzato solo temporaneamente. Un programma potrebbe avere parti scritte in diverse lingue (ad esempio, C , C + + e Asm ), che potrebbe essere compilate separatamente e poi collegare insieme per formare un unico modulo eseguibile .

[ modifica ] Fasi del processo

Il processo di traduzione consiste interno di stadi più o fasi, che svolgono diverse operazioni logiche. E 'utile pensare a queste fasi come parti separate all'interno del traduttore, e può effettivamente essere scritto come operazioni codificate separatamente, ma in pratica spesso sono integrati insieme.

[ modifica ] Analisi di fase

[ modifica ] Analisi Lessicale

Articolo principale:Lexer

L'analisi lessicale è il primo passo, ecco il programma sorgente viene letto da sinistra a destra e raggruppati in componenti lessicali ( token ), che sono sequenze di caratteri che hanno un significato. Inoltre, tutti gli spazi, righe vuote, commenti e altre informazioni non necessarie viene rimosso dal programma di origine. Si verifica inoltre che i simboli del linguaggio ( parole chiave , operatori ,...) siano state digitate correttamente.

Poiché i compiti svolti dal analizzatore lessicale è un caso particolare di pattern matching sono richieste specifiche e metodi di riconoscimento di pattern, e questi metodi sono soprattutto le espressioni regolari e automi finiti . Tuttavia, un analizzatore lessicale è anche il traduttore che gestisce l'input il codice sorgente, e dal momento che questo post spesso implica un dispendio notevole di tempo, l'analizzatore lessicale deve funzionare nel modo più efficiente possibile.

[ modifica ] Analisi

Articolo principale: Parser

In questa fase i personaggi o componenti lessicali sono raggruppati gerarchicamente in frasi grammaticali che il compilatore usato per sintetizzare l'output. Controllare sé i proventi della fase precedente è sintatticamente corretto (a causa della grammatica del linguaggio). In generale, le frasi grammaticali del programma sorgente sono rappresentate da un albero sintattico.

La struttura gerarchica di una regola è generalmente espressa utilizzando ricorsive . Ad esempio, è possibile dare le seguenti regole, come parte della definizione di espressioni:

• Qualsiasi identificatore è un'espressione.
• Ogni numero è una espressione.
• Sé l'espressione ₁ e ₂ sono espressione espressioni, allora lo sono anche:
  • espressione ₁+ espressione ₂
  • espressione ₁ espressione ₂ *
  • (Espressione ₁₎

Regole 1 e 2 sono le regole di base (non ricorsiva), mentre la regola 3 definisce le espressioni in termini di operatori applicati alle altre espressioni.

La divisione tra analisi lessicale e analisi è in qualche modo arbitrario. Un fattore di divisione per determinare sé è una lingua di partenza costrutto è intrinsecamente ricorsivo o meno. Costruzioni lessicali non richiedono la ricorsione, mentre spesso richiedono strutture sintattiche. Ricorsività non è tenuto a riconoscere gli identificatori, che di solito sono stringhe di lettere e cifre, a partire da una lettera. Di solito, gli identificatori sono riconosciuti dalla semplice considerazione del flusso di input, sperando di trovare un personaggio che non è né la lettera o cifra, e dopo aver raccolto tutte le lettere e le cifre trovato fino a quel momento in un componente lessicale chiamato ID . Inoltre, questo tipo di analisi non è abbastanza potente per analizzare le espressioni o proposizioni. Per esempio, non possiamo abbinare correttamente le parentesi di espressioni o parole in frasi iniziano e terminano senza imporre un qualche tipo di nidificazione gerarchica o all'ingresso.

[ modifica ] Analisi semantica

La fase di analisi semantica controlla il programma di origine per cercare di trovare gli errori di semantica e raccoglie le informazioni sulle tariffe per la successiva fase di generazione del codice. Esso utilizza la struttura gerarchica determinata dalla fase di analisi sintattica di identificare gli operatori e gli operandi di espressioni e proposizioni.

Una componente importante di analisi semantica è il controllo dei tipi. Qui, il compilatore controlla sé ogni operatore ha operandi consentito dalla specifica della lingua di origine. Ad esempio, le definizioni di molti linguaggi di programmazione richiede il compilatore per indicare un errore ogni volta che si utilizza un numero reale come indice di una matrice . Tuttavia, il linguaggio di specifica possono imporre restrizioni alla operandi, per esempio, quando un operatore aritmetico binario viene applicato a un intero e un numero reale. Verificare che le modalità sono state definite le dimensioni corrette.

[ modifica ] sintesi in fase

È quello di generare codice oggetto equivalente al programma di origine. Il codice oggetto è generato solo quando il programma è privo di fonte di errore di analisi, che non significa che il programma viene eseguito correttamente, dal momento che un programma può avere idee sbagliate o le espressioni sbagliato i calcoli. Di solito il codice oggetto è il codice macchina rilocabile o codice assembly. Le posizioni di memoria sono selezionati per ciascuna delle variabili utilizzate dal programma. Poi ciascuno dei istruzioni intermedi sono tradotte in una sequenza di istruzioni macchina che esegue lo stesso compito. Un aspetto critico è l'assegnazione di variabili da registri .

[ modifica ] Generazione del codice intermedio

Dopo l'analisi sintattica e semantica, alcuni compilatori generano un intermedio rappresentazione esplicita del programma sorgente. Si può considerare questo come una rappresentazione intermedia del programma per una macchina astratta . Questa rappresentazione intermedia deve avere due caratteristiche importanti: dovrebbe essere facile da produrre e facili da tradurre l'oggetto del programma.

La rappresentazione intermedia può assumere molte forme. Vi è una forma intermedia chiamata " codice a tre indirizzi ", che è come il linguaggio assembly di una macchina in cui ogni locazione di memoria può agire come un record . Le tre code indirizzo è costituito da una sequenza di istruzioni, ognuna delle quali ha più di tre operandi. Questa rappresentazione intermedia ha diverse proprietà:

• Primo .- Ogni istruzione in tre direzioni ha al massimo un operatore, oltre alla cessione, per cui quando queste istruzioni vengono generati, il traduttore deve decidere l'ordine in cui qualsiasi operazione.
• Secondo .- Il traduttore deve generare un nome temporaneo per memorizzare i valori calcolati per ogni affermazione.
• Terza .- Alcune istruzioni in "tre vie" meno di tre operandi, ad esempio, l'assegnazione.

[ modifica ] Ottimizzazione del codice

La fase di ottimizzazione del codice è quello di migliorare il codice intermedio, in modo che sia un codice macchina più veloce. Questa fase della fase di sintesi è possibile soprattutto sé il traduttore è un compilatore (appena un interprete in grado di ottimizzare il codice oggetto). Vi è una grande variazione nella quantità di ottimizzazione del codice che esegue l'vari compilatori. In coloro che fanno un sacco di ottimizzazione, chiamato compilatori ottimizzanti, una parte significativa di tempo, il compilatore è interessato in questa fase. Tuttavia, ci sono semplici ottimizzazioni che migliorano significativamente il tempo di esecuzione senza che il programma in fase di compilazione troppo lento.

[ modifica ] Struttura dei dati chiave

L'interazione tra gli algoritmi utilizzati per le fasi del compilatore e strutture di dati che supportano queste fasi è naturalmente molto forte. Lo scrittore compilatore si sforza di attuare tali algoritmi in modo più efficace possibile, senza aggiungere molto di complessità troppo. Idealmente, un compilatore dovrebbe essere in grado di compilare un programma in tempo proporzionale alle dimensioni.

[ modifica ] Componenti o token lessicali

Quando un analizzatore lessicale incontra i personaggi di un token , rappresenta di solito un segno simbolico, cioè un valore di un tipo di dati enumerato che rappresenta l'insieme di segni della lingua di origine. A volte è anche necessario mantenere la stringa o altre informazioni stesse che ne derivano, come il nome associato a un token di identificazione o il valore di un numero di token.

Nella maggior parte delle lingue l'analizzatore lessicale deve solo generare un token alla volta. In questo caso è possibile utilizzare una variabile globale semplice per mantenere le informazioni dal token. In altri casi (l'esempio più notevole èFORTRAN), potrebbe essere necessario un array (o vettore) di gettoni.

[ modifica ] Syntax Tree

Sé il parser genera un albero di sintassi, di solito costruiti come una struttura standard basata su un puntatore che viene allocata dinamicamente come è fatto l'analisi. L'intera struttura può essere memorizzato come una singola variabile che punta al nodo radice. Ogni nodo della struttura è un record i cui campi rappresentano i dati raccolti sia dal parser e poi l'analizzatore semantico. Ad esempio, il tipo di dati di espressione può essere memorizzato come un campo nella struttura dei nodi di sintassi per l'espressione.

A volte, per risparmiare spazio, questi campi sono assegnati dinamicamente, o memorizzati in altre strutture dati come tabella dei simboli, che permettono l'assegnazione selettiva e deallocazione. Infatti, ogni nodo nell'albero della sintassi si può richiedere diversi attributi per essere memorizzati, a seconda del tipo di struttura del linguaggio di rappresentare. In questo caso, ogni nodo nell'albero della sintassi può essere rappresentata da una variabile di record, con ogni nodo classe che contiene solo le informazioni necessarie per tale causa.

[ modifica ] Tabella dei simboli

Questa struttura di dati mantiene le informazioni associate al identificatori, funzioni , variabili , costanti e tipi di dati . La tabella dei simboli interagisce con quasi tutte le fasi del compilatore: l'analizzatore lessicale, il parser e gli identificatori analizzatore semantico possono essere inseriti nella tabella, l'analizzatore semantico aggiungerà altri tipi di dati e informazioni, e le fasi di generazione e ottimizzazione informazioni utilizzare il codice fornito dalla tabella dei simboli per effettuare le selezioni oggetto codice appropriato.

Poiché la tabella simbolo accedere alle applicazioni così spesso, le operazioni di inserimento, cancellazione e la necessità di accedere a essere efficiente, di durata delle operazioni di preferenza costante. Una struttura dati standard per questo scopo è la tabella degli indirizzi o il calcolo dell'hash, anche sé possono utilizzare strutture ad albero diversi. A volte più tabelle vengono utilizzati e mantenuti inelenco o stack .

[ modifica ] Tabella di letterali

e rapido inserimento di ricerca sono inoltre essenziali per la tabella letterale, che memorizza le costanti e stringhe utilizzate nel programma. Tuttavia, un tavolo letterale bisogni per prevenire le eliminazioni in quanto i dati sono applicate globalmente al programma e una costante o una stringa appare una sola volta in questa tabella. La tabella letterale è importante per ridurre la dimensione di un programma in memoria per consentire il riutilizzo delle costanti e stringhe. E 'inoltre necessario per costruire il generatore di codice per il simbolico indirizzi letterale e di entrare definizioni di dati nel file di codice oggetto.

[ modifica ] Codice Intermediate

Secondo il tipo di codice intermedio (per esempio, tre di codice indirizzo o il codice P) e il tipo di ottimizzazioni eseguite, questo codice può essere memorizzato come un array di stringhe, un file di testo temporaneo o di un elenco relative strutture. In compilatori che eseguono ottimizzazioni complesse deve essere particolare attenzione alla scelta delle rappresentazioni che permettono riorganizzazione facile.

Generazione di codice intermedio

Dopo l'analisi sintattica e semantica, alcuni compilatori generano un intermedio rappresentazione esplicita del programma sorgente. Si può considerare questo come una rappresentazione intermedia per un programma di macchina astratta. Questa rappresentazione intermedia deve avere due caratteristiche importanti: dovrebbe essere facile da produrre e facili da tradurre l'oggetto del programma.

La rappresentazione intermedia può assumere molte forme. Vi è una forma intermedia chiamata "codice a tre indirizzi, che è come il linguaggio assembly per una macchina in cui ogni locazione di memoria può agire come un record. Le tre code indirizzo è costituito da una sequenza di istruzioni, ognuna delle quali ha più di tre operandi. Il programma di origine (1) codice può essere visualizzato in tre direzioni come

 temp1: = entarea1 (60) 

 temp2: = id3 * temp1 (2) 

 TEMP3: = id2 + temp2 

id1: = TEMP3 

Questa rappresentazione intermedia ha diverse proprietà. In primo luogo, ogni istruzione in tre direzioni ha al massimo un operatore, oltre alla cessione. Pertanto, quando tali istruzioni vengono generati dal compilatore deve decidere l'ordine in cui sono eseguite le operazioni, la moltiplicazione precede Oltre al sorgente del programma. In secondo luogo, il compilatore deve generare un nome temporaneo per memorizzare i valori calcolati per ogni affermazione. In terzo luogo, alcune istruzioni in "tre righe" sono meno di tre operatori, come ultimo e prime istruzioni.

Ottimizzazione del codice

La fase di ottimizzazione del codice tenta di migliorare il codice intermedio in modo che sia un codice macchina più veloce. Alcune ottimizzazioni sono banali. Ad esempio, un algoritmo naturale genera il codice intermedio (2) con una istruzione per l'operatore della rappresentazione della struttura dopo l'analisi semantica, anche sé c'è un modo migliore per eseguire gli stessi calcoli utilizzando le due istruzioni

 Temp1: = id3 * 60,0 (3) 

 ID1: = id2 + temp1 

Questo semplice algoritmo è nulla di sbagliato, in quanto il problema può essere risolto in fase di ottimizzazione del codice. Ovvero, il compilatore può dedurre che la conversione di reale a intero 60 può essere fatto una volta e per tutto il tempo di compilazione, in modo che l'operazione entreal essere eliminato. Inoltre, TEMP3 viene utilizzato solo una volta, di trasmettere il suo valore a ID1. Così è sostituto sicuro per TEMP3 id1, da cui l'ultima frase (2) non è necessario e si ottiene il codice (3).

Ci sono molte variazioni nella quantità di ottimizzazione del codice che esegue i vari compilatori. Come fare un sacco di ottimizzazione chiamati "compilatori ottimizzanti, una parte significativa di tempo, il compilatore è interessato in questa fase. Tuttavia ci sono semplici ottimizzazioni che migliorano significativamente il tempo è interessato il compilatore in questa fase. Tuttavia, ci sono semplici ottimizzazioni che migliorano significativamente il tempo di esecuzione senza che il programma in fase di compilazione troppo lento.

[ modifica ] File temporanei

In un primo momento il computer non dispone di memoria sufficiente per memorizzare un programma completo durante la compilazione. Questo problema è stato risolto utilizzando i file temporanei per mantenere i prodotti dei passaggi intermedi durante la traduzione o per compilare la, cioè volare, mantenendo solo le informazioni sufficienti dalle parti precedenti del programma sorgente che permette di procedere con la traduzione.

limiti di memoria sono ormai un problema molto più piccole, e potrà richiedere un unità di compilazione tutto è conservato in memoria, soprattutto sé la collezione è disponibile esclusivamente in lingua. Tuttavia, occasionalmente, trovare utile compilatori generano file intermedi durante talune fasi della lavorazione. Tipico di questi è la necessità di affrontareindietro correzione durante la generazione del codice.