Volumes horaires
- CM 24.0
- Projet -
- TD 24.0
- Stage -
- TP -
- DS -
Crédits ECTS
Crédits ECTS 4.0
Objectif(s)
Introduction aux formalismes et outils utilisés pour la définition et l'analyse de la syntaxe des langages formels et l'étude de leurs propriétés. Application aux langages de programmation.
Responsable(s)
Lionel RIEG
Contenu(s)
- Rappels sur la logique, les quantificateurs, les maths discrètes
- Théorème du point fixe sur les ensembles
- Ensembles inductifs, raisonnement par induction structurelle
- Langages formels
- Automates finis (déterministes et non déterministes)
- Modélisation par des automates (protocole, automate de contrôle)
- Transformation d'automates : élimination des epsilon-transitions, déterminisation, minimisation
- Expressions régulières : équivalence avec les automates, ER au-delà des langages réguliers (cf. langages de programmation)
- Propriétés de clôture des langages réguliers, lemme de l'étoile, langages non réguliers
- Grammaires et hiérarchie de Chomsky, algorithme général de génération
- Grammaires hors-contexte : preuves sur les grammaires, algos de reconnaissance (descendant et ascendant), ambiguïté et grammaires d'expression, lemme de l'étoile
- Structure et construction d'un analyseur : analyses lexicale, syntaxique (LL(1) et plus) et sémantique (grammaires attribuées)
- Typage et propriétés garanties par un langage de programmation
Récursivité et notion de pile d'appels
Contrôle des connaissances
Evaluation : 20% de Projet (évaluation en continu et sur le rendu) et 80% de Examen Ecrit (2h)
Rattrapage : Examen Ecrit (2h)
Documents autorisés pour l'examen terminal : une feuille A4 manuscrite recto-verso
Calendrier
Le cours est programmé dans ces filières :
- Cursus ingénieur - Tronc Commun - Semestre 5
Informations complémentaires
Code de l'enseignement : 3MMTL
Langue(s) d'enseignement : 
Vous pouvez retrouver ce cours dans la liste de tous les cours.