La tokenisation lexicale consiste à convertir un texte en jetons lexicaux (sémantiquement ou syntaxiquement) significatifs , appartenant à des catégories définies par un program...
Worldlex WikiFrancaisLecture gratuite
La tokenisation lexicale consiste à convertir un texte en jetons lexicaux (sémantiquement ou syntaxiquement) significatifs , appartenant à des catégories définies par un programme d'analyse lexicale. Dans le cas d'une langue naturelle, ces catégories comprennent les noms, les verbes, les adjectifs, la ponctuation, etc. Dans le cas d'un langage de programmation, les catégories comprennent les identificateurs , les opérateurs , les symboles de groupement , les types de données et les mots-clés du langage. La tokenisation lexicale est apparentée à la tokenisation utilisée dans les grands modèles de langage (LLM), mais s'en distingue par deux différences. Premièrement, la tokenisation lexicale repose généralement sur une grammaire lexicale , tandis que les tokeniseurs des LLM sont généralement basés sur les probabilités . Deuxièmement, les tokeniseurs des LLM effectuent une seconde étape de conversion des jetons en valeurs numériques.
Programmes basés sur des règles
Un programme basé sur des règles, effectuant la tokenisation lexicale, est appelé tokenizer [ ou scanner , bien que le terme scanner » désigne également la première étape d'un analyseur lexical. Un analyseur lexical constitue la première phase du traitement en amont d'un compilateur . L'analyse se déroule généralement en une seule passe. Les analyseurs lexicaux et syntaxiques sont le plus souvent utilisés par les compilateurs, mais peuvent également servir pour d'autres outils de langages informatiques, tels que les formateurs de code ou les linters . L'analyse lexicale se divise en deux étapes : le balayage , qui segmente la chaîne d'entrée en unités syntaxiques appelées lexèmes et les catégorise en classes de jetons, et l' évaluation , qui convertit les lexèmes en valeurs exploitables.
Les analyseurs lexicaux sont généralement assez simples, la majeure partie de la complexité étant déléguée aux phases d'analyse syntaxique ou sémantique . Ils peuvent souvent être générés par un générateur d'analyseurs lexicaux , notamment lex ou ses dérivés. Cependant, certains analyseurs lexicaux peuvent intégrer une certaine complexité, comme le traitement de la structure des syntagmes pour faciliter la saisie et simplifier l'analyse syntaxique. Ils peuvent également être écrits partiellement ou entièrement à la main, soit pour prendre en charge davantage de fonctionnalités, soit pour optimiser les performances.
Désambiguïsation du terme « lexème »
Token lexical et tokenisation lexicale
=a+b*2;
L'analyse lexicale de cette expression donne la séquence de jetons suivante :
Un nom de jeton est ce que l'on pourrait appeler une partie du discours en linguistique.
La tokenisation lexicale consiste à convertir un texte brut en jetons lexicaux (sémantiquement ou syntaxiquement) significatifs, appartenant à des catégories définies par un analyseur lexical, telles que les identificateurs, les opérateurs, les symboles de groupement et les types de données. Les jetons obtenus sont ensuite traités. Ce processus peut être considéré comme une sous-tâche de l' analyse syntaxique du texte.
La chaîne n'est pas segmentée implicitement par espaces, comme le ferait un locuteur natif . L'entrée brute, soit les 43 caractères, doit être explicitement divisée en 9 jetons à l'aide d'un délimiteur d'espace donné (correspondant à la chaîne ou à l'expression régulièreLorsqu'une classe de jetons représente plusieurs lexèmes possibles, l'analyseur lexical conserve généralement suffisamment d'informations pour reproduire le lexème original, afin qu'il puisse être utilisé dans l'analyse sémantique . L'analyseur syntaxique récupère généralement ces informations auprès de l'analyseur lexical et les stocke dans l' arbre de syntaxe abstraite . Ceci est nécessaire pour éviter toute perte d'informations dans le cas où des nombres pourraient également être des identifiants valides.
Les jetons sont identifiés selon les règles spécifiques de l'analyseur lexical. Parmi les méthodes d'identification, on trouve les expressions régulières , les séquences de caractères spécifiques appelées indicateurs , les caractères de séparation spécifiques appelés délimiteurs , et la définition explicite par un dictionnaire. Les caractères spéciaux, notamment la ponctuation, sont couramment utilisés par les analyseurs lexicaux pour identifier les jetons en raison de leur utilisation naturelle dans les langages écrits et de programmation. Un analyseur lexical ne traite généralement pas les combinaisons de jetons ; cette tâche est dévolue à un analyseur syntaxique . Par exemple, un analyseur lexical classique reconnaît les parenthèses comme des jetons, mais ne vérifie pas si chaque parenthèse « ( » correspond à une parenthèse « ) ».
Lorsqu'un analyseur lexical fournit des jetons à un analyseur syntaxique, la représentation utilisée est généralement un type énuméré , c'est-à-dire une liste de représentations numériques. Par exemple, « Identifiant » peut être représenté par 0, « Opérateur d'affectation » par 1, « Opérateur d'addition » par 2, etc.
Les jetons sont souvent définis par des expressions régulières , interprétées par un générateur d'analyseur lexical tel que lex , ou par des automates à états finis équivalents codés manuellement . L'analyseur lexical (généré automatiquement par un outil comme lex ou conçu manuellement) lit un flux de caractères, identifie les lexèmes et les catégorise en jetons. Ce processus est appelé tokenisation . Si l'analyseur lexical détecte un jeton invalide, il signale une erreur.
Après la tokenisation vient l'analyse syntaxique . Les données interprétées peuvent ensuite être chargées dans des structures de données pour une utilisation générale, une interprétation ou une compilation .
Grammaire lexicale
La spécification d'un langage de programmation inclut souvent un ensemble de règles, la grammaire lexicale , qui définit la syntaxe lexicale. Cette syntaxe est généralement celle d'un langage régulier , dont les règles grammaticales sont des expressions régulières ; elles définissent l'ensemble des séquences de caractères possibles (lexèmes) d'un jeton. Un analyseur lexical reconnaît les chaînes de caractères, et pour chaque type de chaîne trouvé, le programme lexical effectue une action, le plus souvent la simple production d'un jeton.
Deux catégories lexicales communes importantes sont les espaces et les commentaires . Ces derniers sont définis dans la grammaire et traités par l'analyseur lexical, mais peuvent être ignorés (ne produisant aucun jeton) et considérés comme non significatifs , servant tout au plus à séparer deux jetons (comme dans « au lieu de »). Il existe deux exceptions importantes. Premièrement, dans les langages à règles hors-ligne qui délimitent les blocs par indentation, les espaces initiaux sont significatifs, car ils déterminent la structure des blocs et sont généralement traités au niveau de l'analyseur lexical ; voir la section « Structure des phrases » ci-dessous. Deuxièmement, dans certains cas d'utilisation d'analyseurs lexicaux, les commentaires et les espaces doivent être préservés ; par exemple, un outil de formatage doit également afficher les commentaires et certains outils de débogage peuvent fournir au programmeur des messages affichant le code source original. Dans les années 1960, notamment pour ALGOL , les espaces et les commentaires étaient éliminés lors de la phase de reconstruction des lignes (phase initiale du compilateur ), mais cette phase distincte a été supprimée et ces éléments sont désormais gérés par l'analyseur lexical.ifxifx
Détails
Scanner
La première étape, l' analyseur lexical , repose généralement sur un automate fini . Il contient des informations sur les séquences de caractères possibles pouvant être contenues dans chacun des jetons qu'il traite (ces séquences sont appelées lexèmes ). Par exemple, un lexème d'entiers peut contenir n'importe quelle séquence de chiffres . Souvent, le premier caractère non blanc permet de déduire le type du jeton suivant, et les caractères suivants sont traités un par un jusqu'à rencontrer un caractère n'appartenant pas à l'ensemble des caractères acceptables pour ce jeton (cette règle est appelée « correspondance maximale » ou « correspondance la plus longue » ). Dans certains langages, les règles de création des lexèmes sont plus complexes et peuvent impliquer un retour arrière sur les caractères déjà lus. Par exemple, en C, un seul caractère « L » ne suffit pas à distinguer un identificateur commençant par « L » d'une chaîne de caractères littérale.
Évaluateur
Un lexème , en revanche, n'est qu'une chaîne de caractères connue pour appartenir à un certain type (par exemple, une chaîne littérale, une séquence de lettres). La deuxième étape d'un analyseur lexical, l' évaluateur , parcourt les caractères du lexème pour produire une valeur contenant les informations pertinentes pour l'analyseur syntaxique.
Le type du lexème, combiné à sa valeur, constitue ce qui définit un jeton . La valeur du jeton peut être tout ce que l'analyseur syntaxique juge nécessaire pour interpréter un jeton de ce type. Voici quelques exemples de valeurs typiques produites par un évaluateur :
Un jeton pour un identifiant contiendra souvent simplement les caractères du lexème associé.
Les valeurs des jetons pour les mots clés et les caractères spéciaux sont généralement omises, car le type seul contient toutes les informations nécessaires.
Les évaluateurs traitant des littéraux entiers peuvent transmettre la chaîne telle quelle (en reportant l'évaluation à la phase d'analyse sémantique), ou peuvent effectuer eux-mêmes l'évaluation pour produire des valeurs numériques.
Pour une simple chaîne littérale entre guillemets, l'évaluateur n'a besoin de supprimer que les guillemets, mais l'évaluateur d'une chaîne littérale échappée peut également incorporer un analyseur lexical, qui déséchappe les séquences d'échappement.
L'évaluateur peut également supprimer entièrement un lexème, le dissimulant à l'analyseur syntaxique, ce qui est utile pour les espaces et les commentaires.
Par exemple, dans le code source d'un programme informatique, la chaîne de caractères
net_worth_future=(assets–liabilities);
pourrait être converti en le flux de jetons lexicaux suivant ; où chaque ligne représente un jeton composé d'un TYPEsuivi d'une valeur optionnelle :
Les analyseurs lexicaux peuvent être écrits manuellement. Cette méthode est pratique pour les listes de jetons restreintes, mais les analyseurs lexicaux générés automatiquement, dans le cadre d'une chaîne de compilation, sont plus adaptés aux grands nombres de jetons potentiels. Ces outils acceptent généralement des expressions régulières décrivant les jetons autorisés dans le flux d'entrée. Chaque expression régulière est associée à une règle de production dans la grammaire lexicale du langage de programmation, qui évalue les lexèmes correspondants. Ces outils peuvent générer du code source compilable et exécutable, ou construire une table de transition d'états pour un automate fini (intégrée à un modèle de code pour la compilation et l'exécution).
Les expressions régulières représentent de manière concise les motifs que peuvent suivre les caractères des lexèmes. Par exemple, pour une langue basée sur l'anglaisLes expressions régulières et les automates finis qu'elles génèrent ne sont pas suffisamment puissants pour gérer les motifs récursifs, tels que « n parenthèses ouvrantes, suivies d'une instruction, suivies de n parenthèses fermantes ». Elles sont incapables de compter les éléments et de vérifier que n est identique des deux côtés, à moins qu'il n'existe un ensemble fini de valeurs possibles pour n . Un analyseur syntaxique complet est nécessaire pour reconnaître de tels motifs dans toute leur généralité. Un analyseur syntaxique peut empiler les parenthèses, puis tenter de les dépiler et vérifier si la pile est vide à la fin (voir l'exemple dans l' ouvrage *Structure et interprétation des programmes informatiques *).
Obstacles
En règle générale, la tokenisation lexicale s'effectue au niveau du mot. Cependant, il est parfois difficile de définir ce qu'est un « mot ». Souvent, un tokenizer s'appuie sur des heuristiques simples, par exemple :
La ponctuation et les espaces peuvent être inclus ou non dans la liste de jetons résultante.
Toutes les suites contiguës de caractères alphabétiques font partie d'un seul jeton ; il en va de même pour les chiffres.
Les jetons sont séparés par des caractères d'espacement , tels qu'un espace ou un saut de ligne, ou par des caractères de ponctuation.
Dans les langues qui utilisent des espaces entre les mots (comme la plupart de celles qui utilisent l'alphabet latin, et la plupart des langages de programmation), cette approche est relativement simple. Cependant, même dans ce cas, il existe de nombreux cas particuliers, tels que les contractions , les mots composés , les émoticônes et les constructions plus complexes comme les URI (qui, dans certains cas, peuvent être considérées comme des jetons uniques). Un exemple classique est « New York-based », qu'un analyseur lexical naïf pourrait segmenter au niveau de l'espace, même si la segmentation la plus pertinente se situe (sans doute) au niveau du trait d'union.
Pour résoudre les problèmes les plus difficiles, plusieurs solutions existent : développer des heuristiques plus complexes, interroger une table de cas particuliers courants ou adapter les jetons à un modèle de langage qui identifie les collocations lors d’une étape de traitement ultérieure.
Générateur de lexer
La règle de délimitation des blocs (déterminée par l'indentation) peut être implémentée dans l'analyseur lexical, comme en Python . Augmenter l'indentation entraîne l'émission d'un jeton INDENT, tandis que la diminuer entraîne l'émission d'un ou plusieurs jetons DEDENT. Ces jetons correspondent aux accolades ouvrantes {et fermantes }dans les langages qui utilisent des accolades pour les blocs, ce qui signifie que la grammaire lexicale est indépendante de l'utilisation des accolades ou de l'indentation. Cela requiert que l'analyseur lexical conserve un état, à savoir une pile des niveaux d'indentation, et puisse ainsi détecter les changements d'indentation. Par conséquent, la grammaire lexicale n'est pas hors contexte : INDENT et DEDENT dépendent des informations contextuelles des niveaux d'indentation précédents.
Analyse lexicale contextuelle
Les grammaires lexicales sont généralement hors contexte, ou presque, et ne nécessitent donc aucune vérification rétrospective ou prospective, ce qui permet une implémentation simple, claire et efficace. Cela permet également une communication unidirectionnelle simple entre l'analyseur lexical et l'analyseur syntaxique, sans qu'aucune information ne soit renvoyée à l'analyseur lexical.
Il existe toutefois des exceptions. Citons par exemple l'insertion d'un point-virgule en Go, qui nécessite de remonter d'un jeton dans l'ordre ; la concaténation de chaînes de caractères consécutives en Python , qui requiert de stocker chaque jeton dans un tampon avant de l'émettre (afin de vérifier si le jeton suivant est également une chaîne de caractères) ; et la règle de décalage en Python, qui exige de conserver un compteur de niveaux d'indentation (en réalité, une pile pour chaque niveau). Ces exemples ne nécessitent que le contexte lexical et, bien qu'ils complexifient quelque peu l'analyseur lexical, ils restent invisibles pour l'analyseur syntaxique et les phases ultérieures.
Un exemple plus complexe est l'astuce du lexer en C, où la classe de jetons d'une séquence de caractères ne peut être déterminée qu'à la phase d'analyse sémantique, car les noms de types définis et les noms de variables sont lexicalement identiques mais appartiennent à des classes de jetons différentes. Ainsi, dans cette astuce, le lexer appelle l'analyseur sémantique (par exemple, la table des symboles) et vérifie si la séquence requiert un nom défini. Dans ce cas, l'information doit remonter non seulement du parseur syntaxique, mais aussi de l'analyseur sémantique vers le lexer, ce qui complexifie la conception.
Worldlex Wiki