Analizzatore lessicale
Un analizzatore lessicale, a volte chiamato scanner o lexer, è un programma, o una parte di un programma (vedi compilatori e parser), 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 token.
Il token è un elemento che ha un nome, il token name, e un valore, tipicamente il lessema ma può trattarsi anche di un insieme di informazioni elementari come il tipo del numero o il punto del programma in cui è definito. I token costituiscono gli elementi base su cui andrà ad operare un analizzatore sintattico.
L'individuazione di token all'interno di uno stream di caratteri è effettuata attraverso pattern (schemi, modelli).
Funzionamento
modificaCome scritto prima l'analizzatore lessicale individua i token attraverso i pattern, definiti attraverso delle espressioni regolari. Prendiamo ad esempio questi pattern:
cifra = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 numero = cifra cifra* operatore = + | - | x |
Dove il simbolo | indica l'operatore logico OR, 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 token:
| 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, strettamente collegati alle espressioni regolari. 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:
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) |
| + | 4 | 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 così via...
Costruzione di un analizzatore lessicale
modificaUn 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 parser.