Facoltà di Economia Corso di Laurea in Economia Informatica

Strumenti Formali per l’Analisi Lessicale – Sintattica dei Compilatori

Universtità degli Studi “G. D’Annunzio”Chieti – Pescara

Laureanda RelatoreCaterina Mandolini Stefano Bistarelli

Anno Accademico 2003-2004

STRUMENTI FORMALI PER L’ANALISI LESSICALE-

SINTATTICA DEI COMPILATORI.

1) Compilatori

2) Analisi Lessicale – Sintattica

3) Strumenti Formali

Il compilatore come traduttore da linguaggi di alto livello a linguaggi di basso livello

Tipicamente:• Il programma sorgente è scritto in un linguaggio di alto livello. • Il programma oggetto nel linguaggio macchina.

P1 equivalente a P2

P1ProgrammaSorgente

CompilatoreP2ProgrammaOggetto

Linguaggi di Programmazione

Alto livello: Pascal, C, Java

X=Y+5Basso livello: Linguaggio macchina

001 0110010 0001

Il Compilatore ci consentedi Sfruttare le Potenzialità della Macchina (Velocità e Precisione nell’esecuzione delle istruzioni)evitandoci l’Onere di imparare il Linguaggio Macchina

Modello analisi - sintesi

Analisi lessicaleAnalisi sintatticaAnalisi semantica

Analisi

P.S. Analisi Sintesi P.O.RappresentazioneIntermedia

Il modulo dell’analisi: esempio

Vogliamo assegnare alla variabile C il numero 2.795. Supponiamo che l’istruzione di assegnamento sia :=

• C=2.795 …….Errore!!! Analizzatore Lessicale • 2.795:=C …….Errore!!! Analizzatore sintattico • C:=2.795 …….Errore!!! Analizzatore semantico

Analizzatore Lessicale e Parser

Verifica della correttezza sintattica del programma

Linguaggi formali

x y (f(x)<y) Il linguaggio matematico è un linguaggio

formale o informale?

• Conta il numero dei bit La lingua italiana è un linguaggio formale o

informale?

Linguaggio Formale

• E’ un insieme costituito da un numero (finito o infinito) di frasi.

• Ogni frase è una sequenza finita di simboli.

H = {f1, f2, …, fn, …} f1= , f2= , … , fn= n ,…. H è un linguaggio formale?

Grammatiche Generative

<FRASE> <SOGGETTO> <PREDICATO> <COMPLEMENTO>

<SOGGETTO> Luca | Maria<PREDICATO> guarda | chiama<COMPLEMENTO> <ARTICOLO> <NOME><ARTICOLO> il<NOME> cane

Luca chiama il cane

1) <FRASE>2) <SOGGETTO> <PREDICATO>

<COMPLEMENTO>3) Luca <PREDICATO> <COMPLEMENTO>4) Luca chiama <COMPLEMENTO>5) Luca chiama <ARTICOLO> <NOME>6) Luca chiama il <NOME>7) Luca chiama il cane

Albero di derivazione

<FRASE>

<SOGGETTO> <PREDICATO>

Luca chiama

<COMPLEMENTO>

<NOME><ARTICOLO>

caneil

Classificazione delle grammatiche alla Chomsky

I linguaggi regolari ed i linguaggi liberi

sono decidibili. Complessità lineare:

O(n3) e O(n)

Tipo 2: libere dal contesto

A

Tipo 0

Tipo 1: dipendenti dal contesto

A

Tipo 3: regolari

A aB | a

Automa a Stati Finiti

Nastro di input

Controllo a stati finiti

Nastro di input

Controllo a stati finiti Memoria

a pila

Automa a Pila

STRUMENTI AUTOMATICI

• Analizzatore lessicale: LEX• Analizzatore sintattico: YACC(Yet Another Compiler Compiler)

INTERAZIONE LEX – YACC

YACCP.S.

LEX…..

Token

Altro token

Sintassi LEX

P1, P2, …, Pn%%

P1 {Azione 1}P2 {Azione 2}

...Pn {Azione n}

Sintassi YACC

% token T1, T2,…, Tn, %%

A1: 1 {Azione semantica 1}A2: 2 {Azione semantica 2}

...An: n {Azione semantica n}

Programma YACC: esempio% token NUMERO %%espr: espr ‘+’ espr {$$= $1 +

$3;}| espr ‘-’ espr {$$= $1 - $3;}| espr ‘*’ espr {$$= $1 * $3;}| espr ‘/’ espr {$$= $1 / $3;}| espr ‘-’ espr {$$= $1 - $3;}| ‘(’ espr ‘)’ {$$= $2}| NUMERO

Programma LEXNUMERO [0-9]%%{NUMERO}

{yylval=valore(); return (NUMERO);}