IFT313 - Introduction aux langages formels

Département d'informatique
Université de Sherbrooke

Été 2014
Travail pratique 2 - Programmer un analyseur lexical avec JFlex
à remettre le mardi 3 juin 2014


Enseignant: Froduald Kabanza (kabanza@usherbrooke.ca)
Auxiliaire: Francis Bisson (francis.bisson@usherbrooke.ca)

1. Tâches

Vous devez écrire trois fichiers: ScanCoors.jflex, FormatCoors.java et ScanGraph313.jflex selon les spécifications décrites plus bas.

Pour ce travail, vous devez télécharger JFlex 1.4.3 et vous référer à la documentation de JFlex (incluse dans l'archive) pour savoir comment l'utiliser.

Vous devez aussi partir des fichiers fournis dans l'archive suivante : tp2-sources.zip. Vous ne devez modifier que les fichiers à remettre.

1.1. ScanCoors.jflex  [40%]

De façon similaire au travail pratique 1, vous devez implémenter un analyseur lexical avec JFlex pour identifier les numéros de téléphone, les adresses de courriel et les URL.

Types de lexèmes à reconnaître  

Id (SymCoors.java)
Type
Spécification
TEL = 1
Numéro de téléphone
Sans-frais: 1 (888|877|866|800) 123-4567
10 chiffres: 819 821-8000
7 chiffres: 821-8000
ERR_TEL=2
Mauvais numéro de téléphone
Avec parenthèses:  (819)821-8000, (819)-821-8000
Avec des points: 819.821.8000
Deux tirets: 819-821-8000
EMAIL = 3
Adresse courriel
prefixe@domaine.com

Le préfixe peut contenir des lettres, chiffres, des points et des tirets. Le préfixe doit commencer par une lettre et ne peut pas terminer par un point ou un tiret. Le domaine a la même spécification que le préfixe à l'exception qu'il doit contenir au moins un point.
ERR_EMAIL = 4
Mauvaise adresse courriel
1prefixe@domaine.com, prefixe@1domaine.com, a@a-b

N'importe quoi (sauf caractères espaces, virgules, point-virgule, deux-points, saut de ligne et retour de ligne) suivit d'un @ et suivit de n'importe quoi (même exception). Une mauvaise adresse de courriel ne peut pas se terminer par un point. Par exemple, dans cette phrase, le point après le m est pour terminer la phrase: allo@domaine.com.
URL = 5
URL
http://serveur/chemin

serveur: nom de domaine ou adresse ip.
nomdomaine: même spécification que le domaine d'adresse de courriel.
chemin: peut contenir des barres obliques, lettres, chiffres, caractères spéciaux (~, -, #, ?, =, &, ., +). Le chemin doit commencer par une barre oblique et ne peut pas terminer par un caractère spécial.

NEWLINE = 6
Retour de ligne
\n ou \r  ou \r\n
SEPARATOR=7
Token spérateur
Espace(s), tabulation(s), point, deux-points, point-virgule, virgule. Utilisez: «  " "+|[\t\.\;\:\,]  ».
TEXTE=8
Texte
Tout ce qui ne contient pas un espace, une tabulation, un retour de chariot, un saut de ligne et un point. Enfin, tout ce qui n'est pas un séparateur ou une nouvelle ligne. Utilisez l'expression régulière « [^\r\n\ \t\.\;\:\,]+ ».

Test

Pour tester votre analyseur lexical:
  1. Générez ScanCoors.java :  jflex ScanCoors.jflex
  2. Compilez le projet :  javac -cp .;chemin_to_jflex.jar ScanCoors.java TestScanCoors.java
  3. Essayez avec un test fourni :  java -cp .;chemin_to_jflex.jar TestScanCoors test1.txt
test1a.txt
Numéros: 819 821-8000, 1 888 888-8888.
Courriels: allo@domaine.com, bonjour-ift313@devoir.qc.ca.
Mauvais courriels: 1allo@domaine.com, allo@0domaine.com.
Adresses URL: http://www.dmi.usherb.ca/~ebeaudry/ift313/tp2/index.html#test1.

test1a-sortie.txt
  (TOKEN TEXTE Numeros  TYPE  8  START 0  END  7)
  (TOKEN TEXTE :  TYPE  7  START 7  END  8)
  (TOKEN TEXTE    TYPE  7  START 8  END  9)
  (TOKEN TEXTE 819 821-8000  TYPE  1  START 9  END  21)
  (TOKEN TEXTE ,  TYPE  7  START 21  END  22)
  (TOKEN TEXTE    TYPE  7  START 22  END  23)
  (TOKEN TEXTE 1 888 888-8888  TYPE  1  START 23  END  37)
  (TOKEN TEXTE .  TYPE  7  START 37  END  38)
  (TOKEN TEXTE
  TYPE  6  START 38  END  40)
  (TOKEN TEXTE Courriels  TYPE  8  START 40  END  49)
  (TOKEN TEXTE :  TYPE  7  START 49  END  50)
  (TOKEN TEXTE    TYPE  7  START 50  END  51)
  (TOKEN TEXTE allo@domaine.com  TYPE  3  START 51  END  67)
  (TOKEN TEXTE ,  TYPE  7  START 67  END  68)
  (TOKEN TEXTE    TYPE  7  START 68  END  69)
  (TOKEN TEXTE bonjour-ift313@devoir.qc.ca  TYPE  3  START 69  END  96)
  (TOKEN TEXTE .  TYPE  7  START 96  END  97)
  (TOKEN TEXTE
  TYPE  6  START 97  END  99)
  (TOKEN TEXTE Mauvais  TYPE  8  START 99  END  106)
  (TOKEN TEXTE    TYPE  7  START 106  END  107)
  (TOKEN TEXTE courriels  TYPE  8  START 107  END  116)
  (TOKEN TEXTE :  TYPE  7  START 116  END  117)
  (TOKEN TEXTE    TYPE  7  START 117  END  118)
  (TOKEN TEXTE 1allo@domaine.com  TYPE  4  START 118  END  135)
  (TOKEN TEXTE ,  TYPE  7  START 135  END  136)
  (TOKEN TEXTE    TYPE  7  START 136  END  137)
  (TOKEN TEXTE allo@0domaine.com  TYPE  4  START 137  END  154)
  (TOKEN TEXTE .  TYPE  7  START 154  END  155)
  (TOKEN TEXTE
  TYPE  6  START 155  END  157)
  (TOKEN TEXTE Adresses  TYPE  8  START 157  END  165)
  (TOKEN TEXTE    TYPE  7  START 165  END  166)
  (TOKEN TEXTE URL  TYPE  8  START 166  END  169)
  (TOKEN TEXTE :  TYPE  7  START 169  END  170)
  (TOKEN TEXTE    TYPE  7  START 170  END  171)
  (TOKEN TEXTE http://www.dmi.usherb.ca/~ebeaudry/ift313/tp2/index.html#test1  TYPE  5  START 171  END  233)
  (TOKEN TEXTE .  TYPE  7  START 233  END  234)
END!

1.2. FormatCoors.java  [30%]

Vous devez programmer un formateur de texte qui surligne les coordonnées. Le programme FormatCoors.java utilise l'analyseur lexical ScanCoors.jflex. Pour chaque lexème trouvé, vous devez le transcrire correctement dans un fichier HTML. Pour le formatage, vous pouvez vous inspirer du code CSS dans les exemples de fichiers de sortie HTML. Il n'est pas nécessaire de connaître ni HTML, ni CSS.

Test

Pour tester le formateur :
  1. Compiler le projet : javac -cp .;chemin_to_jflex.jar FormatCoors.java
  2. Exécuter la conversion : java -cp .;chemin_to_jflex.jar FormatCoors test1.txt > test1-masortie.html
  3. Ouvrir test1-masortie.html dans un navigateur Web.
L'affichage de la conversion de test1a.txt en test1a-sortie.html donne:
Numeros: 819 821-8000, 1 888 888-8888.
Courriels: , .
Mauvais courriels: 1allo@domaine.com, allo@0domaine.com.
Adresses URL: http://www.dmi.usherb.ca/~ebeaudry/ift313/tp2/index.html#test1.

Autre test:  test1b.txt doit donner test1b-sortie.html.

1.3 ScanGraph313.jflex [30%]

Pour les prochains travaux portant sur l'analyse syntaxique, nous utiliserons un mini langage appelé Graph313. Ce dernier permet la description d'images vectorielles très simples.

Lexèmes
Description
Classe SymGraph313.java
Opérateurs arithmétiques
+, -, *, / 
PLUS, MOINS, MULT, DIV
Opérateurs logiques
&&, ||
ET, OU
Parentèses et accolades
(, ), {, }
LPAREN, RPAREN, LBRACE, RBRACE
Signe égal (assignation)
=
ASSIGN
Comparateurs
<, <=, ==, >=, >
PP, PPE, EG, PGE, PG
Point-virgule
;
POINTVIRGULE
Virgule
,
VIRGULE
Mots clés
define, else, for, if, main, return, while
LINE, RECT, BEGIN, END, POINTS, MODE_POLY, MODE_LINE,
voir fichier pour liste complète
Symbole d'appel de fonction
@
CALL
Identificateur
Suite de lettres ou chiffres débutant par une lettre. 
ID
Réel
Suite de chiffres [ <point> Suite de chiffres]  (1 ou 1.1)
NUMBER
Commentaires
/*  n'importe quoi */
Vous n'avez pas à traiter les commentaires imbriqués
pas de return
Espaces blancs
Saut de ligne (\n), retour de ligne (\r), espace et tabulation (\t)
pas de return
Erreur
Tout ce qui ne peut pas être reconnu correctement.

Bonis + 0.5 si fait correctement.
return SymGraph313.error.

Test

test2a.g313
define etoile(cx, cy, r){
   PI=3.141592654;
   BEGIN MODE_LINE;
   for(i,0,6,1){
      a = i*4*PI/5;
      x = @cos(a) * r;
      y = @sin(a) * r;
      POINTS cx+x, cy+y;
   }
   END;
}

main{
  lx = 0;
  ly = 0;
  for(x, 0, 1000, 1){
    y = 50 + @sin(x/10.0) * 20;
    LINE lx,ly,x,y;
    lx = x;
    ly = y;
  }

  /* test */
  BEGIN MODE_LINE;
  for(x, 0, 1000, 1){
    y = 150 + @sin(x/10.0) * 20;
    POINTS x,y;
  }
  END;

  for(x, 0, 100, 2){
    cx = 250 + @cos(x/2)*(x+20);
    cy = 250 + @sin(x/2)*(x+20);
    @etoile(cx, cy, x/10+4);
  }
}
Exemple d'exécution:
Exemple de rendu


Commandes pour tester :
test2a-sortie.txt
  (TOKEN TEXTE define  TYPE  24  START 0  END  6)
  (TOKEN TEXTE etoile  TYPE  3  START 7  END  13)
  (TOKEN TEXTE (  TYPE  16  START 13  END  14)
  (TOKEN TEXTE cx  TYPE  3  START 14  END  16)
  (TOKEN TEXTE ,  TYPE  4  START 16  END  17)
  (TOKEN TEXTE cy  TYPE  3  START 18  END  20)
  (TOKEN TEXTE ,  TYPE  4  START 20  END  21)
  (TOKEN TEXTE r  TYPE  3  START 22  END  23)
  (TOKEN TEXTE )  TYPE  17  START 23  END  24)
  (TOKEN TEXTE {  TYPE  18  START 24  END  25)
  (TOKEN TEXTE PI  TYPE  3  START 30  END  32)
  (TOKEN TEXTE =  TYPE  10  START 32  END  33)
  (TOKEN TEXTE 3.141592654  TYPE  2  START 33  END  44)
  (TOKEN TEXTE ;  TYPE  5  START 44  END  45)
  (TOKEN TEXTE BEGIN  TYPE  34  START 50  END  55)
  (TOKEN TEXTE MODE_LINE  TYPE  37  START 56  END  65)
  (TOKEN TEXTE ;  TYPE  5  START 65  END  66)
  (TOKEN TEXTE for  TYPE  30  START 71  END  74)
  (TOKEN TEXTE (  TYPE  16  START 74  END  75)
  (TOKEN TEXTE i  TYPE  3  START 75  END  76)
  (TOKEN TEXTE ,  TYPE  4  START 76  END  77)
  (TOKEN TEXTE 0.0  TYPE  2  START 77  END  78)
  (TOKEN TEXTE ,  TYPE  4  START 78  END  79)
  (TOKEN TEXTE 6.0  TYPE  2  START 79  END  80)
...

2. Fichiers à remettre

Vous devez remettre vos 3 fichiers avec la commande turnin suivante sous Unix:

turnin -c ift313 -p tp2 ScanCoors.jflex FormatCoors.java ScanGraph313.jflex

Dans tous vos fichiers, vous devez inscrire vos noms, matricules et adresses courriels dans l'entête.

Vous ne devez pas utiliser de packages autres que JFlex et ceux fournis avec Java 7u21.

Vous devez soumettre votre travail au plus tard le mardi 3 juin 2014 à 23 h 59. Prévoyez le soumettre en avance en cas de problèmes techniques.

3. Évaluation

Ce projet compte pour 5% de la note finale. L’évaluation sera basée sur le niveau de correction de vos programmes, l’efficacité et la simplicité. Le plus votre code sera simple (succinct) et plus il fonctionnera correctement (par exemple, identifier le plus de tokens valides et le moins de tokens invalides) et rapidement, mieux il sera. De manière générale, vous devez respecter les critères usuels d’un code modulaire et bien écrit selon la pratique courante de la programmation.

Votre travail sera évalué en utilisant des scripts automatiques. Si l’évaluation échoue parce que vous n’avez pas respecté les directives, vous serez pénalisé avec la possibilité d’avoir une note nulle si tous les tests échouent. Il est donc important de ne pas modifier les noms de classe et de package (l'instruction package ne doit pas être présente en haut des fichiers .jflex et .java).