Linguaggi Formali e Compilazione

Angelo Morzenti, Luca Breveglieri, Stefano Crespi Reghizzi

• Editore: Società Editrice Esculapio
• Anno: 2019
• Print ISBN: 9788874888757
• eBook ISBN: 9788832597011
• Argomento: Informatica
• Categoria: Linguaggi di programmazione

I compilatori traducono i linguaggi artificiali (come Java e XML) nelle rappresentazioni usate dalle macchine di calcolo: senza di essi non esisterebbe l’informatica. I concetti della compilazione hanno avuto origine nella linguistica strutturale e nella logica matematica, da cui si sono sviluppati gli algoritmi e i metodi di progetto che hanno realizzato innumerevoli linguaggi. Il testo espone in modo piano e rigoroso le grammatiche formali, gli automi, gli algoritmi di analisi sintattica, le relazioni di traduzione e gli automi traduttori, le traduzioni guidate dalla sintassi e le funzioni semantiche, terminando con l’analisi statica del flusso nei programmi. Molti esempi, semplici ma realistici, conducono il lettore verso la comprensione analitica e la capacità progettuale delle tecniche elementari di compilazione.
L’esperienza degli autori nella ricerca e sviluppo su linguaggi e compilatori si riflette nella selezione degli argomenti, sempre motivata da finalità applicativa e da economia concettuale. L’opera vuole trovare un giusto medio tra i testi di orientamento puramente teorico e i manuali dei compilatori. Il passaggio dagli algoritmi all’implementazione è sufficientemente delineato, senza prolissità, affinché un lettore di cultura informatica possa compierlo da solo. Al termine del percorso, il lettore comprenderà il funzionamento delle parti essenziali di un compilatore, conoscerà gli algoritmi usati negli strumenti (scanner parser generator) e potrà progettare semplici linguaggi e traduttori sintattici. Il testo è adatto a un corso universitario di cinque crediti per studenti con almeno due anni di informatica alle spalle. Esso è la base per approfondimenti specialistici in più direzioni, quali: l’ottimizzazione del codice-macchina, i sistemi anti-intrusione, i linguaggi interattivi e grafici, i metodi per il trattamento del linguaggio naturale e i linguaggi per l’accesso ai grandi dati della Rete.

Indice dei contenuti

• 1
• Title Page
• Prefazione
• Indice
• Capitolo 1 - Introduzione
• 1.2 Parti del compilatore e concetti corrispondenti
• Capitolo 2 - Sintassi
• 2.1.2 Tipi di linguaggio
• 2.1.3 Scaletta
• 2.2 Teoria dei linguaggi formali
• 2.2.1.1 Operazioni su stringhe
• 2.2.1.3 Sottostringa
• 2.2.1.5 Ripetizione
• 2.2.3 Operazioni su insiemi
• 2.2.4 Stella e croce
• 2.2.5 Quoziente
• 2.3 Espressioni e linguaggi regolari
• 2.3.2 Derivazione e linguaggio
• 2.3.2.1 Ambiguit delle espressioni regolari
• 2.3.3 Altri operatori
• 2.3.4 Propriet di chiusura della famiglia REG
• 2.4 Astrazione linguistica
• 2.4.1 Lista astratta e concreta
• 2.4.1.1 Sostituzione
• 2.5 Grammatiche generative libere da contesto
• 2.5.1 Limiti dei linguaggi regolari
• 2.5.3 Rappresentazione convenzionale delle grammatiche
• 2.5.4 Derivazione e linguaggio generato
• 2.5.5 Grammatica erronea e regola inutile
• 2.5.6 Regole ricorsive e infinitezza del linguaggio
• 2.5.7 Albero sintattico e derivazione canonica
• 2.5.7.1 Derivazione destra e sinistra
• 2.5.8 Linguaggi a parentesi
• 2.5.9 Composizione regolare di linguaggi liberi
• 2.5.10 Ambiguit
• 2.5.11 Catalogo di forme ambigue e rimedi
• 2.5.11.1 Ambiguit di ricorsione bilaterale
• 2.5.11.2 Ambiguit di unione
• 2.5.11.3 Ambiguit di concatenamento
• 2.5.11.4 Codifica univoca
• 2.5.11.5 Altre situazioni ambigue
• 2.5.11.6 Ambiguit della frase condizionale
• 2.5.11.7 Ambiguit inerente del linguaggio
• 2.5.12 Equivalenza debole e strutturale
• 2.5.12.1 Equivalenza strutturale in senso lato
• 2.5.13 Trasformazioni di grammatiche e formenormali
• 2.5.13.3 Eliminare i nonterminali annullabili e le regole vuote
• 2.5.13.4 Eliminare le regole di copia o categorizzazione
• 2.5.13.5 Eliminare le parti destre ripetute
• 2.5.13.6 Forma normale di Chomsky o binaria
• 2.5.13.7 Forma normale con operatori
• 2.5.13.8 Trasformare la ricorsione da sinistra in destra
• 2.5.13.9 Forma normale in tempo reale e di Greibach
• 2.6 Grammatiche dei linguaggi regolari
• 2.6.1 Dallespressione regolare alla grammatica libera
• 2.6.2 Grammatica lineare e unilineare
• 2.6.3 Equazioni lineari e linguaggio
• 2.7 Linguaggi liberi e regolari a confronto
• 2.7.0.1 Ruolo della derivazione autoinclusiva
• 2.7.1 Limiti dei linguaggi liberi
• 2.7.2 Propriet di chiusura di REG e LIB
• 2.7.3 Trasformazioni alfabetiche
• 2.7.3.1 Chiusura rispetto a trasformazioni alfabetiche
• 2.7.4 Grammatica estesa con espressioni regolari
• 2.7.4.1 Derivazioni e alberi nelle grammatiche libere estese
• 2.8 Grammatiche e famiglie di linguaggi pi generali
• Capitolo 3 - Automi finiti e riconoscimento dei linguaggi regolari
• 3.2 Algoritmi di riconoscimento e automi
• 3.2.1 Un automa generale
• 3.3 Introduzione agli automi finiti
• 3.4 Automa finito deterministico
• 3.4.1 Stato di errore e completamento dellautoma
• 3.4.2 Automa pulito
• 3.4.3 Automa minimo
• 3.4.3.1 Costruzione dellautoma minimo
• 3.4.4 Dallautoma alla grammatica
• 3.5 Automa non deterministico
• 3.5.1 Motivazioni del nondeterminismo
• 3.5.1.2 Dualit sinistra-destra e riflessione del linguaggio
• 3.5.2 Riconoscitore non deterministico
• 3.5.2.1 Funzione di transizione
• 3.5.3 Automa con mosse spontanee
• 3.5.3.1 Unicit dello stato iniziale
• 3.5.5 Ambiguit dellautoma
• 3.6 Dallautoma allespressione regolare direttamente: metodo BMC
• 3.7 Eliminazione del non determinismo
• 3.7.1 Costruzione delle parti finite raggiungibili
• 3.8 Dallespressione regolare allautoma riconoscitore
• 3.8.1 Metodo strutturale di Thompson
• 3.8.2 Metodo di Berry-Sethi
• 3.8.2.2 Espressioni regolari lineari e loro insiemi locali
• 3.8.2.3 Dallespressione regolare allautoma deterministico
• 3.8.2.4 Riconoscitore deterministico mediante lalgoritmo diBerry-Sethi
• 3.9 Espressione regolare con complemento e intersezione
• 3.9.1 Prodotto di automi
• 3.9.1.1 Espressioni regolari estese e ristrette
• 3.9.1.2 Linguaggi senza stella
• 3.10 Riepilogo: relazioni tra linguaggi regolari, automi egrammatiche
• Capitolo 4 - Automi a pila e parsificazione
• 4.2 Automa a pila
• 4.2.1 Dalla grammatica allautoma a pila
• 4.2.1.1 Complessit di calcolo dellautoma a pila
• 4.2.2 Definizione dellautoma a pila
• 4.2.2.1 Diagramma stato-transizione per automi a pila
• 4.2.2.2 Variet di automi a pila
• 4.3 Linguaggi liberi e automi a pila: una sola famiglia
• 4.3.1 Intersezione di linguaggi liberi e regolari
• 4.3.2 Automi a pila e linguaggi deterministici
• 4.3.2.1 Propriet di chiusura dei linguaggi deterministici
• 4.3.2.2 Linguaggi nondeterministici
• 4.3.2.3 Determinismo e inambiguit del linguaggio
• 4.3.2.4 Sottoclassi degli automi deterministici a pila
• 4.3.2.5 Semplici sottofamiglie deterministiche
• 4.4 Analisi sintattica
• 4.4.1 Analisi discendente e ascendente
• 4.5 La grammatica come rete di automi finiti
• 4.5.0.1 Diagrammi sintattici
• 4.5.1 Derivazione per una rete di macchine
• 4.5.1.1 Grammatica linearizzata a destra
• 4.5.1.2 Punto di chiamata e attivazione di una macchina
• 4.5.2 Insieme degli inizi e prospezione
• 4.6 Analisi sintattica deterministica ascendente
• 4.6.1 Dal riconoscitore finito al parsificatoreascendente
• 4.6.2 Costruzione del parsificatore ELR(1)
• 4.6.2.1 Base, chiusura e nucleo di un m-stato
• 4.6.3 Condizione ELR(1)
• 4.6.3.1 Algoritmo del parsificatore
• 4.6.4 Semplificazioni per le grammatiche BNF
• 4.6.4.2 Caratteristiche superflue
• 4.6.5 Implementazione del parsificatore con pilavettore
• 4.6.6 Allungamento della prospezione
• 4.7 Analisi sintattica deterministica discendente
• 4.7.1 Condizione ELL (1)
• 4.7.2 Derivazione passo a passo del parsificatoreELL (1)
• 4.7.2.2 Identificatori delle candidate e puntatori non necessari
• 4.7.2.3 Accorciamento della pila e parsificatore predittivo
• 4.7.3 Costruzione diretta del parsificatore predittivodiscendente
• 4.7.3.1 Parsificatore predittivo
• 4.7.4 Allungamento della prospezione
• 4.8 Famiglie di linguaggi deterministici: un confronto
• 4.9 Valutazione dei metodi di analisi
• 4.10 Un algoritmo generale di analisi sintattica
• 4.10.1 Presentazione introduttiva
• 4.10.2 Algoritmo di Earley
• 4.10.2.1 Osservazioni su complessit e ottimizzazioni
• 4.11 Parsificazione parallela locale
• 4.11.1 Grammatica di Floyd a precedenza di operatori
• 4.11.1.1 Confronto con i linguaggi deterministici
• 4.11.2 Parsificatore sequenziale a precedenza di operatori
• 4.11.3 Algoritmo di parsificazione parallelo
• 4.11.3.1 Complessit
• 4.12 Gestione degli errori e delle modifiche
• 4.12.1 Errori
• 4.12.1.2 Errori sintattici
• 4.12.2 Parsificazione incrementale
• Capitolo 5 - Traduzione, semantica e analisi statica
• 5.2 Relazione e funzione di traduzione
• 5.3 Traslitterazione
• 5.4 Traduzione sintattica pura
• 5.4.1 Forme infissa e polacca
• 5.4.2 Ambiguit della grammatica e della traduzione
• 5.4.3 Grammatica di traduzione e traduttore a pila
• 5.4.3.1 Dalla grammatica di traduzione al traduttore a pila
• 5.4.4 Analisi sintattica e traduzione in linea
• 5.4.6 Traduzione deterministica ascendente
• 5.4.6.1 Forma normale postfissa
• 5.4.6.2 Albero sintattico come traduzione
• 5.4.6.3 Confronto
• 5.5.1 Automa riconoscitore a due ingressi
• 5.5.1.1 Equivalenza dei modelli
• 5.5.2 Funzione di traduzione e automa traduttore
• 5.5.2.1 Traduttore deterministico e sequenziale
• 5.5.2.2 Traduzione in due passate opposte
• 5.5.3 Propriet di chiusura rispetto alla traduzione
• 5.6 Traduzione semantica
• 5.6.1 Grammatica con attributi
• 5.6.1.1 Esempio introduttivo
• 5.6.2 Attributo sinistro e destro
• 5.6.3 Definizione di grammatica con attributi
• 5.6.4 Grafo di dipendenza e valutazione degli attributi
• 5.6.4.1 Esistenza e unicit della soluzione
• 5.6.5 Valutazione semantica in una scansione
• 5.6.5.1 Grammatica a una scansione
• 5.6.6 Altri metodi di valutazione
• 5.6.7 Analisi sintattica e semantica integrate
• 5.6.7.2 Parsificatore a discesa ricorsiva con attributi
• 5.6.7.3 Parsificatore ascendente con attributi
• 5.6.8 Applicazioni tipiche della grammatica conattributi
• 5.6.8.2 Generazione di codice
• 5.6.8.3 Analisi sintattica guidata dalla semantica
• 5.7 Analisi statica del programma
• 5.7.1 Programma come automa
• 5.7.2 Intervallo di vita della variabile
• 5.7.2.1 Calcolo dellintervallo di vita
• 5.7.2.2 Soluzione del sistema di equazioni di flusso
• 5.7.2.3 Applicazione dellanalisi di vita
• 5.7.3 Definizione raggiungente
• 5.7.3.1 Propagazione di costante
• 5.7.3.2 Disponibilit di variabile e inizializzazione
• Riferimenti bibliografici
• Indice analitico
• Back cover