Principi Di Progettazione Dei Compilatori
- ISBN/EAN
- 9788820411527
- Editore
- Franco Angeli
- Collana
- Informatica-diretta da arrigo l. Frisiani - comitat
- Formato
- Brossura
- Anno
- 1987
- Edizione
- 5
- Pagine
- 568
Disponibile
62,50 €
Il volume descrive le tecniche utilizzabili nella scrittura di compilatori per linguaggi ad alto livello quali il Fortran ed il PL/I, illustrando sia la teoria sia gli aspetti pratici connessi con tale
scrittura.
Dopo una introduzione dedicata alla descrizione delle parti di un compilatore, l'autore tratta in modo approfondito grammatiche e linguaggi. Sono quindi discussi gli automi finiti e si mostra come la teoria precedentemente presentata conduce agli analizzatori lessicali e grammaticali. Vengono quindi trattati i riconoscitori top down, l'analisi recursiva discendente, I riconoscitori bottom up incluse le grammatiche a precedenza, la precedenza di operatori ed i metodi a contesto limitato. Dopo aver introdotto un linguaggio per la scrittura di riconoscitori sintattici!, l'autore fa seguire una approfondita discussione sull'organizzazione della memoria nella fase di esecuzione e sulla tabella dei simboli. Dopo aver esposto le varie rappresentazioni interne di un programma sorgente (quali notazione polacca, triple, quadruple), egli illustra l'uso delle routine semantiche, in generale e per strutture tipo Algol. Infine vengono discussi l'allocazione per le variabili in fase di esecuzione, i rimedi agli errori, la generazione e l'ottimizzazione del codice.
Oltre a quanto sopra ricordato, il volume tratta anche argomenti spesso ignorati in pubblicazioni analoghe, in modo da presentare un quadro quanto mai completo sui compilatori. La validità della presentazione è stata confermata da una recente indagine svolta dallo leee Computer Society Education Survey Subcommittee: da essa si apprendo che il testo è usato prezzo il 76% dei dipartimenti Intervistati (di ingegneria elettrica o di scienza
del calcolatore).
Il libro è indicato sia per corsi universitari, quali quelli di compilatori, compilatori e sistemi operativi, linguaggi di programmazione, sia per corsi di specializzazione e per lo studio autonomo da parte di scrittori ed utilizzatori di compilatori, novizi ed anche esperti. Il lettore è agevolato e motivato allo studio dalla ricchezza di materiale «reale» inserito nel testo e di consigli pratici, e la verifica dell'apprendimento è sollecitata da numerosi ed utili esercizi. Per agevolare le indagini e gli approfondimenti il libro è corredato di indici e di una amplissima bibliografia, sia generale sia di interesse storico.
Maggiori Informazioni
| Autore | Gries David |
|---|---|
| Editore | Franco Angeli |
| Anno | 1987 |
| Tipologia | Libro |
| Collana | Informatica-diretta da arrigo l. Frisiani - comitat |
| Num. Collana | 6 |
| Lingua | Italiano |
| Indice | Presentazione di A.L. Frisiani Prefazione 1. Introduzione 1.1. Compilatori, assemblatori, interpreti 1.2. Breve descrizione del processo di compilazione Tabelle delle informazioni Lo scanner L'analizzatore sintattico e l'analizzatore semantico Il programma sorgente interno Preparazione per la generazione del codice Generazione del codice 1.3. Alcuni esempi di strutture di compilatori Compilatore ALCOR Illinois 7090 Compilatore Gier ALGOL /360 WATFOR Compilatore FORTRAN IV H dell'IBM/360 2. Grammatiche e linguaggi 2.1. Introduzione alle grammatiche Esercizi 2.2. Simboli o stringhe Esercizi 2.3. Definizione formale di grammatica e di linguaggio Esercizi 2.4. Alberi sintattici e ambiguità Come ricostruire una derivazione da un albero Ambiguità Una grammatica non ambigua per espressioni aritmetiche Esercizi 2.5. Il problema dell'analisi sintattica Esercizi 2.6. Alcune relazioni riguardanti le grammatiche Relazioni Relazioni riguardanti le grammatiche Esercizi 2.7. Costruzione della chiusura transitiva delle relazioni Matrici booleane e relazioni Esercizi 2.8. Restrizioni pratiche alle grammatiche Esercizi 2.9. Altre notazioni sintattiche Parentesi graffe Parentesi quadre Parentesi tonde usate come metasimboli Fattorizzazione Metasimboli usati come terminali 2.10. Generalità sulla teoria dei linguaggi formali e riferimenti alla letteratura 2.11. Ricapitolazione 3. Lo scanner 3.1. Introduzione Uso delle grammatiche regolari 3.2. Espressioni regolari e automi a stati finiti Diagrammi a stati Automi finiti Rappresentazione interna in un calcolatore FA non deterministico Costruzione di un FA a partire da un NFA Espressioni regolari Costruzione di un FA per una espressione regolare Esercizi 3.3. Programmazione di uno scanner I simboli del linguaggio sorgente Uscita dello scanner Il diagramma a stati Variabili globali e routine necessarie Aggiunta della semantica al diagramma a stati Il programma Discussione Esercizi 3.4. Un costruttore di scanner per compilatori 3.4.1. Struttura dei simboli 3.4.2. L'algoritmo di scansione Classi di caratteri Il diagramma a stati Le tabelle per l'algoritmo di scansione 3.4.3. Dati d'ingresso per il costruttore di tabelle Caratteri Definizione di classe Definizione dei simboli La chiamata di un sottoprogramma Esercizi 3.5. Il sistema AED RWORD Sintassi per la definizione dello scanner Descrizione di una classe di carattere La descrizione dei simboli Esempi di definizioni di scanner Il costruttore 3.6. Riferimenti storici 4. Riconoscitori top-down 4.1. Top-down con backup 4.2. Problemi del top-down e loro soluzione Recursione diretta a sinistra Recursione a sinistra in generale Rappresentazione della grammatica in memoria Analisi senza backup 4.3. Analisi recursiva discendente Esercizio 4.4. Riferimenti storici 5. Grammatiche a precedenza semplice 5.1. Le relazioni di precedenza e il loro uso Esercizi 5.2. Definizione e costruzione delle relazioni Costruzione delle relazioni di precedenza Esercizi 5.3. L'algoritmo di analisi Esercizi 5.4. Funzioni di precedenza Esercizi 5.5. Difficoltà nella costruzione di grammatiche a precedenza Esercizi 5.6. Riferimenti storici 6. Altri riconoscitori bottoni-up 6.1. Precedenza di operatori Grammatiche a operatori Grammatiche a precedenza di operatori Costruzione delle relazioni Frasi principali - Loro individuazione e riduzione Esercizi 6.2. Precedenze di ordine superiore Precedenza (1,2)(2,1) Realizzazione pratica della precedenza (1,2)(2,1) L'algoritmo di analisi (1,2)(2,1) modificato Precedenza (m, n) Esercizi 6.3. Contesto limitato Definizione di contesto limitato (1,1) Il riconoscitore a contesto limitato (1'1) Definizione di contesto limitato (m, n) Riconoscitore e costruttore a contesto limitato (m, n) 6.4. Matrici di transizione Vantaggi e svantaggi delle matrici di transizione Costruzione della grammatica ad operatori ampliata Analisi in una AOG Condizioni sufficienti perchè una AOG sia non ambigua Esercizi 6.5. Riferimenti storici 7. Linguaggio a produzioni 7.1. Il linguaggio Produzioni Metasimboli Azioni Un esempio Nomi di classe Conflitti tra simboli del PL e del linguaggio sorgente Elenco delle regole sintattiche Esercizi 7.2. Uso del PL Analisi bottoni-up in PL Top-down senza backup in PL Programmazione in PL Esercizi 7.3. Chiamata di routine semantiche 7.4. Riferimenti storici 8. Organizzazione di aree di memoria in fase di esecuzione 8.1. Aree dati e aree display Esercizi 8.2. I template 8.3. Memorizzazione di tipi semplici di dati 8.4. Memorizzazione di matrici Vettori Matrici bidimensionali Matrici a più dimensioni Vettore d'informazione Strutture dati di Hoare Strutture dati del PL/ I Strutture dati di Standish Esercizi 8.5. Memorizzazione di stringhe 8.6. Memorizzazione di strutture 8.7. Corrispondenza tra parametri effettivi e parametri formali Chiamata per indirizzo Chiamata per valore Chiamata per risultato Argomenti fittizi Chiamata per nome Nome di matrice come parametro effettivo Nomi di procedure come parametri effettivi Esercizi 8.8. Organizzazione della memoria per il FORTRAN 8.9. Organizzazione della memoria per l'ALGOL Relazioni fra il DISPLAY attivo e l'area dati Aree dati per le procedure Indirizzamento di una variabile Ingresso nei blocchi, definizioni di matrici ed uscita dai blocchi Chiamata di una procedura Inizializzazione ed uscita di una procedura I thunk e come richiamarli Nomi di procedure come parametri effettivi Salti Esercizi 8.10 Allocazione dinamica di aree di memoria Il metodo delle targhe di confine per l'allocazione di aree di memoria Garbage collection Sistemi di allocazione a due livelli 8.11. Riferimenti storici 9. Organizzazione della tavola dei simboli 9.1. Introduzione all'organizzazione delle tabelle 9.2. Tabelle ordinate e non ordinate 9.3. Indirizzamento hash 9.3.1. Il rehash Rehash lineare Rehash casuale Rehash per aggiunta dell'indice hash Rehash quadratico 9.3.2. Concatenamento 9.3.3. Funzioni hash 9.4. Tavole dei simboli strutturate ad albero Esercizi 9.5. Tavole dei simboli con strutture a blocchi Apertura e chiusura dei blocchi Inserimento e ricerca Discussione Struttura a blocchi con indirizzamento hash 9.6. Riferimenti storici 10. I dati nella tavola dei simboli 10.1. Il descrittore Il compilatore ALCOR Illinois 7090 /360 WATFOR 10.2. Descrittore per i componenti di strutture Rappresentazione delle strutture nella tavola dei simboli Costruzione della tavola dei simboli Trattamento del riferimento An .... A 1.AO La frase MOVE CORRESPONDING Esercizi 11.Forme interne del programma sorgente 11.1. Operatori ed operandi 11.2. Notazione polacca Valutazione delle espressioni aritmetiche Estensione della notazione polacca ad altri operatori Esercizi 11.3. Quadruple Quadruple per le espressioni aritmetiche Estensione delle quadruple ad altri operatori Esercizi 11.4. Triple, alberi e triple indirette Triple Alberi Triple indirette 11.5. Blocchi 11.6. Riferimenti storici 12. Introduzione alle routine semantiche 12.1. Trasformazione della notazione infissa in notazione polacca Le routine semantiche Analisi di una proposizione Discussione Esercizi 12.2. Trasformazione della forma infissa in quadruple Esercizi 12.3. Implementazione delle routine semantiche e delle pile Collegamenti con la semantica 12.4. Elaborazione semantica con analisi top-down 12.5. Riferimenti storici 13. Routine semantiche per strutture tipo ALGOL 13.1. Notazione per le routine semantiche Indirizzamento delle pile semantiche Sottoprogrammi e variabli usate 13.2. Frasi condizionali Esercizi 13.3. Etichette e salti Collegamento delle operazioni di salto Riferimenti con strutture a blocchi non ancora definite Esercizi 13.4. Variabili ed espressioni Operatori aritmetici e logici Esercizi 13.5. Cicli FOR Esercizi 13.6. Ottimizzazione delle espressioni booleane Calcolo ottimale delle espressioni booleane 13.6.1. Il metodo bottom-up Modifica delle produzioni L'informazione semantica Esercizi 13.6.2. Il metodo top-down Esercizi 14. Allocazione in fase di esecuzione di aree di memoria per le variabili 14.1. Assegnazione di indirizzi alle variabili Variabili con valori iniziali Problemi di allineamento Uso delle strutture a blocchi per risparmiare spazio 14.2. Allocazione di aree di memoria per variabili temporanee Uso di una pila in fase di esecuzione per le variabili temporanee Uno schema più generale di allocazione Estensione dell'algoritmo ad altre variabili temporanee Indicazione del range nella descrizione di una variabile temporanea Esercizi 14.3. Variabili in COMMON ed in EQUIVALENCE Blocchi COMMON Variabili in EQUIVALENCE Tabella dei blocchi COMMON in fase di compilazione e catene COMMON Catene EQUIVALENCE Schema di realizzazione 15. Tecniche per rimediare agli errori 15.1. Introduzione Correzione di errori di ortografia 15.2. Rimedio agli errori semantici Eliminazione dei messaggi ridondanti Eliminazione dei messaggi ripetuti La routine ERRMES 15.3. Rimedio agli errori sintattici Rimedio agli errori negli analizzatori top-down Rimedio agli errori negli analizzatori bottom-up 16. Interpreti 16.1. Lo schema generale 16.2. I valori nella pila S 16.3. Conversione degli operandi 16.4. Gestione della memoria in fase di interpretazione 16.5. Dump della tavola dei simboli 16.6. Altri strumenti per la messa a punto 16.7. Discussione 17. Generazione del codice 17.1. Introduzione Forme di codice oggetto La macchina usata per descrivere la generazione del codice 17.2. Generazione del codice per semplici espressioni aritmetiche Generazione del codice a partire dalle quadruple Generazione del codice a partire dalle triple Generazione del codice a partire da un albero Generazione del codice a partire dalla notazione polacca Generazione del codice all'interno delle routine semantiche Produzione di un codice migliore 17.3. Indirizzamento degli operandi Elenco delle variabili e delle procedure usate Gli operandi nelle quadruple Descrizione dei registri e dell'accumulatore Forme di indirizzi degli operandi La procedura GETINREG (OPERAND, 1) La procedura FIXAD (OPERAND, INSTR) Generazione del codice per le quadruple aritmetiche Discussione 17.4. Estensione della generazione del codice ad altri tipi di quadruple Ottimizzazione degli operatori ABS e meno unario Generazione del codice per espressioni miste Generazione del codice per una quadrupla (:=A,,B) Generazione del codice per i salti e le frasi condizionali 17.5. Generazione di un codice compatto Interpretazione Generatore di codice per la quadrupla + Costruzione di sottoprogrammi più generali Sequenze di bit 17.6. Moduli oggetto CSECT Tipi di schede di modulo oggetto Il dizionario dei simboli esterni Le schede di testo Il dizionario di rilocazione RLD Conclusione Esercizi 18. Ottimizzazione del codice 18.1. Ottimizzazione all'interno dei blocchi elementari Il folding Eliminazione delle operazioni ridondanti Discussione della tecnica del folding e dell'eliminazione 18.2. Ottimizzazione limitata dei cicli Cenni alla realizzazione Rappresentazione interna dei cicli Restrizione sui cicli La tabella dei cicli il controllore dei cicli Elaborazione delle operazioni invarianti Il passo di riduzione della forza Discussione delle due tecniche Estensione della riduzione della forza Effettuazione dell'ottimizzazione in un numero minore di passi 18.3. Ottimizzazione più efficace Regioni e lista delle regioni Dipendenza dei test Schema generale di ottimizzazione Spostamento delle operazioni invarianti Riduzione della forza Sostituzione dei test Eliminazione delle assegnazioni inutili 18.4. Discussione e riferimenti storici Folding ed eliminazione delle operazioni ridondanti Ottimizzazione dei cicli Allocazione dei registri Operazioni per elaboratori in parallelo Altre ottimizzazioni 19. Macro-istruzioni 19.1. Un semplice schema per le macro-istruzioni Chiamate e definizioni di macro nidificate Formato delle definizioni e delle chiamate di macro Un semplice schema per macro Esercizi 19.2. Altre caratteristiche delle macro Sistemi "orientati verso la riga" ed a campo fisso Forma interna delle macro Creazione di simboli Variabili di fase di elaborazione delle macro Macro-istruzioni condizionali Opzioni del PL/ 1 per la fase di compilazione 19.3. Generatore di macro GPM Chiamata delle macro Definizioni delle macro Espansione delle macro Cenni sull'algoritmo di espansione delle macro Discussione Esercizi 19.4. Riferimenti storici 20. Sistemi di scrittura di traduttori 20.1. Introduzione Il principio informatore dei TWS Classificazione dei TWS 20.2. Descrizione di due compilatori di compilatori Linguaggi di tipo FSL Il BMCC 21. Suggerimenti per chi scrive un compilatore 21.1. Una filosofia generale 21.2. In che linguaggio deve essere scritto un compilatore? 21.3. Lo scanner può aiutare l'analizzatore sintattico 21.4. Discussione su algoritmi di analisi 21.5. Un suggerimento per le routine semantiche 21.6. Struttura del compilatore 21.7. Organizzazione delle tabelle in un compilatore 21.8. Il codice rientrante 21.9. Messa a punto del compilatore 21.10. Messaggi di errore per la fase di compilazione 21.11. Verifica degli errori nella fase di esecuzione e relativi messaggi 21.12. La tecnica del bootstrap Appendice. li linguaggio di programmazione usato nel libro A.1. Identificatori A.2. Costanti A.3. Tipi dei dati e definizione delle variabili A.4. Validità degli identificatosi A.5. Definizioni di procedure A.6. Variabili e valori: uso dei puntatori A.7. Espressioni A.8. Frasi Riferimenti bibliografici Indice analitico |
| Stato editoriale | In Commercio |
Questo libro è anche in: