INFO 2108

Théorie des langages:

syntaxe et sémantique des langages de programmation

Titulaire

Statut

30h cours +30h TP+ travail personnel important

Objectif

Aborder les principales théories nécessaires à la compréhension, la compilation et l'interprétation des langages de programmation.

Contenu

Syntaxe

Expressions régulières et automates d'états finis
Langages non-contextuels:

Grammaires de Backus-Naur (BNF)
Analyse syntaxique descendante et ascendante
Générateurs d'analyseurs syntaxiques: LL, LR, LALR.

Sémantique

Génération de code (bases)
Sémantique statique:

vérification de types
grammaires attribuées

Sémantique dénotationnelle: domaines de Scott, points fixes, interprétation abstraite
Sémantique opérationnelle structurée
Sémantique axiomatique (rappels)

Horaire

Cours le jeudi soir de 18h à 21h à l'auditoire I2 pendant 6 séances; ensuite le jeudi matin de 8h30 à 10h30.

L'horaire en format ICS (iCal)

Si votre ordinateur ne comprend pas ce format, le voici converti en HTML

Pédagogie

Le cours (30h) se concentre sur les concepts fondamentaux. Les travaux pratiques (30h) comportent deux parties: Un exercice intégré couvrant la plupart du cours, vise à réaliser à l'aide d'outils courants (générateurs d'analyseur lexical, syntaxique) le compilateur d'un petit langage. Un outil de test automatique est à la disposition des étudiants, et sert également à l'évaluation. Le langage de travail est le C, que les étudiants apprendront par eux-même. D'autre part, des petits exercices en salle sur papier permettent de manipuler les concepts du cours dans un cadre simplifié.

Evaluation

Les travaux pratiques ont une pondération importante mais pas majoritaire. L'évaluation de l'exercice intégré est décrite dans un document séparé. L'examen écrit reçoit une pondération majoritaire.

Prérequis

Connaissance d'un langage impératif typé, si possible Pascal, et si possible d'un langage fonctionnel typé d'ordre supérieur comme ML, CaML, Miranda, Haskell.

Références

Aho, Sethi, Ullman: "Compilateurs: principes, techniques et outils", InterEditions/Dunod.
BUMP #I 412/037.
R. Wilhelm, D. Maurer: "Les compilateurs: théorie, construction, génération", Masson, 1994.
BUMP #I 412/030, ISBN 2225846154.
John Levine, Tony Mason & Doug Brown « lex & yacc », 2nd Edition October 1992, ISBN 1-56592-000-7, 366 pages.
B. W. Kernighan & D. M. Ritchie « Le langage C », Masson
La programmation en C, Byron S. Gottfried, Série Schaum, McGraw-Hill, ISBN : 2704212309
M. Hennessy: "The semantics of programming languages: an elementary introduction using structural operational semantics", Wiley, 1990.
G. Winskel: "The Formal Semantics of Programming Languages: An Introduction.", MIT Press, 1993.

Sur le Web

Sophie Gire, Théorie des langages, syllabus résumé pour le début du cours.
Fraunhofer Institute, The catalog of compiler construction tools , liste d'outils.

Examens PostScript, LaTeX, PDF, html)