Université Sidi Mohmed Ben Abdellah
Faculté polydisciplinaire de Taza Compilation
Travaux Dirigés
Série N°3
Exercice 1
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 '_'.
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.
2-3- Donner quelques lexèmes qui sont définis par cette unité lexicale.
2-4- Trouver des constantes qui ne sont pas reconues par cette unité lexicale.
Exercice2
Soit la grammaire G=(VT, VN, R,E) telle que: VT=(+,*,(,),nbr), telle que: VN=(E,T,F,E’,T’) et
R=(E→TE’, E’→+TE’, E’→ε, T→FT’, T’→*FT’, T’→ε, F→(E), F→nbr).
1-Décrire le langage généré par cette grammaire
2- Calculer les deux ensembles First et Follow pour les éléments de VN .
Exercice3
Soit la grammaire G0 définie par les productions suivantes:
S →aE|bF ; E→bE|ε ; F→aF|aG ; G→Gc|d
1. Montrer que G0 est non LL(1).
2. Ecrire une grammaire G1 non récursive a gauche telle que L(G1) = L(G0).
3. Ecrire une grammaire G2 factorisée a gauche telle que L(G2) = L(G1).
4. Calculer les ensembles First(A) et Follow(A) pour les symboles A non terminaux de G2, et
First() pour les parties droites des règles de G2.
5. Montrer que G2 est de type LL(1).
Exercice4
Soit la grammaire G=(VT, VN, R,E) de l’exercice 2
1-Construire la table de transition de l’analyseur syntaxique du langage généré par la
grammaire G.
2- Appliquer l’algorithme de l’AS prédictif non récursif sur la chaine suivante:
CH1= nbr*(nbr+nbr)$
CH2=nbrnbr+nbr$
Pr. A. Saaidi 1 Année universitaire 2017/2018
Université Sidi Mohmed Ben Abdellah
Faculté polydisciplinaire de Taza Compilation
3- Appliquer l’algorithme de l’AS prédictif non récursif avec récupération sur erreur en mode
panique sur les deux chaines suivantes:
CH2=nbrnbr+nbr$
Exercice5
Soit la grammaire G définie par les productions suivantes: S→G = D|D , G→*D|i , D→G
1- Calculer C l’ensemble de collection canonique de G augmentée par la production S’→S.
2- Construire l’AFD des Items de G augmentée.
3- Construire la table d’analyse de G par l’algorithme SLR(1).
4- Déduire que l’algorithme SLR(1) est incapable de gérer la grammaire G
Exercice6
Soit la grammaire G définie dans l’exercice 5
1- Calculer C l’ensemble de collection canonique des items modifiées de G augmentée.
2- Construire l’AFD des Items généralisés de G augmentée.
3- Construire la table d’analyse de G par l’algorithme LR(1).
4- Déduire que les conflits de SLR(1) sont remédiés par LR(1).
5- Appliquer l’analyseur LR sur les deux chaînes suivantes: i=i , ii
Pr. A. Saaidi 2 Année universitaire 2017/2018
