INFO502 : théorie des langages

TP4 : parser des expressions régulière à la Kleene, en C

Hivers / printemps 2017

• Consignes

• Liens utiles

• 1. Préliminaires

• 2. Grammaire

  • Tokens

  • Règles de grammaire

• 3. Associativité, priorités ...

• 4. Synomymes

• 5. Nouvelles commandes

• 6. Concaténation implicite

• 7. Pour finir (Bonus)

Consignes

Le rendu de TP se fera uniquement à travers l'interface web TPLab. Vous devrez fournir une unique archive .tar contenant les deux fichiers tp4-Roudoudou.l et tp4-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 : info502-tp4.tar

• le sujet du TP 3 (lien)

• encadrant de TP : Pierre.Hyvernat@univ-smb.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 tp3-Roudoudou.c
yacc -d tp4-Roudoudou.y
conflits: 4 décalage/réduction
gcc -Wall -Wno-unused-function -Wextra -pedantic -std=gnu99 -O3 -lgc -c y.tab.c
lex tp4-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 tp3-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 tp4-roudoudou.l. Comme les noms PLUS, STAR, etc. sont déjà utilisés 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 tp4-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. On commence avec la grammaire toplevel (ceci est indiqué dans le fichier par la ligne %start toplevel):

toplevel:
        END                 { printf("\n"); exit(0); }
    |   line toplevel

Autrement dit, le toplevel accepte 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 ligne (définie par la grammaire line) suivie du toplevel. Dans ce cas, aucune action n'est donnée. Il y aura par contre des actions associées aux règles de la grammaire line.)

Les lines sont simplement des commandes (cmd) suivies d'un retour chariot (token NL, pour "newline"), et les commandes sont générées par la grammaire:

cmd:
                            { printf("?"); }
    |   expr                { print_C_regex($1); }

Autrement dit, une commande est soit :

• vide, auquel cas on affiche simplement un point d'interrogation,

• une expression (expr est un nouveau symbole non-terminal de la grammaire). Dans ce cas, l'action est :

  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 toplevel et line 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
add(symbol('a'),cat(symbol('b'),symbol('c')))

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

Remarques sur la page (ou le sujet) : contact.
mentions légales

,

Dernière révision: le 23-10-2017 à 14:24.