Automates, langages et compilation
ECTS : 5
Volume horaire : 51
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.
Compétence à 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
Bibliographie, lectures recommandées :
- Jean-Michel Autebert, Théorie des langages et des automates, 1994, Masson