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