Principi di progettazione dei compilatori

A cura di: David Gries

Principi di progettazione dei compilatori

Pagine: 568

ISBN: 9788820411527

Edizione: 5a edizione 1987

Codice editore: 700.6

Disponibilità: Nulla

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.

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

Contributi: A. L. Frisiani, M. Vincenzi

Collana: Informatica

Livello: Textbook, strumenti didattici - Testi per professional