Swappa :: LEX

Torna alla pagina di traduttori

 :: LEX ::

LEX

 definizioni
 %%
 regole
 %%
 subroutine (codice C dell'utente)

File minimo:

%%

E' solo un separatore. La parte obbligatoria è quella delle regole: le def e le sub sono opzionali. Sarebbe il separatore che introduce la sezione delle regole. Il secondo separatore non è obbligatorio perché le sub non sono obbligatorie.

Se non ci sono regole, allora esegue il comportamento di default: ricopia in output. Per compilare, supponendo di aver salvato in es1.l, si fa semplicemente

 flex es1.l

e salta fuori il file lex.yy.c (nome di default) che contiene lo scanner.

Questo file .c non contiene il main, perché presuppone di essere chiamato da qualcun altro. Inoltre non contiene la funzione yywrap che viene chiamata per sapere se si è raggiunta la fine del file (yywrap restituisce 1, se no restituisce 0 se non si è ancora arrivati alla fine del file.

Per compilare, devo linkare con la libreria di lex che contiene le robe mancanti:

 gcc lex.yy.c -ll

Oppure, possiamo scriverle direttamente nel file che diamo in pasto a LEX. Nella sezione routine ausiliarie, aggiungiamo

 int yywrap() {
   return 1;
 }

 int main() {
   yylex();
   return 0;
 }

Compilando con

 gcc lex.yy.c

non è necessario linkare le librerie perché ho già definito le funzioni che servono. Questo "scanner", quando viene eseguito, altro non fa che fare echo di quello che scrivo.

Scrivere le regole

Nella teoria, le espressioni regolari hanno questi operatori:

 a = carattere semplice
 a.b = concatenazione
 a + b = a o b
 a* = 0 o n ripetizioni di a

La sezione regole è fatta da una sequenza di regole, sottoforma tabellare, in cui c'è una regexp seguita dall'azione che voglio intraprendere.

 regexp azione

Le regexp vanno scritte in una certa sintassi (quella di grep). L'azione è invece un'istruzione C. Se è un'istruzione singola, la si scrive direttamente. Se invece è un blocco, allora uso le parentesi graffe. Sono separate da uno spazio

Vediamo di scrivere un traduttore che traduce alcune parole da British English in American English. Ad esempio, in British colore si scrive colour, mentre negli USA è color. Benzina = petrol in Inghilterra, gas in America. Vasca da bagno = bath in Inghilterra, bathtub in America. Quindi, quando legge una di queste parole, deve convertirla in americano.

 %{ 
 #include <stdio.h> 
 %}
 
 colour      printf("color")
 mechanise   printf("mechanize");
 petrol      printf("gas")
 bath        printf("bathtub")

Esercizio

Voglio un programma che mi traduca in inglese la seguente frase:

 Io vorrei avere un cane e un gatto.

 
 io      printf("I");
 vorrei  printf("would like");
 gatto   printf("cat");
 cane    printf("dog");
 avere   printf("to have");
 un      printf("a");
 e       printf("and");

Funziona. Se scrivo

 io vorrei      avere un    cane   e  un gatto

il programma la ricopia direttamente. Se vogliamo invece un po' di formattazione aggiuntiva, mi occorrono alcune regole per definire meglio le espressioni regolari.

 \n   a capo
 \t   tab
 \b   backspace

Le parentesi [] mi rappresentano classi di carattere, di cui deve matcharne uno solo. Ad esempio:

 [0-9]

mi matcha un qualsiasi carattere che va da 0 a 9: la stringa 1 viene riconosciuta come appartenente a quella classe, ma la stringa 11 no.
Nelle classi di carattere posso anche mettere uno spazio:

[ ]

che serve per riconoscere il singolo spazio, e anche

 [\n]

che riconosce il singolo "a capo".

Per riconoscere ogni carattere tranne l'a capo, uso il . (sì, è proprio un punto). Ad esempio, .* = una qualsiasi sequenza di caratteri in una riga.

Poi, c'è l'operatore * delle regexp standard, che può essere tradotto in modo più potente in LEX:

? = 0 o 1 occorrenza
+ = 1 o più occorrenze
* = 0 o più occorrenze
{x,y}, con x minore di y = da x a y occorrenze

Questi operatori si applicano al simbolo che li precede, che può essere un singolo carattere o qualcosa tra parentesi tonde.

Ad esempio,

ab?

matcha con a oppure ab. Se avessi voluto che matchasse con la stringa vuota oppure con ab avrei dovuto scrivere così:

 (ab)

Se vogliamo che gli spazi vengano levati, aggiungo la regola

 [ ]+   printf(" ");

oppure

 " "+   printf(" ");

Ma vogliamo fare ancora meglio. Ad esempio, eliminare gli spazi all'inizio della riga. Occorrono altri operatori per le regexp.
All'interno delle [] il segno - può avre diversi significati:

all'inizio o alla fine della classe, indica semplicemente il segno -
se lo uso in mezzo a dei caratteri, allora è un intervallo della codifica ASCII, come in 0-9 oppure a-b

Il segno ^ ha significati diversi a seconda che si trovi all'interno delle [ ] oppure fuori:

se si trova all'inizio della [], vuol dire nega il resto
se è al di fuori delle [ ], ma sempre all'inizio di una regexp, indica inizio riga

Il simbolo $ serve invece per dire alla fine della riga, e lo metto alla fine della mia regexp

ab$

Quindi, per levare gli spazi all'inizio metterei una regola

 ^" "     printf("");

Le alternative si possono scrivere in due modi:

uno è quello di mettere le alternative all'interno di una classe, perché come dicevamo sopra il match deve avvenire con uno solo dei suoi elementi
l'altro è quello di mettere una |: a|b vuol dire a o b

E' anche possibile costituire delle costanti in questo modo:

 {numero}     [0-9]+

in cui associo la regexp [0-9]+ con l'etichetta {numero}. Posso poi scrivere regole così:

 {numero}   printf("Brao bao bab");

Altre complicazioni

In inglese sia gatto che gatta si traducono con cat. Io vorrei tradurre entrambi gli animali con cat. Ecco tre regole alternative ma di pari funzionalità, in base a quello che abbiamo spiegato sopra:

 gatt(a|o)   printf("cat");
 gatt[ao]    printf("cat");
 gatta|o     printf("cat");

Se voglio cane e cagna, allora metto

 ca(ne|gna)   printf("dog");

Vogliamo però anche tradurre il mio e la mia con my. Pertanto devo matchare entrambe le cose. Posso scrivere due regole distinte, una per il mio e una per la mia.
Ma c'è anche uno sgamo strano: se nelle azioni metto una | dico a LEX che, in caso di match con quella regexp, deve eseguire l'azione della riga successiva. Pertanto, potrei scrivere:

 "il mio"   |
 "la mia"   printf("my");

Se voglio invece il tutto in una singola riga, potrei scrivere

 (il)|(la)[ ]+mio|a    printf("my");

ma non funziona molto bene...

Queste invece funzionano:

 [ \t]+mi(a|o)[ \t]+    |
 (((I|i)l)|((L|l)a))" "+mi(o|a)    printf("my");

Riassunto degli operatori per le espressioni regolari

. = qualsiasi carattere tranne l'a capo
\n = a capo
* = zero o più occorrenze
+ = uno o più
? = zero o uno
^ = inizio linea
$ = fine linea
a|b = alternativa
(ab)+ = raggruppamento (le parentesi tonde)
"a+b" = espressione letterale a+b (il + non viene interpretato)
[] = classe di caratteri. Dentro le quadre, le tonde perdono significato e diventano semplici caratteri. Nelle classi, il ^ diventa una negazione o un letterali.
- [a-z] = un qualsiasi carattere alfabetico
- [a\-z] = un carattere tra a, - e z (la \- fa perdere il significato al trattino e lo tratta come letterale)
- [A-Za-z0-9] = un qualsiasi alfanumerico
- [ \t\n] = uno spazio vuoto
- [^ab] = qualsiasi cosa tranne a, b
- [a^b] = qui il ^ diventa un letterale, quindi vuol dire: uno qualsiasi tra a, ^, b
- [a|b] = uno tra a, |, b (nota la differenza con (a|b), che vuol dire: a o b)

Regole più complesse

 [0-9]+     printf("Ho visto un intero: %s\n", yytext);

In questa regola d'esempio, stiamo utilizzando una variabile che ci viene offerta da Lex. Ce n'è un'altra: yylength.

yytext = contiene la stringa che ha appena matchato la mia espressione
yylength = contiene la lunghezza della stringa che ha appena matchato la mia espressione

 .   /* non fa nulla*/

Questa regola serve per ignorare i caratteri. Come abbiamo visto all'inizio, se non c'è nessuna regola, LEX fa echo a schermo. Qui la regola per riconoscere i caratteri c'è, ma la sua azione è nulla, quindi non fa niente.

 [0-9]+ printf("Ho trovato un numero: %s\n", yytext);
 [a-zA-Z0-9]+ printf("Ho trovato una parola: %s\n", yytext);

A questo punto, queste due regole sono autoesplicative. Da notare che queste regole riconoscono numeri (interi) e parole, ma i segni di interpunzione vengono echoati perché non c'è nessuna regola che li matcha.

Utilizzare costanti

Nella parte delle definizioni, posso mettere robe del genere (viste anche prima) per facilitare la scrittura delle espressioni regolari.

Per esempio, abbiamo le seguenti costanti:

 digit [0-9]
 letter [a-zA-Z]

vogliamo un lexer che

riconosca gli identificatori (sequenze di caratteri che iniziano con una letter e sono seguiti da letter o digit)
stampi a video l'identificatore
ne stampi il numero alla fine del programma

Ecco la soluzione:

 %{ 
 #include <stdio.h> 

 int numID = 0;

 %}
 digit [0-9]
 letter [a-zA-Z]

 

 {letter}{letter}*{digit}* {
				printf("Ho trovato l'identificatore %s\n", yytext);
				numID ++;
			  }

 {digit}+ /* non faccio nulla */
 

 int yymatch() {
  printf("YYMATCH: trovati %d identificatori\n", numID);
  return 0;
 }

 int yywrap() {
   return 1;
 }

 int main() {
  yylex();
  printf("MAIN: Numero di identificatori trovati = %d\n", numID);
  return 0;
 }

Esercizio

Voglio un lexer che, dopo aver letto un file, mi dica semplicemente:

numero di caratteri letti
numero di parole lette
numero di righe lette

 %{ 
 #include <stdio.h> 
 int numChar = 0;
 int numLines = 0;
 int numWords = 0;
 %}
 digit [0-9]
 letter [a-zA-Z]
 
 [^ \t\n]+ {
		    // Numero di caratteri
		    printf("Trovata parola %s \n", yytext);
		    //numChar += strlen(yytext);yylength
		    numChar += yyleng;
		    // Numero di parole
                    numWords ++;
		  }

 \n                {
                    // Numero di righe

                    numLines ++;
		  }
 [ \t\n] {
          numChar ++;
        }
 
 int yywrap() {
   return 1;
 }

 int main() {
   yylex();
   printf("MAIN: Numero di caratteri trovati = %d\n", numChar);
   printf("MAIN: Numero di parole trovate = %d\n", numWords);
   printf("MAIN: Numero di righe trovate = %d\n", numLines);
   return 0;
 }

Torna alla pagina di traduttori