Consignes

Le rendu de TP se fera uniquement à travers l'interface web TPLab. Vous devrez fournir une unique archive .tar contenant les deux fichiers tp3-Roudoudou.l et tp3-Roudoudou.y (où Roudoudou est remplacé par votre nom).

Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans vos fichiers.

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

• vos fichiers devront comporter un commentaire au début avec vos nom, prénom, filière et numéro du TP,
• votre code doit compiler avec les options -Wall -Wno-unused-function -Werror -Wextra -pedantic -std=gnu99 -O3.

Liens utiles

• l'archive du TP : info633-tp3.tar
• le sujet du TP 1 (lien)
• le sujet du TP 2 (lien)
• encadrant de TP : Pierre.Hyvernat@univ-savoie.fr

1. Préliminaires

Définir une valeur de type regex (pour le type défini dans le TP précédent) est verbeux :

   regex test =
      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'))
              )
            )
         );

Tester vos fonction du TP précédents sur des regex non triviales était donc un peu lourd.

L'objectif de ce TP est d'introduire la notion de parseur : c'est un programme qui lit du texte (fichier, chaine de caractères, stdin, ...) et le transforme en valeurs utilisable par votre programme. Il sera ainsi possible de définir la regex précédente simplement avec

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

Nous allons utiliser Lex et Yacc pour cette tache:

• Lex permet de faire une analyse lexicale du texte. Son but principal sera de découper le texte en morceaux appelés tokens. La chaine "a* (aab + bb*a + bb)*" deviendra ainsi

  SYMB(a) STAR LPAR SYMB(a) SYMB(a) SYMB(b) PLUS SYMB(b) SYMB(b) STAR SYMB(a) PLUS SYMB(b) SYMB(b) RPAR STAR
  

  Cette analyse lexicale s'apparente à la décomposition d'une phrase en mots.
• Yacc permet de faire une analyse grammaticale du résultat. Son but sera d'interpréter les tokens en fonction d'une grammaire. C'est lui qui transformera la suite de tokens en

        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'))
                )
              )
           )
  

$ make
gcc -Wall -Wno-unused-function -Wextra -pedantic -std=gnu99 -O3 -lgc -c utils.c
gcc -Wall -Wno-unused-function -Wextra -pedantic -std=gnu99 -O3 -lgc -c tp2-Roudoudou.c
yacc -d tp3-Roudoudou.y
conflits: 4 décalage/réduction
gcc -Wall -Wno-unused-function -Wextra -pedantic -std=gnu99 -O3 -lgc -c y.tab.c
lex tp3-Roudoudou.l
gcc -Wall -Wno-unused-function -Wextra -pedantic -std=gnu99 -O3 -lgc -c lex.yy.c
gcc -Wall -Wno-unused-function -Wextra -pedantic -std=gnu99 -O3 -lgc main.c utils.o tp2-Roudoudou.o y.tab.o lex.yy.o -o regex:w
$ ./regex
>> a+b.c
add(symbol('a'),cat(symbol('b'),symbol('c')))
>>

2. Grammaire

Tokens

Les tokens (càd les mots) sont définis dans le fichier tp3-roudoudou.l. Comme les nom PLUS, STAR, etc. sont déjà utilisé par le type regex, j'ai utilisé les noms

• rePLUS pour l'addition ("+"),
• reSTAR pour l'étoile ("*"),
• reZERO pour l'expression vide ("0"),
• reONE pour le mot vide ("1"),
• reDOT pour la concaténation (".").
• reSYMB pour un symbole.

Les autres tokens définis sont :

• END pour la fin du fichier,
• NL pour un saut de ligne,
• LPAR et RPAR pour les parenthèses, ouvrantes et fermantes.

Règles de grammaire

Le fichier Yacc tp3-Roudoudou.y contient la grammaire utilisée. La règle initiale est spécifiée avec

%start commandes

"%start" est un mot clé Yacc, et commandes est le symbole non-terminal de la grammaire par lequel on commence.

La fonction (appelée yyparse) essaiera donc de repérer des chaines dans le langage des commandes.

Les grammaires sont données dans une syntaxe à la BNF, mais avec des actions possibles, données entre accolades. Pour les commandes, on commence avec la grammaire

commandes:
        END                 { printf("\n"); exit(0); }
    |   commande commandes

Autrement dit, une commande est soit :

• le token END (qui est généré à la fin du fichier), auquel cas l'action affiche simplement un saut de ligne et quitte le programme,
• une commande (au singulier), suivie d'autres commandes (au pluriel). Dans ce cas, aucune action n'est donnée. (Il y aura par contre des actions associées aux règles de la grammaire commande.)

Le symbole non-terminal commande est défini par la grammaire

commande:
        NL                  { printf(">> ");  }
     |  expr NL             { print_C_regex($1);
                              printf("\n");
                              printf(">> "); }

Une commande est générée par

• le token NL ("new line") seul, auquel cas on affiche simplement un nouveau prompt,
• une expression (nouveau symbole non-terminal de la grammaire) suivie d'un token NL. Dans ce cas, l'action est un peu plus complexe :
  1. on appelle la fonction print_C_regex,
  2. on passe à la ligne,
  3. on affiche le nouveau prompt.
  Le point important est l'argument de la fonction print_C_regex: "$1" est remplacé par la valeur obtenue par le symbole non-terminal expr de la règle. Ce symbole est le premier de la règle et s'appelle donc "1". Le deuxième s'appellerait "$2", etc.
  Il faut donc que les symboles non-terminaux puissent avoir une valeur ! Le type des valeurs associées au symbole non-terminal expr est donné par la ligne

  %type <regex> expr
  

Les symboles non-terminaux commandes et commande n'avaient pas de valeur. Le symbole non-terminal expr en a. La valeur associée à une règle est donnée en définissant la "variable" "$$". Ainsi, la règle

expr:
     ...
     |   expr rePLUS expr    { $$ = plus($1, $3); }
     ...

signifie qu'une expression peut être générée par :

• une expression (dont la valeur sera dénoté par "$1")
• le token rePLUS
• une expression (dont la valeur sera dénoté par "$3")

L'expression résultat sera obtenu en calculant le résultat de la fonction plus appliquée aux deux expressions $1 et $3.

>> a+b.c*
syntax error

3. Associativité, priorités ...

Il y a deux manières de lire a+b+c:

• add(symbol('a'),add(symbol('b'),symbol('c')))
• add(add(symbol('a'),symbol('b')),symbol('c'))

La grammaire donnée est donc ambigue. Yacc le détecte car il affiche un message conflits: 4 décalage/réduction lors de la compilation.

Il est possible de préciser laquelle des deux possibilités on souhaite utiliser en déclarant le token rePLUS (correspondant au symbole "+") avec

%left rePLUS

ou

%right rePLUS

dans le fichier tp3-Roudoudou.y, par exemple après les déclarations des tokens

%token reZero ...
%token ...

%right rePLUS reDOT

%left rePLUS reDOT

%left rePLUS
%left reDOT

4. Synomymes

5. Nouvelles commandes

$ ./regex
>> (a.b.c)* / "ab"
c(abc)*

$ ./regex
>> "abc" IN a.b*.c
TRUE
>> "abc" IN c.b*.a
FALSE

6. Concaténation implicite

Comme la concaténation implicite ne correspond a aucun token, on ne peut pas déclarer de priorité ! Il va donc falloir désambiguer la grammaire à la main.

expr:
    ...
  | ...
  | ...

term:
    ...
  | ...
  | ...

atom:
    ...
  | ...
  | ...

$ ./regex
>> a+bc
a + bc
>> ab+c
ab + c
>> abc*
abc*
>> a.b*c+d
ab*c + d
>> (ab + c)*d+e
(ab + c)*d + e

7. Pour finir (Bonus)