Théorie des langages
Introduction
Théorie des langages
N 1/8
Introduction
Organisation du cours
Cours : A02, mercredi 08h-09h30
TDs :
Groupes Horaire Salle
G1 Dimanche 11h-12h30 S10
G2 Dimanche 12h30-14h S11
Théorie des langages
N 2/8
Introduction
Mode d’évaluation
Contrôle continu :
Contrôle continu : épreuve écrite de 1h30
Examen E : épreuve écrite de 1h30
Session 1
Session 2 (Rattrappage)
Théorie des langages
N 3/8
Introduction
Motivations
Concept de langage formel
Créé par les linguistes pour décrire les langages naturels
→ Effectuer des traductions automatiques
Noam CHOMSKY: modèle mathématique pour les grammaires
1958: langage ALGOL décrit à l’aide d’une grammaire “Hors-Contexte”
Pourquoi étudier les langages formels?
Conception de langages : syntaxe, grammaire
Analyse
Lexicale (déterminer les entités syntaxiques)
Syntaxique (vérifier la syntaxe)
Compilation : traduction
Générateurs d’analyseurs lexicaux
Méta-compilateurs : compilateurs de compilateurs, ou générateur de compilateurs
⇒ Nécessaire pour l’étude des langages de programmation
Théorie des langages
N 4/8
Introduction
Un compilateur, c’est quoi?
Un compilateur est un programme qui
prend en entrée une donnée textuelle source (programme, donnée xml, fichier
de configuration, etc)
la reconnaît (l’analyse) pour vérifier sa correction
émet éventuellement un message d’erreur
le traduit dans un langage cible
programme source Compilateur programme cible
messages d’erreur
Théorie des langages
N 5/8
Introduction
Outils pour la compilation
Correction :
Entrée invalide détectée ?
Sortie conforme aux attentes ?
⇒ Outil de prédilection = théorie des langages
Efficacité :
Faut-il attennnnnnndre le résultat de la compilation ?
⇒ Outil de prédilection = algorithmique
Bonne conception du logiciel :
Logiciel facile à modifier/étendre ? )
⇒ Outil de prédilection = génie logiciel
Théorie des langages
N 6/8
Introduction
A quoi sert la théorie des langages en
compilation?
Permet de définir rigoureusement et reconnaître algorithmiquement (pour
les langages source et cible) :
leur vocabulaire ou lexique : les mots autorisés
⇒ analyse lexicale
⇒ automates à nombre fini d’états, expressions régulières
leur syntaxe : la structure des phrases autorisées
⇒ analyse syntaxique
⇒ automates à pile, grammaires algébriques
leur sémantique : la signification des phrases autorisées
⇒ analyse sémantique
⇒ grammaires attribuées
Théorie des langages
N 7/8
Introduction
Plan du cours
1. Alphabets et langages
2. Grammaires
3. Automates finis
4. Expressions régulières
5. Grammaires Hors-Contexte
6. Automates à pile
7. Analyse lexicale
8. Analyse syntaxique
Théorie des langages
8/8
