Volume horaire
- CM :
51 h
- Volume horaire global (hors stage) :
51 h
Compétences à acquérir
- Être capable de reconnaître et de définir des langages rationnels et algébriques, et de manipuler les structures qui les représentent
- Pouvoir écrire un analyseur syntaxique simple pour analyser des données structurées
Description du contenu de l'enseignement
Le but de ce cours est d'acquérir les bases des langages formels :
- Mots et langages, lemme d'Arden (équations linéaires sur les langages)
- Automates finis et langages rationnels : équivalence entre langages reconnus par automates finis et langages rationnels. Algorithmes de déterminisation et de minimisation.
- Grammaires et langages algébriques. Transformation de grammaires, ambiguïté, équivalence avec les langages reconnus par automates à pile.
- Brève introduction à la calculabilité et aux machines de Turing
La principale application de ce cours sera aux premières étapes de la compilation : analyse lexicale et syntaxique, avec utilisation des outils Flex et Bison en TP.
Bibliographie, lectures recommandées
- Jean-Michel Autebert, Théorie des langages et des automates, 1994, Masson