Plan de cours IFT313

Éric Beaudry

Description

Plan de cours IFT 313 – Introduction aux langages formels Été 2010 Département d’informatique IFT 313 Introduction aux langages formels Plan de cours Été 2010 Enseignant Éric Beaudry Courriel : [e-mail] Local : D6-0047 Téléphone : [phone] poste 63664 Site Web: http://planiart.usherbrooke.ca/~eric/ift313/ Disponibilité : à déterminer à la première séance de cours. Auxiliaire Francis Bisson Courriel : [e-mail] Horaire Exposé magistral : Mardi 13h30 à 15h20 salle D3-2036 Jeudi 8h30 à 10h20 salle D3-2036 Reprises* : Vendredi 9h30 à 11h20 salle D3-2036 * Il y aura deux séances de reprise les vendredi 7 mai et 25 juin afin de compenser les séances de cours annulées les jeudis 13 mai et 8 juillet. 1Description officielle de l'activité pédagogique Objectifs S'initier aux fondements théoriques des langages de programmation, en particulier aux langages formels, à la théorie des automates ainsi qu'à l'analyse lexicale et syntaxique. Contenu Langages réguliers et expressions régulières. Automates finis et analyseurs lexicaux. Langages et grammaires hors contexte. Arbre syntaxique et grammaire ambiguë. Automates à pile de mémoire, analyseurs syntaxiques descendants et analyseurs syntaxiques ascendants. Machines caractéristiques. Classes de grammaires hors contexte : LL, SLR, LALR et LR. Applications aux langages de programmation. Générateurs d'analyseurs lexicaux et syntaxiques ...

Sujets

• informatique

Informations

• Publié par: Nisig
• Nombre de lectures: 129
• Langue: Français

Extrait

Plan de cours

IFT 313

–

Introduction aux langages formels

Été 2010

2010-04-15

1

Département d’informatique

IFT 313

Introduction aux langages formels

Plan de cours

Été 2010

Enseignant

Éric Beaudry

Courriel :

[e-mail]

Local :

D6-0047

Téléphone :

[phone] poste 63664

Site Web:

http://planiart.usherbrooke.ca/~eric/ift313/

Disponibilité : à déterminer à la première séance de cours.

Auxiliaire

Francis Bisson

Courriel

:

[e-mail]

Horaire

Exposé magistral :

Mardi 13h30 à 15h20

salle D3-2036

Jeudi

8h30 à 10h20

salle D3-2036

Reprises* : Vendredi

9h30 à 11h20

salle D3-2036

*

Il y aura deux séances de reprise les vendredi 7 mai et 25 juin afin de compenser les séances de

cours annulées les jeudis 13 mai et 8 juillet

.

Description officielle de l'activité pédagogique

1

Objectifs

S'initier aux fondements théoriques des langages de programmation, en particulier aux langages

formels, à la théorie des automates ainsi qu'à l'analyse lexicale et syntaxique.

Contenu

Langages réguliers et expressions régulières. Automates finis et analyseurs lexicaux. Langages et

grammaires hors contexte. Arbre syntaxique et grammaire ambiguë. Automates à pile de mémoire,

analyseurs syntaxiques descendants et analyseurs syntaxiques ascendants. Machines

caractéristiques. Classes de grammaires hors contexte : LL, SLR, LALR et LR. Applications aux

langages de programmation. Générateurs d'analyseurs lexicaux et syntaxiques.

Crédits

3

Organisation

3 heures d’exposé magistral par semaine

1 heure d’exercices par semaine

5 heures de travail personnel par semaine

Préalable

MAT 115

1

http://www.usherbrooke.ca/fiches-cours/ift313

Plan de cours

IFT 313

–

Introduction aux langages formels

Été 2010

2010-04-15

2

1

Présentation

Cette section présente les objectifs et le contenu détaillé du cours.

Cette section représente la description officielle

du cours telle qu'adoptée par les comités de programme du département d'informatique. Elle ne peut être modifiée

sans l'autorisation des comités de programme.

1.1

Mise en contexte

Des langages de programmation tels que Java, C++, C# nécessitent un compilateur pour traduire du code source en

un code exécutable ou intermédiaire. Les langages pour le Web tels que HTML ou XML ont aussi besoin d’être

interprétés et traduits en différents formats, pour permettre par exemple la manipulation de données spécifiées dans

ces langages par diverses applications. De tels compilateurs, interpréteurs ou traducteurs de langages sont en

principe structurés en plusieurs phases, chacune opérant à un niveau d’abstraction particulier du langage source. Par

exemple, la traduction d’un programme source en Java (fichier de type « .java ») en code exécutable sur une

machine

virtuelle Java

(fichier « .class ») implique au moins une phase d’analyse lexicale, une phase d’analyse syntaxique et

une phase d’analyse sémantique. L’analyse lexicale reconnaît et isole les différentes mots du code source constituant

une unité lexicale (les variables, les accolades, les mots-clés du langage tels que « if », « while », etc.). La séquence

de mots reconnus est ensuite passée à un analyseur syntaxique, qui

vérifie que la syntaxe du programme source est

correcte. Finalement la phase sémantique effectue la traduction en code cible ou code exécutable.

Chacune de ces phases repose sur des principes, des concepts et des techniques bien établis. L’analyse lexicale

repose le plus souvent sur les concepts d’

expressions régulières

et d’

automates finis

alors que l’analyse syntaxique

repose sur les concepts de grammaires hors-contextes et d’automates à piles. En outre, il existe des outils efficaces

de génération automatique d’analyseurs lexicaux et d’analyseurs syntaxiques.

Ce cours introduit les principes fondamentaux, les concepts, les structures de données, les techniques ainsi que les

algorithmes pour l’analyse lexicale et l’analyse syntaxique des langages de programmation. Néanmoins, bien que la

matière du cours soit enseignée dans une optique de langages de programmation, elle s’avère fondamentale pour

d’autres domaines de l’informatique. En particulier, certains concepts et principes que nous verrons constituent une

bonne base théorique pour des techniques et outils de traitement du langage naturel dans le domaine de l’intelligence

artificielle.

Les mêmes concepts et principes sont utiles pour comprendre des techniques avancées de vérification et

de validation automatique des programmes en génie logiciel.

1.2

Objectifs spécifiques

À la fin de cette activité pédagogique, l’étudiante ou l’étudiant sera capable :

1.

de comprendre le rôle des différentes phases d’analyse d’un compilateur (lexicale, syntaxique et

sémantique);

2.

de reconnaître un langage régulier, d’écrire une expression régulière pour ce langage et d’utiliser des outils

comme

grep

(Unix / Linux) et

Regex

(Java);

3.

d’écrire et de programmer un automate fini pour reconnaître un langage régulier;

4.

d’écrire une expression régulière équivalente à un automate fini non déterministe (AFN);

5.

de convertir un AFN en un automate fini déterministe (AFD);

6.

de calculer un AFD minimal à partir d’un autre AFD;

7.

de programmer un simulateur d’AFD pour reconnaître des unités lexicales dans un fichier texte;

8.

d’utiliser un générateur d’analyseur lexical;

9.

de reconnaître et d’expliquer les différents types de grammaires (sensible au contexte, hors contexte,

régulière);

10.

de donner une grammaire pour reconnaître un langage donné et l’inverse (donner langage pour grammaire);

11.

d’expliquer la notion d'arbre d’analyse et son utilité;

12.

de déterminer si une grammaire est ambiguë;

13.

d’écrire un automate à pile pour accepter un langage donné;

14.

de simuler un automate à pile;

15.

de pouvoir décrire et simuler un automate à pile LL;

16.

de générer une table d’analyse LL pour une grammaire donnée;

17.

de comprendre et de pouvoir simuler l’algorithme d’analyse LL non récursif;

Plan de cours

IFT 313

–

Introduction aux langages formels

Été 2010

2010-04-15

3

18.

de programmer un analyseur syntaxique récursif pour une grammaire donnée;

19.

d’utiliser un générateur d’analyseurs syntaxiques LL («

top-down

»);

20.

de décrire et simuler un automate à pile LR;

21.

de calculer l’AFD des « préfixes viables » d’une grammaire donnée;

22.

de générer des tables d’analyse LR(0), SLR(1), LR(1) et LALR(1) d’une grammaire donnée;

23.

d’expliquer les avantages et inconvénients des approches d'analyse LL, LR(0), SLR(1), LR(1) et LALR(1);

24.

de simuler et d’expliquer le fonctionnement de l’algorithme d’analyse LR;

25.

d’utiliser un générateur d’analyseurs syntaxiques LR («

bottom-up

»).

1.3

Contenu détaillé

Thème

Contenu

Heures

Objectifs

1

Introduction au fonctionnement des compilateurs et des traducteurs

de langages de programmation : qu’est-ce que l’analyse lexicale,

syntaxique et sémantique.

2

1

2

Analyse lexicale :

langages réguliers, expressions régulières, automates fini

déterministes (AFD), automates finis non-déterministes (AFN).

7

2-7

3

JFlex : outil de génération d’analyseurs lexicaux.

2

8

4

Analyse syntaxique (introduction) :

types de grammaires, relation entre langages et grammaires,

automates à pile, grammaires hors-contextes et grammaire ambiguë.

5

9-14

5

Analyse syntaxique descendante :

automates à pile LL, notions d’ensemble

First

et

Follow

pour les

grammaires LL, génération de tables d’analyses LL(1), analyse

récursive

6

15-18

6

JavaCC : outil de génération d’analyseur syntaxique LL(1).

3

19

7

Analyse syntaxique ascendante :

automates à pile LR, notions préfixes viables, d’éléments LR(0), AFD

pour reconnaître des préfixes viables. Construction d’analyseurs

LR(0), SLR(1), LR(1) et LALR(1).

16

20-24

8

JavaCUP : outil de génération d’analyseurs syntaxiques LR.

4

25

9

Autres outils d'analyse lexicale et syntaxique.

3

1-25

10

Révision et consultation.

4

1-25

2

Organisation

2.1

Méthode pédagogique

Le cours comprend trois heures d’exposé magistral, une heure d’exercices dirigés et cinq heures de travail personnel

par semaine. Si la situation l’exige, selon l’appréciation du professeur, il pourrait y avoir quatre heures d’exposé

magistraux durant une semaine, suivi de deux heures d’exposé magistral et deux heures d’exercices la semaine

suivante.

2.2

Calendrier du cours

Sem

aine

Dates

Contenu

[thèmes entre crochets; réf. section 1.4]

Laboratoire /

Travaux pratiques

Lecture *

1

27 et 29

avril

Plan de cours + introduction. [1]

Langages réguliers + Expressions régulières. [2]

Automates fini (AF) + Analyse lexicale par un

automate fini déterministe (AFD). [2]

TP1

A : 2.1-2.4

D : 1, 2.1-2.5

Plan de cours

IFT 313

–

Introduction aux langages formels

Été 2010

2010-04-15

4

2

4 et 6

mai

Convertir une expression régulière en un automate

fini non déterministe (AFN). [2]

Convertir un AFN en un AFD. [2]

Génération d’un ADF directement à partir

d’expressions régulières (« items »). [2]

Exercices : expressions

régulières, AFN, AFD

(en classe)

S : 5.6-5.7, 6.1,

6.4-6.6

A :2.5

W :2.6-2.7

D :3.5, 3.8

7 mai

(*reprise)

Calculer un AFD minimal. [2]

Générateurs d’analyseur lexicaux : JFlex. [3]

TP2

Doc JFlex

3

11 mai

Séance d’exercices avec l’auxiliaire

d’enseignement le mardi 11 mai.

Pas de cours le jeudi 13 mai.

Exercices : JFlex

(D4-1017)

4

18 et 20

mai

Grammaires. Langages générés par une

grammaire. Dérivation. Arbre d’analyse. [4]

Grammaires ambiguës. Grammaires hors contexte

(GHC). [4]

Automates à pile pour une GHC. [4]

Exercices sur les grammaires et les automates à

piles. [4]

Exercices : JFlex

(D4-1017)

S :3, 10, 18

A : 3.1

W :3.1-3.3

D :4.1-4.4

5

25 et 27

mai

Automate à pile LL. [5]

Notions d’ensembles

First et Follow pour des

grammaires LL(1). [5]

Tables d’analyse LL(1). LL driver. Analyseurs

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

un driver LL(1). [5]

Exercices : grammaires

LL(1)

(En classe)

TP3

S :7, 4.1-4.4, 19

A :3.2

W :4

D :4.4

6

1

er

et 3

juin

Analyseurs syntaxiques descendants récursifs

LL(1). [5]

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

JavaCC. Notions de grammaires attribués et

d’arbres syntaxiques. [5,6]

Exercices JavaCC (D4-

1017)

TP4

A :3.3-3.5, 4

D :2.4, 5

7

8 et 10

juin

Révision + consultations. [10]

TP5

8

15 juin

Examen périodique.

Date, heure (après 17h) et local à confirmer.

9

22 juin

Automates à piles LR. Notion de

poignée

(

handle

). [7]

Correction de l’examen périodique.

A : 3.3, 3.4-3.5

D : 4.5-4.9

S : 20

25 juin

(*reprise)

Notion de préfixes viables (

viable prefixes

) +

notion d’éléments (items) LR(0). AFD pour

reconnaître les préfixes viables. [7]

Analyseurs LR(0). [7]

10

29 juin et

1

er

juillet

Analyseurs SLR(1). [7]

Analyseurs LR(1). [7]

Exercices : grammaires

LR(0) et SLR(1).

Plan de cours

IFT 313

–

Introduction aux langages formels

Été 2010

2010-04-15

5

11

6 juillet

Analyseurs LALR(1). [7]

Pas de cours le jeudi 8 juillet.

Exercices : grammaires

LR(1) et LALR(1)

TP6

12

13 et 15

juillet

Exercices sur l’analyse LR. [7]

Générateurs d’analyseurs syntaxiques LR: Java

CUP. [8]

Exercices :

Java CUP (D4-1017)

TP7

13

20 et 22

juillet

Retour sur JavaCUP et l’analyse LR. [7,8]

Introduction à XML et à la lecture de fichiers

XML. [9]

Implémentation d’un analyseur XML. [9]

14

27 et 29

juillet

Révision sur la première moitié de cours. [10]

Révision sur la deuxième moitié de cours. [10]

Exercices :

Java CUP (D4-1017)

Période

du 3 au

13 août

Examen final.

* Pour les lectures, les lettres correspondent aux manuels référencés à la fin du plan de cours et les chiffres aux

sections.

2.3

Évaluation

Travaux pratiques (7) : 40 %

Examen périodique:

20 %

Examen final:

40 %

2.3.1

Qualité du français et de la présentation

Conformément aux articles 36, 37 et 38 du règlement facultaire d’évaluation des apprentissages

2

l’enseignant peut

retourner à l’étudiante ou à l’étudiant tout travail non conforme aux exigences quant à la qualité de la langue et aux

normes de présentation.

2.3.2

Plagiat

Un document dont le texte et la structure se rapporte à des textes intégraux tirés d’un livre, d’une publication

scientifique ou même d’un site Internet, doit être référencé adéquatement. Lors de la correction de tout travail

individuel ou de groupe une attention spéciale sera portée au plagiat, défini dans le Règlement des études comme « le

fait, dans une activité pédagogique évaluée, de faire passer indûment pour siens des passages ou des idées tirés de

l’œuvre d’autrui. ». Le cas échéant, le plagiat est un délit qui contrevient à l’article 8.1.2 du Règlement des études

3

:

« tout acte ou manœuvre visant à tromper quant au rendement scolaire ou quant à la réussite d’une exigence relative

à une activité pédagogique. » À titre de sanction disciplinaire, les mesures suivantes peuvent être imposées : a)

l’obligation de reprendre un travail, un examen ou une activité pédagogique et b) l’attribution de la note E ou de la

note 0 pour un travail, un examen ou une activité évaluée. Tout travail suspecté de plagiat sera référé au Secrétaire

de la Faculté des sciences.

2.4

Échéancier des travaux

TP

Spécification

donnée le

Thème

Pondération

Date de remise

1

29 avril

Analyseur lexical avec un AFD. Trouver des

unités lexicales

avec et sans Regex en Java.

5 %

7 mai

2

7 mai

Programmer un analyseur lexical avec JFlex

5 %

21 mai

3

25 mai

Grammaires LL(1)

5 %

3 juin

2

http://www.usherbrooke.ca/sciences/intranet/informations-academiques/reglement-d-evaluation/

3

http://www.usherbrooke.ca/programmes/etude

Plan de cours

IFT 313

–

Introduction aux langages formels

Été 2010

2010-04-15

6

4

1

er

juin

Programmer un analyseur syntaxique récursif

5 %

10 juin

5

8 juin

Générer un analyseur syntaxique

avec JavaCC

5 %

23 juin

6

6 juillet

Grammaires LR(0), SLR(1), LR(1) et LALR(1)

5 %

15 juillet

7

15 juillet

Mini-projet avec JavaCUP

10 %

2 août

Directives particulières



Les travaux sont effectués par équipe de 1 à 3 étudiant(e)s.



La qualité du français et de la présentation peut être considérée dans le résultat du travail.



Toute soumission en retard vaut zéro, sauf celles motivées par des raisons valables, conformes au règlement

des études (par exemple, maladie avec attestation d’un médecin).

3

Matériel nécessaire pour le cours

3.1

Manuels (optionnel)

[S]

T. A. Sudkamp

.

Languages and Machines.

Third Edition Edition. Addison-Wesley, 2005.

[A]

A. W. Appel.

Modern Compiler Implementation in Java

. Second Edition. Cambrdidge, 2002.

[W]

P. Wolper

.

Introduction à la calculabilité.

3

e

Édition. Dunod, 2006.

[D]

A.V. Aho, R. Sethi & J.D. Ullman

.

Compilers: Principles, Techniques and Tools.

Addison-Wesley, 1988.

[G]

D. Grune, H.E. Bal, C.J.H. Jacobs & K.G. Langendoen.

Modern Compiler Design.

Wiley, 2000.

3.2

Documentation et logiciels gratuits pour le cours

1.

JFlex – The Fast Scanner Generator for Java

http://jflex.de/

2.

JavaCC is a parser / scanner generator for Java

https://javacc.dev.java.net/

3.

JavaCUP : LALR Parser Genetrator for Java

http://www.cs.princeton.edu/~appel/modern/java/CUP/

4.

Java Standard Edition Development Kit 6 (JDK)

http://java.sun.com

/

5.

Environnements de développement intégré (IDE)

NetBeans :

http://www.netbeans.org/

Eclipse:

http://www.eclipse.org/

6.

Normes de rédaction et de programmation du département

http://www.dmi.usherb.ca/~fraikin/cours/Normes/normes-de-programmation.pdf

7.

Connexion par SSH et la soumission par turnin :

http://www.dmi.usherb.ca/~fraikin/cours/SSH-turnin