Université Amar Telidji Laghouat 3 ème Année Informatique

Faculté des Sciences Épreuve de Compilation Date : 22/03/2021

Département d’Informatique Durée de l’épreuve : 1h.10

Nom :........................................... Prenom :...................................... Groupe :............ Note :................../20

Barème : Partie A (1 + 1 + 2 + 3). +x point(s) par question correcte. −x point(s) par question incorrecte.
Partie B (2 + 2.75 + 2.25 + 3 + 3).

Partie A :.........../07

Partie B :.........../13

Partie A :
1. Parmi les langages suivants, quel(s) est (sont) le(s) langage(s) qui ne peut (peuvent) être contrôlées par un auto-
mate d’états finis :
— {ai bj | i = j}

— {ai bj | i, j ≥ 0}

— {ai + bj | i, j ≥ 1}

— {ai bj | 0 < i < j}

2. Un nombre réel en C ++ est définit comme suit : toute entité correspondante à entier (toute suite non vide de
chiffres précédée éventuellement d’un seul caractère parmi (”−” | ”+”)) suivi éventuellement d’un point et d’une
suite non vide de chiffres.
Remarque : ch ∈ {0, 1, ..., 9}

— Parmi les représentations graphiques suivantes, quel est l’AEFD qui correspond à la description donnée
ci-dessus :

Automate A1 Automate A2

ch ”.” ch ch ”.” ch
ch ch ch ch
start s0 s1 s2 s3 start s0 s1 s2 s3 ch s4

” − ”|” + ” ” − ”|” + ”

Automate A3
ch ”.” ch
ch ch
start s0 s1 s2 s3 ch s4

” − ”|” + ”

Epreuve de Compilation Page 1/4

 3. On veut analyser syntaxiquement des expressions arithmétiques. Les opérandes sont des nombres entiers. Les
opérateurs permis sont −, ×, et ↑ (opérateur de puissance). Les opérateurs − et × sont associatifs à gauche.
L’opérateur ↑ est associatif à droite. L’ordre ↑, ×, − est un ordre selon la priorité décroissante des opérateurs (↑
est le plus prioritaire).
— Parmi les grammaires suivantes, expliquer quelle(s) est (sont) celle(s) qui ne correspond(ent) pas à la des-
cription donnée ci-dessus :

G1 G2 G3 G4
E −→ F ↑ E | F E −→ E − T | T E −→ E ↑ F | F E −→ E ↑ F | F
F −→ F × G | G T −→ T × F | F F −→ F × G | G F −→ G × F | G
G −→ G − H | H F −→ F ↑ G | G G −→ G − H | H G −→ H − G | H
H −→ (E) | nbr G −→ (E) | nbr H −→ (E) | nbr H −→ (E) | nbr
.......................................... .......................................... .......................................... ...........................................
.......................................... .......................................... .......................................... ...........................................
.......................................... .......................................... .......................................... ...........................................
.......................................... .......................................... .......................................... ...........................................
.......................................... .......................................... .......................................... ...........................................
.......................................... .......................................... .......................................... ...........................................
.......................................... .......................................... .......................................... ...........................................

4. Pour chaque grammaire Gi ( i=1,2,3) suivante, Gi est-elle LL(1) ? justifier sans construction de la table d’analyse
LL(1).

G1 G2 G3
< E >−→< E > + < E > < E >−→< E > + < T > | < T > < E >−→< T >< E ′ >
< E >−→< E > × < E > < T >−→< T > × < F > | < F > < E ′ >−→ + < T >< E ′ > | ϵ
< E >−→ nbr | (< E >) < F >−→ nbr | (< E >) < T >−→< F >< T ′ >
< T ′ >−→ × < F >< T ′ > | ϵ
< F >−→ nbr | (< E >)

G1 est-elle LL(1) ? :.......................... G2 est-elle LL(1) ? :.......................... G3 est-elle LL(1) ? :..........................

Justification :...................................... Justification :...................................... Justification :......................................

.......................................................... .......................................................... ..........................................................
.......................................................... .......................................................... ..........................................................
.......................................................... .......................................................... ..........................................................
.......................................................... .......................................................... ..........................................................
.......................................................... .......................................................... ..........................................................
.......................................................... .......................................................... ..........................................................
.......................................................... .......................................................... ..........................................................

Partie B :
Soit l’equation suivante :
1 1 1 1
+ + + ··· (1)
nbr1 nbr2 nbr3 nbrn
On désire développer un évaluateur de l’equation (1) en utilisant l’instruction suivante :

id := 1 ÷ nbr1 + 1 ÷ nbr2 + 1 ÷ nbr3 + · · · 1 ÷ nbrn (2)

Remarques : On suppose que n > 0.
nbr est un nombre entier et id est un identificateur. nbr et id sont reconnus par l’analyseur lexical.

(a) Trouver la grammaire G = ({I, E, T }, {id, :=, +, ÷, nbr, 1}, I) qui permet d’analyser l’ instruction (2).
...... −→ ...... := ...... (1)
...... −→ ...... + ...... | ......
(2) (3)
T −→ 1......nbr (4)

Epreuve de Compilation Page 2/4

 (b) Construire la collection d’ensembles d’items LR(1) pour la grammaire obtenue en (a).
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................

(c) Donner sa table d’analyse LR(1).

id := + ÷ nbr 1 # I E T
I0
I1
I2
I3

Epreuve de Compilation Page 3/4

 (d) Analyser la chaı̂ne a := 1 ÷ 5 + 1 ÷ 2#

Pile Chaine Actions

#I0 a := 1 ÷ 5 + 1 ÷ 2#

(e) Ecrire une Définition Dirigée par la Syntaxe DDS qui permet d’évaluer les expressions de l’instruction (2).

Production Règle sémantique

Bonne chance

Epreuve de Compilation Page 4/4