Utilisateur:Regards sur sciences/agreg/leçons/25. Analyses lexicale et syntaxique. Applications.
analyse lexicale
[modifier | modifier le wikicode]En informatique, l’analyse lexicale, lexing, segmentation 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[1] ou lexer. Un analyseur lexical est généralement combiné à un analyseur syntaxique pour analyser la syntaxe d'un texte.
Lexème
[modifier | modifier le wikicode]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[2].
Certains auteurs utilisent le terme « token » pour représenter à la fois la chaîne de caractère en cours de traitement par l'analyseur lexical et la structure de donnée produite en sortie de ce traitement[3].
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
[modifier | modifier le wikicode]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[2].
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. ;
| Nom | Valeurs |
|---|---|
| identifiants | |
| mots-clefs | |
| ponctuation | }, (, ;
|
| opérateurs | |
| littéraux | |
Un nom d'unité lexicale peut être comparé au concept de nature grammaticale.
Grammaire lexicale
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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 :
- Le balayage qui segmente la chaîne de caractères d'entrée en lexèmes[4] 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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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].
Limites
[modifier | modifier le wikicode]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.
Indentation comme syntaxe
[modifier | modifier le wikicode]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[. 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).
analyse syntaxique
[modifier | modifier le wikicode]L'analyse syntaxique consiste à mettre en évidence la structure d'un texte, généralement une phrase écrite dans une langue naturelle, mais on utilise également cette terminologie pour l'analyse d'un programme informatique. L'analyseur syntaxique (parser, en anglais) est le programme informatique qui réalise cette tâche. Cette opération suppose une formalisation du texte, qui est vue le plus souvent comme un élément d'un langage formel, défini par un ensemble de règles de syntaxe formant une grammaire formelle. La structure révélée par l'analyse donne alors précisément la façon dont les règles de syntaxe sont combinées dans le texte. Cette structure est souvent une hiérarchie de syntagmes, représentable par un arbre syntaxique dont les nœuds peuvent être décorés (dotés d'informations complémentaires).
L'analyse syntaxique fait habituellement suite à une analyse lexicale qui découpe le texte en un flux (parfois un graphe orienté acyclique) de lexèmes, et sert à son tour de préalable à une analyse sémantique. Connaître la structure syntaxique d'un énoncé permet d'expliciter les relations de dépendance (par exemple entre sujet et objet) entre les différents lexèmes, puis de construire une représentation du sens de cet énoncé.
En pratique, et sauf dans les cas très simples, des coroutines sont en général nécessaires pour lier les deux. Ainsi, en FORTRAN où les espaces n'étaient pas significatifs, GOTO5=1 ou DO1I=3, affectations autorisées par la syntaxe bien que perverses, auraient été par erreur considérées comme des fautes de syntaxe si l'opération d'analyse lexicale avait été réalisée totalement avant que ne commence la syntaxique. Dans la pratique, les compilateurs bas de gamme les refusaient.
- ↑ « Anatomy of a Compiler and The Tokenizer », sur www.cs.man.ac.uk (consulté le 5 janvier 2018).
- ↑ 2,0 et 2,1 (en) Compilers Principles, Techniques, & Tools, 2nd Ed., WorldCat, p. page 111.
- ↑ (en) « Perl 5 Porters », sur perldoc.perl.org.
- ↑ Termes normalisés par ISO/CEI 2382-15:1999 Technologies de l'information — Vocabulaire — Partie 15 : Langages de programmation
- ↑ « Structure and Interpretation of Computer Programs », sur mitpress.mit.edu (consulté le 5 janvier 2018).
- ↑ (en) Scannerless Generalized-LR Parsing, University of Amsterdam, August 1997.