Automi e Linguaggi Formalifrossi/2013-parte1.pdf · Linguaggi regolari e grammatiche (cap.5 ALC)...

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)


Sito del corso

URL: http://www.math.unipd.it/˜frossi/automi2013.html

Contiene:

programma

date appelli

lucidi

voti

...


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/).


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)


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.


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


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


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


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


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


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


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


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


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


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


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


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)


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


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.


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>


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


Specifica dei token

Linguaggi regolari

Espressioni regolari per descrivere i token

Automi a stati finiti per descrivere analizzatori lessicali

Da espressione regolare ad automa


Automi e Linguaggi Formalifrossi/2013-parte1.pdf · Linguaggi regolari e grammatiche (cap.5 ALC)...

Documents

Transcript of Automi e Linguaggi Formalifrossi/2013-parte1.pdf · Linguaggi regolari e grammatiche (cap.5 ALC)...