Principi di progettazione dei compilatori
Autori e curatori
Contributi
A. L. Frisiani, M. Vincenzi
Collana
Livello
Textbook, strumenti didattici. Testi per professional
Dati
pp. 568,   figg. 166,     5a edizione  1987   (Codice editore 700.6)

Tipologia: Edizione a stampa
Prezzo: € 62,50
Disponibilità: Nulla
Codice ISBN: 9788820411527

Presentazione del volume

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.

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






newsletter facebook rss

Linkedin Facebook Twitter RSS Informatemi