I linguaggi umani europei sono codificati utilizzando un ristretto insieme di simboli, i caratteri dell'alfabeto; tuttavia sono troppo pochi per descrivere un insieme di concetti sufficiente per l’uso: non si considerano infatti i singoli caratteri ma i loro raggruppamenti in parole.

Analogamente, nei linguaggi formali, i programmi sono codificati utilizzando un ristretto insieme di simboli, di solito l'ASCII, e anche in questo caso si considerano unità non tanto i singoli caratteri ma dei raggruppamenti significativi, i token appunto. Un compilatore tuttavia riceve in input una sequenza di caratteri ASCII ed il suo primo compito è quello di “spezzettare” l'input in token.

L'operazione di tokenizzazione può essere svolta in vari modi. Si può scrivere direttamente un programma in C, o si può utilizzare il formalismo delle grammatiche anche per riconoscere i token. Tuttavia il problema della tokenizzazione è sufficientemente noto da poter essere automatizzato e abbastanza complesso da essere scomodo da implementare a mano. Il meccanismo delle grammatiche è molto potente, ma applicarlo alla tokenizzazione si rivela inefficiente.

Tradizionalmente si divide l'analisi sintattica in due fasi, la prima detta analisi lessicale (che corrisponde alla tokenizzazione dell'input) e la seconda di analisi sintattica vera e propria. Per la generazione di analizzatori lessicale si utilizza spesso il tool Lex, che è progettato specificamente per essere utilizzato insieme allo Yacc. Infatti molte assunzioni del codice generato da Lex si sposano bene con quelle dello Yacc. Per esempio l'analizzatore lessicale prodotto da Lex è una funzione C chiamata yylex(), che è esattamente quella che si aspetta Yacc per l'analizzatore lessicale.

Lex utilizza per la specifica dell'analizzatore lessicale le espressioni regolari, che sono un formalismo più efficiente delle grammatiche ma meno potente. La distinzione tra grammatiche e espressioni regolari sta nel fatto che le espressioni regolari non sono in grado di riconoscere strutture sintattiche ricorsive, mentre questo non è un problema per le grammatiche. Una struttura sintattica come le parentesi bilanciate, che richiede che le parentesi aperte siano nello stesso numero di quelle chiuse non può essere riconosciuta da un analizzatore lessicale, e per questo scopo si ricorre all’analizzatore sintattico. Invece costanti numeriche, identificatori o keyword vengono normalmente riconosciute dall'analizzatore lessicale.

Nel seguente listato si può vedere il sorgente Lex dell'analizzatore lessicale di b2c.

%{

extern int line_nr;
char* new_string(char* s, int n);
int yywrap(void);

%}

identifier [A-Za-z][A-Za-z0-9]*
integer [0-9]+
string ["][^"]*["] 

%%

[ \t]+ { /* skip */ }
"\n" { ++line_nr; 
return(SEP); }
":" { return(SEP); } 
">=" { return(GE); }
"<=" { return(LE); }
"<>" { return(NE); }
[Aa][Nn][Dd] { return(AND); }
[Oo][Rr] { return(OR); }
[Nn][Oo][Tt] { return(NOT); }
[Ll][Ee][Tt] { return(LET); }
[Ff][Oo][Rr] { return(FOR); }
[Tt][Oo] { return(TO); }
[Nn][Ee][Xx][Tt] { return(NEXT); }
[Ww][Hh][Ii][Ll][Ee] { return(WHILE); }
[Ww][Ee][Nn][Dd] { return(WEND); }
[Ii][Ff] { return(IF); }
[Tt][Hh][Ee][Nn] { return(THEN); }
[Ee][Ll][Ss][Ee] { return(ELSE); }
[Ee][Nn][Dd][Ii][Ff] { return(ENDIF); }
[Pp][Rr][Ii][Nn][Tt] { return(PRINT); }
[Ii][Nn][Pp][Uu][Tt] { return(INPUT); }
{identifier} { yylval.str = new_string(yytext, yyleng); 
return(VARIABLE); }
{integer} { yylval.str = new_string(yytext, yyleng); 
return(INTEGER); }
{string} { yylval.str = new_string(yytext, yyleng); 
return(STRING); } 
. { return yytext[0]; }

%%

/* wrap function */
int yywrap(void) { 
return 1; 
}

char* new_string(char* s, int n) {
char* t = malloc(n+1);
strncpy(t, s, n);
t[n]='\0';
return t;
}

La seguente tabella riassume le principali espressioni regolari supportate da Lex.

L'input di Lex viene diviso in tre parti, separate da %%. La prima parte comprende delle definizioni, che sono delle sottoespressioni regolari, da utilizzare più avanti; nel listato possiamo vedere definizioni per identifier, integer, string. In generale le espressioni regolari possono essere anche molto complesse, quindi queste definizioni sono indispensabili per semplificare le espressioni regolari vere e proprie. La seconda parte comprende le espressioni regolari che vengono riconosciute dall'analizzatore lessicale; si può notare che alcune utilizzano definizioni dalla prima parte. Associata ad ogni espressione regolare c'è un pezzo di codice C che viene eseguito ogni volta che una espressione regolare viene riconosciuta. La terza parte comprende solo codice di supporto in C. Parti di codice possono essere inserite sia nella prima parte (inserendolo tra %{ e %}) che nella seconda, inserendolo tra { } immediatamente dopo ogni espressione regolare che si vuole riconoscere.

Lex genera una funzione, yylex(), che legge lo standard input e viene ripetutamente invocata dal parser ogni volta che è richiesto un nuovo token. Per essere esatti Lex genera un file, lex.yy.c, che viene normalmente incluso (con una #include) nel sorgente generato da Yacc. Infatti molte dichiarazioni, come i token (SEP, GE, AND,...) e le strutture dati per comunicare con il parser vengono dichiarate nel sorgente generato da Yacc, y.tab.c. La funzione yylex() viene richiamata ripetutamente dalla funzione principale del parser , yyparse().

Torniamo al Lex: una volta che un token viene riconosciuto, abbiamo varie possibilità: possiamo ignorarlo (come facciamo per gli spazi bianchi) e passare al token successivo; oppure possiamo ritornare il codice del token riconosciuto. Quando viene ritornato un token, la funzione yylex() termina ma sarà richiamata dal parser quando avrà bisogno di un altro token.

Notiamo che può essere necessario fare qualche azione supplementare oltre a ritornare un token o ignorarlo. Possiamo notare che quando incontriamo un newline, incrementiamo il contatore delle linee in input. Molto più importante è il fatto che di certi token occorre conoscere qualcosa di più oltre al loro tipo. Per esempio, di una variabile non basta sapere che è una variabile: occorre sapere quale è. Lex mantiene in un buffer il testo letto dall'input e riconosciuto, buffer accessibile all'utente tramite le variabili char* yytext e int yyleng.

Yacc fornisce le variabili per passare informazioni alla yyparse(). Ad ogni token, come pure ad ogni simbolo grammaticale, è possibile associare un valore. I valori associabili ad un token sono definiti da una union, dichiarata nel sorgente Yacc. Nel nostro caso dichiareremo anche un campo str di tipo char*. La variabile yylval, che è una union, è utilizzata per passare al parser il valore associato al token corrente; per variabili, costanti e stringhe provvederemo a passare informazioni supplementari, usando i campi di yylval.

Il testo riconosciuto da una espressione regolare si trova momentaneamente nel buffer yytext, ma dobbiamo provvedere a copiarlo da qualche parte per passarlo al parser; questa operazione è effettuata dalla funzione new_string. Notiamo infine la funzione yywrap(), che viene invocata da yylex() quando incontra la fine dell'input per decidere il da farsi. Se ritorna 1, vuol dire che l'input è proprio finito. Altrimenti la yywrap() può prendere provvedimenti, come aprire un altro file e collegarlo allo standard input, ritornando 0 per dire a yylex() di continuare a leggere.