Théorie des langages : Td automates finis et compilation
Télécharger PDFUniversit ́
e de CaenAnn ́
ee 2018/2019
UFR des Sciences2` eme session
Mercredi 3 Juillet
L3 – INF6ACT
Th ́
eorie des langages et compilation
dur ́
ee 2h
Documents autoris ́es : notes personnelles, diapos du cours.
Chaque candidat doit, en d ́ebut d’ ́epreuve, porter son nom dans le coin de la copie
r ́eserv ́e `a cet usage; il le cachettera par collage apr`es la signature de la feuille
d’ ́emargement. Sur chacune des copies intercalaires, il portera son num ́ero de place.
Exercice I. Automate Fini
On se donne l’automate fini suivant :0123 a, baba Question 1.Donner la table de transitions de cet automate.
Question 2.Parmi les mots suivants, lesquels sont reconnus par l’automate ?aaa, aba,
aabbaba, abaaba, aababaaaa, abcb
Question 3.Quel est le langage reconnu par cet automate ?
Question 4.D ́eterminiser l’automate.
On consid`ere maintenant le langage :aba(a + b)∗ Question 5.Parmi les mots suivants, lesquels appartiennent au langage ?aaa, aba, aabbaba,
abaaba, aababaaaa, abcb
Question 6.Construire un automate fini reconnaissant ce langage.
Exercice II. Compilation
On souhaite ajouter `a notre calculette le support des tableaux.
Pour la suite, on supposera qu’un tableau de taillelgconnue et fix ́ee est stock ́e dans la
pile en empilant d’abord sa longueur puis ses ́el ́ements. Par exemple, le tableautab = [12, 3]
est transcrit par la suite de mots2 12 3. On supposera ́egalement que l’adresse du tableau
correspond `a la position du mot indiquant sa taille.
On utilise les opcodesPUSHR xetSTORER xqui effectuent les op ́erations suivantes :
CodePilesppc
PUSHRnP[sp-1] := P[P[sp-1] + n]sppc+2
STORERnP[P[sp-2] + n] := P[sp-1]sp-2pc+2
Soit le code suivant
PUSHI 3
PUSHI 3
PUSHI 0
PUSHI 1
PUSHI 2
PUSHI 5
STORER 1
PUSHI 0
PUSHI 0
PUSHR 1
PUSHI 1SUB PUSHR 1
STORER 1
PUSHI 0
PUSHR 1WRITE POPHALT et le r ́esultat de son assemblage
Adr | Instruction
-----+---------------
0 | PUSHI3 2 | PUSHI3 4 | PUSHI0 6 | PUSHI1 8 | PUSHI2 10 | PUSHI5 12 | STORER1 14 | PUSHI0 16 | PUSHI0 18 | PUSHR1 20 | PUSHI1 22 | SUB
23 | PUSHR1 25 | STORER1 27 | PUSHI0 29 | PUSHR1 31 | WRITE
32 | POP
33 | HALT
Question 7.Compl ́eter la trace d’ex ́ecution suivante.
pc || fp pile
====================================================
0 | PUSHI
3 |
0 [ ] 0
2 | PUSHI
3 |
0 [ 3 ] 1
4 | PUSHI
0 |
0 [ 3 3 ] 2
6 | PUSHI
1 |
0 [ 3 3 0 ] 3
8 | PUSHI
2 |
0 [ 3 3 0 1 ] 4
10 | PUSHI
5 |
0 [ 3 3 0 1 2 ] 5
12 | STORER
1 |
0 [ 3 3 0 1 2 5 ] 6
14 | PUSHI
0 |
0 [ 3 3 0 5 ] 4
16 | PUSHI
0 |
0 [ 3 3 0 5 0 ] 5
18 | PUSHR
1 |
0 [ 3 3 0 5 0 0 ] 6
20 | PUSHI
1 |
0 [ 3 3 0 5 0 3 ] 6. .. .. 31 | WRITE| 0 [ 3 5 0 5 5 ] 55 32 | POP| 0 [ 3 5 0 5 5 ] 5
33 | HALT| 0 [ 3 5 0 5 ] 4
Question 8. ́
Ecrire le code MV`aP correspondant `a la fonction suivante :
int b = [2, 5, 6]
int f ( x ) {b[x]=1 return b[x+1]} println(f(1))
On donne la grammaire suivante permettant de prendre en compte la d ́eclaration (initialis ́ee)
de tableaux :
declaration returns [ String code ]
<...>
| ’int’ IDENTIFIANT ’=’ ’[’ elems ’]’
{ //` A compl ́
eter }
<...>; elems returns [ String code, int size]
@init{ $code = new String(); $size = 0; }
: ( ENTIER
{ //` A compl ́
eter }
( ’,’ ENTIER
{ //` A compl ́
eter })* )?; Question 9.Compl ́eter les actions de la grammaire afin de g ́en ́erer le code MV`aP correct.
On se donne ́egalement la grammaire de l’utilisation des tableaux :
instruction returns [ String code ]
<...>
| IDENTIFIANT ’[’ expr ’]’ ’=’ expr finInstruction
{ //` A compl ́
eter }
<...>; expr returns [ String code ]
<...>
| IDENTIFIANT ’[’ expr ’]’
{ //` A compl ́
eter }
<...>; Question 10.Compl ́eter les actions de la grammaire afin de g ́en ́erer le code MV`aP.
Exercice III. AnalyseLLetSLR
Soit la grammaireGd’axiomeSet de terminaux{id, nb, [, ]}d ́efinie par : S→id A
A→[ B ] A|[ B ]B→nb Question 11.Donner un arbre d’analyse pour le mot suivant :id [ nb ] [ nb ].
Question 12.Cette grammaire est elleLL(1)? Justifier.
On consid`ere la version augment ́ee de la grammaireG: init→S
S→id A
A→[ B ] A|[ B ]B→nb On dispose de l’automate fini caract ́eristique des itemsLR(0)deG.init→•S S→•id A0 init→S•1 S→id•A
A→•[ B ] A
A→•[ B ]2 S→id A•3 A→[•B ] A
A→[•B ]B→•nb 4
A→[ B•] A
A→[ B•]5 B→nb•6 A→[ B ]•A
A→[ B ]•
A→•[ B ] A
A→•[ B ]7 A→[ B ] A•8 Sid A[ Bnb ]A [
Question 13.
13 . a)Quel ́état de l’automate contient un conflit d ́ecaler/r ́eduire ?
13 . b)Donner la table des ensemblesSuivant.
13 . c)Expliquer comment le conflit d ́ecaler/r ́eduire pr ́ec ́edent se r ́esout.
On donne la table d’analyseSLRdeG.
$idnb[]SAB
0d 21
1accepter
2d 43
3r S→id A
4d 65
5d 7
6r B→nb
7r A→[ B ]d 48
8r A→[ B ] A
Question 14.Pour la tableSLR, expliquer de fa ̧con claire et d ́etaill ́ee comment est d ́etermin ́ee :
14 . a)la ligne associ ́ee `a l’ ́etat0;
14 . b)la ligne associ ́ee `a l’ ́etat1;
14 . c)la ligne associ ́ee `a l’ ́etat7.
Question 15.
15 . a)D ́erouler l’analyseSLRsur l’entr ́eeid [ nb ] [ nb ].
15 . b)Grˆace `a cette analyse, comment obtient on la d ́erivation droite pourid [ nb ] [ nb ]?
15 . c)D ́erouler l’analyseSLRsur l’entr ́eeid [ nb [ nb ].