Exercice 17 : TD/TP Bison

En utilisant la grammaire récursive à gauche non ambiguë, écrire un source bison qui produise et affiche l’arbre abstrait associé à une expression régulière (sans utiliser flex).

Structure d'un fichier Bison

La structure est semblable à celle de Flex

• En-tête et définitions
  • prédéclaration qui sera inclus au début
  • Définition, options
• Grammaire :
  • règles et code associé
• post-code C comme en flex

En-tête et définitions

%{    /*========== Section : Definitions =============*/
#include <stdio.h>
extern int yylex(); // si issu de flex
int yylex(); // si `yylex()` est défini plus loin
int yyerror (char const *message); // à définir
%}

Bison suppose :

• l'existence d'une fonction int yylex() pour la lecture des tokens (écrite à la main ou fournie par Flex),
• la définition d'une fonction int yyerror(char const *) pour les messages d'erreurs,

Valeurs sémantiques, terminaux, non terminaux

• ⚠️ convention : terminaux en majuscule et non terminaux en minuscules, contrairement à ce qu'on fait pour les grammaires ...

Les symboles terminaux ou non ont en général une valeur sémantique déclarée en fin de partie 1.

• type de la valeur sémantique des jetons : YYSTYPE
  • par défaut : intx
• Si type unique (pas fréquent)
  • #define YYSTYPE double
• Si plusieurs types (fréquent), les types possibles sont définis via un %union
  • %union { int typeint; double typedouble; }
• les terminaux sont définis par des directives %token avec leur type (par exemple typeint ou typedouble)
• les non-terminaux sont indiqués par %type
• Le type par défaut d'un non terminal est int

Les symboles Non-Terminaux n'ont pas besoin d'être déclarés (sauf si on veut associer une valeur sémantique).

/* Typage des valeurs de symboles term. ou non-term */
%union {  
  type1  nom1;  
  type2  nom2; 
}
%token<nom1> TOK1 TOK2
%token<nom2> TOK3
%type<nom2> var1
%type var2

Règles de grammaire

%%   /*========== Section : Regles de grammaire ==========*/
var1 :   /* mot vide ! */        {$$=0;}
     | TOK1 var2  TOK2 '\n'      { /* Action */ }
     | var2 TOK3 var1 '+' TOK4   { $$ = fonct($2,$3,$5); }
     | error TOK6                { yyerrok; }
;
var2 : TOK7 var1 TOK6    { /* ... */}

• le caractère : sépare les parties droites et gauches d'une règle de grammaire.
• pour des règles successives avec la même partie gauche, on peut laisser vide la partie gauche et utiliser le caractère | pour démarrer la partie droite.
• le caractère ; termine un bloc de règle avec la même partie gauche.
• Dans un bloc action d'une règle Bison, la lecture de la valeur se fait avec $i qui identifie la valeur du symbole en position "i" dans la partie droite de la règle (commence à $1).
• error est un token fourni par bison et yyerrok signale que l'erreur a été traitée.

Code utilisateur

%%   /*========== Section : Code utilisateur =============*/
int main(void) { return yyparse(); }

Rappel

Pour rappel, la grammaire non ambiguë et récursive à gauche obtenue à l'exercice précédent était :

• S -> S'|'E | E
• E -> ET|T
• T -> T* | F
• F -> (S) | a | .. | z | @ | 0

Les tokens seront :

• SYMBOLE pour a | .. | z | @ | 0
• l'entier correspondant au code ASCII pour les autres caractères (tokens que nous laisserons anonymes donc non déclarés).
• le type des non-terminaux sera des arbres binaires

%{
#include <stdio.h>
#include <stdlib.h>
#include "arbin.h"
void yyerror(char*);
int yylex();
%}
%union { /* YYSTYPE */
// TODO
}
// TODO : déclaration des tokens et des non terminaux
%%
ligne : error '\n' {yyerrok; exit(0);}
      | s '\n' {ab_afficher($1); exit(0);}
      ;
// TODO les règles !
%%
int yylex(){
    int i=getchar();
    if ((i>='a' && i<='z')||i=='@'||i=='0'){
        yylval.typeInt=i;
        return SYMBOLE;
    }
    else return i;
}
void yyerror(char *s) {
    fprintf(stderr,"ERREUR : %s\n",s);
}
int main(){
    return yyparse();
}

En prenant le source bison suivant (attention, à la concaténation qui est implicite !) La compilation bison avertit : "4 conflits par décalage/réduction" ! Examinez le fichier y.output afin de résoudre ce problème !

%token SYMBOLE
%left '|'
%left CONCAT
%left '*'
%%
expr :  '(' expr ')'    {$$ = $2;}
    | expr expr  %prec CONCAT { $$=ab_construire('.',$1,$2);}
    | expr '|' expr   {$$= ab_construire('|',$1,$3);}
    | expr '*' {$$= ab_construire('*',$1,ab_creer());}
    | SYMBOLE {$$=ab_construire(yylval.i, ab_creer(), ab_creer());}
;

Bison avertit 4 conflits par décalage/réduction

bison q2.y
q2.y: conflicts: 4 shift/reduce

Pour comprendre ce qu'il se passe, lancer la commande suivante :

bison q2.y -r itemset

Cela génère un fichier q2.outputavec la description de l'automate des items et les règles appliquées (décalage ou réduction).

Regardez attentivement les états 8 et 10. Dans ces deux états, bison a le choix entre décalage et réduction. Par défaut, bison choisit toujours le décalage.

bison q2.y -g //génère q2.gv
dot -Tpdf q2.gv -o q2.pdf

Les sources du conflit sont donc dans l'état 8 :

State 8

    1 expr: • '(' expr ')'
    2     | • expr expr
    2     | expr • expr
    2     | expr expr •
    3     | • expr '|' expr
    3     | expr • '|' expr
    4     | • expr '*'
    4     | expr • '*'
    5     | • SYMBOLE

    SYMBOLE  shift, and go to state 1
    '*'      shift, and go to state 7
    '('      shift, and go to state 2

    SYMBOLE   [reduce using rule 2 (expr)]
    '('       [reduce using rule 2 (expr)]
    $default  reduce using rule 2 (expr)

    expr  go to state 8

State 10

    1 expr: • '(' expr ')'
    2     | • expr expr
    2     | expr • expr
    3     | • expr '|' expr
    3     | expr • '|' expr
    3     | expr '|' expr •
    4     | • expr '*'
    4     | expr • '*'
    5     | • SYMBOLE

    SYMBOLE  shift, and go to state 1
    '*'      shift, and go to state 7
    '('      shift, and go to state 2

    SYMBOLE   [reduce using rule 3 (expr)]
    '('       [reduce using rule 3 (expr)]
    $default  reduce using rule 3 (expr)

    expr  go to state 8

bison q2.y -r cex

ajoute en plus des exemples provoquant les conflits. Expliquer ce qu'il se passe sur

• aa(a)
• aaa
• a|a(a)
• a|aa

Dans le cas de aa(a) ou aaa, arrivé à l'état 8, il est possible, après avoir lu aa :

• soit de faire un reduce de expr expr •
• soit de faire un shift de • '(' expr ')' dans le cas de aa(a)
• soit de faire un shift de • SYMBOLE dans le cas de aaa.

Par défaut, bison choisit le shift. Pour respecter les priorités des opérateurs, il faut lui imposer de faire un reduce.

%left '|'  // Opérateur le moins prioritaire
%left CONCAT
%left '*' // Opérateur le plus prioritaire

Il faut donc modifier pour inclure les concaténations implicites de SYMBOLE et '(' :

%left '|'  // Opérateur le moins prioritaire
%left CONCAT '(' SYMBOLE
%left '*' // Opérateur le plus prioritaire

Dans le cas de a|aa ou a|a(a), arrivé à l'état 10, il est possible, après avoir lu a|a :

• soit de faire un reduce de expr '|' expr •
• soit de faire un shift de • '(' expr ')' dans le cas de aa(a)
• soit de faire un shift de • SYMBOLE dans le cas de aaa.

Pour respecter les priorités, il faut ici choisir le shift, parce que la concaténation est prioritaire sur le '|'. La modification précédente résout le conflit.