Centre Universitaire de Bordj Bou Arreridj Année Universitaire : 2007/2008

Département de l’informatique

Spécialité : Ingénieur en informatique " 4ième année"

Module : Compilation

Les expressions régulières :

Exercice n°1 :
Décrire les langages dénotés par les expressions régulières suivantes :
a- 0(0/1)*0
b- aab(a/b)*(bb/aa)*
c- a(a/b)*b
d- ((ε/b)a*)*
e- ((aa)*a
f- (a/b)*(c/d)*

Exercice N° 2
Soit l’expression régulière (a/ab)(c/bc)
Donner deux expressions régulières décrivant le même langage

Exercice N°3
Donner une expression régulière décrivant :
a- Les mots sur {a,b,c} qui commencent par b
b- Les mots sur {a,b,c} qui contiennent exactement 3 a
c- Les mots sur {a,b,c} qui contiennent au moins 3a
d- Les mots sur {a,b,c} qui contiennent au plus 3a
e- Les mots sur {a,b,c} qui contiennent le facteur babb au moins 2 fois
f- Les mots sur {a,b,c} qui ne contiennent pas 2a consécutifs
g- Les mots sur {a,b,c} qui ne contiennent pas le facteur ab

Exercice N° 4
Donner une expression régulière décrivant:
a- Les nombres entiers multiples de 5.
b- Les nombres binaires.
c- Les nombres hexadécimaux.
d- Toutes les chaines de 0 et de 1 avec un nombre pair de 0 et un nombre impair de 1
SI TU VEUX TU PEUX
Qui ne veut pas quand il peut, ne peut pas quand il veut
Centre Universitaire de Bordj Bou Arreridj Année Universitaire : 2007/2008

Département de l’informatique

Spécialité : Ingénieur en informatique " 4ième année"

Module : Compilation

Les automates finis

Exercice N° 1 :

Soit l’automate δ a b c

0 0,1 3
1 2,4
2 3 0,4
3 3
4 1

Les mots : abc, baabc, aabcbcab, abcabcca appartiennent- ils au langage reconnu par l’automate ?

Exercice N°2 : On considère l’AFN suivant :

Donner une expression régulière correspondant au langage qu’il reconnait

Exercice N°3 : construire les automates finis non déterministes reconnaissant les expressions
régulières suivantes :

a- (a|b)*a(a|b)
b- a(b/ c)*
c- Les mots sur {0,1}tels que chaque 1est suivi immédiatement d’un 0

Exercice N°5 : Déterminiser l’AFN suivant : q0={0} et F{3}

Exercice N°6 : donnez le langage reconnu par cet AFN puis déterminisez-le et minimisez-le si
nécessaire

De la discussion jaillit la lumière

Centre Universitaire de Bordj Bou Arreridj Année Universitaire : 2007/2008

Département de l’informatique

Spécialité : Ingénieur en informatique " 4ième année"

Module : Compilation

Analyse syntaxique descendante

Exercice N° 1 :Soit la grammaire G suivante :

Z  XYZ / d
Y  c /ϵ
XY/a
Calculez les ensembles Premier et Suivant.
Exercice N° 2 :Considérer la grammaire G suivante :
S a/b/(T)
T T,S/S
1. La grammaire est elle LL(1) ?
2. Eliminer la récursivité à gauche et factoriser si nécessaire.
3. Monter que la grammaire obtenue en 2 est LL(1) , donner sa table d’analyse.
4. Expliciter le comportement de l’analyseur sur le mot(a,(b,a),a).
Exercice N° 3 : soit la grammaire des expressions booléennes :
A A ou B / B
B B et C / C
C non C/(A)/ vrai / faux
1. Eliminer la récursivité à gauche et factoriser si nécessaire.
2. Donner sa table d’analyse de la nouvelle grammaire. Est-elle LL(1) ? ,
3. Expliciter le comportement de l’analyseur sur le mot : non (vrai ou faux) et vrai
Exercice N° 4 : Soit la grammaire G suivante :
S  SxXS / y
X  ySX / x /y / ϵ
1 : Eliminez la récursivité à gauche et factorisez si nécessaire.
2 : Donnez la table d’analyse de la nouvelle grammaire Est-elle LL(1). ?
Quand on veut chercher un abri, il faut choisir l’ombre d’un grand arbre
Centre Universitaire de Bordj Bou Arreridj Année Universitaire : 2007/2008
Département de l’informatique
Spécialité : Ingénieur en informatique " 4ième année"
Module : Compilation

Analyse syntaxique ascendante

Exercice N° 1

Soit la grammaire suivante :

S  BB
B  aB / b
1. Construire la table d’analyse SLR pour cette grammaire, Est-elle SLR ?
[Link] le comportement de l’analyseur sur la chaine aabaab

Exercice N° 2

Soit la grammaire :
S -> A | xb
A -> aAb | B
B -> x
Trouvez les tables Action, Goto et l’automate LR(1) de cette grammaire.
Analyser la chaine axbb

Exercice N°3
Considérer la grammaire :
S AS /b
A SA /a
1. La grammaire est-elle SLR(1) ? si oui construire la table d’analyse SLR(1)
2. Cette grammaire est-elle LR(1), LALR(1)

Exercice N° 4

Soit G la grammaire suivante :

SaAd / bBd/ aBe / bAe
Ac Bc
1. Cette grammaire est-elle LR(1)?
2. Cette grammaire est-elle LALR(1)?
3. Cette grammaire est-elle SLR(1)?

“With money you can buy a clock but not time, with money you can buy a book but not
knowledge”
Centre Universitaire de Bordj Bou Arreridj Année Universitaire : 2007/2008
Département de l’informatique
Spécialité : Ingénieur en informatique " 4ième année"
Module : Compilation

Analyse par précédence d’opérateurs

Exercice N° 1 :Considérons la grammaire:

S  (L) /a
L  S,S / S
-soit la table de relations de précédence d’opérateurs pour cette grammaire :
a ( ) , #
a > > >
( < < = <
) > > >
, < < > >
# < <

1. en utilisant les relations de précédence , analyser la chaine : (a,(a,a))

Exercice N° 2 : Considérons la grammaire:

exprb -> exprb ou termeb| termeb

termeb -> termeb et facteurb| facteurb
facteurb -> non facteurb / (exprb) / vrai / faux
- Construire les relations de précédence pour cette grammaire.
- Analyser la chaine non ( vrai ou faux), en utilisant les relations de précédence.

Utilisation des grammaires ambiguë :

Exercice N°3 : Considérer la grammaire :
E E sub E sup / E sub E/ E sup E/{E} / c
1- Construire la tables d’analyse SLR( 1) pour cette grammaire.
2- En donnant à sub et sup des priorités égales et en les faisant associatifs à droite, résoudre
les conflits d’actions qui apparaissent dans la table SLR(1).

Exercice N° 4 : considérer la grammaire des expressions booléennes suivantes :

EE and E / E or E/ not E / (E)/ id
1-Cette grammaire est-elle ambiguë? Pourquoi ?
2-Construire la tables d’analyse SLR( 1) pour cette grammaire.
3-Si l’ordre croissant de précédence des opérateurs est or ;not, and( or< not < and) et si les
opérateurs or et and sont associatifs à gauche , résoudre les conflits d’actions qui apparaissent
dans la table SLR(1).
« the pessimist sees difficulty in every opportunity, the optimist sees the opportunity in every difficulty »,
Centre Universitaire de Bordj Bou Arreridj Année Universitaire : 2007/2008
Département de l’informatique
Spécialité : Ingénieur en informatique " 4ième année"
Module : Compilation

Exercice 1 :
Considérons la grammaire :
E L
L LB\B
B 0 \ 1
Cette grammaire engendre des chaines binaires.
Calculer le nombre décimal représenté par la chaine
- En utilisant des attributs hérités
- En utilisant des attributs synthétisés.
-pour permettre le calcul des nombres réels nous remplaçons la première règle par la suivante :
E L.L \ L
Utiliser des attributs synthétisés pour calculer le nombre décimal représenté par la chaine binaire
( par exemple 1011.101 représente le nombre 11.625)
- Donner un arbre décoré pour 1011.101

Exercice 2 :
Soit la grammaire suivante
EE+T|T
T  [Link] | nb
Cette grammaire engendre des expressions arithmétiques formées de constantes entières et
réelles.
et de l’opérateur + Lorsque l’on additionne ,entiers, le résultat est un entier,sinon c’est un réel.
- Ecrire une définition dirigée par la syntaxe DDS qui détermine le type de chaque sous_
expression.
- Donner un arbre syntaxique décoré pour la chaine 5+6.1+3
Exercice 3 : Soit la grammaire G1 suivante engendrant des listes à la schème, d’axiome L,
d’alphabet terminal {a, ( , ) } et dont les règles sont :
L −→ ( S ) | a
S −→ L S |
Question 2 : La grammaire G1 est-elle SLR(1) ? Justifier.
Question 3 : Détailler le déroulement de l’analyseur SLR(1) pour la grammaire G1 sur l’entrée
"( a ( ) ) $".
Question 4 : Décorer la grammaire G1 d’actions sémantiques permettant de déterminer si une
liste contient au moins une occurrence de la liste vide. Par exemple, la réponse doit être positive
pour les listes ( )ou ( a ( a ( ) ) a ( a ) ) ; elle est négative pour ( a ( a ( a a) ) a ( a ) ).

« La simplicité est le fruit d’un long travail »,

Centre Universitaire de Bordj Bou Arreridj Année Universitaire : 2007/2008
Département de l’informatique
Spécialité : Ingénieur en informatique " 4ième année"
Module : Compilation

Exercice 1 : Ecrire une expression de type pour les types suivants :

a) Un tableau de pointeurs vers des réels, dont les indices sont compris entre 1 et 100.
b) Un tableau à deux dimensions dont les lignes sont indicées de 0 à 9 et les colonnes de -10
à 10.
c) Les fonctions dont le domaine est les fonctions des entiers vers des pointeurs vers des
entiers, et dont le codomaine est les structures composées d’un entier et d’un caractère.

Exercice 2 : La grammaire ci-dessous définit des listes de listes. L’interprétation des symboles
est la même que celle du cours, avec l’ajout du type liste , qui indique une liste d’éléments dont le
type T est placé après.
P D ; E
D D ; D| id : T
T liste de T| caractère | entier
E ( L) | littéral | nb| id
L E, L | E
Ecrire des règles de traduction similaires à celles vue en cours permettant de déterminer le type
des expressions ( E ) et celui des listes ( L).
Exercice 3 : A l’aide du schéma de traduction vue en cours , calculer les types des expressions
dans les fragments de programmes ci –dessous . Expliciter le type à chaque nœud de l’arbre
syntaxique :
C : caractère ; i :entier ;
C mod i mod 3

P : ^ entier ; a : tableau [ 10] d’entier ;

a[ p^]
Exercice 4 : soit la déclaration suivante :
Type modele= pointeur ( tableau ( 10, pointeur(entier)))
modele1= tableau ( 10, pointeur(entier))
Var X : modele
Y : pointeur( modele1)
Z : pointeur ( tableau ( 10, pointeur(entier)))
O : pointeur(modele)
Lesquelles des variables ci- dessus sont structurellement équivalentes ? Lesquelles équivalentes par
noms ?
Exercice 5: Exprimer le type des fonctions suivantes, à l’aide de variables de type :
a- La fonction Ref qui prend en argument un objet d’un type quelconque et retourne un pointeur vers
cet objet.
b- Une fonction qui prend en argument un tableau d’éléments d’un type quelconque indicé par des
entiers, et retourne un tableau dont les éléments sont des pointeurs vers les éléments du tableau
donné.
" Le savoir que l'on ne complète pas chaque jour diminue tous les jours. "
Centre Universitaire de Bordj Bou Arreridj Année Universitaire : 2007/2008
Département de l’informatique
Spécialité : Ingénieur en informatique " 4ième année"
Module : Compilation

Exercice 1 : Représentation de code

Traduire l’expression a * -(b + c)|(a + b) en
a) un arbre abstrait
b) une notation postfixèe
c) du code à 3 adresses
Exercice 2 : traduire en code postfixé et donner le DAG le programme suivant :
A := b* c + b* -c
Exercice 3 : traduire en code postfixé le programme suivant :
If ( j<= 100) then sum := sum + j ; j := j+1 else j:=100-j
Exercice 4: traduire en code postfixé le programme suivant :
Sum := 0 ;
J := 1 ;
while ( j<= 100) do begin sum := sum + j ; j := j+1 end
Exercice 5 :soit les instructions C suivantes :
X =1 ;
Y= a*b +c ;
X= x+1 ;
Y= a/ (b+c) – d / e +f
Produire le code à trois adresses implantant ces instructions.
Exercice 6: soit le fragment de code C suivant :
z =0 ;
Do { x++ ; if ( y<10){ z= z+2 * x ; h= 5 ;}
Else h= -5;
Y+=h; } while ( x<= 50 && z<=5 * y );
Ecrire le code à trois adresses
Exercice 7 : Traduire l’expression –( a +b ) * ( c + d) + ( a+b+c) en
a) Quadruplets ;
b) Triplets ;
c) Triplets indirects
Exercice 8 : traduire en quadruplets l’expression booléenne suivantes :
a=b or b>c and not ( d >a)
Exercice 9: en utilisant les schéma de traduction vus en cours, traduire le programme suivant en
quadruplets:
While a < c and b <c do
If a=1 then c:= c + 1
Else while a <= d do a:= a +2;

La beauté est une demi-faveur donnée par dieu ; L’intelligence en est entière.
Centre Universitaire de Bordj Bou Arreridj Année Universitaire : 2007/2008
Département de l’informatique
Spécialité : Ingénieur en informatique " 4ième année"
Module : Compilation

Exercice N° 1 : Soit le fragment de code suivant :

t1= t0 t4= t2*2
t2= 4 t5= t0 ^ 2
t3= t1*t1 t6= t5 + t3
t7= t4 + t6
Appliquer une séquence de transformations sur ce code de façon à minimiser la taille de code résultant
Exercice N2 : Considérer la procédure suivante de multiplication de matrices :

Pour i :=1 à n faire

Pour j :=1 à n faire
Pour k := 1 à n faire c[i,j] :=c[i,j]+ a[i,k] * b[k,j]
1- Supposons que la taille des éléments des tableaux soit égales à 4 octets, produire le code à trois
adresses pour ce programme.
2- Déterminer le graphe de flow de contrôle
3- déterminer les boucles du graphe
4- Déplacer le code invariant à l’extérieur des boucles.
5- Réduire la force des opérateurs dans chaque boucle
6- Eliminer les sous expressions communes pour chaque bloc de base.
Exercice N3 :

1- Calculer les ensembles Gen(b) et Kill(b) pour chacun des blocs du programme.
2- Calculer les In(b) et Out(b) pour chacun des blocs du programme.
3- Supprimer les calculs redondants (sous-expressions communes).
« De votre expérience, faite la différence »