Cours 2020-2021

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 : LL, LL(*)
  • Générateurs d'analyseurs syntaxiques ascendante:  LR, SLR, LALR.

Sémantique

  1. Sémantique statique:
    1. vérification de types
    2. grammaires attribuées
  2. Génération de code (bases)
  3. Sémantique opérationnelle structurée
  4. 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

Pré-requis

Les unités d’enseignement d’une des propositions suivantes:

  1. Algorithmique [INFOB237] et Fondements mathématiques pour l'informatique (2e partie) [INFOB221]
  2. Concepts des systèmes d'exploitation [INFOB231]

Méthodes d'enseignement

Les modalités d'enseignement et d'évaluation des unités d'enseignement ont été rédigées en fonction de la situation à la rentrée académique 2020-2021. Cependant, ces modalités pourraient faire l'objet de modifications en fonction de l'évolution de la crise sanitaire liée à la covid-19. Les étudiants seront informés de toute modification de la situation générale (passage à l'enseignement à distance partiel ou complet) par les autorités de l'UNamur tandis que les modifications propres à chaque unité d'enseignement leur seront communiquées par les enseignants, via webcampus

Le cours ex-cathedra se concentre sur les concepts fondamentaux. Les travaux pratiques en salle illustrent les concepts par des exemples simples: 

Le projet pratique forme à l'emploi d'outils : générateurs d'analyseur lexical, syntaxique, de code pour un petit langage.

Mode d'évaluation

Les modalités d'enseignement et d'évaluation des unités d'enseignement ont été rédigées en fonction de la situation à la rentrée académique 2020-2021. Cependant, ces modalités pourraient faire l'objet de modifications en fonction de l'évolution de la crise sanitaire liée à la covid-19. Les étudiants seront informés de toute modification de la situation générale (passage à l'enseignement à distance partiel ou complet) par les autorités de l'UNamur tandis que les modifications propres à chaque unité d'enseignement leur seront communiquées par les enseignants, via webcampus

70% Examen écrit à livre ouvert. Les examens écrits précédents sont disponibles sur le site Web du cours.

30% Projet, évalué par le test automatique, un rapport et un examen oral. Le projet doit être fait pendant le semestre, il ne peut être repassé en 2ème session.

Sources, références et supports éventuels

  1. AhoSethiUllman: "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. John LevineTony Mason & Doug Brown « lex & yacc », ISBN 1-56592-000-7, 366 pages.
  4. M. Hennessy: "The semantics of programming languages: an elementary introduction using structural operational semantics", Wiley, 1990.
  5. G. Winskel: "The Formal Semantics of Programming Languages: An Introduction.", MIT Press, 1993.
  6. T. Parr: "The Definitive ANTLR Reference", The Pragmatic Bookshelf, 2013.
  7. R. Wilhelm et al. "Compiler Design", 3 volumes, Springer Verlag, 2013.

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