AccueilLicence généraleInformatiqueEnseignementsLangages et automates

Licence InformatiqueUE Langages et automates

Contenu

Objectifs de l’enseignement :

Ce module présente les principaux concepts et techniques sur lesquels repose de manière générale la traduction d'un format dans un autre. A partir de connaissances minimales en langages formels et en génération et manipulation d'automates, l'objectif est de comprendre les différents algorithmes utilisés dans le contexte de l'analyse lexicale et syntaxique et de la traduction. La pratique d'un outil de génération automatique de traducteurs, orienté automates, permet de renforcer les connaissances acquises en théorie des langages et d'illustrer les principes d'analyse sémantique et de traduction. Les domaines d'application concernés sont nombreux : conversion de formats, interprétation ou compilation de programmes informatiques, enjolivement de texte, extraction d'informations, calculs statistiques,…

Plan du cours :

  • Les modèles de langages
    • Modèles pour les langages réguliers : expressions régulières, grammaires régulières et automates à états finis
    • Modèles pour les langages algébriques : grammaires algébriques et automates à pile
    • Equivalences entre modèles
  • Principes d'analyse syntaxique et de traduction
    • Analyse syntaxique par implémentation d'automates à pile
    • Traduction dirigée par la syntaxe, exemple de la compilation
  • Le générateur de traducteurs ANTLR

Compétences visées

A l'issue de cet enseignement, l'étudiant doit être capable de / d’ :

  • expliquer et utiliser les concepts et outils mis en œuvre dans toute activité de traduction
  • modéliser un langage et construire, à partir du modèle du langage, un programme de traduction de ce langage.

Langue utilisée

Langue principale utilisée par cet enseignement : Français.

Bibliographie

  • « Introduction to Automata Theory, Languages and Computation », 2nde édition, J. Hopcroft, R. Motwani, J. Ullman , Addison-Wesley, 2001.
  • « The Theory of Parsing, Translating and Compiling », 2nde édition, Alfred Aho, Jeffrey Ullman, Prentice Hall Inc., 1972.
  • « The definitive ANTLR Reference, Building Domain-Specific Languages », Terence Parr, ISBN 978-0-9787-3925-6, 2007

Pré-requis obligatoires

Bases solides de programmation orientée objet.

Pré-requis recommandés

Initiation à la théorie des langages : modèles de langages (expressions régulières, grammaires et automates).

Modalités d'organisation

Les notions théoriques qui sous-tendent la traduction des langages, c'est-à-dire la modélisation des langages et les principes d'analyse et de traduction, sont d'abord présentées en cours et en travaux dirigés. Ces concepts sont ensuite utilisés lors de travaux dirigés sur ordinateur, à travers l'apprentissage et l'expérimentation de l'outil ANTLR de génération de traducteurs.

Volume des enseignements

  • Cours magistraux : 15 heures
  • Travaux dirigés : 15 heures

Les formations qui utilisent cet enseignement