IFT 313

Introduction aux langages formels

Département d'informatique

Université de Sherbrooke

Été 2014

Professeur: Froduald Kabanza

Courriel: kabanza@usherbrooke.ca
Local: D4-1022-2
Téléphone: +1 819 821-8000 (62865)
Disponibilité: Mardi 11:00 - 12:00 ou sur rendez-vous

Auxiliaire: Francis Bisson

Horaire

Lundi 13:30-15:20 Local D3-2037
Mardi 8:30-10:20 Local D3-2037

Liens


Devoirs

Devoir Spécification donnée le Thème Pondération Date de remise
1 6 mai Analyseur lexical avec un AFD. Trouver des unités lexicales avec et sans Regex en Java. 5% (notes) 20 mai
2 13 mai Programmer un analyseur lexical avec JFlex 5% (notes) 3 juin
3 3 juin Grammaires LL(1) 5% (notes) 10 juin
4 10 juin Mini-projet avec JavaCC 10% (notes) 15 juillet
5 14 juillet Grammaires LR(0), SLR(1), LR(1) et LALR(1) 5% (notes) 22 juillet
6 22 juillet Mini-projet avec JavaCUP 10% (notes) 4 août

Calendrier du cours

Date Contenu
28/4

Plan de cours

Introduction

Langages réguliers et expressions régulières

Applet pour regex

29/4

Automates fini (AF) et analyse lexicale par un automate fini déterministe (AFD).

5/5

Convertir une expression régulière en un automate fini non déterministe (AFN).

Convertir un AFN en un AFD.

Minimisation d'un AFD

6/5

Lab #1: Exercices sur les expressions régulières, AFN, AFD

Devoir #1 : Analyseur lexical avec un AFD. Reconaître des unités lexicales avec et sans Regex en Java. Regex en Java

12/5

Générateurs d’analyseur lexicaux : JFlex.

Lemme de l'étoile

Grammaires. Langages générés par une grammaire. Dérivation. Arbre d’analyse.

13/5

Lab #2: se familiariser avec JFLEX

Devoir #2 : Programmer un analyseur lexical avec JFLEX.

19/5

Congé

20/5

Grammaires ambiguës. Grammaires hors contexte (GHC).

Automates à pile pour une GHC.

26/5

Automate à pile LL.

Notions d’ensembles First et Follow pour des grammaires LL(1).

27/5

Lab #3 : Exercices sur les grammaires et les automates à piles.

2/6

Analyseurs syntaxiques descendants non-récursifs LL(1)

3/6

Lab #4 : Exercices : grammaires LL(1)

Devoir #3 : Grammaires LL(1)

9/6

Analyseurs syntaxiques descendants récursifs LL(1).

Notions de grammaires attribuées.

Générateurs d’analyseurs syntaxiques LL(1) : JavaCC.

10/6 Révision de mi-session

Lab #5 :  Familiarisation avec JavaCC

Devoir #4 : Programmer un parseur avec JavaCC.

16/6
Automates à piles LR. Notion de poignée (handle).
17/6

Période des examens périodiques : pas de cours.

23/6

Examen de IFT313 - Consulter l'horaire des examens pour les détails.

24/6

Congé universitaire - Journée nationale du Québec

30/6

Congé universitaire - Journée nationale du Québec

1/7 Correction de l’examen périodique.

Rapel sur automates à piles LR et notion de poignée (handle).

Analyseur LR(0): notion de préfixes viables (viable prefixes); notion d’éléments (items) LR(0).

7/7

Analyseurs LR(0), suite : AFD pour reconnaître les préfixes viables.

8/7

Analyseurs SLR(1): pilote LR (1); générer une tables d'analyse SLR(1).

Analyseurs LR(1) et LALR(1): générer une tables d'analyse LR(1) et LALR(1).

14/7

Lab #6 (Exercices 1-2 et Exercice 3) :  grammaires LR(0) et SLR(1).

Devoir #5 : grammaires LR(0), SLR(1), LR(1), LALR(1)

15/7

Lab #7 : Exercices: grammaires LR(1) et LALR(1).

21/7

Générateur d’analyseurs syntaxiques LR: Java CUP.

Lab #8 : Laboratoire supervisé sur Java CUP

Devoir #6 : Programmer un parseur avec Java CUP.
22/7 Révision finale
28/7

Consultation au laboratoire sur Java CUP

29/7

Consultation au laboratoire sur Java CUP

4/8

Consultation au laboratoire sur Java CUP

5/8

Période des examens finaux (du 5 au 15 août)