Vediamo ora come operare l'analisi lessicale, ovvero la trasformazione di una stringa in ingresso in una lista di token. Descriveremo questi token mediante un certo tipo di espressioni che corrispondono in modo naturale a degli automi dai quali si può estrarre un programma di riconoscimento.
Lo scopo dell'analisi lessicale è quello di riconoscere nel codice in input alcuni gruppi di caratteri che corrispondono a specifici simboli, in modo da creare una lista di token da far poi analizzare all'analizzatore sintattico.
Un token è una coppia la cui prima componente è il nome (il simbolo che identifica una cerca categoria sintattica, quale può essere un identificatore, un operatore matematico, ecc) e la seconda è il valore del token (lo specifico operatore, ad esempio).
In sostanza creare un analizzatore lessicale significa specificare una lista di token; l'analizzatore poi andrà a riconoscere nelle sequenze di caratteri in ingresso le "istanze" (i valori) dei vari token.
Le sequenze di caratteri sono associate ad un token mediante i pattern, cioè sequenze generali che i token possono assumere. I pattern possono essere descritti mediante regex (regular expressions).
Per definizione una strinza in ingresso che corrisponde ad un certo pattern si dice lessema. Possono esserci token a cui corrispondono anche infiniti lessemi, ad esempio i token identificatore, a cui corrispondono tutti i nomi che un programmatore potrebbe mai dare ad una variabile.
Di seguito il nome dei token verrà indicato in maiuscolo, ad esempio $\lang N,v\rang$ e ci riferiremo ad un tonek con il suo nome.
Sia $A$ un alfabeto fissato. Seguono a mitraglietta le definizioni:
E, per non annoiarci, definiamo le operazioni tra stringhe qui sotto.