ECTS : 5
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
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