IFT313 - Introduction aux langages formels

Département d'informatique
Université de Sherbrooke

Été 2014
Devoir 1 - à remettre le madi 20 mai 2014

Enseignant  : froduald.kabanza@usherbrooke.ca
Correcteur : francis.bisson@usherbrooke.ca (personne contact pour les questions)

1. Tâches

Vous devez écrire trois programmes en Java: PiloteAFD.java, Test2.java et ProgrammeRegex.java selon les spécifications décrites plus bas.

Pour ce travail pratique, vous devez utiliser les fichiers contenus dans l'archive suivante :
tp1-sources.zip

1.1. Programme 1: PiloteDFA.java  [40%]

Vous devez compléter le fichier PiloteDFA.java qui implémente le pilote d'automates finis déterministes (DFA Driver) pour reconnaître des unités lexicales (tokens), c'est-à-dire les plus longues sous-chaînes acceptées par l'automate. Vous pouvez le faire en modifiant l'algorithme de simulation d'un AFD vu en classe et repris ci-dessous:

Algorithm DFASimulator  // Simulateur d’AFD
{
     currentState =  initialStateOfTheDFA
     currentInputPosition = 0;
     currentChar = nextChar();
     currentInputPosition++;
     while ((a != EOF) && (currentState != 0))
     {
          currentState = trans[currentState][currentChar];
          currentChar = nextChar();
          currentInputPosition++;
     }
    if ((isIn(currentState, finalStates) && (currentChar == EOF))
       return TRUE;
    else return FALSE;
}

Vous pouvez modifier cet algorithme à votre guise. Par exemple, vous pourriez remplacer  nextChar() par une méthode Java appropriée pour lire le prochain caractère, comme input.read(). Nous avons vu aussi en classe comment modifier cet algorithme pour reconnaître des unités lexicales (tokens). Plus précisément, vous devez introduire de nouvelles variables afin de mémoriser la position initiale de lecture après le dernier token, l’état accepteur le plus récent et la position de lecture correspondante. Vous devez en plus traiter les actions associées aux états accepteurs.

Spécifications

La classe PiloteDFA.java doit avoir:

Classes fournies

public class Token
{
  private int type = 0;      // Type de token
  private String text = "";  // Texte associé au token
  private int left = 0;      // position du premier caractère
  private int right = 0;     // position de fin
  private Object action = null; // action associée

  public Token(int type, String text, int left, int right, Object action) { ... }

  //...
}

public class DFA{
  public DFA(char symboles[], int init, int[][] trans, int[] finalStates, Object[] actions)
  { ... }
  public int initialState();
  public int nextState(int state, char c);
  public boolean isFinal(int state);
  public int tokenType(int state);
  public Object tokenAction(int state);
}

Le constructeur prend un tableau de symboles, l'état initial, une table de transition, un tableau d'états finaux accepteurs et un tableau d'action. La méthode initialState() retourne le numéro de l'état initial; cela doit être différent de zéro (0). La méthode nextState(int state, char c) implémente les transitions de l'automate. Elle retourne l’état successeur de l'état state sous la transition du caractère c. Si une telle transition n’existe pas, elle retourne 0. La méthode isFinal(int state) retourne true si l'état passé en argument est un état accepteur. La méthode tokenType(int state) retourne un entier positif si son argument est un état accepteur sinon moins un (-1) si l’état est non accepteur. De façon similaire, la méthode actionType(int state) retourne l'action associée à l'état. Ces deux dernières méthodes devront être invoquées dans la méthode nextToken() de votre classe PiloteDFA; dans ce cas, son argument serait le plus récent état accepteur rencontré durant la lecture. En principe, tokenType() ne devrait être invoqué qu’avec un état accepteur comme argument.

Test

Pour tester votre pilote d'AFD, vous devez utiliser le programme fourni Test1.java. Ce programme implémente l'AFD suivant.
AFD

public class Test1{
   
    public static void main(String[] args) throws java.lang.Exception{
        char[] symboles = new char[] { 'a', 'b', 'c', '1', '2', '3', '(', ')', ' ' };
        int trans[][] = new int[][]{
            /*        'a', 'b', 'c', '1', '2', '3', '(', ')', ' '  X */
            /*S0*/   { 0,   0,   0,   0,   0,   0,   0,   0,   0,  0},
            /*S1*/   { 2,   2,   2,   3,   3,   3,   4,   5,   6,  0},
            /*S2*/   { 2,   2,   2,   2,   2,   2,   0,   0,   0,  0},
            /*S3*/   { 0,   0,   0,   3,   3,   3,   0,   0,   0,  0},
            /*S4*/   { 0,   0,   0,   0,   0,   0,   0,   0,   0,  0},
            /*S5*/   { 0,   0,   0,   0,   0,   0,   0,   0,   0,  0},
            /*S6*/   { 0,   0,   0,   0,   0,   0,   0,   0,   6,  0},
        };
       
        int finalStates[] = new int[] {2, 3, 4, 5, 6};
        String actions[] = new String[] {"Identificateur", "Nombre",
                "ParenthèseOuvrante", "ParenthèseFermante", "EspaceBlanc"};
       
        DFA dfa = new DFA(symboles, 1, trans, finalStates, actions);
        FileReader input = new FileReader(args[0]);
        PiloteDFA driver = new PiloteDFA(dfa, input);
       
        Token tk;
        do{
            tk = driver.nextToken();
            System.out.println(tk);
        }while (tk.type() != -1);
        System.out.println("\nEnd\n");
    }
}


Le programme Test1 prend comme argument un nom de fichier en entrée. Pour l'exécuter en ligne de commande, faites:
$ javac *.java
$ java Test1 test1a.txt

Des exemples de fichier d'entrée (test1a.txt) et de sortie (sortie1a.txt) sont fournis. N'oubliez pas de les modifier pour bien tester votre pilote DFA.

1.2. Programme 2: Test2.java [20%]

Le deuxième programme à réaliser est Test2.java et il ressemble à Test1.java. Vous devez construire un automate qui accepte les unités lexicales suivantes:
  1. entier positif: [0-9]+  (ex: 0, 12, 9472, 3)
  2. réel positif: [0-9]+{ . [0-9]+}  (ex: 9.33, 39, 0.93, 0.48)
  3. opérateur +: '+'
  4. opérateur -: '-'
  5. parenthèse ouvrante: (
  6. parenthèse fermante: )
  7. espace blanc: ' '*
L'alphabet est formé des 16 caractères suivants : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, '.', '(', ')', '+', '-', ' ').

Votre travail consiste à écrire l'automate sur papier (n'est pas à remettre), de coder sa table de transition et ses sept états finaux accepteurs.

Le programme Test2 prend comme argument un nom de fichier en entrée. Pour l'exécuter en ligne de commande, faites:
$ javac *.java
$ java Test2 test2a.txt

Des exemples de fichier d'entrée (test2a.txt) et de sortie (sortie2a.txt) sont fournis.

1.3. Programme 3: ProgrammeRegex.java [40%]

Vous devez utiliser le package regex de Java pour écrire un programme ProgrammeRegex.java qui trouve des numéros de téléphone, des adresses de courriel et des URL dans un fichier texte. Lisez très attentivement le texte ci-dessous pour bien comprendre ce qui doit être accepté et refusé. Les spécifications fournies ont été simplifiées par rapport aux vraies spécifications. Tous les éléments surlignées en vert doivent être extrait.

Au Canada, les numéros de téléphone sont composés de dix chiffres. Les trois premiers forment l'indicatif régional et les sept derniers forment le numéro local. Pour écrire un numéro de téléphone, on commence habituellement par l'indicatif régional, suivit d'un espace et du numéro local. L'écriture de l'indicatif régional est optionnelle, mais recommandée. Le numéro local est décomposé en deux blocs séparés par un tiret; le premier bloc a trois chiffres et le deuxième a quatre chiffres. Par exemple, on peut écrire 819 821-8000 ou 821-8000.

Anciennement, l'indicatif régional était écrit entre deux parenthèses (ouvrante et fermante), comme (819)821-8000. Depuis que la composition à dix chiffres est obligatoire dans plusieurs régions au Canada, cette forme est déconseillée. Mais, comme elle est encore très présente, un bon programme doit encore les reconnaître. Par contre, il ne faut pas écrire tous les chiffres d'un seul bloc, ni utiliser des points. Les chaînes 8198218000, 8218000, 819.821.8000 doivent donc être refusées. Un espace ou un tiret peut séparer l'indicatif régional sans parenthèse et le numéro local. Un indicatif régional entre parenthèses peut être collé au numéro local, ou séparé par un espace.

Pour les numéros sans-frais, on doit ajouter un 1 devant l'indicatif sans-frais. Les indicatifs sans-frais en vigueur sont : 800, 888, 877 et 866. Un espace ou un tiret peut séparer le code de pays, l'indicatif sans frais et le numéro local. Dans les autres numéros on peut inclure le code de pays suivi d'un espace, mais seulement si l'indicatif régional n'est pas entre parenthèses et est lui-même est séparé par un espace du numéro local.

Pour plus d'informations sur l'écriture des numéros de téléphone, vous pouvez communiquer avec l'Office québécois de la langue française :

Téléphone :
    514 873-6565
 ou 1 888 873-6202
Télécopie :
    514 873-3488
Courriel :
    info@oqlf.gouv.qc.ca
Web :
    http://www.oqlf.gouv.qc.ca/

Une adresse de courriel valide a la forme suivante: prefixe@domaine.com. Le préfixe est composé de lettres et de chiffres, mais il doit commencer par une lettre. Ainsi, 1allo@domaine.com n'est pas valide à cause du chiffre un. Le préfixe peut aussi contenir des points (.) et des tirets (-), mais ces derniers ne peuvent ni commencer, ni terminer un préfixe. Le nom de domaine a une forme semblable au préfixe, à l'exception qu'il doit contenir au moins un point.

Exemples d'adresses de courriel valides: bob@usherbrooke.qc.ca, john@hotmail.com, abcdef@g.h.i.k et s103.2@y92.org.

Exemples d'adresses invalides: 92aaaa@www.domaine.com, 2323-@toto.com et .ass@.dfdf..

Enfin, une URL est composée d'un protocole, suivit de deux-points, deux barres obliques, d'un nom de domaine et, optionnellement d'un chemin d'accès. Le nom de domaine peut être remplacé par une adresse IP, c'est-à-dire quatre blocs de 1 à 3 chiffres séparés par des points (ex.: 192.168.0.1). Ici, il n'est pas requis de vérifier si les nombres sont compris entre 0 et 255 inclusivement. Le chemin d'accès doit commencer par une barre oblique (/). Le chemin peut contenir des lettres, des chiffres et certains caractères spéciaux (~, ?, ~, =, +, &, ., #). Par contre, une URL ne peut pas se terminer par l'un de ces caractères spéciaux. Par exemple, prenons l'adresse http://www.usherbrooke.ca/. Le point suivant la barre oblique ne doit pas faire partie de la chaîne reconnue. De plus, seules les adresses débutant par HTTP sont recherchées. Les adresses comme https://www.usherbrooke.ca/monbureau ou ftp://ftp.site.com doivent être ignorées.

Habituellement, un serveur Web utilise le port 80. Mais il est possible d'utiliser d'autres ports. Dans de tels cas, on ajoute un deux-points (:) après le nom de domaine suivi du numéro de port. Par exemple, http://127.0.0.1:8080/ pourrait désigner l'adresse d'un serveur Web local.

Ce texte est disponible à l'adresse suivante: http://planiart.usherbrooke.ca/kabanza/cours/ift313/TPs/tp1/index.html#programme3.


Le texte dans le cadre ci-dessus est intégrallement dans le fichier test3a.txt. Votre programme devrait produire en sortie:
819 821-8000
821-8000
(819)821-8000
514 873-6565
1 888 873-6202
514 873-3488
info@oqlf.gouv.qc.ca
http://www.oqlf.gouv.qc.ca/
prefixe@domaine.com
allo@domaine.com
bob@usherbrooke.qc.ca
john@hotmail.com
abcdef@g.h.i.k
s103.2@y92.org
aaaa@www.domaine.com
http://www.usherbrooke.ca/
http://127.0.0.1:8080/

Attention: le fichier test fourni ne vérifie pas tous les cas limites. Vous avez la responsabilité d'écrire d'autres tests afin de vérifier que votre programme fonctionne correctement. Il est déconseillé d'écrire une seule expression régulière en une seule ligne. Allez-y plutôt par fragments.

Par exemple:
        String tel = "(\\d{3} )?\\d{3}-\\d{4}";
        String courriel = "\\p{Alpha}+@\\p{Alpha}+[.]\\p{Alpha}+";
        String url = "http[:]//\\p{Alpha}+";
        Pattern pattern = Pattern.compile(
tel + "|" + courriel + "|" + url);

2. Fichiers à remettre et autres directives

Vous devez remettre vos 3 fichiers avec la commande turnin suivante sous Unix:
turnin -c ift313 -p tp1 PiloteDFA.java Test2.java ProgrammeRegex.java

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

Vous ne devez pas utiliser d'autres packages autres que ceux fournis avec Java SE 7u21.

Vous devez soumettre votre travail au plus tard le mardi 20 mai 2014 à 23 h 59.

Pour toute question, contactez francis.bisson@usherbrooke.ca

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.