IFT313

Introduction aux langages formels

Département d'informatique
Université de Sherbrooke

Lab 6
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.
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 « | »).
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).
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 / Scene  [# État] /
(
Shift? Reduce?
Accept? Error?
 ...
...
...

* 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 ();"