Generareanalizzatori lessicali conFlex -...

UNIVERSITÀ DEGLI STUDI DI ROMA “TOR VERGATA”

Generare analizzatori lessicali con Flex

Corso di laurea triennale in Informatica Corso di linguaggi e traduttori

Prof.ssa : Dora GiammarresiTutor : Francesca Capri

Anno Accademico 2010/2011

TerminologiaTre concetti necessari per comprendere la fase di

analisi lessicale:� TOKEN: simbolo che rappresenta uno specifico tipo

di lessema, per esempio una parola chiave o una sequenza di caratteri che denota un identificatore. In genere è rappresentato da un nome ed un attributo opzionale.LESSEMA: sequenza di caratteri del programma � LESSEMA: sequenza di caratteri del programma sorgente che corrisponde al pattern di un token(istanza specifica di un token).

� PATTERN o MODELLO: descrizione compatta delle possibili forme che il lessema di un token può assumere. Nel caso di una parola chiave il pattern è semplicemente la sequenza di caratteri che formano quella parola chiave.

16/11/2010Linguaggi e traduttori A.A. 2010/2011 2

Esempi : token, pattern e lessema

TOKEN LESSEMA PATTERN

if if if

id count, a123 [A-Za-z] ([A-Za-z]|[0-9])*

16/11/2010 Linguaggi e traduttori A.A. 2010/20113

id count, a123 [A-Za-z] ([A-Za-z]|[0-9])*

digit 0, 3 [0-9]

L’ analisi lessicale nel compilatore

Fasi di un compilatore:

L’analisi lessicale è la prima fase


prima fase del processo di compilazione

L’ analisi lessicale nel compilatore

Facendo un ingrandimento della parte cerchiata nell’immaginerelativa al compilatore, si può vedere meglio come lavora un

analizzatore lessicale e come questo interagisce con un analizzatore sintattico o parser.


Analizzatore lessicale

Analizzatore sintatticoProgramma

sorgente

token

getNextToken

Tabella

Ruolo dell’ analizzatore lessicale

Data in input una sequenza di caratteri (stringa che forma il programma sorgente) di un alfabeto, un analizzatore lessicale o scannero lexer , li raggruppa in lessemi e verifica se questi possono essere decomposti in una sequenza di token, tale che ogni tokensequenza di token, tale che ogni tokenappartenga al lessico:

� in caso positivo, restituisce in uscita la sequenza di token corrispondente ai lessemi trovati.

� in caso negativo, restituisce un errore lessicale.

Linguaggi e traduttori A.A. 2010/20116

16/11/2010

Ruolo dell’ analizzatore lessicale

L’analizzatore lessicale è in grado di svolgere ulteriori operazioni e/o compiti:

� Elimina e/o ignora spazi vuoti e commenti(spazi, tabulazioni, ritorni a capo)Elimina e/o ignora spazi vuoti e commenti(spazi, tabulazioni, ritorni a capo)

� Associa i messaggi di errore prodotti dal compilatore al programma sorgente

� Se nel programma sorgente sono presenti delle macro potrebbe occuparsi della relativa espansione


Un po’ di storia………Esitono molti generatori automatici:

� Lex, Flex, ScanGen,.... : generano un codice in C

� JLex, Sable, Cup, .... : generano un codice in Java

Lex fu il primo generatore di scanner. Esso fu inventato da Mike Lex fu il primo generatore di scanner. Esso fu inventato da Mike Lesk e Eric Shmidt (AT&T Bell Lab) nel 1975. Lex è distribuito con il sistema operativo Unix. Esistono tanti software alternativi al Lex.

Uno dei più conosciuti ed usati è Flex ( Fast Lexical analyser generator) introdotto da Vern Paxson intorno al 1987 per risolvere problemi di efficienza. Esso è frequentemente usato con Bison, un parser generator alternativo a Yacc, ma è comunque utilizzabile come generatore di programmi stand-alone. Flex è un prodotto della Free Software Foundation, Inc.


Flex : introduzione

Flex è quindi un tool che genera analizzatori lessicali, vediamo in che modo:

prende in input un file che specifica il lessico di� prende in input un file che specifica il lessico diun certo linguaggio, solitamente nella forma diespressioni regolari e includendo altre funzioniausiliarie, definizioni di token, .....

� produce in output un codice (scritto in un certolinguaggio) che implementa il ruolo dello scanner.


Flex : generazione di uno scanner

lex.l Compilatore Flex

lex.yy.c

Compilatore a.exe


lex.yy.cCompilatore

C

a.exeoutput(es. sequenza di

token)

File di INPUT

a.exe

Flex : file lex.l

lex.l: file sorgente in formato Flex, che serve

per avere una descrizione dello scanner dagenerare. La descrizione è nella forma dicoppie comprendenti:

� espressione regolare : definiscono rigorosamente gli� espressione regolare : definiscono rigorosamente glielementi che devono essere riconosciuti nel flusso di dati.

� codice C : azioni da effettuare al verificarsi del match

con una RE.

Le coppie, RE e codice C, formano la sezioneREGOLE DI TRADUZIONE del file lex.l


Flex : file lex.yy.c

lex.yy.c: file di codice sorgente C, che

definisce la funzione ‘yylex()’. Questafunzione può essere utilizzata direttamente da una ipotetica funzione main per il recupero dei token e non ritorna al chiamante recupero dei token e non ritorna al chiamante fino a quando non ha esaurito i suoi dati in lettura.


Flex : funzione yylex()

La funzione, ‘yylex()’, scandisce l’input file yyine ritorna il prossimo token, ricopiando sul file yyoutil testo non riconosciuto. Per default, i file yyin e yyout sono inizializzati rispettivamente a stdin e stdout. Il token riconosciuto (una costante, un numero, un'istruzione, ecc…), sarà fornito, con numero, un'istruzione, ecc…), sarà fornito, con l'indicazione del tipo ,al parser (Bison), ogni volta che questo la richiamerà. Il parser in base alle informazioni ricevute, applicherà le regole opportune. L’implementazione di questa funzione sibasa su un DFA che rappresenta le RE. Al termine di ogni azione l’automa si ricolloca sullo stato iniziale, pronto a riconoscere nuovi simboli.


Flex : file a.exe

a.exe : file eseguibile ottenuto compilando il file lex.yy.c tramite un compilatore C. Quando l'eseguibile viene lanciato, analizza il proprio ingresso in cerca di occorrenze delle proprio ingresso in cerca di occorrenze delle espressioni regolari. Ogni volta che ne individua una, viene eseguito il corrispondente codice C.


Flex : struttura dei programmiUn file sorgente in formato Flex consiste di 3 sezioni,

separate da %%:

dichiarazioni

%%%%

regole di traduzione

%%

funzioni ausiliarie


Flex : struttura dei programmiUn file sorgente in formato Flex consiste di 3 sezioni,

separate da %%:

dichiarazioni {sezione opzionale}dichiarazioni

%% obbligatorio anche se la sezione precedente è vuota

regole di traduzione {sezione obbligatoria }

%% possiamo ometterlo se la sezione seguente è vuota

funzioni ausiliarie {sezione opzionale}


Flex : sezione dichiarazioni (1/3)Questa sezione contiene:

� Definizioni regolariOgni definizione è del tipo:

nome definizione

Esempi di definizione: DIGIT [0-9] LETTER [A-Za-z] ID {LETTER}({LETTER}|{DIGIT})*

Il nome sarà lo stesso che, nella sezione regole di traduzione, potrà essere utilizzato per riferirsi alla specifica definizione, attraverso la dicitura {nome}


Flex : sezione dichiarazioni (2/2)� Opzioni

Flex permette il passaggio di opzioni che altrimenti sarebbero dovute essere passate attraverso la riga di comando. Le opzioni vengono passate attraverso la direttiva:

%option nomeopzione

Esempi di opzioni:Esempi di opzioni:

%option main: Flex fornisce un routine main() di default

%option noyywrap: questa direttiva comporta che nonvenga chiamata la funzione yywrap() dopo che è stato raggiunto un

carattere di end-of-file (fine file) e si assume, quindi, che non esistanopiù file da analizzare. La funzione yywrap() dovrebbe, teoricamente,impostare correttamente la variabile globale yyin e ritornare il valorezero se esistono altri file da analizzare, oppure ritornare un valore nonzero nel caso in cui il lavoro da compiere sia giunto al termine (e,quindi, ottenere anche la terminazione nell'esecuzione dello scanner).


Flex : sezione dichiarazioni (3/3)

� segmento di codice CIl codice C, delimitato da

%{ %}sarà ricopiato parola per parola nel file di output lex.yy.clex.yy.c

Esempio di segmento C:%{

#include <stdio.h> #define PAP 1#define PCH 2#define SUM 3

%}


Flex : sezione regole di traduzione (1/3)

Questa sezione è l’unica obbligatoria ed è la più importante del file Flex, perché è qui che vengono specificate:

� le regole di matching

� le azioni da intraprendere per ogni simbolo riconosciutosimbolo riconosciuto

Anche in questa sezione è possibile inserire codice tra%{ e %}. Ciò deve avvenire prima della prima regola. Può servire per esempio per dichiararevariabili locali usate nella routine di scanning.


La sezione regole di traduzione avrà la seguente struttura:

pattern {action}

pattern sono espressioni regolari che permettono di avere un

riscontro con determinate stringhe di caratteri del linguaggio sorgente. Questi pattern possono essere resi più compatti


sorgente. Questi pattern possono essere resi più compatti richiamando in essi i nomi associati alle diverse definizioni come descritto nella sezione dichiarazioni.

action la parte action può :

� Essere vuota (contiene solo ; ), al match del pattern non succede nulla.

� Contenere porzione di codice C, racchiuso tra {} , associata ad uno specifico pattern e solo in presenza di esso sarà eseguito integralmente.

� Contenere solo | indica che quell’azione è definita nella stesso modo della regola che segue.



Esempi di regole di traduzione:{ID} { printf("IDENTIFICATORE\n"); }

[a-z]+ {ECHO;}

\t |\n ;

Direttive speciali che possono essere incluse in un’azione sono:

� ECHO: copia yytext nell’output dello scanner

� REJECT: cerca un'alternativa al match corrente


Flex : sezione funzioni ausiliarie

Quest'ultima sezione contiene semplicemente codice C che sarà copiato così com'è nel file di output lex.yy.c Questa sezione è opzionale e viene spesso usata per contenere funzioni richiamate dallo scanner come supporto all'elaborazione. Di fatto, qua possono essere riportate tutte quelle funzioni utili che

sono richiamate all'interno da qualche azione nella sezione delle regole di traduzione. sono richiamate all'interno da qualche azione nella sezione delle regole di traduzione. Se si vuole generare uno scanner che possa vivere di vita

propria, bisogna fornirlo di una funzione main, tale funzione va inserita proprio in questa sezione.


Flex : osservazioni� Sia nella sezione delle dichiarazioni che in quella delle regole

di traduzione tutto ciò che si trova all'interno della coppia di identificatori %{ e %} viene copiato direttamente nel file di output lex.yy.c senza alcuna modifica. %{ e %} devono apparire a inizio dilinea (non indentati).

� Nella sezione regole di traduzione è possibile inserire codicetra %{ e %}, basta che ciò avvenga prima della prima regola.tra %{ e %}, basta che ciò avvenga prima della prima regola.

� In Flex qualsiasi cosa tra /* e*/ è considerato commento e copiatodirettamente nel file di output lex.yy.c Però ci sono due eccezioni:

1. Nella sezione regole di traduzione i commenti non possonoapparire all’inizio di una linea o immediatamente dopo una listadi stati dello scanner.

2. Nella sezione dichiarazioni i commenti non possono appariresulla linea in cui si trova la direttiva %option


Flex : come avviene il match?

Il programma finale generato da Flex:� legge il suo input un carattere alla volta da sinistra a destra

finché trova il più lungo prefisso di input (quello sarà il corrente lessema) che fa match con uno dei pattern della sezione delle regole di traduzione.

� Il testo corrispondente al match viene reso disponibile � Il testo corrispondente al match viene reso disponibile

attraverso la variabile globale yytext e la sua lunghezza viene

memorizzata in yyleng.� Vengono quindi eseguite le azioni corrispondenti al pattern per

il quale avviene il match.

� Prosegue la scansione dell’input alla ricerca di altri match.


Flex : risoluzione dei conflitti (1/2)Durante il processo di match si possono

presentare due tipologie di conflitti che Flexrisolve grazie a due regole di cui è fornito:

1. Se più prefissi della sequenza d’ingresso soddisfano uno o più pattern, si sceglie sempre il prefisso più lungo possibile

2. Se il prefisso più lungo corrisponde a due o più pattern,

possibile

2. Se il prefisso più lungo corrisponde a due o più pattern, si sceglie il pattern elencato per primo nella sezione delle regole di traduzione.

La seconda regola ci permette di rendere riservate le parole chiave soltanto se si definiscono prima le regole per le parole chiave e poi quelle per gli identificatori.


Flex : risoluzione dei conflitti (2/2)Esempio di conflitto

Dato il file :

%%for {return FOR_CMD;}

format {return FORMAT_CMD;}[a-z]+ {return GENERIC_ID;}[a-z]+ {return GENERIC_ID;}

e la stringa di ingresso “format”, la procedura yylex ritorna il valore FORMAT_CMD, preferendo la seconda regola alla prima perché descrive una sequenza più lunga, e la seconda regola alla terza perché definita prima nel file sorgente.

Se non viene trovato alcun match, viene eseguita la regola di default : il carattere dell’input non riconosciuto viene considerato un match e copiato nell’output.


Flex : come definire i pattern nelle regole?x il carattere 'x'

. ogni carattere eccetto '\n'

[xyz] una classe di caratteri; in questo caso, 'x', 'y' o 'z'

[a-z] una classe con un range; ogni carattere compreso tra 'a' e 'z'

[^A-Z] una classe negata: ogni carattere NON nella classe

r* zero o più r, dove r è un'altra espressione regolare

r+ una o più r

r? zero o una r


r? zero o una r

r{2,5} tra due a cinque r

r{2,} due o più r

r{4} esattamente 4 r

{nome} l'espansione della definizione di nome

(r) r, parentesizzata per raggruppare

rs concatenazione: r seguita da s

r|s alternativa: r oppure s

r/s restrizione: r ma solo se seguita da s

^r r ma solo a inizio linea

r$ r ma solo a fine linea

Flex : variabili e routine predefinite

� int yylex(void) : routine di scanning

� yytext : contiene la stringa che ha appena matchato con

un pattern. Può essere di tipo char * oppure char []

� yyleng : contiene il numero dei caratteri riconosciuti

yylval : � yylval : valore associato al token

� FILE *yyin : input file (default: stdin)

� FILE *yyout : output file (default: stdout)

� unput(c) : rimette il carattere c nella stringa dei simboli da

esaminare

� input() : legge il carattere successivo


Flex : primo programma

Il primo e più piccolo programma Flex ammesso è:

%%

Genera uno scanner che semplicemente prende il suoinput (un carattere per volta) e lo ricopia nel suoinput (un carattere per volta) e lo ricopia nel suooutput, per la regola di default.


Flex : esempio sezione dichiarazioni del file lexer2.l%option noyywrap inserisce la direttiva %option che mi permette

di non chiamare la funzione yywrap()

%{

#define PAP 1

#define PCH 2

#define SUM 3

#define MIN 4

#define MUL 5 codice C racchiuso tra %{ %} che dichiara

#define DIV 6 delle costanti che verranno riportate

#define ID 7 nel file di output

#define NUM 8#define NUM 8

#define MOD 9

#define ASSIGNOP 10

%}

delim [ \t\n]

ws {delim}+

letter [A-Za-z]

digit [0-9] definisco i nomi dei token

number {digit}+(\.{digit}+)?(E[+\-]?{digit}+)?

id {letter}({letter}|{digit})*


Flex : esempio sezione regole di traduzione del file lexer2.l

%% richiamo il token ws definito nella sezione dichiarazioni

{ws} {}

{id} {printf("ID \n"); }

{number} {printf("NUM \n");}

"+" {printf("SUM \n");}

"-" {printf("MIN \n");}"-" {printf("MIN \n");}

"*" {printf("MUL \n");}

"/" {printf("DIV \n"); } regole di traduzione

"%" {printf("MOD \n"); }

"(" {printf("PAP \n");}

")" {printf("PCH \n");}

"=" {printf("ASSIGNOP \n");}

"$" {return 0;}


Flex : esempio sezione funzioni ausiliarie del file lexer2.l

%%

int main()

{

int a;

a = yylex(); implemento il main che contiene yylex() a = yylex(); implemento il main che contiene yylex()

system("PAUSE");

return 0;

}


Flex : compilazione dei file

� Per prima cosa inserire i percorsi completi in cui sono installati Flex e il compilatore C, più la cartella bin, nella variabile di sitemapath.

Esempio:

C:\Dev-Cpp\bin (compilatore C)

C:\Program Files (x86)\GnuWin32\bin (flex)

� Posizionarsi tramite shell nella cartella dove vi sono i file da compilarecompilare

� Digitando flex nomeFile.l si compila il file flex e si crea il file lex.yy.c

Esempio:

flex lexer2.l

� Digitando gcc lex.yy.c si ottiene il file eseguibile a.exe


Link utili

� Dove scaricare Flex:

http://flex.source forge.net/

� Manuale di Flex:

http://flex.sourceforge.net/manual/http://flex.sourceforge.net/manual/

� Compilatore C:

http://www.bloodshed.net/download.html

� Materiale relativo alle espressioni regolari:

http://it.wikipedia.org/wiki/Espressione_regolare


Generareanalizzatori lessicali conFlex -...

Documents

Transcript of Generareanalizzatori lessicali conFlex -...