Analyse lexicale

En informatique, l’analyse lexicale, lexing ou tokenization est la conversion d’une chaîne de caractères (un texte) en une liste de symboles (tokens en anglais). Elle fait partie de la première phase de la chaîne de compilation. Ces symboles sont ensuite consommés lors de l'analyse syntaxique. Un programme réalisant une analyse lexicale est appelé un analyseur lexical, tokenizer ou lexer. Un analyseur lexical est généralement combiné à un analyseur syntaxique pour analyser la syntaxe d'un texte.

Lexème

« Un lexème est une suite de caractères dans un programme source qui correspond au motif d'un symbole lexical et qui est analysé par l'analyseur lexical comme une instance de ce symbole lexical ».

Certains auteurs utilisent le terme « token » pour représenter à la fois la chaîne de caractères en cours de traitement par l'analyseur lexical et la structure de donnée produite en sortie de ce traitement.

Le terme « lexème » en informatique n'a pas le même sens que lexème en linguistique. En informatique sa définition se rapproche de celle de morphème en linguistique.

Unité lexicale

Une unité lexicale ou token lexical ou plus simplement token est un couple composé d'un nom et d'une valeur optionnelle. Le nom de l’unité lexicale est une catégorie d'unité lexicale.

Quelques exemples de noms d'unités lexicales qu'on rencontre le plus souvent :

• identifiers (identifiants) : nom de variables ou de fonctions choisis par le programmeur du code analysé. Ne peut être un mot réservé du langage ;
• keywords (mots-clefs) : mots réservés du langage ;
• separators (ponctuation) : caractères de ponctuation simples comme les points et les virgules ou composés comme les parenthèses et les crochets ;
• operators (opérateurs) : symboles s'appliquant sur des arguments et produisant un résultat ;
• literals (littéraux) : suite de caractères représentant une valeur numérique, logique, etc. ;

Exemples d'unités lexicales

Nom	Valeurs
identifiants	x, color, UP
mots-clefs	if, while, return
ponctuation	}, (, ;
opérateurs	+, <, =
littéraux	true, 6.02e23, "music"

Un nom d'unité lexicale peut être comparé au concept de nature grammaticale.

Grammaire lexicale

Les langages de programmation définissent souvent des règles, sous la forme d'une grammaire, définissant la syntaxe à adopter. Ces règles prennent souvent la forme d'expressions rationnelles et définissent les séquences de caractères utilisées pour former des lexèmes.

Les langages reconnus par une expression rationnelle sont appelés les langages rationnels. À toute expression rationnelle, on peut associer un automate fini. Il existe également des langages non rationnels.

Deux des plus importantes catégories d'unités lexicales sont les caractères d'espacement et les commentaires. Elles sont toutes deux définies dans la grammaire de la plupart des langages et traités par les lexers, mais sont le plus souvent considérées comme non-signifiantes ; dans le meilleur des cas séparant deux tokens et n'en générant pas par elles-mêmes. Il y a deux exceptions majeures à cela. Tout d'abord les langages dits à indentation comme syntaxe comme le Python qui délimitent les blocs de code par l'indentation et pour qui les caractères d'espacement sont signifiants et peuvent donc générer des tokens. Ensuite dans certaines utilisations des lexers, notamment certains outils de débogage ou d'impression élégante (pretty-printers en anglais) il peut être nécessaire de conserver le code source original pour pouvoir l'afficher plus tard à l'utilisateur.

Analyseur lexical

On appelle analyseur lexical (lexer en anglais) tout programme effectuant une analyse lexicale.

L'analyseur lexical sert à :

• éliminer les « bruits » du texte source : commentaires, espaces ;
• reconnaître les opérateurs et les mots-clés : +, >, if, return, … ;
• reconnaître les identificateurs, les chaînes de caractères littérales et les nombres littéraux.

Lorsque l'analyseur lexical détecte un lexème invalide, il rapporte une erreur. En revanche, les combinaisons de lexèmes sont généralement laissées à l'analyseur syntaxique : par exemple, un analyseur lexical typique reconnaît les parenthèses comme étant des lexèmes mais ne vérifie pas qu'une parenthèse ouvrante « ( » est forcément associée à une parenthèse fermante « ) ».

Un analyseur lexical peut être écrit :

• « à la main » : il faut construire l'automate fini non déterministe à partir d'une expression rationnelle E, puis l'exécuter pour déterminer si une chaîne d'entrée appartient au langage reconnu par E ;
• par une table décrivant l'automate et un programme exploitant cette table ;
• par un générateur d'analyseurs lexicaux : Lex, Flex., ANTLR, etc.

Bien que les lexers soient principalement utilisés pour écrire des compilateurs, ils entrent dans la conception d'autres outils de traitement des langages informatiques comme les lint ou les systèmes d'impression élégante (troff).

Processus

L'analyse lexicale constitue la première phase des processus de compilation modernes. L'analyse est généralement réalisée en parcourant le texte source une seule fois.

Elle consiste en la démarcation, et si possible caractérisation de segments de la chaîne de caractères d'entrée en une suite de lexèmes qui seront passés à une autre forme d'analyse.

Par exemple, l'instruction sum = 2 + 3; en langage C produit après analyse lexicale la liste de symboles suivante :

Valeur	Catégorie lexicale
sum	identifiant
=	opérateur d'affectation
2	entier littéral
+	opérateur d'addition
3	entier littéral
;	fin de déclaration

La suite de caractères d'entrée, implicitement segmentée par des espaces comme dans les langages naturels a été transformée en une liste de six unités lexicales :

[(identifiant, sum), (opérateur d'affectation, =), (entier littéral, 2), (operator, +), (entier littéral, 3), (fin de déclaration, ;)]

Généralement, quand une unité lexicale représente plusieurs lexèmes, l’analyseur lexical sauvegarde suffisamment d'informations pour pouvoir reproduire le lexème original et l'utiliser lors de l'analyse sémantique. L’analyseur syntaxique récupère ces informations et les stocke sous la forme d'un arbre de syntaxe abstraite (AST). Cela est nécessaire pour éviter la perte d'information dans le cas des nombres et des identifiants.

Les lexèmes sont identifiés en fonction de règles établies par l’analyseur lexical. Parmi les méthodes utilisées pour identifier les lexèmes on trouve : les expressions régulières, une suite spécifique de caractères que l'on nomme drapeau, des caractères appelés séparateurs et un dictionnaire.

L'analyseur lexical ne traite en général pas les combinaisons d’unités lexicales, cette tâche étant laissée à l’analyseur syntaxique. Par exemple, un analyseur lexical typique peut reconnaître et traiter les parenthèses mais est incapable de les compter et donc de vérifier si chaque parenthèse fermante « ) » correspond à une parenthèse ouvrante « ( » précédente.

L'analyse lexicale d'une chaîne de caractères se déroule en trois étapes :

1. Le balayage qui segmente la chaîne de caractères d'entrée en lexèmes et leur associe une catégorie lexicale (entier littéral, opérateur d'addition, identifiant…) ;
2. L'évaluation qui convertit chaque lexème en une valeur.

Balayage

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.

Évaluation

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. 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.

Limites

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.

Indentation comme syntaxe

Certains langages, comme Python, utilisent 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. 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).

Générateur d'analyseur lexical

Les analyseurs lexicaux sont souvent générés par des outils appelés générateurs d'analyseurs lexicaux. Un des plus communément utilisé est Lex, conjointement avec le générateur d'analyseur syntaxique Yacc et leurs équivalents libres Flex et Bison. Ces générateurs sont une forme de langage dédié, prenant en entrée une spécification lexicale (généralement des expressions régulières et quelques balises) et produisent en sortie un lexer.

Ces outils permettent le développement rapide d'un analyseur lexical fonctionnel.

Liste de générateurs d'analyseurs lexicaux

• 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 : générateur de lexer pour C et C++

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

Complexité algorithmique

La performance des lexers, en particulier dans les langages stables dans lesquels le lexer est très souvent appelé (comme C ou HTML) est une préoccupation majeure. Les lexers générés grâce à Lex/Flex sont considérés comme raisonnablement rapides mais peuvent dans certains cas être deux à trois fois plus lents que les lexers écrits « à la main » ou des outils comme re2c.

Algorithme naïf

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.

Analyse de la complexité

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.

Autres algorithmes

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

Annexes

Articles connexes

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