Cours 2017-2018

Théorie des langages : syntaxe et sémantique [INFOB314]

  • 5 crédits
  • 30h+30h
  • 2e quadrimestre
Langue d'enseignement: Français
Enseignant: Schobbens Pierre

Acquis d'apprentissage

L'étudiant sera capable : 

- de reconnaître un problème traitable par une expression régulière, une grammaire hors-contexte, une grammaire attribuée.

- de formaliser ce problème et d'utiliser des outils pour exécuter cette formalisation.

Objectifs

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

Contenu

Syntaxe

  1. Expressions régulières et automates d'états finis
  2. 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)

 

Table des matières

Syntaxe

  1. Expressions régulières et automates d'états finis
  2. 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)

 

Description des exercices

Les travaux pratiques comportent deux parties: Un projet pratique vise à réaliser le compilateur d'un petit langage. Un outil de test automatique est à la disposition des étudiants, et sert également à l'évaluation.  D'autre part, des exercices en salle sur papier permettent de manipuler les concepts du cours dans un cadre simplifié.

Disciplines

Sémantique des langages de programmation

Méthodes d'enseignement

Le cours ex-cathedra se concentre sur les concepts fondamentaux. Les travaux pratiques illustrent les concepts par l'emploi d'outils sur des exemples simples: générateurs d'analyseur lexical, syntaxique, de code pour un petit langage. Il comprennent un projet pratique et des exercices en salle.

Mode d'évaluation

Le projet pratique a une pondération importante d'un tiers. L'examen écrit reçoit une pondération de 2/3. Les examens écrits précédents sont disponibles sur le site Web du cours.

Sources, références et supports éventuels

  1. Aho, Sethi, Ullman: "Compilateurs: principes, techniques et outils", InterEditions/Dunod.
    BUMP #I 412/037.
  2. R. Wilhelm, D. Maurer: "Les compilateurs: théorie, construction, génération", Masson, 1994.
    BUMP #I 412/030, ISBN 2225846154.
  3. R. Wilhelm et al. "Compiler Design", 3 volumes, Springer Verlag, 2013.
  4. John Levine, Tony Mason & Doug Brown « lex & yacc », ISBN 1-56592-000-7, 366 pages.
  5. Terence Parr, "The Definitive ANTLR Reference", The Pragmatic Programmers, 2012.
  6. M. Hennessy: "The semantics of programming languages: an elementary introduction using structural operational semantics", Wiley, 1990.
  7. G. Winskel: "The Formal Semantics of Programming Languages: An Introduction.", MIT Press, 1993.

Langue d'enseignement

Français

Lieu de l'activité

NAMUR

Faculté organisatrice

Faculté d'informatique
rue Grandgagnage 21
5000 NAMUR
T. 081725252
F. 081724967
secretariat.info@unamur.be

Cycle

Etudes de 1er cycle