TP 2 : Analyse syntaxique avec Bison
Démonstration en direct

Un fichier bison contient la représentation d'une grammaire hors contexte, composée de règles. Il n'y a pas de convention établie, mais en général les non-terminaux sont en minuscules et les terminaux en majuscules.

Prenons l'exemple de la grammaire de l'exercice 1 du TD 3 :

S -> S(S)
S -> ε

Pour cette grammaire, on peut écrire dans un fichier ExTD3.y :

%token OPAR FPAR

%start phrase

%%

phrase : phrase OPAR phrase FPAR
       | %empty
       ;

%%

La déclaration %start est optionnelle (par défaut c'est la partie gauche de la première règle). Le mot %empty est aussi optionnel. On peut tout simplement ne rien écrire à la place.

Ici l'ordre, ou le fait d'utiliser une ou plusieurs lignes %token est sans importance (mais pas en général).

On peut d'ores et déjà compiler ce fichier, avec

bison ExTD3.y

ce qui produit un fichier ExTD3.tab.c. Ce fichier contient une fonction yyparse() qui réalise l'analyse syntaxique de l'entrée.

Il est possible d'obtenir diverses informations de Bison avec diverses options. Par exemple,

bison -v ExTD3.y

produit un fichier ExTD3.output qui détaille l'automate LALR, avec tous les états et les transitions. En particulier, ce fichier détaille les éventuels conflits.

head -n 32 ExTD3.output

L'appel alternatif

bison --report=all ExTD3.y

produit le même fichier, avec encore plus de détails.

head -n 34 ExTD3.output # extraire les 34 premières lignes

D'autre part, l'option --graph permet de produire une représentation graphique de l'automate dans un fichier au format Graphviz (gv).

bison --report=all --graph ExTD3.y

Le fichier ExTD3.gv produit à ce stade peut être transformé en SVG (ou PDF, …) à l'aide de la commande dot du logiciel Graphviz.

dot -Tsvg ExTD3.gv > ExTD3.svg

Ceci permet de visualiser un automate complet, avec états, items et symboles prévisionnels, etc. Ici aucun état n'a besoin d'un symbole prévisionnel.

Puisque le fichier contient des déclarations (%token ou autres) pour tous les symboles terminaux, Bison peut produire un fichier d'en-tête déclarant des constantes pour les différentes unités lexicales. L'option -d sert à cela :

bison -d ExTD3.y

produit un fichier ExTD3.tab.h que vous pouvez consulter. Les différentes constantes associées aux symboles terminaux sont définies comme membre d'un type énuméré (enum yytokentype) :

head -n 60 ExTD3.tab.h | tail -n 12 # extraire les lignes 48 à 60

Donc, si l'on veut écrire un analyseur lexical, on peut inclure ce fichier et utiliser les constantes. Dans notre cas on peut créer le fichier ExTD3.l

%{
#include "ExTD3.tab.h"
%}

%%

"(" { return OPAR; }
")" { return FPAR; }

[[:space:]] { ; }

. { fprintf (stderr, "caractère illégal (%c) ignoré\n", yytext[0]); }

%%

Il faut, comme d'habitude, dans l'analyseur lexical (ExTD3.l) utiliser l'option noyywrap :

%{
#include "ExTD3.tab.h"
%}

%option noyywrap                        

%%

"(" { return OPAR; }
")" { return FPAR; }

[[:space:]] { ; }

. { fprintf (stderr, "caractère illégal (%c) ignoré\n", yytext[0]); }

%%

À ce stade, on peut générer notre analyseur lexical avec Flex.

flex --header-file=ExTD3.lex.h -o ExTD3.lex.c ExTD3.l

Notons que l'option --header-file dit à Flex de produire également un ficher d'en-tête déclarant (parmi d'autres choses) la fonction yylex(). De cette façon, lorsqu'on voudra faire référence à yylex() dans un fichier source, il nous suffira d'y inclure ExTD3.lex.h

#include "ExTD3.lex.h"

au lieu de devoir se souvenir de

extern int yylex();

C'est précisément ce qu'il nous faut pour le fichier ExTD3.tab.c, produit par Bison. En outre, on doit également fournir à Bison une fonction yyerror() appelée lors de la gestion des erreurs de syntaxe (le fichier stdio.h est inclus pour cette raison) :

%{
#include <stdio.h>
#include "ExTD3.lex.h"
void yyerror (const char * msg);
%}

%token OPAR FPAR

%start phrase

%%

phrase : phrase OPAR phrase FPAR
       | %empty
       ;

%%

void yyerror(const char * msg) {
  fprintf(stderr, "Erreur de syntaxe : %s\n", msg);
}

Il faut maintenant écrire un fichier ExTD3.main.c contenant le programme principal, qui appelle la fonction yyparse().

#include <stdio.h>
#include "ExTD3.tab.h"

int main(void) {
  int r = yyparse();
  printf("-> Analyseur lexical retourne : %d\n", r);
  return r;
}

La fonction yyparse() renvoie 0 si elle est parvenue à analyser correctement l'entrée, et 1 sinon.

Notez que c'est la fonction yyparse() qui appelle yylex() quand elle a besoin de la prochaine unité lexicale.

On peut produire un exécutable en compilant chacun des fichiers C. Dans notre exemple, la séquence complète serait :

bison -d ExTD3.y
flex --header-file=ExTD3.lex.h -o ExTD3.lex.c ExTD3.l
gcc -c ExTD3.tab.c
gcc -c ExTD3.lex.c
gcc -c ExTD3.main.c
gcc ExTD3.tab.o ExTD3.lex.o ExTD3.main.o -o ExTD3.bin

Il est largement temps de créer un makefile.

all: obj
        gcc -o ExTD3.bin ExTD3.lex.o ExTD3.tab.o ExTD3.main.o

obj: ExTD3.main.c lex
        gcc -c ExTD3.lex.c
        gcc -c ExTD3.tab.c
        gcc -c $<

lex: ExTD3.l syntax
        flex --header-file=ExTD3.lex.h -o ExTD3.lex.c $<

syntax: ExTD3.y
        bison -d $<

clean:
        rm -f ExTD3.lex.c ExTD3.tab.c ExTD3.bin *.o

On peut tester sur l'entrée standard, par exemple avec

make clean > /dev/null
make > /dev/null
echo "( () () )" | ./ExTD3.bin

Nous pouvons généraliser le makefile ci-dessus pour l'ensemble des exercices du TP comme suit. Pour cela, on introduit la variable PREFIX au tout début du fichier. Par défaut, on l'initialise à exo1 ce qui veut dire que le makefile s'attend à trouver au moins :

1. un fichier Bison appelé exo1.y,
2. un fichier Lex appelé exo1.l,
3. un fichier C appelé exo1.main.c contenant une implémentation de la fonction main.

Dans un premier temps, make appelle bison sur exo1.y et produit exo1.tab.c et exo1.tab.h. Puis, flex est appelé pour produire exo1.lex.c et exo1.lex.h à partir de exo1.l. Ensuite, les fichiers exo1.lex.c, exo1.tab.c et exo1.main.c sont compilés avec GCC en fichiers .o correspondants. À la fin, GCC produit un unique exécutable appelé exo1.bin.

PREFIX=exo1

all: obj
        gcc -o $(PREFIX).bin $(PREFIX).lex.o $(PREFIX).tab.o $(PREFIX).main.o

obj: $(PREFIX).main.c lex
        gcc -c $(PREFIX).lex.c
        gcc -c $(PREFIX).tab.c
        gcc -c $<

lex: $(PREFIX).l syntax
        flex --header-file=$(PREFIX).lex.h -o $(PREFIX).lex.c $<

syntax: $(PREFIX).y
        bison -d $<

clean:
        rm -f $(PREFIX).lex.c $(PREFIX).tab.c $(PREFIX).bin $(PREFIX).*.o

Pour compiler les fichiers sources relatifs à un autre exercice, comme par exemple l'exercice 2, il suffit de donner une autre définition à PREFIX lors de chaque appel à make. En supposant que nos fichiers relatifs à l'exercice 2 sont préfixé par exo2, on pourra appeler make avec

make PREFIX=exo2 clean
make PREFIX=exo2

sans avoir besoin de faire des copies de notre makefile ou de créer des répertoire séparés pour chaque exercice du TP.

Il est possible d'écrire les terminaux composés d'un seul caractère littéralement dans le fichier ExTD3.y. Les déclarations %token deviennent optionnelles (mais inoffensives).

%{
#include <stdio.h>
#include "ExTD3.lex.h"
void yyerror (const char * msg);
%}

%start phrase

%%

phrase : phrase '(' phrase ')'
       | %empty
       ;

%%

void yyerror(const char * msg) {
  fprintf(stderr, "Erreur de syntaxe : %s\n", msg);
}

Bien sûr, le fichier ExTD3.tab.h ne définit pas de constante pour ces types d'unités lexicales. L'analyseur lexical doit simplement renvoyer le caractère lui-même.

%{
#include "ExTD3.tab.h"
%}

%option noyywrap                        

%%

"(" { return '('; }
")" { return ')'; }

[[:space:]] { ; }

. { fprintf (stderr, "caractère illégal (%c) ignoré\n", yytext[0]); }

%%

On peut bien sûr regrouper toutes ces unités lexicales mono-caractère

%{
#include "ExTD3.tab.h"
%}

%option noyywrap                        

%%

[()] { return yytext[0]; }

[[:space:]] { ; }

. { fprintf (stderr, "caractère illégal (%c) ignoré\n", yytext[0]); }

%%

Le fichier ExTD3.y peut définir une action à exécuter lorsqu'une règle est reconnue, c'est-à-dire lorsque l'algorithme d'analyse effectue une réduction sur sa pile. L'action est du code C arbitraire, placé entre accolades (comme dans les actions de l'analyseur lexical).

%{
#include <stdio.h>
#include "ExTD3.lex.h"
void yyerror (const char * msg);
%}

%start phrase

%%

phrase : phrase '(' phrase ')' { printf("S(S)\n"); }
       | %empty { printf("epsilon\n"); }
       ;

%%

void yyerror(const char * msg) {
  fprintf(stderr, "Erreur de syntaxe : %s\n", msg);
}

Le code est recopié dans le fichier ExTD3.tab.c. Les éventuelles erreurs dans les actions ne seront détectées que lors de la compilation de ce dernier fichier.

make clean > /dev/null
make > /dev/null
echo "( () () )" | ./ExTD3.bin

Pour déboguer un analyseur produit par Bison il y a deux étapes. Il faut d'abord appeler ce dernier avec l'option -t (t pour trace).

bison -d -t ExTD3.y

Il faut ensuite affecter la valeur 1 à la variable globale yydebug avant l'appel à yyparse() dans le programme principal.

#include <stdio.h>
#include "ExTD3.tab.h"

int main(void) {
  yydebug = 1;
  int r = yyparse();
  printf("-> Analyseur lexical retourne : %d\n", r);
  return r;
}

On peut aussi changer la valeur de la variable yydebug dans une action de l'analyseur, ou avec un debugger, etc.

bison -d -t ExTD3.y
flex --header-file=ExTD3.lex.h -o ExTD3.lex.c ExTD3.l
gcc -c ExTD3.tab.c
gcc -c ExTD3.lex.c
gcc -c ExTD3.main.debug.c
gcc ExTD3.tab.o ExTD3.lex.o ExTD3.main.debug.o -o ExTD3.debug.bin
echo "( () () )" | ./ExTD3.debug.bin 2>&1 | head -n 10

Pendant l'analyse, chaque symbole (terminal ou non) a une valeur. Lors de la réduction par une règle, les symboles de la partie droite ont des valeurs notées $1, $2 etc. La valeur d'un symbole est fixée au moment où il est créé

• pour un symbole non terminal : l'action associée à la règle peut affecter une valeur à $$, qui devient la valeur du symbole dans la partie gauche de la règle
• pour un symbole terminal : c'est l'analyseur lexical qui doit fixer sa valeur ; il utilise pour cela la variable spéciale yylval

Le type de valeur d'un symbole est YYSTYPE. Par défaut, celui-ci est initialisé à un entier, i.e. int.

head -n 70 ExTD3.tab.h | tail -n 8 # extraire les lignes 62 à 70

Cependant, on peut changer ce type avec YYSTYPE ou avec %union. Il y a d'autres façons de changer la valeur : lire le manuel.

Commençons par calculer des valeurs uniquement pour les symboles non terminaux. On veut calculer la profondeur maximale d'une expression parenthésée. On peut écrire ce calcul dans les règles directement :

%{
#include <stdio.h>
#include "ExTD3.lex.h"
void yyerror (const char * msg);
%}

%start phrase

%%

phrase : phrase '(' phrase ')' {
           if($1 > $3) {
             $$ = $1;
           } else {
             $$ = $3 + 1;
           }
           printf("S(S) = %d\n", $$);
         }
       | %empty {
           $$ = 0;
           printf("epsilon = %d\n", $$);
         }
       ;

%%

void yyerror(const char * msg) {
  fprintf(stderr, "Erreur de syntaxe : %s\n", msg);
}

Le résultat obtenu pour ( () () ) en entrée est le suivant.

make clean > /dev/null
make > /dev/null
echo "( () () )" | ./ExTD3.bin

Supposons maintenant que l'on ajoute une règle autorisant des nombres entiers (parmi les parenthèses), et que la profondeur d'un nombre soit égale à ce nombre. On ajoute dans ExTD3.y

%{
#include <stdio.h>
#include "ExTD3.lex.h"
void yyerror (const char * msg);
%}

%token NUM

%start phrase

%%

phrase : phrase '(' phrase ')' {
           if($1 > $3) {
             $$ = $1;
           } else {
             $$ = $3 + 1;
           }
           printf("S(S) = %d\n", $$);
         }
       | %empty {
           $$ = 0;
           printf("epsilon = %d\n", $$);
         }
       | NUM {
           $$ = $1;
           printf("NUM = %d\n", $$);
         }
       ;

%%

void yyerror(const char * msg) {
  fprintf(stderr, "Erreur de syntaxe : %s\n", msg);
}

Ici la valeur $1 est celle du symbole terminal NUM. Cette valeur doit être fixée par l'analyseur lexical. Il utilise pour cela la variable globale yylval. Dans ExTD3.l on écrit

%{
#include "ExTD3.tab.h"
%}

%option noyywrap                        

%%

[()] { return yytext[0]; }

[0-9]+ { yylval = atoi(yytext); return NUM; }

[[:space:]] { ; }

. { fprintf (stderr, "caractère illégal (%c) ignoré\n", yytext[0]); }

%%

Le résultat obtenu pour ( () (5) ) en entrée est le suivant.

make clean > /dev/null
make > /dev/null
echo "( () (5) )" | ./ExTD3.bin

Retrouvez le code source de cette page dans le dépôt Git sur https://gitlab.inria.fr/lectures-mfelsoci/demos-compilation.