Analyse lexicale

La première étape, le balayage, est généralement réalisée par un automate fini. Cet automate possède les informations nécessaires pour traiter toutes les séquences de caractères pouvant être contenues dans un lexème (chaque caractère de ces séquences étant un lexème). Par exemple un int peut contenir toutes les suites possibles de chiffres. Dans de nombreux cas le premier caractère signifiant lu peut être utilisé pour déduire la nature du lexème courant et chaque caractère suivant sera ajouté à la valeur du token jusqu'à la lecture d'un caractère non acceptable. Dans certains langages cependant, la règle peut être plus complexe et nécessiter du retour sur trace sur des caractères déjà lus. Par exemple en C, un caractère « L » n'est pas suffisant pour différencier un identifiant commençant par « L » d'un littéral composé de ce seul caractère.

Un lexème n'est qu'une suite de caractères caractérisés par un type. Pour construire une unité lexicale l'analyseur lexical nécessite une seconde étape, l'évaluation, qui produit une valeur. Le type du lexème combiné avec sa valeur est ce qui constitue un token, qui peut ensuite être livré à un analyseur syntaxique. Certains lexèmes, comme ceux représentant la ponctuation n'ont pas réellement de valeur, leur fonction d'évaluation peut donc rendre une valeur nulle ; seul leur type est nécessaire. De la même manière, l'évaluation peut supprimer complètement un lexème, le dissimulant à l’analyseur syntaxique comme cela peut être le cas pour les caractères d'espacement ou les commentaires. L'évaluation des identifiants est souvent simple, en passant directement la chaîne de caractères les constituant en valeur, mais pour les valeurs numériques l’analyseur lexical peut faire le choix de les transformer en unité lexicale sous forme de chaînes de caractères (différant leur traitement à l'analyse sémantique) ou de les évaluer lui-même.

Même s'il peut être possible, voire nécessaire en cas de petit nombre de lexèmes, d'écrire un analyseur lexical « à la main », ceux-ci sont souvent générés par des outils automatiques. Ces outils acceptent généralement les expressions régulières décrivant les lexèmes autorisés. Chaque expression régulière est associée à une règle de production de la grammaire formelle du langage évalué. Ces outils peuvent générer du code source qui peut être compilé et exécuté ou construire une table de transition d'états pour un automate-fini.

Une expression régulière représente une version compacte du motif que les lexèmes doivent suivre pour constituer une unité lexicale valide. Par exemple, pour un langage basé sur la langue française, un identifiant peut être n'importe quel caractère alphabétique ou un tiret bas suivi par n'importe quelle suite de chiffres ou de caractères ASCII alphanumériques et/ou de tirets bas. Cette suite peut être représentée par la chaîne de caractères suivante [a-zA-Z_][a-zA-Z_0-9]*.

Les expressions régulières et les automates finis qu'elles génèrent ne sont pas assez puissants pour traiter des motifs récursifs comme ce qu'on trouve dans les langages de Dyck[5]. Ces traitements sont laissés à l’analyseur syntaxique.

Dans des langages anciens comme l'ALGOL, la première étape de la compilation était appelée la reconstruction de ligne qui consistait à parcourir le texte pour y identifier des mots-clefs et supprimer les caractères d'espacement et les commentaires. Les analyses lexicales et syntaxiques étaient réalisées par un seul programme parser-lexer[6].

Typiquement, l'analyse lexicale agit au niveau des mots. Il peut cependant parfois être difficile de différencier ce qu'est un « mot ». Souvent les analyseurs lexicaux se basent sur des heuristiques simples, par exemple :

• caractères d'espacement et de ponctuation peuvent ou pas faire partie de la liste de lexèmes valides ;
• toutes les suites continues de caractères alphanumériques peuvent être interprétées comme un seul et même lexème ;
• les lexèmes sont séparés par des caractères d'espacement ou de ponctuation ;

Dans des langages qui utilisent des espaces inter-mots (comme la plupart des langages de programmation et des langages naturels utilisant l'alphabet latin) cette approche est facile à mettre en œuvre. Malgré cela, il existe de nombreux cas (contractions, émoticônes, mots composés, URI, etc.) qui nécessitent des heuristiques plus complexes pour être traités par l'analyseur lexical. Un exemple classique est la suite de caractères « New York-based » qui en anglais forme un seul mot mais qui naïvement peut être séparé en deux voire trois lexèmes.

L'analyse lexicale peut être particulièrement difficile en ce qui concerne les langues naturelles écrites en scriptio continua pour lesquelles il n'existe aucun symbole de ponctuation ou de séparation des lexèmes comme en grec ancien ou en chinois.

Certains langages, comme Python, utilise l'indentation pour délimiter les blocs de code. L’analyseur lexical doit donc générer une unité lexicale INDENT à l'augmentation de l'indentation et une unité lexicale DEDENT à sa réduction[7]. Ces unités lexicales correspondent à ceux générés à la lecture de crochets ouvrant « { » et fermant « } » dans des langages comme le C. Pour pouvoir être pris en compte par l’analyseur syntaxique, celui-ci doit pouvoir conserver l'état courant de l'indentation (puisque les blocs peuvent être imbriqués les uns dans les autres) ce qui rend donc la grammaire du langage analysé contextuelle. INDENT-DEDENT dépendent du contexte (en l'occurrence du niveau d'indentation précédent).

• ANTLR : génère lexers et parsers
• DFASTAR : génère en C++ des automates finis
• Flex : variante libre de Lex
• Ragel : compilateur d'automates finis générant ses sorties en code source dans les langages suivants : C, C++, Objective-C, Java, Go et Ruby
• re2c[8] : générateur de lexer pour C et C++

• JavaCC :  compilateur de compilateur écrit en Java
• JFLex[9] : générateur d'analyseur lexical pour Java écrit en Java
• AnnoFlex[10] : un autre générateur d'analyseur lexical pour Java écrit en Java
• RE/flex[11] : variante rapide de lex/flex pour C++
• Quex[12] : générateur de lexer C and C++ écrit en Python
• FsLex[13] : générateur de lexer reconnaissant les caractères ASCII et Unicode pour F#
• PLY[14] : implémentation de Lex en Python

1. On génère pour chaque symbole un automate qui reconnaît l'expression rationnelle associée au symbole. Cet automate sera identifié par le symbole.
2. Tant que le mot n'a pas été entièrement analysé et qu'il n'y a pas d'erreur :
   1. On lit le mot lettre par lettre en faisant avancer les automates en parallèle pour chaque lettre.
   2. Lorsqu'un automate entre dans un état final, on conserve le sous-mot trouvé et l'identificateur de l'automate.
   3. Si tous les automates sont dans un état puits ou que le mot a été entièrement analysé :
      1. Si aucun automate n'a atteint d'état final : on renvoie une erreur.
      2. Sinon, on ajoute le couple (plus grand sous-mot avec un automate en état final, type de l'automate l'ayant trouvé) à la liste des entités lexicales. On se replace alors juste après ce sous-mot, on remet les automates à zéro et on continue la lecture du mot.

Dans le cas des langages de programmation, cet algorithme s’exécute souvent en temps linéaire par rapport à la taille du mot d'entrée. Cependant, il existe des cas pathologiques où l'algorithme s'exécute en temps quadratique, tel que celui-ci : avec deux lexèmes : a et a…ab, l'entrée aⁿ nécessite que l'algorithme aille jusqu'à la fin du mot pour chaque a qu'il reconnait. La complexité est alors quadratique.

Il existe d'autres algorithmes capables d'analyser un mot en temps linéaire[16].

• Grammaire
• Compilateur de compilateur
• Analyse syntaxique
• Analyse sémantique
• Lex (logiciel)
• modèles de lexiques (LMF)