Leçon 4 sur 5
L'analyse lexicale et l'analyse syntaxique
Je sais découper un programme source en unités lexicales, calculer les ensembles PREMIER et SUIVANT d'une grammaire, construire une table d'analyse LL(1), écrire un analyseur par descente récursive et suivre une analyse ascendante par décalage-réduction.
- 1 h 30
- 6 exercices corrigés
- QCM de 6 questions
À la fin de la leçon, vous saurez :
- Décrire les phases d'un compilateur et le rôle de l'analyseur lexical et de l'analyseur syntaxique
- Spécifier des unités lexicales par des expressions régulières et programmer un analyseur lexical
- Éliminer la récursivité à gauche et factoriser une grammaire, puis calculer PREMIER et SUIVANT
- Construire une table LL(1), dérouler une analyse et écrire un analyseur par descente récursive
- Dérouler une analyse ascendante par décalage-réduction et expliquer les conflits
Avant de commencer : Leçons 1 à 3 (expressions régulières, automates finis, grammaires hors contexte) ; Algorithmique avancée et structures de données (piles, récursivité).
1Je découvre
La calculatrice d'Alpha a maintenant une grammaire non ambiguë (leçon 3). Reste à écrire le programme qui, à partir du texte x = 2 + 3 * (4 - 1) ;, retrouve l'arbre de dérivation, ou signale clairement l'erreur quand l'utilisateur tape 2 + * 3.
Alpha remarque que son programme doit d'abord regrouper les caractères : 1, 2, ., 5 forment un nombre, prix2 forme un identificateur, les espaces ne comptent pas. Ensuite seulement, il peut vérifier que la suite « nombre, plus, nombre, fois… » respecte la grammaire. C'est exactement ainsi que travaillent les compilateurs de C, de Java ou l'interpréteur Python : un analyseur lexical fabrique des unités, un analyseur syntaxique construit la structure. Des outils comme Lex et Yacc (ou Flex et Bison) génèrent ces programmes automatiquement depuis des expressions régulières et une grammaire.
Comment un compilateur transforme-t-il une suite de caractères en suite d'unités lexicales, puis en arbre syntaxique, en temps linéaire ?
La suite se lit avec votre compte Kharandi Université
La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.
Voir toutes les leçons de Théorie des langages et compilation