Ecole Polytechnique Universitaire de Marseille
Département Génie Industriel et Informatique
3 ième année
1998-1999

TITRE DU COURS : THEORIE DES LANGAGES FORMELS ET COMPILATION

NOM DE L'INTERVENANT :  Bernard ESPINASSE

OBJECTIFS VISES PAR LE COURS :

Les microprocesseurs disposent généralement d'un jeu d'instructions très sommaire, peu convivial et qui varie d'un processeur à l'autre. Afin de fournir à l'utilisateur de systèmes informatiques des formalismes universels, expressifs et concis, de nombreux langages de programmation ont été créés. L'objet de la théorie des langages est de les définir. La compilation, pour sa part, à pour objet de transformer les programmes écrits dans ces langages en code machine. L'objectif de ce cours est de fournir au futur ingénieur les connaissances conceptuelles qui lui permettront de mieux comprendre les langages informatiques ainsi que leur compilation.

PREREQUIS : Eléments d'algèbre.

OUVRAGES DE REFERENCE

1. M. GROSS, A.LENTIN, "Notions sur les grammaires formelles", Gauthier-Villards, Paris, 1967.
2. A. AHO, R.SETHI, J. ULLMAN, "Compilateurs : principes, techniques et outils", InterEditions, 1993.

PROGRAMME (séances de 2 heures)

Séance 1 : Théorie des mots
• Présentation générale du cours
• Cadre dans lequel se situe la théorie des langages (définitions).
• Structure de monoïde libre : cas des chaînes de caractères munies de la concaténation
Lecture recommandée : Livre 1, chapitre 1.

Séance 2 : Calcul sur les mots
• Calcul associatif construit sur la congruence et l'équivalence de Thue
• Problème des mots et sa résolution
Lecture recommandée : Livre 1, chapitre 1.

Séance 3 : Les systèmes combinatoires (systèmes de réécriture)
• Systèmes combinatoires dans le monoïde libre
• Notions de production
• Schéma de production
• Types de production : Semi-Thueiennes, normales et antinormales.
• Definition et propriétés des systèmes combinatoires (caractère monogénique, l'ambiguïté d'une démonstration, ...)
Lecture recommandée : Livre 1, chapitre 3.

Auto-apprentissage 1
Étudier livre 1, chapitre 4 : Machine de Turing.

Séance 4 : Introduction aux grammaires et aux langages formels
• Notion de langage, en lien avec celle d'algorithme devant être effectués par des machines :
• Syntaxe et sémantique d'un langage
• Notion de grammaire
• Notion de dérivation dans une grammaire
• Langage de Backus pour l'écriture des grammaires des langages de programmation.
Lecture recommandée :  Livre 1, chapitre 7 (cf. aussi livre 3, chapitre 2.7)

Séance 5 : Grammaires et langages de Chomsky (C-grammaires et C-langages)
• Différentes classes de grammaires selon leur capacité descriptive
• Classification de Chomsky
• Grammaires régulières et grammaires hors contexte
• Grammaires ambigues
• Opérations ensemblistes et symboliques sur les langages
• Expressions régulières : definition et propriétés
Lecture recommandée :  Livre 1, chapitre 7 (cf. aussi livre 3, chapitre 2.7)

Séance 6 : Les automates à états finis
• Introduction aux automates
• Automates à états finis
• Langage reconnu (grammaires régulières)
• Caractère déterministe ou non déterministe
Lecture recommandée :  Livre 1, chapitre 10 (cf. aussi livre 4, chapitre 4)

Séance 7 : Les automates à états finis
• Passage d'un automate non déterministe à un automate déterministe
• Passage d'une grammaire régulière à un automate à états fini
Lecture recommandée :  Livre 1, chapitre 10  (cf. aussi livre 4, chapitre 6)

Séance 8 : Les automates à pile
• Langage reconnu (grammaires hors contexte)
• Caractère déterministe ou non déterministe
• Passage d'une grammaire hors contexte à un automate à pile
Lecture recommandée :  Livre 1, chapitre 10 (cf. aussi livre 4, chapitre 10)

Auto-apprentissage 2
Étudier livre 2, chapitre 2 : Un compilateur simple en une passe.

Séance 9 : Introduction à la compilation
• Notions de traducteur, interpréteur et compilateur
• Architecture et grandes fonctions des compilateurs :
• Analyse lexicographique
• Analyse syntaxique
• Génération et optimisation du code
Lecture recommandée :  Livre 2, chapitre 1.

Séance 10 : Analyse syntaxique d'un compilateur
• Méthodes générales :
• Méthode générale descendante
• Méthode générale montante
• Autres méthodes
Lecture recommandée :  Livre 2, Chapitre 3.

Examen sans document le ....

BIBLIOGRAPHIE COMPLEMENTAIRE

1. Cl.BENZAKEN, "Systèmes formels : Introduction à la logique et à la théorie des langages", Masson éditeur, 1991.
2. J-M. AUTEBERT, "Théorie des langages et des automates", Masson, 1994.