Leçon 3 sur 5
Les grammaires hors contexte
Je sais définir une grammaire hors contexte, produire des dérivations et des arbres de dérivation, reconnaître et lever une ambiguïté, et écrire la grammaire d'un petit langage de programmation.
- 1 h 25
- 7 exercices corrigés
- QCM de 7 questions
À la fin de la leçon, vous saurez :
- Définir une grammaire hors contexte et le langage qu'elle engendre
- Construire des dérivations gauches et droites et l'arbre de dérivation d'un mot
- Reconnaître une grammaire ambiguë et la transformer pour exprimer priorité et associativité
- Concevoir une grammaire pour un langage donné et justifier qu'elle l'engendre
- Situer les grammaires dans la hiérarchie de Chomsky et mettre une grammaire en forme normale de Chomsky
Avant de commencer : Leçons 1 et 2 (langages réguliers, automates finis, lemme de l'étoile) ; Mathématiques discrètes (récurrence, arbres).
1Je découvre
Alpha a terminé l'automate qui reconnaît les nombres de sa calculatrice (leçon 2). Il veut maintenant accepter des expressions comme 2 + 3 * (4 - 1). Deux problèmes surgissent. D'abord, les parenthèses peuvent s'imbriquer sans limite, et nous avons démontré qu'aucun automate fini ne sait les vérifier. Ensuite, son programme calcule 2 + 3 * 4 = 20, alors que la réponse attendue est 14 : il ne sait pas que la multiplication est prioritaire.
Les concepteurs des langages de programmation ont rencontré le même problème. La norme du langage C, la documentation de Python ou celle de Java décrivent leur syntaxe par des règles de réécriture : « une expression est une expression, suivie de +, suivie d'un terme, ou bien un terme ». Ce sont des grammaires.
Le linguiste Noam Chomsky les a formalisées dans les années 1950 pour étudier les langues humaines ; elles sont devenues l'outil de base de la compilation.
Comment décrire avec un nombre fini de règles un langage où les structures s'emboîtent, comme les expressions parenthésées, et comment faire apparaître la structure d'un programme ?
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