Analizzatore lessicale
Un Analizzatore lessicale, avvolte chiamato scanner o lexer, è un programmma, o un parte di un programma (vedi compilatori e parsers), che si occupa di analizzare lessicalmente un dato input, genericamente il codice sorgente di un programma.
Quindi il compito di un analizzatore lessicale è di analizzare uno stream di caratteri in input e produrre in uscita uno stream di tokens.
Il token è un elemento che ha un tipo e un valore, lessema. I tokens costituiscono gli elementi base su cui andrà ad operare un analizzatore sintattico.
L'individuazione di tokens all'interno di uno stream di caratteri è effettuata attraverso pattern, in italiano modelli.
Funzionamento
Come scritto prima l'analizzatore lessicale individua i tokens attraverso i patterns, prendiamo ad esempio questi patterns:
cifra = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0
numero = cifra cifra*
operatore = + | - | x | /
Dove il simbolo | indica l'or inglese, l'alternativa. Il simbolo *, asterisco, indica che l'elemento che lo precede può essere ripetuto zero o più volte.
Dai modelli sopra riportati abbiamo che una cifra può essere 1 o 2 o 3 .. e così via; un numero è composto da almeno una cifra, e può essere seguito da più cifre. Gli operatori sono quelli classici della matematica.
Se noi diamo in input all'analizzatore lessicale la seguente espressione:
123 + 141 / 725
Ci aspetteremo che l'output sia formato dai seguenti tokens:
| Tipo token | Lessema (valore del token) |
|---|---|
| numero | 123 |
| operatore | + |
| numero | 141 |
| operatore | / |
| numero | 725 |
Da notare come gli spazi bianchi vengano saltati.
Per effettuare questo lavoro gli analizzatori lessicali si basano su un automa a stati finiti deterministico. Si parte da uno stato iniziale, e ci si sposta negli altri stati in base al carattere in ingresso sino a quando non si raggiunge uno stato di accettazione nel quale si può inviare il token in output. Ad esempio per il nostro modello avremmo un automa simile al seguente:
File:Analizzatorelessicale1.png
Si inizia dallo stato iniziale (1), e in base al carattere in arrivo ci si può spostare allo stato 2 o al 4. Se arriva una cifra ci si sposterà al 2, e rimarremmo qui finchè non arriva qualcosa di diverso da una cifra, in tal caso passeremo allo stato 3. In questo stato, stato di riconoscimento, produrremmo il token, in questo caso di tipo numero, e lo invieremo in uscita. Dopo il riconoscimento si tornerà allo stato iniziale sempre con lo stesso valore di prima.
Nel caso del nostro esempio, 123 + 141 / 725, gli spostamenti tra gli stati sarebbero stati i seguenti:
| Carattere | Stato Attuale | Azione |
|---|---|---|
| 1 | 1 | Vai a stato (2) |
| 2 | 2 | Vai a stato (2) |
| 3 | 2 | Vai a stato (2) |
| + | 2 | Vai a stato (3) |
| + | 3 | Produci token di tipo Numero e valore 123 |
| + | 1 | Vai a stato (4) |
| + | 2 | Produci token di tipo Operatore e valore + |
| 1 | 1 | Vai a stato (2) |
| 4 | 2 | Vai a stato (2) |
| 1 | 2 | Vai a stato (2) |
| / | 2 | Vai a stato (3) |
| / | 3 | Produci token di tipo Numero e valore 141 |
e cosi via...
Costruzione di un analizzatore lessicale
Un analizzatore lessicale può essere scritto a mano, ma questo comporterebbe un grosso impiego di tempo. In aiuto ai programmatori vengono strumenti di generazione automatica di lexer, quale ad esempio Lex. Altri strumenti di generazione di analizzatori lessicali sono integrati nei generatori di parsers.