Université Sidi Mohamed Ben Abdellah Année Universitaire : 2023 / 2024
Faculté des Sciences Dhar Mehraz Fès Filière : SMI
Département d’Informatique S5
Épreuve de la compilation (session normale)
Durée : 1h 30
Exercice I : (6.5 Points)
1. Minimisation. Minimisez l’automate suivant et dessinez le graphe de l’automate
minimal obtenu.
2. Déterminisation. Soit A l’automate non déterministe suivant :
Construisez un automate déterministe A1 équivalent à A. Donnez sa table et son
graphe de transition.
Exercice II : (2.5 Points)
1 Ecrire une grammaire pour générer les identificateurs d’un langage comme Pascal ou C.
On considérera qu’un identificateur est valide s’il commence par une lettre (majuscule ou
minuscule) suivi d'un nombre quelconque (éventuellement aucun) de symboles. Ces
symboles sont constitués par des lettres, des chiffres, et du caractère '_'.
1
Université Sidi Mohamed Ben Abdellah Année Universitaire : 2023 / 2024
Faculté des Sciences Dhar Mehraz Fès Filière : SMI
Département d’Informatique S5
2 Une constante de type chaîne de caractères est délimitée par des apostrophes et constituée
d'un nombre quelconque de caractères. Pour permettre à une apostrophe de faire partie
d'une chaîne de caractères, on double celle-ci.
2.1. Ecrire la grammaire qui permet de générer cette unité lexicale.
2.2. Construire l’automate qui permet de reconnaitre cette unité lexicale.
Exercice III :(4 Points)
Donnez l’expression régulière équivalente à l’automate suivant :
Exercice IV : (4 Points)
Exercice V :(2 Points)
1) En utilisant la méthode de Glushkov, donnez l’automate’ acceptant le langage reconnus
*
par l’expression rationnelle suivante : (a + ba) a(aa + b(ab) ∗a)∗a
Questions de Cours : (1 Point)
1. Décrire toutes les phases d’un compilateur.
