Pré-requis:
Algorithmique, programmation.
Familles de Compétences
Type de compétence:
TEC : Technique
MET : Méthodologique
MOD : Modélisation
OPE : Opérationnel
Niveau de compétence:
Base | Intermédiaire | Avancé |
|
I. Mots, Langages et Grammaires (24h)
Définitions, dérivations, langage engendré par une grammaire
Classification de Chomsky
Langages réguliers (grammaires, automates d’états finis, expressions régulières)
Langages algébriques (grammaires, automates à pile)
II. Analyse lexicale (12h)
Les expressions régulières dans l’analyse lexicale,
Générateur d’analyseur lexical (Lex, JCC).
III. Analyse syntaxique (24h)
Méthodes d’analyse syntaxique (ascendante, descendante),
Automates à pile dans l’analyse syntaxique,
Analyse descendante récursive,
Générateur d’analyseur syntaxique (Yacc, JCC).
IV. Travaux Pratiques
TP1 : Automates d’états finis
TP1 : Mise en œuvre d’un analyseur lexical (Lex, JCC),
TP2 : Mise en œuvre d’un analyseur syntaxique (JCC).
TP (10 Heures)
A. Aho, J.D. Ullman, « The Theory of Parsing, Translation, and Compiling », Prentice Hall, Inc., Englewood Cliffs, New Jersey, 1972.
P. J. Denning, J. B. Dennis, and J. E. Qualitz, “Machines, languages, and Computation”, Prentice-Hall, Inc. Englewood cliffs, New Jersey, 1978.
R. Floyd, R., Biegel, « Le Langage des Machines : Introduction à la calculabilité et aux langages formels », Thomson Publishing, France, 1994.
J.E. Hopcroft, J.D. Ullman, « Introduction to Automata Theory and Computation », Addison Wesley Publishing Company, 1979.
Wolper, Pierre, « Introduction à la calculabilité », InterEditions, Paris, 1991.