Ce cours présente les fondements des langages de programmation et développe les phases d’analyse lexicale et syntaxique d’un compilateur. Les étudiants sauront, à l’issue du semestre, réaliser un analyseur lexical et un analyseur syntaxique.

I. Mots, Langages et Grammaires (24h)
1. Définitions, dérivations, langage engendré par une grammaire
2. Classification de Chomsky
3. Langages réguliers (grammaires, automates d’états finis, expressions régulières)
4. Langages algébriques (grammaires, automates à pile)
II. Analyse lexicale (12h)
1. Les expressions régulières dans l’analyse lexicale,
2. Générateur d’analyseur lexical (Lex, JCC).
III. Analyse syntaxique (24h)
1. Méthodes d’analyse syntaxique (ascendante, descendante),
2. Automates à pile dans l’analyse syntaxique,
3. Analyse descendante récursive,
4. Générateur d’analyseur syntaxique (Yacc, JCC).
IV. Travaux Pratiques
1. TP1 : Automates d’états finis
2. TP1 : Mise en œuvre d’un analyseur lexical (Lex, JCC),
3. TP2 : Mise en œuvre d’un analyseur syntaxique (JCC).

TP (10h)

A. Aho, J.D. Ullman, « The Theory of Parsing, Translation, and Compiling », Prentice Hall, Inc., Englewood Cliffs, New Jersey, 1972.
P. J. Denning, J. B. Dennis, and J. E. Qualitz, “Machines, languages, and Computation”, Prentice-Hall, Inc. Englewood cliffs, New Jersey, 1978.
R. Floyd, R., Biegel, « Le Langage des Machines : Introduction à la calculabilité et aux langages formels », Thomson Publishing, France, 1994.
J.E. Hopcroft, J.D. Ullman, « Introduction to Automata Theory and Computation », Addison Wesley Publishing Company, 1979.
Wolper, Pierre, « Introduction à la calculabilité », InterEditions, Paris, 1991.