automi e linguaggi formalifrossi/2013-parte1.pdf · linguaggi regolari e grammatiche (cap.5 alc)...
TRANSCRIPT
Automi e Linguaggi Formali
Docente: Francesca Rossi
E-mail: [email protected]
Docente: Francesca Rossi Automi e Linguaggi Formali
Orario e ricevimento
Orario:
Lunedi’, Martedi’, Mercoledi’, Giovedi’ 13:30-15:30 LUM250
Crediti: 8 crediti formativi, circa 64 ore di lezioneRicevimento:
Martedi’ 11:00-13:00, studio 428, IV piano, Torre Archimede(Via Trieste 63)
Docente: Francesca Rossi Automi e Linguaggi Formali
Sito del corso
URL: http://www.math.unipd.it/˜frossi/automi2013.html
Contiene:
programma
date appelli
lucidi
voti
...
Docente: Francesca Rossi Automi e Linguaggi Formali
Altre informazioni utili
Libro principale: Automi, linguaggi e calcolabilita’,J. E. Hopcroft, R. Motwani, and J. D. Ullman, terza edizione,Pearson/Addison-Wesley, 2009.
Altro libro: Compilatori: principi, tecniche e strumenti, A.H.Aho, M. S. Lam, R. Sethi, J. D. Ullman, seconda edizione,Pearson/Addison-Wesley, 2009.
Compitini (forse): Due compitini, uno a meta’ del corso euno alla fine. Possono sostituire lo scritto.
Esame: Scritto e, se richiesto dal docente, colloquio orale.Cinque appelli: due a fine corso (Dicembre-Gennaio), uno allafine del II trimestre (Aprile), uno a Luglio, uno a Settembre.
I lucidi per i capitoli 1-7 del libro principale sono basati suilucidi in inglese di Gosta Grahne e David Ford(http://www.cs.concordia.ca/~grahne/hmu slides/).
Docente: Francesca Rossi Automi e Linguaggi Formali
Sommario del corso
Struttura dei un compilatore e fasi principali (cap.1 CPTS)
Analisi lessicale (cap. 3 CPTS)
Automi a stati finiti (cap.1,2 ALC)
Espressioni regolari (cap.3 ALC)
Pumping lemma e proprieta’ dei linguaggi regolari (cap.4ALC)
Minimizzazione degli automi a stati finiti (cap.4 ALC)
Analisi sintattica top-down e bottom-up (cap.4 CPTS)
Grammatiche libere da contesto (cap.5 ALC)
Linguaggi regolari e grammatiche (cap.5 ALC)
Automi a pila (cap.6 ALC)
Pumping lemma per linguaggi liberi da contesto (cap.7 ALC)
Macchine di Turing, problemi ricorsivamente enumerabili(cap.8 ALC)
Riduzioni e teorema di Rice (cap.9 ALC)
Classi P e NP (cap.10 ALC)
Docente: Francesca Rossi Automi e Linguaggi Formali
Linguaggi di programmazione
Linguaggi di programmazione = notazione per descriverecalcoli e computazioni
Per eseguire un programma, deve essere tradotto in una formache puo’ essere capita da un calcolatore ⇒ compilatore
Principi e tecniche utili non solo per costruire compilatori, main molte altre aree dell’informatica: linguaggi diprogrammazione, architettura, teoria dei linguaggi, algoritmi,ingegneria del software, ecc.
Docente: Francesca Rossi Automi e Linguaggi Formali
Compilatori
Compilatore: programma che legge un programma scritto inun linguaggio di programmazione (linguaggio sorgente) e lotraduce in un programma equivalente scritto in un altrolinguaggio (linguaggio oggetto)
Un compilatore mostra anche gli errori che trova durante latraduzione
Se il linguaggio oggetto e’ eseguibile da una macchina, unutente puo’ eseguirlo per passare da input ad output
Interprete: esegue direttamente le operazioni specificate nelprogramma sorgente (traducendo un’istruzione alla volta edeseguendo il pezzo di programma oggetto generato)
Di solito piu’ veloce l’esecuzione di programmi compilati
Assembler: compilatore da linguaggio assembly a codicemacchina
Docente: Francesca Rossi Automi e Linguaggi Formali
Struttura di un compilatore
Due parti: analisi e sintesi
Analisi (front end): prende un programma e lo divide in partisu cui impone una struttura grammaticale; crea unarappresentazione intermedia del programma sorgente; segnalapossibili errori; mette informazioni sul programma in unatavola dei simboli, da passare alla sintesiSintesi (back end): costruisce il programma oggetto dallarappresentazione intermedia e la tavola dei simboli
Sequenza di fasi: ogni fase trasforma una rappresentazione delprogramma sorgente in un’altra
Fasi principali: analisi lessicale, analisi sintattica, analisisemantica, generazione del codice intermedio, ottimizzazioneedel codice, generazione del codice
Docente: Francesca Rossi Automi e Linguaggi Formali
Analisi lessicale (scanning)
Legge la stringa di caratteri del programma sorgente eraggruppa i caratteri in sequenze chiamate lexemiPer ogni lexema, un token <nome-token,valore-attributo>
nome-token: simbolo associato al tokenvalore-attributo: punta alla tavola dei simboli
Esempio: comando posizione = iniziale + velocita’* 60
lexema posizione ⇒ token <id,1>: riga 1 della tavola deisimboli contiene posizionelexema = e token <=> (nessun valore attributo)lexema iniziale e token <id,2>, riga 2 contiene inizialelexema + e token <+>lexema velocita’ e token <id,3>, riga 3 contiene velocita’lexema * e token <*>lexema 60 e token <60>Rappresentazione finale: <id,1> <=> <id,2> <+> <id,3><*> <6>
Useremo: linguaggi regolari, automi a stati finiti,espressioni regolari
Docente: Francesca Rossi Automi e Linguaggi Formali
Analisi sintattica (parsing)
Il parser usa la prima componente dei token per creare unarappresentazione ad albero della lista di tokens (strutturagrammaticale)
Albero: insieme di nodi e archi diretti (da padre a figlio), taleche un nodo (radice) non ha padri, e tutti gli altri hannoesattamente un padre. Foglie: nodi senza figli.
Albero sintattico: nodo interno = operazione, figli =argomenti dell’ operazione
Mostra l’ordine in cui eseguire le operazioni
Useremo: grammatiche libere da contesto, automi a pila,linguaggi liberi da contesto
Docente: Francesca Rossi Automi e Linguaggi Formali
Esempio
Dalla lista di tokens <id,1> <=> <id,2> <+> <id,3> <*><6> all’albero sintattico
=
/ \
<id,1> +
/ \
<id,2> *
/ \
<id,3> 60
Prima dobbiamo moltiplicare il lexema del token <id,3>, cioe’velocita’ con 60
poi dobbiamo sommare il risultato con il valore di iniziale
poi dobbiamo mettere il risultato nella locazionedell’identificatore posizione
Docente: Francesca Rossi Automi e Linguaggi Formali
Analisi semantica
Usa l’albero sintattico e la tavola dei simboli per controllare laconsistenza semantica del programma
Colleziona informazioni sui tipi e le mette nella tavola deisimboli (per la fase di generazione del codice)
Controllo dei tipi (type checking): il tipo di ogni operazionedeve andare d’accordo con i tipi dei suoi operandi
Esempio: un indice di un array deve essere un intero (errore sead esempio floating-point)
Coercion: conversione di tipo
a volte un’operazione puo’ essere applicata sia a due interi chea due floating-pointse un operando e’ intero e l’altro e’ floating point, l’interoviene convertito in floating-point
Docente: Francesca Rossi Automi e Linguaggi Formali
Esempio
Se posizione, iniziale, e velocita’ sono dichiarati comenumero floating-point, e se il lexema 60 e’ un integer, l’operazione* e’ applicata ad un numero integer (60) e ad un floating-point(velocita’) ⇒ conversione di 60 in un floating-point. Dall’alberosintattico di sinistra a quello sulla destra:
= =
/ \ / \
<id,1> + <id,1> +
/ \ / \
<id,2> * <id,2> *
/ \ / \
<id,3> 60 <id,3> inttofloat
|
60
Docente: Francesca Rossi Automi e Linguaggi Formali
Generazione del codice intermedio
Rappresentazione intermedia simile al codice macchina
Spesso codice a tre indirizzi: sequenza di istruzioni similiall’assembly con tre operandi per istruzione
Nell’esempio, si ottiene:t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3
Al piu’ un operatore sulla destra: le istruzioni danno l’ordinein cui effettuare le operazioni
Esempio: la moltiplicazione precede la somma
Un nome temporaneo generato per contenere il valorecalcolato da ogni istruzione
Docente: Francesca Rossi Automi e Linguaggi Formali
Ottimizzazione del codice
Miglioramento del codice intermedio per ottenere un migliorecodice oggetto
Migliore: piu’ veloce, piu’ corto, meno energia necessaria, ecc.
Esempio: dat1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3
at1 = id3 * 60.0
id1 = id2 + t1
Conversione da integer a floating-point fatta a a tempo dicompilazione (e non a tempo di esecuzione), e quindieliminata dal codice
t3 era usato solo per trasmettere un valore ad id1
Docente: Francesca Rossi Automi e Linguaggi Formali
Generazione del codice
Da rappresentazione intermedia a codice oggetto
Registri o locazioni di memoria per ogni variabile del codice
Da ogni istruzione in codice intermedio a sequenza diistruzioni in codice macchina
Esempio: dat1 = id3 * 60.0
id1 = id2 + t1
aLDF R2, id3
MULF R2, R2, #60.0
LDF R1, id2
ADDF R1, R1, R2
STF id1, R1
Il primo operando specifica una destinazione, F: floating-point
id3 in R2, poi moltiplicazione con 60.0 e risultato in R2, poiid2 in R1, poi somma di R1 e R2 in R1, poi R1 in id1
Docente: Francesca Rossi Automi e Linguaggi Formali
Strumenti per la costruzione di un compilatore
Generatori di parser: generano automaticamente un parserdalla descrizione della grammatica di un linguaggio
Generatori di scanner: generano automaticamente unanalizzatore lessicale dalla descrizione tramite espressioniregolari dei token di un linguaggio
Generatori di generatori di codice: da regole per tradurre ognioperazione in una sequenza di istruzioni in linguaggiomacchina
Docente: Francesca Rossi Automi e Linguaggi Formali
Ruolo dell’analisi lessicale
Legge i caratteri del programma, li raggruppa in lexemi,produce in output una sequenza di token per ogni lexema
Quando trova un lexema che rappresenta un indentificatore,mette il lexema nella tavola dei simboli
Elimina spazi bianchi e commenti
Scanning (compattazione della stringa di caratteri coneliminazione di commenti e spazi bianchi) seguito da analisilessicale (tokens da lexemi)
Diagramma o altro modo di descrivere i lexemi di ogni token
Useremo automi a stati finiti e espressioni regolari(equivalenti)
Docente: Francesca Rossi Automi e Linguaggi Formali
Token, pattern, lexemi
Token: coppia <nome token, valore attributo>
nome token: simbolo astratto che rappresenta un’unita’lessicale (una parola chiave, un identificatore, ecc.)
Pattern: descrizione della forma che i lexemi di un tokenpossono avere
Esempio: se il token e’ una parola chiave, il pattern e’ lasequenza di caratteri che formano la parola chiave. Peridentificatori, il pattern descrive tante stringhe di caratteri, chesono tutte identificatori.
Lexema: sequenza di caratteri del programma sorgente cherispetta il pattern di un token
Esempi:
token if, pattern: caratteri i e f, lexema: iftoken id, pattern: una lettera seguita da lettere e cifre, esempidi lexemi: posizione, inizialetoken number, pattern: un numero, esempi di lexemi:3.14159, 0, 6.2
Docente: Francesca Rossi Automi e Linguaggi Formali
Casi tipici di token
Un token per ogni parola chiave
Vari token per gli operatori
Un token per tutti gli identificatori
Vari token per le costanti (numeri, letterali, ecc.)
Token per altri simboli (parentesi, virgola, ecc.)
Nome token per dire che token e’, valore attributo per indicarequale lexema come istanza del token.
Docente: Francesca Rossi Automi e Linguaggi Formali
Esempio
Comando Fortran E = M * C ** 2
Token generati:<id, puntatore ad E nella tavola dei simboli><assign-op><id, puntatore ad M nella tavola dei simboli><mult-op><id, puntatore a C nella tavola dei simboli><exp-op><number, valore intero 2>
Docente: Francesca Rossi Automi e Linguaggi Formali
Input buffering
Esempio: per sapere di essere alla fine di un identificatore,dobbiamo almeno leggere un carattere che non e’ ne’ unalettera ne’ una cifra
Esempio (C): < potrebbe essere un operatore oppure l’iniziodi <=
Esempio (Fortran 90, spazi sono ignorati): nel comando
DO 5 I = 1.25
il primo lexema e’ DO5I (e’ un comando di assegnamento),mentre in
DO 5 I = 1,25
il primo lexema e’ la parola chiave DO (comando for)
Spesso e’ necessario leggere oltre la fine di un lexema percapire che lexema e’
Due puntatori per scorrere l’input: uno all’inizio del lexemacorrente, uno per leggere oltre, finche’ non si trova un lexemache corrisponde ad un token
Docente: Francesca Rossi Automi e Linguaggi Formali
Specifica dei token
Linguaggi regolari
Espressioni regolari per descrivere i token
Automi a stati finiti per descrivere analizzatori lessicali
Da espressione regolare ad automa
Docente: Francesca Rossi Automi e Linguaggi Formali