Théorie des langages : Exercices automate fini
Télécharger PDFUniversit ́e de CaenAnn ́ee 2018/2019
UFR des Sciences1`ere session
Mercredi 20 mars
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.
Rendre 2 copies s ́
epar ́
ees en notant bien le num ́
ero de place :
•l’une qui traite l’exercice I (Automate fini) et l’exercice
III (analyse LL)
•l’autre qui traite l’exercice II (Compilation)
Exercice I. Automate Fini` A rendre avec l’exercice III
On se donne l’automate finiA1 suivant :PI ab ab Question 1.Donner la table de transitions de cet automate.
Question 2.Donner l’ex ́ecution de l’automateA1 sur les quatre mots suivants :ε, aa,
ab, abbbaaab. Lesquels sont accept ́es parA1 ?
Question 3.Quel est le langage reconnu par l’automateA1 ?
Question 4.Donner une expression r ́eguli`ere de ce langage.
On consid`ere ́egalement l’automate finiA2 :EO ba ba Question 5.Quel est le langage reconnu parA2 ? En donner une expression r ́eguli`ere.
On d ́esigne maintenant parL1 etL2 les langages r ́eguliers reconnus parA1 etA2 , etparL 1∩L 2
leur intersection.
Question 6.Construire l’automate produit deA1 etA2 reconnaissantL1 ∩L2 .1 Exercice II. Compilation` A rendre sur une copie s ́epar ́ee
On souhaite ajouter `a notre calculette le support de la bouclefor in. Le principe de
cette boucle (pr ́esente en python) est quefor el in tabeffectue une boucle en prenant
poureltous les ́el ́ements du tableautab.
Pour la suite, on supposera qu’un tableau de taillenest 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 longueur.
On utilise l’opcodePUSHR xqui effectue l’op ́eration suivante:Code Pilesppc
PUSHRnP[sp-1] := P[P[sp-1] + n]sppc+1
Soit le code suivant
PUSHI 0
PUSHI 0
PUSHI 2
PUSHI 12
PUSHI 3
JUMP 0
LABEL 0
PUSHI 0
STOREG 0
LABEL 1
PUSHG 0
PUSHG 2INF JUMPF 2
PUSHG 0
PUSHR 3
STOREG 1
PUSHG 1WRITE POP
PUSHG 0
PUSHI 1ADD STOREG 0
JUMP 1
LABEL 2HALT et le r ́esultat de son assemblage
Adr | Instruction
-----+---------------
0 | PUSHI0 2 | PUSHI0 4 | PUSHI2 6 | PUSHI12 8 | PUSHI3 10 | JUMP12 12 | PUSHI0 14 | STOREG0 16 | PUSHG0 18 | PUSHG2 20 | INF
21 | JUMPF42 23 | PUSHG0 25 | PUSHR3 27 | STOREG1 29 | PUSHG1 31 | WRITE
32 | POP
33 | PUSHG0 35 | PUSHI1 37 | ADD
38 | STOREG0 40 | JUMP16 42 | HALT2 Question 7.Compl ́eter la trace d’ex ́ecution suivante.
pc || fp pile
====================================================
0 | PUSHI
0 |
0 [ ] 0
2 | PUSHI
0 |
0 [ 0 ] 1
4 | PUSHI
2 |
0 [ 0 0 ] 2
6 | PUSHI
12 |
0 [ 0 0 2 ] 3
8 | PUSHI
3 |
0 [ 0 0 2 12 ] 4
10 | JUMP
12 |
0 [ 0 0 2 12 3 ] 5
12 | PUSHI
0 |
0 [ 0 0 2 12 3 ] 5
14 | STOREG
0 |
0 [ 0 0 2 12 3 0 ] 6
16 | PUSHG
0 |
0 [ 0 0 2 12 3 ] 5
18 | PUSHG
2 |
0 [ 0 0 2 12 3 0 ] 6
20 | INF| 0 [ 0 0 2 12 3 0 2 ] 7. .. .. 31 | WRITE| 0 [ 0 12 2 12 3 12 ] 6
32 | POP| 0 [ 0 12 2 12 3 12 ] 6
33 | PUSHG
0 |
0 [ 0 12 2 12 3 ] 5
35 | PUSHI
1 |
0 [ 0 12 2 12 3 0 ] 6
37 | ADD| 0 [ 0 12 2 12 3 0 1 ] 7
38 | STOREG
0 |
0 [ 0 12 2 12 3 1 ] 6
40 | JUMP
16 |
0 [ 1 12 2 12 3 ] 5
16 | PUSHG
0 |
0 [ 1 12 2 12 3 ] 5
18 | PUSHG
2 |
0 [ 1 12 2 12 3 1 ] 6
20 | INF| 0 [ 1 12 2 12 3 1 2 ] 7
21 | JUMPF
42 |
0 [ 1 12 2 12 3 1 ] 6
23 | PUSHG
0 |
0 [ 1 12 2 12 3 ] 5
25 | PUSHR
3 |
0 [ 1 12 2 12 3 1 ] 6
27 | STOREG
1 |
0 [ 1 12 2 12 3 3 ] 6
29 | PUSHG
1 |
0 [ 1 3 2 12 3 ] 5
31 | WRITE| 0 [ 1 3 2 12 3 3 ] 6
32 | POP| 0 [ 1 3 2 12 3 3 ] 6
33 | PUSHG
0 |
0 [ 1 3 2 12 3 ] 5
35 | PUSHI
1 |
0 [ 1 3 2 12 3 1 ] 6
37 | ADD| 0 [ 1 3 2 12 3 1 1 ] 7
38 | STOREG
0 |
0 [ 1 3 2 12 3 2 ] 6
40 | JUMP
16 |
0 [ 2 3 2 12 3 ] 5
16 | PUSHG
0 |
0 [ 2 3 2 12 3 ] 5. .. .
Question 8. ́
Ecrire le code MVaP correspondant `a la fonction suivante:
int b = [ 4 , 5]
int f ( x ) {
return x+3} println( f(6) + 1)3 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 completer }
<...>; elems returns [ String code, int size]
@init{ $code = new String(); $size = 0; }
: ( ENTIER
{ //` A completer }
( ’,’ ENTIER
{ //` A completer })* )?; 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 pour la bouclefor in:
instruction returns [ String code ]
<...>
| ’for’ IDENTIFIANT ’in’ IDENTIFIANT bloc
{ //` A completer }
<...>; Question 10.Compl ́eter les actions de la grammaire afin de g ́en ́erer le code MV`aP pour
cette boucle. On pourra supposer l’existence d’une variable globale sp ́ecialeiforque l’on pourra utiliser pour stocker l’indice courant du tableau.4 Exercice III. Analyse LL` A rendre avec l’exercice I
On consid`ere la grammaireGd ́efinie par l’axiomeS, les variables{S, GN, GV, GP, PR}, les
terminaux{art, de, nom, prepo, verbe}et les r`egles de production : S→GN GV
GN→art nom GP
GP→de GN|ε
GV→verbe PR GN
PR→prepo|ε
Question 11.Donner un arbre d’analyse pour le mot suivant :
art nom de art nom verbe prepo art nom
Question 12.
12 . a)Quelles sont les variables effa ̧cables ?
12 . b)Donner la table des ensemblesPremier.
12 . c)On note$le symbole terminal qui marque la fin des mots `a analyser. Donner la
table des ensemblesSuivant.
On dispose de la table d’analyseLL(1)deG:
$artdenomprepoverbe
SS→GN GV
GNGN→art nom GP
GPGP→εGP→de GNGP→ε
GVGV→verbe PR GN
PRPR→εPR→prepo
Question 13.Expliquer de fa ̧con claire et d ́etaill ́ee comment la ligne associ ́ee `a la vari-
ableSdans la table est obtenue. Mˆeme question pour la ligne correspondant `aGP.
Question 14.D ́erouler l’analyseLL(1)sur l’entr ́eeart nom verbe art nom.` A partir
de cette analyse, comment retrouver la d ́erivation gauche associ ́ee `aart nom verbe artnom? 5