Un compilateur comporte toujours une première phase qui détermine les unités lexicales à l'aide d'un automate fini.
Considérons le texte suivant :
int f(int arg) {
return 2*arg+1;
}
Ce texte est d'abord découpé en lexèmes : dans l'exemple ci-dessus, int, (, return et 1 sont des lexèmes, tandis que in ou int f n'en sont pas. Chaque lexème appartient à une unité lexicale, qui comporte un ou plusieurs lexèmes. Voici les unités lexicales correspondant aux exemples précédents : ident (qui contient tous les identificateurs), par-gauche (qui contient seulement la parenthèse ouvrante), return (qui contient seulement le mot-clé return), nombre (qui contient tous les lexèmes numériques).
L'analyse lexicale d'un texte, c'est-à-dire d'un mot sur l'alphabet ASCII, consiste à le transformer en une suite d'unités lexicales, c'est-à-dire en un mot sur un autre alphabet. Par exemple, le texte précédent int f ... est transformé en ident ident par-gauche ident ident par-droite acc-gauche return nombre mult ident plus nombre point-virgule acc-droite. Certaines unités lexicales sont affectées d'une valeur (par exemple, la valeur numérique d'un nombre, ou la valeur textuelle d'un ident). Pour vérifier que le texte int f .. est un programme C++ correct, on doit vérifier que le mot ident ident ... vérifie les règles de grammaire de C, ce qu'on appelle l'analyse syntaxique. Cette vérification ne peut pas se faire avec un automate fini, car elle nécessite de garder en mémoire les états passés. On doit donc combiner un automate fini avec une pile, mais la description de cet algorithme dépasse le cadre de ce cours.