Théorie des langages et des
automates
Année universitaire 2017/2018
Préambule
initiation à la théorie des langages formels.
les langues sont les supports de communication.
Les langues permettent aux hommes d'échanger entre eux des
informations et des idées.
les langages leur permettent de communiquer avec les machines.
Les langues utilisées dans la vie de tous les jours entre êtres
humains sont dites naturelles. Elles sont généralement informelles
et ambigües et demandent toute la subtilité d'un cerveau humain
pour être interprétées correctement.
Les langages formels créés par l'homme pour communiquer avec
les ordinateurs sont non ambigus pour pouvoir être interprétés par
une machine.
2
Préambule
À la base, un ordinateur ne comprend qu'un seul langage, pour
lequel il a été conçu: son langage machine.
Pour communiquer avec des langages plus évolués, il est
nécessaire d'utiliser un interprète (qui traduit interactivement les
instructions entrées au clavier), ou bien un compilateur (qui traduit
tout un programme).
3
Plan du cours
Chapitre Remarques sur le contenu du chapitre Charge TD Charge
horaire horaire
TD
Chapitre 1 : Introduction générale --- TD1: Expressions ---
Introduction: mots et Préambule et motivations et Langages
langages Mots et langages Réguliers
Chapitre 2 : Les expressions régulières --- TD1: Expressions ---
Automates finis et Les automates finis non déterministes et Langages
Expressions régulières Les automates finis déterministes Réguliers+ TD2:
Les automates avec -transitions Automates à états
Les automates minimales finis
Chapitre 3 : Les grammaires ---- TD3 : Grammaires ----
Les grammaires Langage engendré par une grammaire et Automates à
Types de grammaires piles
grammaires et dérivation
Transformation d'une grammaire régulière en un
automate fini
Transformation d’automate fini en une grammaire
régulière
Chapitre 4 : Généralités. ---- TD3 : Grammaires ----
Automate à piles Configurations. et Automates à
Exemple introductif. piles
Automates à pile et automates traditionnels.
Transitions dans un PDA
Langage reconnu par un PDA
Chapitre 5 : Généralités --- Exercices ----
Machine de Turing Fonctionnement d’une Machine de Turing d’application
TM pour langages réguliers
TM pour les langages hors contexte
4
Plan du cours
Chapitre Remarques sur le contenu du chapitre Charge TD Charge
horaire horaire
TD
Chapitre 1 : Généralités --- TD1: Analyse ---
Analyse Lexicale Unité lexicale, Lexème et Modèles Lexicale
TP1: Flex
(Introduction)
Chapitre 2 : Rôle de l’analyseur syntaxique --- TD2: Analyse ---
Analyse Syntaxique Suppression de la récursivité à gauche Syntaxique
Factorisation à gauche TP2: Bison
Analyse syntaxique Descendante
Analyse syntaxique Ascendante
Chapitre 3 : Rôle et phases de l’analyse sémantique ---- TD3 : Analyse ----
Analyse Sémantique Outils pour effectuer l’analyse sémantique Sémantique
Représentation et reconnaissance des types
Dictionnaires (tables de symboles)
Chapitre 4 : Généralités. ---- TD4 : Génération ----
Production de code Les objets et leurs adresses de code
Code intermédiaire
Architecture du processeur
5
évaluation
Une note de contrôle continu
Une note sur le devoir surveillé
Une note sur l’examen
Note CC + Note DS 40% de la note Finale
Note Examen 60% de la note Finale
Moyenne = Contrôle Continu * 40% + Examen * 60%
6
Motivations
Description et analyse de langages (traitement du texte, codes,
langages de programmation, langages naturels, . . . )
Modèles de calcul, conception d’algorithmes.
7
Bibliographie
J.E. Hopcroft, J.D. Ullman. Introduction to automata theory,
languages and computation. Addison-Wesley, 1979.
M. Sipser. Introduction to the theory of computation. PWS
Publishing Company, 1996.
A. Lingas, R. Karlsson, S. Carlsson. Automata, Languages and
Programming. Lecture Notes in Computer Science – 20th
International Colluquium ICALP93. Springer-Verlag Ed.