En informatique, l’analyse lexicale, ou est la conversion d’une chaîne de caractères (un texte) en une liste de symboles ( en anglais, ce qui signifie « jeton »). 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 ..
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 ; + Exemples d'unités lexicalesNom Valeurs identifiantsmots-clefsponctuation}, (, ;opérateurslittéraux 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 : ValeurCatégorie lexicalesumidentifiant=opérateur d'affectation2entier littéral +opérateur d'addition3entier 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 deux étapes : Le balayage qui segmente la chaîne de caractères d'entrée en lexèmes Termes normalisés par ISO/CEI 2382-15:1999 Technologies de l'information — Vocabulaire — Partie 15 : Langages de programmation et leur associe une catégorie lexicale (entier littéral, opérateur d'addition, identifiant…) ; 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) 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