Ce cours est l'ancien PIL qui devient LF suite a la suppression de LF en L3
Code UE DLIN222
ancien intitulé: PIL Principe d'Interprétation des Langagues
nouvel intitulé: LF Langages Formels
UE Mutualisable (Oui / Non) et EF autorisés (le cas échéant) =>ca veut dire quoi, UE mutualisable et EF?
Prérequis: Néant
Objectifs d’apprentissage:
À l’issue du cours, l’étudiant·e sera capable de :
Comprendre et manipuler les notions fondamentales de langages formels et d’automates finis.
Concevoir et démontrer des équivalences de langages à l’aide d’outils théoriques (lemme d’Arden, lemme de la pompe, clôtures).
Identifier et construire des grammaires hors contexte et relier ces grammaires aux automates à pile correspondants.
Appliquer les méthodes d’analyse syntaxique descendante et ascendante, y compris la construction et l’exploitation d’automates LR et SLR.
Démontrer la décidabilité de problèmes simples sur les automates et les grammaires.
Le cours permet de découvrir et s’approprier quelques outils mathématiques, en particulier : les démonstration par l’absurde, des démonstration de propositions utilisant des quantificateurs, les relations d’équivalence.
Le cours prépare au cours de compilation de L3, en considérant l'analyse de vrai langage de programmation.
Programme, Plan et Contenus (19 000 caractères max):
Le cours s’articule autour de trois grands axes progressifs : les langages formels et automates finis, les grammaires hors contexte et automates à pile, puis l’analyse syntaxique.
Première partie (5 cours) – Introduction aux langages formels, expressions rationnelles et automates finis.
On y aborde la hiérarchie de Chomsky, les opérateurs sur les langages, le lemme d’Arden et le théorème de Kleene. Les travaux dirigés visent à manipuler les opérateurs, démontrer des égalités de langages, construire et simplifier des automates d’état fini, déterministes et non déterministes, effectuer des déterminisations, supprimer les ε-transitions, et appliquer les méthodes de minimisation et de preuve de rationalité (lemme de la pompe, propriétés de clôture, décidabilité).
Deuxième partie (4 cours) – Grammaires hors contexte et automates à pile.
Les notions d’arbre de dérivation, d’ambiguïté, de normalisation (forme normale de Chomsky) et de décidabilité sont introduites. L’automate à pile est présenté comme modèle de reconnaissance des langages algébriques. Les exercices portent sur la construction, le nettoyage et la désambiguïsation de grammaires, ainsi que sur la démonstration de la nature algébrique d’un langage.
Troisième partie (3 cours) – Analyse syntaxique.
Cette section couvre les méthodes d’analyse descendantes (facile) puis ascendantes (plus difficile) avec les automates LR(0), SLR(1), LR(1) et LALR(1). Les étudiants apprennent à construire et utiliser ces automates pour analyser des langages, à travers des exemples de complexité croissante.
Enseignement à Distance (Oui / Non) Non
Modalités pédagogiques particulières: Cours disponible sur utube.
Bibliographie: 'Aho et Ullman "Compilateurs : principes, techniques et outils".
Langue(s) d’enseignement: Francais
Nature de l’évaluation ECT
UE,
Nombre Crédits ECTS normal
Volume horaire : CM 18/ TD 24 /TP 0 Total 42
Types d’épreuves pour chaque session :
Partiel 36% Devoir Maison 4% Examen 60%
Rattrapage: on oublie le partiel et le DM c'est plus dur car ca porte sur toute l'année
Modalités:
ECTS:
Type:
Complexité:
Condition d'accès:
Année: 25/26