Analyse lexicale et syntaxique
L'analyse lexicale et syntaxique constituent le frontal d'un compilateur, décomposant le texte source en lexèmes (tokens) et reconnaissant sa structure grammaticale sous forme d'arbre d'analyse ou d'arbre syntaxique.
Definition
L'analyse lexicale est la phase qui regroupe les caractères d'entrée en lexèmes (tokens), et l'analyse syntaxique (parsing) est la phase qui détermine si et comment ces lexèmes forment un programme valide selon une grammaire, produisant un arbre syntaxique.
Scope
Ce sujet aborde l'analyse lexicale, qui convertit les flux de caractères en lexèmes (tokens) à l'aide de langages réguliers et d'automates finis, et l'analyse syntaxique (parsing), qui reconnaît la structure de phrase d'un programme par rapport à une grammaire hors-contexte. Il inclut l'analyse descendante (LL) et ascendante (LR), les générateurs d'analyseurs, l'ambiguïté et la récupération d'erreurs, ainsi que la construction d'arbres syntaxiques abstraits.
Core questions
- Comment les langages réguliers et hors-contexte sont-ils utilisés pour décrire la structure d'un programme ?
- Quels sont les compromis entre l'analyse LL et LR ?
- Comment l'ambiguïté et les erreurs d'analyse sont-elles détectées et gérées ?
- Comment un arbre syntaxique abstrait est-il construit à partir d'un flux de lexèmes (tokens) ?
Key theories
- Analyse LR
- Knuth a introduit l'analyse LR, une technique ascendante qui analyse de manière déterministe la vaste classe des grammaires LR en temps linéaire, constituant la base de nombreux générateurs d'analyseurs.
- Analyse générale hors-contexte
- L'algorithme d'Earley analyse des grammaires hors-contexte arbitraires, y compris les ambiguës, offrant une méthode générale lorsque les analyseurs déterministes restreints sont insuffisants.
- Fondements réguliers et hors-contexte du frontal
- Le Dragon Book systématise l'utilisation des expressions régulières et des automates finis pour l'analyse lexicale (scanning) et des grammaires hors-contexte pour l'analyse syntaxique (parsing), y compris les algorithmes de construction LL et LR standards.
Clinical relevance
L'analyse lexicale et syntaxique sont fondamentales non seulement pour les compilateurs, mais aussi pour les interpréteurs, les linters, les formateurs, les IDE et les processeurs de formats de données. Une analyse robuste avec une bonne récupération d'erreurs est essentielle pour l'expérience développeur de tout outil linguistique.
History
La hiérarchie des langages formels de Chomsky, à la fin des années 1950, a fourni la théorie des langages réguliers et hors-contexte. Knuth a formalisé l'analyse LR en 1965, et Earley a proposé un algorithme général hors-contexte en 1970. Les générateurs d'analyseurs comme yacc ont rendu l'analyse LR pratique, tandis que des travaux ultérieurs ont exploré les grammaires d'expressions d'analyse et les analyseurs basés sur des combinateurs.
Debates
- Analyseurs générés versus analyseurs écrits à la main
- Les praticiens débattent de l'utilisation des générateurs d'analyseurs à partir de grammaires formelles, qui sont concis et vérifiables, par rapport aux analyseurs récursifs descendants écrits à la main, qui offrent souvent de meilleurs messages d'erreur et un meilleur contrôle au prix d'un code plus conséquent.
Key figures
- Donald Knuth
- Jay Earley
- Alfred Aho
- Noam Chomsky
Related topics
Seminal works
- knuth1965
- earley1970
- aho2006
Frequently asked questions
- Quelle est la différence entre un analyseur lexical (lexer) et un analyseur syntaxique (parser) ?
- Un analyseur lexical regroupe les caractères bruts en lexèmes (tokens) tels que les identificateurs et les opérateurs, tandis qu'un analyseur syntaxique organise ces lexèmes en un arbre syntaxique hiérarchique selon la grammaire du langage.
- Quelle est la différence entre l'analyse LL et l'analyse LR ?
- Les analyseurs LL fonctionnent de manière descendante, prédisant les productions à partir du préfixe d'entrée, tandis que les analyseurs LR fonctionnent de manière ascendante, réduisant les sous-chaînes reconnues ; l'analyse LR gère une classe de grammaires strictement plus grande mais est plus complexe à construire.