Linguaggi e compilatori
Corso di Laurea in Informatica
Mauro Leoncini
A.A. 2023/2024
Mauro Leoncini L&C Anno Accademico 2023/24 1 / 29
Linguaggi e compilatori
1 Analizzatore lessicale (lexer)
Riconoscimento di token
Altri compiti del lexer
Il lexical analyzer Lex
Mauro Leoncini L&C Anno Accademico 2023/24 2 / 29
Analizzatore lessicale (lexer) Riconoscimento di token
Linguaggi e compilatori
1 Analizzatore lessicale (lexer)
Riconoscimento di token
Altri compiti del lexer
Il lexical analyzer Lex
Mauro Leoncini L&C Anno Accademico 2023/24 3 / 29
Analizzatore lessicale (lexer) Riconoscimento di token
Lo schema del front-end
Il compito principale del lexer è di trasformare la sequenza di caratteri
che costituisce l'input del compilatore (cioè il programma) in una
sequenza di token
Riconsideriamo lo schema del front-end (già visto a suo tempo)
token
Analizzatore
Codice
Prog. AST semantico e
Lexer Parser inter-
sorgente generatore di
medio
codice intermedio
getT oken
Symbol
table
Il lexer agisce come subroutine del parser e, ad ogni chiamata,
restituisce a quest'ultimo un token
Ma che cos'è esattamente un token?
Mauro Leoncini L&C Anno Accademico 2023/24 4 / 29
Analizzatore lessicale (lexer) Riconoscimento di token
Token
Un token è un oggetto astratto, che rappresenta un elemento
signi cativo per l'analisi sintattica
Esempi di token sono i numeri, gli identi catori e le parole riservate di
un linguaggio di programmazione.
Ci sono altre due nozioni da introdurre allo scopo di comprendere bene
che cosa si intenda quando si parla di token
La prima è quella di lessema, cioè una sotto-stringa dell'input che è
istanza concreta di un token: ad esempio x e somma possono essere due
lessemi riconosciuti come token di tipo identi catore
La seconda è una descrizione formale (nella terminologia inglese si usa
il termine pattern) che consente allo scanner di riconoscere i lessemi
come istanze di particolari token
È facile immaginare, anche da quanto detto nel precedente set di slide,
che le descrizioni formali dei lessemi da riconoscere come token sono
proprio le espressioni regolari
Mauro Leoncini L&C Anno Accademico 2023/24 5 / 29
Analizzatore lessicale (lexer) Riconoscimento di token
Token
Possiamo ora essere più precisi nel de nire i token
Un token è un oggetto caratterizzato da due attributi, un nome
obbligatorio e un valore opzionale.
Il token name è un identi catore, che può essere arbitrario (anche se è
opportuno che sia anche signi cativo); ciò che è cruciale è che uno
stesso nome abbia lo stesso senso per lexer e parser
Indicheremo i token name usando il grassetto
Tipici nomi per i token sono id, number, literal, ...
Il valore non è presente sempre, ma è necessario per denti catori e
numeri.
Nel caso degli identi catori, il valore è proprio il corrispondente
lessema, mentre nel caso dei numeri è il valore numerico del lessema
Mauro Leoncini L&C Anno Accademico 2023/24 6 / 29
Analizzatore lessicale (lexer) Riconoscimento di token
Esempio
Supponiamo che la porzione di input da analizzare abbia come pre sso
somma = 0
Alle richieste del parser, il lexer restituisce in sequenza i token
(id, “somma”)
assignment
(number, 0)
Si noti la dierenza fra i due valori presenti: nel caso di id il valore è
una stringa (lo stesso lessema presente nell'input) mentre per
number il valore è il numero 0
Abbiamo cercato di evidenziare questo fatto usando gli apici (oltre che
il font typewriter usato sempre per le stringhe)
Nel parsing, come vedremo, il valore di un token non è importante e
dunque ci riferiremo ai token con il solo token name
Il valore di un token serve ovviamente nella generazione del codice
Mauro Leoncini L&C Anno Accademico 2023/24 7 / 29
Analizzatore lessicale (lexer) Riconoscimento di token
Pattern, lessemi e (nomi di) token
La seguente tabella riassume, mediante alcuni esempi, i concetti che
abbiamo presentato
Token name Pattern Esempio di lessema
id [:alpha:][:alnum:]* pippo1
number [+- ][1-9][:digit:]* -3.14
comparison < | > | <= | >= | = | != <
literal [:alpha:] Pi greco
if if if
while while while
Solo per ragioni di spazio, nella precedente tabella il pattern che
descrive il token number non include la notazione scienti ca.
Mauro Leoncini L&C Anno Accademico 2023/24 8 / 29
Analizzatore lessicale (lexer) Altri compiti del lexer
Linguaggi e compilatori
1 Analizzatore lessicale (lexer)
Riconoscimento di token
Altri compiti del lexer
Il lexical analyzer Lex
Mauro Leoncini L&C Anno Accademico 2023/24 9 / 29
Analizzatore lessicale (lexer) Altri compiti del lexer
Scanning e altre funzioni
L'analizzatore lessicale è l'unico modulo del compilatore che legge
l'input testuale
Il termine scanner viene a volte utilizzato per riferirsi all'analizzatore
lessicale nel suo insieme
Tuttavia esso è propriamente il modulo separato che eettua la lettura
del testo, utilizzando opportune tecniche di buering
L'analizzatore lessicale vero e proprio, nel processo di tokenizzazione,
procede anche a riconoscere e ltrare commenti, spazi e altri
caratteri di separazione
Deve inoltre associare gli eventuali errori trovati da altri moduli del
compilatore (in particolare dal parser) alle posizioni (righe di codice)
dove tali errori si sono veri cati allo scopo di emettere appropriati
messaggi diagnostici
Mauro Leoncini L&C Anno Accademico 2023/24 10 / 29
Analizzatore lessicale (lexer) Altri compiti del lexer
Progetto di un analizzatore lessicale
Procederemo ora nel modo seguente
Dapprima introdurremo uno strumento per la generazione di
analizzatori lessicali
Impiegheremo poi lo strumento per realizzare il modulo di
riconoscimento dei token del linguaggio XXX
Solo in un secondo momento vedremo i principi interni di
funzionamento di un lexer, cioè come sia possibile, a partire dalle
espressioni regolari, realizzare in modo automatico il riconoscimento di
token de niti da quelle espressioni regolari
Mauro Leoncini L&C Anno Accademico 2023/24 11 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Linguaggi e compilatori
1 Analizzatore lessicale (lexer)
Riconoscimento di token
Altri compiti del lexer
Il lexical analyzer Lex
Mauro Leoncini L&C Anno Accademico 2023/24 12 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Che cosa è Lex
Lex è un generatore di analizzatori lessicali.
Si tratta cioè di un software in grado di generare automaticamente un
altro programma che riconosce stringhe di un linguaggio regolare.
Non solo, il software generato da Lex ha capacità di scanning, cioè di
acquisire le stringhe da analizzare in sequenza (da le o standard
input) e di passare l'output ad un altro programma, tipicamente un
parser.
Lex può quindi essere uno strumento prezioso nella realizzazione di un
compilatore.
Mauro Leoncini L&C Anno Accademico 2023/24 13 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Come funziona Lex
L'input per un programma Lex è costituito essenzialmente da un
insieme di espressioni regolari/pattern da riconoscere.
Inoltre, ad ogni espressione regolare E, l'utente associa un' azione,
espressa sotto forma di codice in linguaggio C.
Tale codice andrà in esecuzione quando l'analizzatore lessicale
prodotto da Lex avrà riconosciuto un lessema descritto da E
NOTA. Il programma Lex originale era utilizzabile solo con il
linguaggio C. La versione oggi disponibile in ambiente Linux
(denominata Flex) può lavorare anche con il C++
Mauro Leoncini L&C Anno Accademico 2023/24 14 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Schema d'uso di Lex
Sorgente
Compilatore [Link].c/
Lex
Lex [Link]
(lexer.l)
[Link].c/ Compilatore
[Link]
[Link] C/C++
Running token
charstring
[Link] sequence
Mauro Leoncini L&C Anno Accademico 2023/24 15 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Struttura generale di un programma Lex
Un generico programma Lex contiene tre sezioni, separate dal dalla
sequenza %%
Dichiarazioni
%%
Regole di traduzione
%%
Funzioni ausiliarie
La sezione Dichiarazioni può contenere de nizione di
costanti/variabili, speci ca di header le e, soprattutto, de nizioni
regolari, cioè espressioni regolari con un nome
La sezione intermedia speci ca le regole di traduzione, ovvero le
descrizioni delle azioni che devono essere eseguite a seguito del
riconoscimento dell'istanza di un pattern
Mauro Leoncini L&C Anno Accademico 2023/24 16 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Struttura generale di un programma Lex (continua)
L'ultima sezione può contenere funzioni aggiuntive (che vengono
tipicamente invocate nella parte relativa alle regole di traduzione)
Se lo scanner non è utilizzato come routine del parser o di altro
programma, quest'ultima sezione contiene anche il main program.
Se presente, il main dovrà ovviamente contenere la chiamata allo
scanner prodotto automaticamente dal compilatore Lex
Nel caso del C, l'entry point dello scanner è la funzione yylex
Nel caso del C++, Lex produce una classe FlexLexer e lo scanner si
invoca chiamando il metodo yylex
Il lessema corrispondente al token riconosciuto viene registrato dallo
scanner nella variabile globale yytext
Mauro Leoncini L&C Anno Accademico 2023/24 17 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Un primo, semplicissimo, tokenizer
%{
# include < iostream >
using namespace std ;
%}
DIG [0 -9]
DIG1 [1 -9]
/* read only one input file */
% option noyywrap C ++
%%
"+" { cout << " operatore <" << yytext [0] << " >" << endl ;}
" -" { cout << " operatore <" << yytext [0] << " >" << endl ;}
"=" { cout << " operatore <" << yytext [0] << " >" << endl ;}
{ DIG1 }{ DIG }* { cout << " numero <" << yytext << " >" << endl ;}
. { cout << " Altro token <" << yytext [0] << " >" << endl ;}
%%
int main ( int argc , char ** argv ) {
FlexLexer * lexer = new yyFlexLexer ;
lexer -> yylex ();
return 0;
}
Mauro Leoncini L&C Anno Accademico 2023/24 18 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Analizzare più di un le
Al termine dell'esecuzione, yylex invoca il metodo yywrap.
Questo può quindi essere utilizzato per aprire un secondo le di input
e chiamare nuovamente yylex
Se viene utilizzata l'opzione noyywrap, il metodo yywrap non viene
invocato e non deve essere ride nito.
Il le wrap.l nell cartella condivisa su gdrive illustra un esempio di
utilizzo di yywrap, valido per flex con l'opzione -+ (si veda la slide
successiva).
Mauro Leoncini L&C Anno Accademico 2023/24 19 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Compilazione ed esecuzione
Il programma Lex ( le di norma con estensione .l) viene compilato
con il seguente comando
flex -+ -o <source>.cpp <filename>.l
dove <filename> e <source> indicano i nomi rispettivamente del le
Lex e del programma C++ generato.
L'opzione -+ indica proprio che il target è il linguaggio C++
Se si omette l'opzione -o, il le viene creato con il nome default
[Link]
Il le C++ può essere compilato nel modo noto
Mauro Leoncini L&C Anno Accademico 2023/24 20 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Applicazioni standalone
Uno strumento come Lex può essere utilmente impiegato anche per la
creazione di applicazioni standalone
Ad esempio, il programma Lex riportato nelle slide seguenti emula
l'utility wc di Linux; conta cioè caratteri, parole e linee presenti in un
le
Del programma daremo in realtà due versioni, di fatto identiche ma
organizzate in modo diverso, la prima in un le singolo e la seconda su
due le, che andremo a compilare separatamente.
I programmi mettono in evidenza l'esistenza di un'altra variabile
globale, yyleng, che memorizza la lunghezza del lessema che ha
provocato il match
Mauro Leoncini L&C Anno Accademico 2023/24 21 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Versione di wc realizzata con Lex ( le singolo)
%{
# include < iostream >
using namespace std ;
unsigned long charCount = 0, wordCount = 0 , lineCount = 0;
%}
word [^ \t\ n ]+
eol \ n
% option noyywrap C ++
%%
{ word } { wordCount ++; charCount += yyleng ; }
{ eol } { charCount ++; lineCount ++;}
. charCount ++;
%%
int main ( int argc , char ** argv ) {
FlexLexer * lexer = new yyFlexLexer ;
lexer -> yylex ();
cout << lineCount << " " << wordCount << " "
<< charCount << endl ;
return 0;
}
Mauro Leoncini L&C Anno Accademico 2023/24 22 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
File Lex, senza main, per wc
%{
# include < iostream >
using namespace std ;
unsigned long charCount = 0, wordCount = 0 , lineCount = 0;
%}
word [^ \t\ n ]+
eol \ n
% option noyywrap C ++
%%
{ word } { wordCount ++; charCount += yyleng ; }
{ eol } { charCount ++; lineCount ++;}
. charCount ++;
%%
Il main program (prossima slide) deve importare l'header le
FlexLexer.h
Mauro Leoncini L&C Anno Accademico 2023/24 23 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Main program per l'applicazione wc
# include < iostream >
# include < FlexLexer .h >
using namespace std ;
extern unsigned long charCount , wordCount , lineCount ;
int main () {}
FlexLexer * lexer = new yyFlexLexer ;
lexer -> yylex ();
cout << lineCount << " " << wordCount << " "
<< charCount << endl ;
return 0;
}
Se supponiamo che questo le abbia nome [Link], la
compilazione dell'applicazione può procedere nel modo seguente
g++ -c [Link]
g++ -c [Link]
g++ -o wc wcsep.o wcmain.o
Mauro Leoncini L&C Anno Accademico 2023/24 24 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Il linguaggio Kaleidoscope
Utilizzeremo questo semplice linguaggio per studiare su un caso
concreto i concetti teorici analizzati a lezione
[Link]
Seguiremo abbastanza fedelmente il tutorial
docs/tutorial/MyFirstLanguageFrontend/[Link]
Introdurremo però alcune importanti varianti, soprattutto
nell'implemetazione di lexer e parser
Esattamente come nel tutorial procederemo arricchendo per gradi il
linguaggio
Nella prima versione, Kaleidoscope permette solo la de nizione di
funzioni e la scrittura di espressioni aritmetiche
NOTA: Nei riferimenti al tutorial, la scrittura <tutorial> sarà da
considerare una sorta di macro per l'url sopra riportato
Mauro Leoncini L&C Anno Accademico 2023/24 25 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Il linguaggio e il suo lessico
In questa prima versione, Kaleidoscope accetta soltanto tre tipi di
frasi, che presentiamo attraverso tre esempi
1 def g(x y z) x*y+z;
2 extern f(x y);
3 3*f(3,4)-x;
La prima frase descrive la forma delle de nizioni di funzione
La seconda l'utilizzo di funzioni esterne
La terza suggerisce in ne la possibilità di utilizzare espressioni
aritmetiche, che includano le quattro operazioni fondamentali e
l'utilizzo di (chiamate di) funzioni
Tutto ciò ci consente di comprendere quale sia (a questo punto) il
lessico del linguaggio
Mauro Leoncini L&C Anno Accademico 2023/24 26 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Il lessico di Kaleidoscope (prima versione)
Fanno parte del lessico
Gli operatori aritmetici +, -, * (che denota la moltiplicazione) e /
Le parentesi tonde e la virgola
Il punto e virgola (separatore delle espressioni)
Le due parole chiave def e extern
I numeri interi e decimali
Gli identi catori
Andremo a breve a de nire le espressioni regolari che descrivono i
possibili lessemi delle categorie lessicali appena introdotte
Prima però vogliamo brevemente procedere con esempi di
riconoscimento di token utilizzando il programma disponibile nel
tutorial
Mauro Leoncini L&C Anno Accademico 2023/24 27 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Il Lexer di Kaleidoscope
Il codice per il Lexer è scaricabile all'url
<tutorial>/[Link]#full-code-listing
Il codice in questione eettua anche parsing e costruzione dell'AST.
Per ora la nostra attenzione è solo sull'analisi lessicale e dunque il
lexer è stato scorporato e inserito in un le a parte
Abbiamo anche predisposto un main per testare il lexer
Tutto il software si trova nella cartella condivisa GDRIVE
(sotto-cartella Kaleidoscope1 ).
Compilazione ed esecuzione (usando clang):
> clang++ -c [Link]
> clang++ -c [Link]
> clang++ -o klex lexer.o main.o
> echo "3*x-2;" | ./klex
Mauro Leoncini L&C Anno Accademico 2023/24 28 / 29
Analizzatore lessicale (lexer) Il lexical analyzer Lex
Il lexer realizzato con Lex
Il codice che abbiamo appena descritto è stato realizzato (dagli autori
del tutorial) in modo diretto, senza ausilio di strumenti automatici
In questa fase del nostro percorso, vogliamo semplicemente ottenere lo
stesso risultato (ovvero il riconoscimento di un sottoinsieme dei token)
usando lex
Gli esempi già presentati sono su cienti per svolgere questo primo
esercizio.
L'aspetto cruciale consiste, come è ovvio, nella de nizione delle
espressioni regolari
A riguardo vanno distinti
identi catori e parole chiave
numeri interi e decimali
operatori aritmetici e confronto (solo <)
separatori
eventuali token formati da un singolo carattere
Mauro Leoncini L&C Anno Accademico 2023/24 29 / 29