Vous êtes ici

  1. Accueil
  2. Théorie des langages

Théorie des langages

Théorie des langages

En pratique :

Volume horaire de cours : 8
Volume horaire global de TD : 8
Volume horaire global de TP : 8
Langue principale : français

Description du contenu de l'enseignement

Découvrir et apprendre à utiliser la théorie des langages de description de langages les plus utilisés dans les applications informatiques : expressions régulières et grammaires algébriques, concept de puissance d'expression et de hiérarchie de Chomsky, classes de reconnaisseurs de langages, automates finis, automates à pile, analyseurs LL.
Découvrir et apprendre à résoudre les difficultés d'usage de ces formalismes : non-déterminisme, ambiguïté, limitation des reconnaisseurs.
Découvrir et apprendre à utiliser des outils qui mettent en œuvre ces théories : ANTLR et Xtext.


Compétences à acquérir

  • Choisir le bon formalisme pour chaque besoin : langages rationnels ou algébriques.
  • Développer des expressions régulières ou une grammaire algébrique en fonction d'un besoin.
  • Les mettre en œuvre en utilisant des outils logiciels : ANTLR et Xtext.
  • Valider ces mises en œuvre.
  • Résoudre les difficultés inhérentes à ces systèmes.

Bibliographie, lectures recommandées

  • Jacques Vélu, « Méthodes mathématiques pour l'informatique », (Dunod 2005). Traite de nombreux sujets, dont la théorie des langages formels.
  • André Arnold et Irène Guessarian, « Mathématiques pour l'informatique », (ÉdiScience, 2005). Idem en plus austère.
  • Scheila Greibach, « Formal languages: Origins and Directions », (Annals of Computing History, 1981). Traite de l'histoire des concepts de la théorie des langages formels.
  • A.K. Dewdney, « The new Turing Omnibus », (Owl Books, 2001). Traite de nombreux sujets informatiques, dont la théorie des langages formels. Un must read pour une formation en informatique.
  • Les travaux pratiques utilisent les outils ANTLR et Xtext, décrits dans les ouvrages suivants, Terence Parr, « The Definitive ANTLR Reference », (Pragmatic Bookshelf, 2007) et Lorenzo Bettini, « Implementing Domain-Specific Languages with Xtext and Xtend » (Packt, 2013).