IFT313

Introduction aux langages formels

Département d'informatique
Université de Sherbrooke

Lab 6
Réponse à l'exercice 3

L'Agence spatiale canadienne vous demande d'écrire un chargeur de fichiers de requêtes pour la planification d'acquisitions d'images satellitaires. Une requête spécifie une scène ainsi qu'une ou plusieurs dates. La scène est spécifiée par un polygone d'au moins trois (3) coordonnées géographiques*. Les dates peuvent être spécifiées individuellement ou de façon répétive (each month, each day, each week) sur un interval donné. Par exemple, la écrire "2007-01-01 to 2007-12-31 each month" est l'équivalent d'écrire "2007-01-01, 2007-02-01, 2007-03-01, 2007-04-01, 2007-05-01, 2007-06-01, 2007-07-01, 2007-08-01, 2007-09-01, 2007-10-01, 2007-11-01, 2007-12-01". Un fichier de requêtes peut contenir zéro ou plusieurs requêtes.

Exemple de fichier :

Scene(N45W72, N45W71, N44W71, N44W72)
 at (2007-07-29, 2007-08-29);

Scene(N58W75, N58W71, N56W73) at
  (2007-07-29 to 2008-07-29 each month);

Scene(N45.3W71.8, N45.5W71.8, N45.5W71.6, N45.3W71.6)at(2007-07-29
 to 2008-07-29 each month, 2007-07-15 to 2008-07-15 each month);


a)  Déterminez quels seraient les types de symboles terminaux retournés au niveau de l'analyse lexical. Pour chaque type, donnez un exemple de lexème pris dans l'exemple ci-dessus.

Type
Explication
Exemple
'scene'
Mot clé
scene
'('
Parenthèse ouvrante
(
')'
Parenthèse fermante
)
coor
Une coordonnée composé d'une latutude et longitude.
N45W72
','
Virgule
,
at
Mot clé

date
Une date fixe
2007-07-29
'to'
Le mot clé to
to
'each'
Le mot clé each
each
duree
Une durée. Les mots clés "day", "month" et "year".
day
';'
Point-virgule
;

Note: il y avait plusieurs solutions possibles.

b)  Donnez une grammaire SLR du langage de spécification de requêtes. Utilisez des noms de symboles significatifs. Numérotez vos règles de productions (n'utilisez pas l'opérateur ou « | »).

  1. S' → fichier $
  2. fichier → fichier requête
  3. fichier →
  4. requête → 'scene'  '('  coors ')' 'at' '(' when ')'  ';'
  5. coors → coors ',' coor
  6. coors → coor
  7. when → when ',' date2
  8. when → date2
  9. date2 → date
  10. date2 → date to date 'each' duree

c)  Montrez que votre grammaire est bien SLR en donnant sa table d'analyse. Vous pouvez simplifier les noms de symbole, mais sans introduire d'ambiguïtés. L'ADF n'est pas demandé. Les numéros dans la table doivent correspondre avec la numérotation des règles en b).


action goto

'at'

coor
date
duree
each
'scene'
'to'
(
)
,
;
$
coors
date2
fichier requête
when
0





r1





r2


1


1





s3





Acc



2

2





r1





r1





3







s4









4

s6










5




5








s9
s7







6








r5
r5







7

s8















8








r4
r4







9
s10
















10







s11









11


s14










13


12
12








s15
s17







13








r7
r7







14






s19

r8
r8







15










s16






16





r3





r3





17


s14










18



18








r6
r6







19


s20














20




s21












21



s22













22








r9
r9








d)  Simuler l'algorithme LR_Parser, avec la table SLR calculée en c), sur la chaîne suivante :

Scene(N45W72, N45W71) at (2007-07-29);

Pile ( État Init / Symbole  État / Symbole / État / ...)
Prochain Token en entrée
Action
 #0 /
scene
Initialisation
 #0 / fichier #1
scene R2
 #0 / fichier #1 / scene #3
(.
S3
#0 / fichier #1 / scene #3 / ( #4
N45W72 [coor]
S4
#0 / fichier #1 / scene #3 / ( #4 / N45W72 #6
,
S6
#0 / fichier #1 / scene #3 / ( #4 / coors #5
,
R5
#0 / fichier #1 / scene #3 / ( #4 / coors #5 / , #7
N45W71 [coor]
S7
#0 / fichier #1 / scene #3 / ( #4 / coors #5 / , #7 / N45W71 #8
)
S8
#0 / fichier #1 / scene #3 / ( #4 / coors #5
)
R4
#0 / fichier #1 / scene #3 / ( #4 / coors #5 / ) #9
at
S9
#0 / fichier #1 / scene #3 / ( #4 / coors #5 / ) #9 / at #10
(
S10
#0 / fichier #1 / scene #3 / ( #4 / coors #5 / ) #9 / at #10 / ( #11
2007-07-29 [date]
S11
#0 / fichier #1 / scene #3 / ( #4 / coors #5 / ) #9 / at #10 / ( #11 / 2007-07-29 #14
)
s14
#0 / fichier #1 / scene #3 / ( #4 / coors #5 / ) #9 / at #10 / ( #11 / date2 #13 )
R8
#0 / fichier #1 / scene #3 / ( #4 / coors #5 / ) #9 / at #10 / ( #11 / when #12 )
R7
#0 / fichier #1 / scene #3 / ( #4 / coors #5 / ) #9 / at #10 / ( #11 / when #12 / ) #15
;
S15
#0 / fichier #1 / scene #3 / ( #4 / coors #5 / ) #9 / at #10 / ( #11 / when #12 / ) #15 / ; #16
$
S16
#0 / fichier #1 / requête #2
$
R3
#0 / fichier #1
$
R1


Accepte

* Vous pouvez supposer qu'une validation est faite à l'analyse sémantique pour le nombre de points et de dates. Ainsi, vous n'avez pas besoin d'écrire une grammaire qui refuse la chaîne "Scene() at ();"