Volumes horaires
- CM 13.5
- Projet -
- TD 17.5
- Stage -
- TP 2.0
- DS -
Crédits ECTS
Crédits ECTS 3.0
Objectif(s)
Introduction aux techniques utilisées de description et d’analyse des langages. Application aux langages de programmation. Présentation des notions de bases de la théorie de la calculabilité : algorithmes, fonctions calculables, problèmes indécidables
Responsable(s)
Xavier NICOLLIN
Contenu(s)
I Analyse syntaxique des langages hors-contextes
- Syntaxe et sémantique des langages informatiques: traduction dirigée par la syntaxe.
- Rappels sur les grammaires hors-contextes: arbres de dérivation, ambiguïté.
- Formalisation de sémantiques simples par grammaires attribuées. Notion de méta-interpréteur (Bison-Yacc et AntLR).
- Structure d'un interpréteur complexe: analyse lexicale, analyse syntaxique, notion de syntaxe abstraite.
- Théorie des plus petits points fixes de Kleene.
- Analyse syntaxique LL(1). Calculs de directeurs LL(1).
- Programmation d'un analyseur LL(1) en langage Python.
- Ouverture: analyse syntaxique au-délà de LL(1) (e.g. LR(1) et LL(*))
II Calculabilité
1. Calcul, algorithme, machine de Turing, fonctions partielles calculables
2. Propriétés :
Existence de fonctions non calculables, Indécidabilité du problème de l’arrêt, Existence d’algorithmes universels
3. Problèmes de décision sur les langages et les programmes.
Preuves par réduction : problème de correspondance de Post
Théorie des Langages 1
Programmation en langage Python
Contrôle des connaissances
CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) :
Comme mentionné dans le règlement-cadre de scolarité de l'Institut polytechnique de Grenoble (section 4, article 1) :
"Le manque d’assiduité ou de ponctualité est pris en compte dans l’évaluation."
Il est donc a fortiori pris en compte.
SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : examen écrit.
Salle spécifique :
Durée : 3h
Documents autorisés : tous documents autorisés
Dispositifs électroniques (ex : calculatrices): aucun matériel autorisé
Commentaires :
En cas d'examen à distance :
1) il faudra rendre une "attestation sur l'honneur" certifiant que vous composerez seul et ne communiquerez qu'avec vos enseignants. Le retard dans la remise de l'attestation ou le non respect des consignes de nom et format de fichier pourra entraîner une pénalité.
2) un délai de 15 minutes sera accordé en fin d'examen pour remettre la copie manuscrite scannée. Le retard dans la remise de la copie ou le non respect des consignes de nom et format de fichier pourra entraîner une pénalité.
3) ordinateur et téléphone portable sont autorisés pendant l'épreuve, uniquement pour accéder au sujet, consulter les documents disponibles sur Chamilo, communiquer avec les enseignants et déposer la copie pour le premier, uniquement pour scanner la copie et la transférer éventuellement sur l'ordinateur ou la déposer directement pour le second.
SESSION DE RATTRAPAGE :
Type d'examen: écrit
Salle spécifique : non
Durée : 1h30
Documents autorisés: tous documents autorisés
Dispositifs électroniques (ex : calculatrices): aucun matériel autorisé
Commentaires :
En cas d'examen à distance :
1) il faudra rendre une "attestation sur l'honneur" certifiant que vous composerez seul et ne communiquerez qu'avec vos enseignants. Le retard dans la remise de l'attestation ou le non respect des consignes de nom et format de fichier pourra entraîner une pénalité.
2) un délai de 15 minutes sera accordé en fin d'examen pour remettre la copie manuscrite scannée. Le retard dans la remise de la copie ou le non respect des consignes de nom et format de fichier pourra entraîner une pénalité.
3) ordinateur et téléphone portable sont autorisés pendant l'épreuve, uniquement pour accéder au sujet, consulter les documents disponibles sur Chamilo, communiquer avec les enseignants et déposer la copie pour le premier, uniquement pour scanner la copie et la transférer éventuellement sur l'ordinateur ou la déposer directement pour le second.
N1=E1
N2=E2
Calendrier
Le cours est programmé dans ces filières :
- Cursus ingénieur - Tronc Commun - Semestre 6
Informations complémentaires
Code de l'enseignement : 3MMTL2
Langue(s) d'enseignement : 
Le cours est rattaché aux structures d'enseignement suivantes :
- Equipe Algorithmique-Mathématiques discrètes
- Equipe Bases théoriques de l'informatique
Vous pouvez retrouver ce cours dans la liste de tous les cours.
Bibliographie
- J. Hopcroft, R. Motwani, J. Ullman : Introduction to Automata Theory, Languages, and Computation. (3rd edition, 2006).
- Pierre Berlioux, Michel Lévy : Théorie des langages, polycopié Ensimag
- T. Parr: The Definitive ANTLR 4 Reference (2nd edition, 2013).
- N. J. Cutland : Computability. Cambridge University Press 1980
- A. Aho, M. Lam, R. Sethi, J. Ullman : Compilers. Principles, Techniques and Tools, Addison-Wesley (2nd edition, 2013).