Consignes

Le rendu de TP se fera uniquement à travers l'interface web TPLab. Vous devrez fournir un unique fichier .c contenant le code des fonctions demandées.

Le TP3 utilisera les fonctions écrites dans ce TP. Il faut donc avoir une version des fonctions :

pour le TP3.

Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans votre fichier principal.

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

Liens utiles

1. Préliminaires

  1. Quel est le langage reconnu par l'expression régulière (ERE POSIX) "^(a?){30}a{30}$" ?
  2. Vérifiez que "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" (30 a consécutifs) est bien reconnu par cette expression régulière avec grep.
  3. Donnez une version "Kleene" de cette expression régulière en remplaçant ? et {30} par leurs équivalents "Kleene".

Le petit script Python suivant permet de tester l'expression régulière précédente sur des chaines : 

#!/usr/bin/python
import re
import sys

if len(sys.argv) < 2:
    sys.exit(-1)

n = int(sys.argv[1])

r = "^(a?){" + str(n) +"}a{" + str(n) + "}$"
print("regex: '{}'".format(r))

while True:
    s = sys.stdin.readline().strip()
    if re.match("^"+r+"$", s):
        print("contient '{}': oui".format(s))
    else:
        print("contient '{}': non".format(s))

Pour l'utiliser, il suffit de lancer la commande avec un argument entier, puis de donner des chaines : 

$ python test-regex.py 15
regex: '(a?){15}a{15}'
aaaaaaaaaaaaaa
contient 'aaaaaaaaaaaaaa': non
aaaaaaaaaaaaaaa
contient 'aaaaaaaaaaaaaaa': oui
aaaaaaaaaaaaaaaa
contient 'aaaaaaaaaaaaaaaa': oui

(Le premier argument permet de changer le 30 en un nombre arbitraire...)

  1. Vérifiez que "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa" (29 a consécutifs) n'est pas reconnue par "^(a?){30}a{30}$".
  2. Vérifiez que "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" (30 a consécutifs) est reconnue par "^(a?){30}a{30}$".

    Qu'en pensez-vous ?

facultatif

Faites des tests similaires avec la bibliothèque d'expressions régulières de votre langage favori. (C, Java, Javascript, PHP, ...)

2. Regex à la Kleene, en C

Pour compiler le code fournit, il faut disposer de la bibliothèque libgc (paquet libgc-dev sous Debian ou Ubuntu).

Cette bibliothèque permet de remplacer les appels à la fonction malloc par des appels à la fonction GC_MALLOC. Les espaces alloués ainsi seront automatiquement libérés (pas besoin de faire de free) par le Garbage Collector défini dans la bibliothèque.

L'archive du TP contient les définitions suivantes (dans le fichier regex.h) : 

/* une regex est une structure arborescente
 * chaque noeud a un type (voir au dessus)
 * pour une somme ou un produit, il y a deux fils
 * pour une etoile, il n'y a qu'un seul fils (le deuxième est NULL)
 * pour un symbole, il n'y a pas de fils et le champs "symbol" contient ... le symbol
 * pour 0 et 1, il n'y a pas de fils, et le champs "symbol" contient 0 */
typedef struct regex_s {
    enum CASE_REGEX regex_type;
    struct regex_s *first_son;
    struct regex_s *second_son;
    char symbol;
} *regex;

où le type énuméré des types de regex est 

enum CASE_REGEX {
    ZERO,
    ONE,
    SYMBOL,
    PLUS,
    TIMES,
    STAR
};

Le fichier utils.c contient également des fonctions pour faciliter la création de nouvelles regex. 

regex zero() ;
regex one() ;
regex symbol(char c) ;
regex plus(regex r1, regex r2) ;
regex cat(regex r1, regex r2) ;
regex star(regex r1) ;

N'hésitez pas à les utiliser pour faire vos tests... Par exemple, pour obtenir la regex du TD2, exercice 3, il suffit de faire 

    regex r =
      cat(
        star(symbol('a')),
        star(
          plus(
            plus(
              cat(cat(symbol('a'), symbol('a')), symbol('b')),
              cat(symbol('b'), cat(star(symbol('b')), symbol('a')))
                ),
              cat(symbol('b'), symbol('b'))
              )
            )
         );

Pour tester vos fonctions, il suffit d'écrire une fonction test dans votre fichier tp2-Roudoudou.c. Cette fonction sera appelée par la fonction main (que vous n'avez pas besoin d'écrire).

N'effacez pas vos fonctions de tests... Une fois les tests effectués, renommez la fonction en test_2, ... (Vos fonctions de tests pourront être regardées pour la notation du TP.)

La fonction récursive print_regex déjà définie dans le fichier tp2-Roudoudou.c est un peu naïve. Sur l'expression si dessus, elle affiche 

((a)*).((((((a).(a)).(b)) + ((b).(((b)*).(a)))) + ((b).(b)))*)

Modifiez la fonction pour supprimer des parenthèses :

Vous pouvez aussi omettre le symbole "." pour les concaténations.

Avec ces modifications, l'expression précédente sera affichée comme 

a*(aab + bb*a + bb)*

Écrivez la fonction (récursive) contains_epsilon qui renvoie 1 lorsque le langage d'une expression régulière contient le mot vide.

Écrivez la fonction (récursive) derivative qui calcule la regex dérivée à partir d'une regex et d'un symbole.

Vous avez maintenant tous les outils nécessaires pour écrire la fonction match qui renvoie 1 lorsque le langage d'une regex contient une chaine donnée, et 0 sinon.

La fonction main fournie permet de tester l'expression régulière données dans la partie préliminaire lorsqu'on donne un arguments sur la ligne de commandes : 

$ ./regex 15
(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)(1 + a)1aaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
contient 'aaaaaaaaaaaaaa': non
aaaaaaaaaaaaaaa
contient 'aaaaaaaaaaaaaaa': oui
aaaaaaaaaaaaaaaa
contient 'aaaaaaaaaaaaaaaa': oui

Testez votre implémentation en remplaçant 15 par 30 et

  1. vérifiez que "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa" (29 a consécutifs) n'est pas reconnue par "^(a?){30}a{30}$".
  2. vérifiez que "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" (30 a consécutifs) est reconnue par "^(a?){30}a{30}$".

Qu'en pensez-vous ?

Affichez les dérivées successives à l'intérieur de la fonction match et proposez une explication concernant l'inefficacité de votre fonction match.

Utilisez la fonction simplify (définie dans le fichier utils.c) et testez à nouveau.

Qu'en pensez-vous ?

3. Autres fonctions

Implémentez certaines des fonctions suivantes :