Automates, langages et compilation

Ects : 5
Compétence à acquérir :
Définir la notion de langage formel et introduire les méthodes permettant de spécifier les langages : description à travers des expressions, reconnaissance par des automates et génération par des grammaires formelles. 
Mise en pratique par un projet sur machine

Description du contenu de l'enseignement :
Langages et automates : alphabets, mots, langages, automates déterministes et non-déterministes, lemme de pompage, exemples 
Expressions : expressions régulières, équivalence entre expressions régulières et langages d’automates 
Analyse lexicale 
Grammaires : langages non rationnels, grammaires régulières, algorithme de reconnaissance CYK. 
Automates à pile : automates à pile, langages non-algébriques 
Analyse syntaxique 
Exemple de grammaires XML 
Introduction à la compilation 
Hiérarchie de Chomsky, Machines de Turing, introduction à la calculabilité  
Applications avec Flex/Bison