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

P1

Programma

Sorgente

CompilatoreP2

Programma

Oggetto

Linguaggi di Programmazione

Alto livello: Pascal, C, Java

X=Y+5Basso livello: Linguaggio macchina

001 0110010 0001

Il Compilatore ci consente

di 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.Rappresentazione

Intermedia

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 LEX

NUMERO [0-9]

%%

{NUMERO} {yylval=valore();

return (NUMERO);}