Compilation

Cette unité obligatoire se déroule au S5 de la licence LST A - mention Informatique.

Responsable

Mirabelle Nebut

Volume horaire

L'unité comporte une séance de cours, TD et TD-machine hebdomadaire de 1h30 chacune.

Crédits

5 ECTS

• Objectifs
• Contenu
• Organisation
• Bibliographie

Objectifs

L'objectif de l'UE est :

• d'étudier les différentes techniques, notions théoriques et algorithmes impliqués dans la construction des applications de traitement de données textuelles, essentiellement les phases d'analyse lexicale et syntaxique et la constuction d'un modèle sémantique ;
• de les appliquer en TP à des cas d'études de type DSL (Domain-Specific Languages) externes, en expérimentant la construction de l'application à la main, puis en utilisant des générateurs d'analyseurs lexical et syntaxique (JFlex, Cup, antLR).

Contenu

La construction des applications de traitement de données textuelles est un sujet passionnant par la diversité des aspects traités : l'UE aborde à la fois des notions de théorie du langage, des aspects très algorithmiques et des aspects de génie logiciel. En effet, les outils de base pour définir le langage source (langage de programmation à la Java comme DSL maison) appartiennent au domaine de la théorie des langages, domaine plutôt théorique très appliqué à l'informatique. On rappellera donc comment définir les unités lexicales d'un langage par des expressions rationnelles représentées par des automates finis, et on verra comment définir la structure syntaxique d'un langage par une grammaire algébrique représentée par un automate à pile, puis sa sémantique par une grammaire attribuée et une représentation interne. Par ailleurs, la bonne conception de l'application est nécessaire~: logiciel-compilateur facilement extensible et modifiable, modulaire. Les concepts, techniques et outils de génie logiciel pour concevoir et réaliser un compilateur sont maintenant bien connus : ils appartiennent aussi au domaine de la compilation. On verra en outre comment, en s'appuyant sur la définition formelle de certains modules, on peut générer automatiquement leur code.

Organisation

Le but des cours et des TD est d'acquérir les bases (notions théoriques, algorithmes) et de préparer les TD-machines.

Le but des TPs n'est pas de construire un compilateur pour un langage de programmation, qui irait jusqu'à la génération de code exécutable (cet aspect n'est plus du tout couvert par l'UE). L'idée est de s'exercer sur quelques cas d'études de type DSL externe. On utilisera pour ce faire les outils (pour Java) JFlex et Cup, générateurs d'analyseurs lexicaux et d'analyseurs syntaxiques respectivement, puis antLR (idem). Ces outils prennent en entrée une description (expressions régulières dans un cas, grammaire algébrique dans l'autre) et génèrent automatiquement l'analyseur équivalent. L'idée est de vous faire bien comprendre tous les avantages apportés par les notions théoriques qui sous-tendent la compilation : plutôt que de se coltiner l'écriture à la main de tels analyseurs, on peut utiliser des outils sûrs qui exploitent ces notions et font le travail à notre place.

Bibliographie

• un grand classique, "le Dragon" :

  Aho, Sethi, Ullman
  Compilateurs : principes, techniques et outils
  InterEditions, 1991

• un ouvrage très pragmatique :

  Grune, Bal, Jacobs, Langendoen
  Compilateurs
  Dunod, 2002
  

• un ouvrage plus formel, très rigoureux :

  Wilhelm, Maurer
  Les compilateurs : théorie, construction, génération
  Masson, 1994
  

• un ouvrage très pragmatique, orienté Java :

  Appel
  Modern Compiler Implementation in Java
  Cambridge University Press, 1998
  

• un livre tout génie logiciel sur les DSL :

  Fowler
  Domain-Specific Languages
  Addison Wesley, 2011
  

L'évaluation est basée sur le contrôle continu : rendus des TP, petites interrogations en amphi en cours de semestre, gros contrôle récapitulatif en fin de semestre.

Trois notes seront attribuées à chaque étudiant durant le semestre :

• I : une note sur 20 correspondant à une ou des interrogations écrites réparties sur le semestre (en amphi);
• TP : une note sur 20 correspondant à des TPs rendus par binôme ou monôme;
• DS : une note sur 20 correspondant au devoir surveillé de fin de semestre.

La note finale sur 20 (N) est calculée comme une moyenne pondérée de ces trois notes.
Attention la note de TP est en dehors du SUP et est conservée en seconde session.

N = (TP + sup(DS1 + 2*DS2, 3*DS2)) /4

Lors de la seconde session seule la note de TP est conservée, la note obtenue lors de la seconde session remplaçant sup(DS1 + 2*DS2, 3*DS2).

L'unité acquise apporte 5 ECTS.

Mode d'emploi de l'UE :

• pour bien en profiter : assister aux cours, aux TDs et au TPs. Les supports et les corrections sont toujours incomplets et ne remplacent pas le présentiel.
• pour limiter le temps que vous y passerez :
  • comprendre le cours pendant le cours, en étant attentif, en posant des questions (généralement, quand un étudiant ne comprend pas un transparent, la moitié de l'amphi se pose aussi des questions)
  • bien lire les documents fournis : les supports de cours ne sont pas là uniquement pour faire joli, les réponses aux exercices de TD sont dedans !
  • relire le cours concerné par la séance de TD avant d'y aller.
  • si les supports de TD sont fournis avant la séance : au moins lire le sujet, si possible le chercher (c'est en étant actif que le cerveau apprend, pas en lisant une correction)
  • travailler régulièrement, et venir voir les enseignants de TD et/ou amphi si c'est la brasse coulée.
• vous êtes absent pour une raison ou une autre ?
  • prévenez votre enseignant de TD et d'amphi, ou Patricia Caron
  • demandez un aménagement des rendus de TP sur PROF
• vous avez des critiques constructives à apporter à l'UE ? Parlez-en gentiment à l'enseignant d'amphi ou de TD

Supports de cours

Introduction :

• transparents introduction, introduction 6 par page
  

Analyse lexicale :

• transparents incluant des rappels : format standard, format 6 par page

Grammaires algébriques :

• transparents format standard, format 8 par page

Grammaires attribuées :

• transparents format standard, format 8 par page

Grammaires attribuées :

• transparents format standard, format 8 par page

Un brin d'analyse sémantique :

• transparents format standard, format 8 par page

Automates à pile :

• transparents format standard, format 8 par page

Analyse descendante LL(1) :

• transparents format standard, format 8 par page

Analyse ascendante :

• transparents format standard, format 8 par page

Énoncés de TD

• rappels expressions régulières et automates à nombre fini d'état format standard, format 2 par page
• analyse lexicale format standard, format 2 par page
• grammaires algébriques format standard, format 2 par page
• Grammaires attribuées : format standard, format 2 par page
• automates à pile généraux, analyse syntaxique universelle: format standard, format 2 par page
• analyse syntaxique et grammaires LL(1) : format standard, format 2 par page
• analyse ascendante : format standard, format 2 par page

Énoncés de TP

• TP1 : génération non outillée de planning Latex sujet, sujet 2 par page, archive
• TP2 : génération outillée de planning Latex : analyse lexicale sujet, sujet 2 par page, archive
• TP3 : génération outillée de planning Latex : analyse syntaxique sujet, sujet 2 par page, archive
• TP4 : génération outillée de planning Latex : génération des fichiers Latex sans Visiteur sujet, sujet 2 par page, archive
• TP5 : grammaires à opérateurs et Cup sujet, sujet 2 par page archive Les scripts et les sources sont prévus pour le paquetage calcul et les noms ParserCalcul, ScannerCalcul, lexiqueCalcul.lex et syntaxeCalcul.cup.
• TP6 : outil ANTLR, lexique et syntaxe sujet, sujet 2 par page, archive
• TP7 : outil ANTLR, grammaires attribuées sujet, sujet 2 par page, archive

Documentation

• Présentation du langage Init, format 2 par pages
• Présentation du langage Ava
• Présentation de Ava et Init sur une seule feuille
• documentation de JFlex
• documentation de Cup
• pour mettre à jour vos variables d'environnement pour JFlex et Cup : utiliser source /home/enseign/COMPILS5/envm5.sh.

  #!/bin/sh
  # pour avoir JFlex et Cup
  export CLASSPATH=.:classes/:../classes/:/usr/share/java/JFlex.jar:/usr/share/java/cup.jar:/home/enseign/COMPILS5/bcel/bcel-5.2.jar:$CLASSPATH
  # pour être sûr d'avoir ant + voir les scripts
  export PATH=/usr/local/bin:scripts:$PATH
  

Contrôle continu 2011

• rappels
• analyse lexicale
• grammaires algébriques, définitions de base
• écriture de grammaires algébriques
• régulier ? algébrique ?
• Grammaires ambiguës

Annales

• décembre 2010, session 1 : format normal, format 2 par page
• mars 2011, session 2 : format normal, format 2 par page
• décembre 2009, session 1 : format normal, format 2 par page
• février 2010, session 2 : format normal, format 2 par page
• janvier 2009, session 1 (exceptionnellement durée 2h) : format normal, format 2 par page
• juin 2009, session 2 (exceptionnellement durée 2h) : format normal, format 2 par page
• janvier 2008, session 1 : format normal, format 2 par page
• juin 2008, session 2 : format normal, format 2 par page

Ces sujets correspondent à des cours différents de celui d'après 2007-2008.

• janvier 2007
• février 2006
• janvier 2006
• septembre 2004
• juin 2004