Ce mémento résume les fonctionnalités essentielles de Bison et du couplage Flex et Bison et les illustre avec des exemples ou des liens vers les exercices adéquats. On se reportera aux pages du manuel, pour des informations plus complètes.
Un exemple couvrant l'ensemble des éléments que l'on utilisera par la suite :
---- ExoBison/memento1.bison
%{ /*========== Section : Definitions =============*/
#include <stdio.h>
extern int yylex();
int yyerror (char const *message) {
fputs (message, stderr); fputc ('\n', stderr); return 0;
}
%}
%error-verbose /* message d'erreur plus complet */
%start var2 /* Definition de l'axiome (defaut=1ere regles) */
%token TOK1 TOK2 '\n' '+' /* Declaration des symboles terminaux (cf. partie 2)*/
/* Typage des valeurs de symboles term. ou non-term, (cf. partie 4) */
%union { type1 selecteur1; type2 selecteur2; }
%token <selecteur1> TOK3
%type <selecteur2> var1
/* Declaration de tokens avec priorité et associativité ( cf. partie 5) */
%left <selecteur2> TOK4
%right TOK6
%nonassoc TOK7
%% /*========== Section : Regles de grammaire ==========*/
var1 : /* mot vide ! */ {$$=0;}
| TOK1 var2 TOK2 '\n' { /* Action */ }
| var2 TOK3 var1 '+' TOK4 { $$ = fonct($2,$3,$5); /* cf. partie 4 */ }
| error TOK6 { yyerrok; /* cf partie 3 */ }
;
var2 : TOK7 var1 TOK6 { /* ... */}
%% /*========== Section : Code utilisateur =============*/
int main(void) { return yyparse(); }
Éléments de syntaxe :
int yylex() pour la lecture des tokens (écrite à la main ou fournie par Flex),
int yyerror(char const *) pour l'impression des messages d'erreurs,
main() pour l'analyseur.
yyerror() et main(), peuvent éventuellement être fournies par la librairie bison (gcc -ly), mais l'on préférera l'écriture explicite dans les spécifications.
cf. aussi l'annexe A des slides du cours
Les différents Tokens (symboles Terminaux) gérés par bison sont identifiés par des valeurs entières :
int yylex().
int yylex().
> bison -d -o foo.c spec.bison" produit le code de la fonction yyparse() dans "foo.c" et la définition des tokens dans "foo.h"
Exemple de fichier ".h" produit avec la spécification précédente :
/*--- memento1.h généré par bison -d ----*/
...
#define TOK1 258
#define TOK2 259
#define TOK3 260
#define TOK4 261
#define TOK6 262
#define TOK7 263
#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
typedef union YYSTYPE {
type1 selecteur1;
type2 selecteur2;
} YYSTYPE;
# define YYSTYPE_IS_DECLARED 1
#endif
extern YYSTYPE yylval;
Exemple d'utilisation dans une spécification Flex :
---memento1.flex---
%{
#include "memento1.h"
}%
%%
expr1 {return(TOK1);}
expr2 {return(TOK2);}
expr3 {return('+');}
. {return(yytext[0]);
%%
On renvoie aux exercices ExoLexParse pour plus de détails, et en particulier sur l'utilisation d'un Makefile générique.
Cette partie est traitée spécifiquement dans l'exercice ExoLexParse/Utilisation Combinée de Flex et Bison (partie 3.4)
Les éléments de Bison concernés sont :
cf. aussi l'annexe A des slides du cours
Conformément aux principes de l'analyse lexicale, Flex et Bison permettent d'associer une valeur sémantique à un Token (symbole Terminal). Cette valeur est inutile pour l'analyse syntaxique proprement dite mais sera ensuite nécessaire au niveau de l'analyse sémantique ou des traitements ultérieurs.
---Exemple d'analyse lexicale :
Unité lexicale { Identifiant de Catégorie , valeur dans la catégorie )
"234" { Token ENTIER, valeur entière 234}
"+" { Token OP_PLUS, nil}
"number" { Token IDENT, pointeur dans une table de symbole }
"{1,2}" { Token INT_SET, valeur typée à définir}
Bison permet aussi d'associer une valeur aux Variables de la grammaire (symboles Non-Terminaux). Ceci permet par exemple :
Pour les valeurs typées associées aux Tokens (symboles Terminaux) :
Le partage entre Bison et l'analyseur lexical se réalise ainsi :
%union {
type1 selecteur1;
type2 selecteur2;
}
#if ! defined YYSTYPE
typedef union YYSTYPE {
type1 selecteur1;
type2 selecteur2;
} YYSTYPE;
#endif
extern YYSTYPE yylval;
%token <selecteur1> TOK3 %left <selecteur2> TOK4
yylval.selecteur1=Valeur_de_Type1; return(TOK3);
Symb : Symb1 TOK3 Symb2 Symb3 TOK4 .... { printf( "TOK3 vaut %s, TOK4 vaut %s", $2,$5);}
yylex(), stock cette valeur dans la pile au coté du Token
à chaque opération "shift", et rend accessible ces valeurs sous forme d'un tableau "$1 $2 ...$n" à chaque opération "reduce" sur n symboles.
Pour les valeurs typées associées aux Variables (symboles Non-Terminaux) :
---- ExoBison/baseN.bison
%{
#include <stdio.h>
extern int yylex();
int yyerror (char const *msg) { return 0;}
#define N 10
%}
%union { int entier; char car; }
%token <car> CHIF
%type <entier> var
%%
Axiome : var '\n' {printf("Val=%d\n",$1);}
var : /* vide */ {$$=0;}
| var CHIF {$$ = N * $1 + ($2-'0');}
%%
int main(void) { return yyparse(); }
---- ExoBison/baseN.flex
%option nounput noinput
%{
#include "yyparse.h"
%}
%%
[0-9] {yylval.car=yytext[0];
return(CHIF);}
.|\n return(yytext[0]);
%%
int yywrap (void) {return 1;}
Avertissement : Les explications qui suivent utilisent les termes de l'analyse syntaxique ascendante LR pratiquée par Bison. Vous pouvez dans un premier temps ignorer ces éléments, en remplaçant "conflit" par "ambiguïté", "shift" par "dérivation ou évaluation droite", "reduce" par "dérivation ou évaluation gauche".
Imposer qu'une grammaire soit non ambiguë, ou sans conflit dans une résolution LR est parfois impossible, souvent très contraignant, et généralement complexifie énormément l'écriture de la grammaire.
Une solution est d'accepter certaines ambiguïtés dans la grammaire et de rajouter des règles de résolution de conflit externes à la définition des grammaires algébriques.
Bison permet ainsi de définir des règles de Priorité et d'Associativité sur des tokens qui permettront de résoudre des conflits de type shift/reduce. L'utilisation la plus directe correspond à ce que l'on appelle des grammaires d'opérateurs ou aussi à un usage pratiqué depuis longtemps par les mathématiciens.
Prenons l'exemple générique, d'une grammaire d'expressions à base d'opérateurs binaires :
%%
expr : expr OP1 expr
| expr OP2 expr
| /* .... */
| ATOM
;
%%
Il y a ambiguïté si l'on analyse par exemple ATOM OP1 ATOM OP2 ATOM qui peut produire
deux arbres de syntaxe abstraite :
Dérivation : Gauche , Droite
OP2 OP1
/ \ / \
OP1 ATOM ATOM OP2
/ \ / \
ATOM ATOM ATOM ATOM
La même ambiguïté existe aussi pour l'expression ATOM OP1 ATOM OP1 ATOM.
Dans une résolution LR, le conflit se produit donc dans la position ATOM OP1 ATOM . OP2 où l'on a le choix :
De façon générale, les règles de priorité/associativité s'appliquent quand on rencontre un conflit shift/reduce avec une opération shift qui empile un token OP2 et un reduce qui "mange" un token OP1.
La priorité est définie par l'ordre des déclarations des tokens dans des directives %letf, %right ou %nonassoc :
NB: Des tokens déclarés dans une directive %token n'ont aucune priorité et aucune associativité.
%letf OP1 OP2 // OP1 et OP2 meme priorite %right OP3 // OP3 prioritaire sur OP1 et OP2 %left OP4 // OP4 prioritaire sur OP1,OP2,OP3
5+2+4 == (5+2)+4 == 5+(2+4) %right '+' ou %left '+' 5-2-4 == (5-2)-4 != 5-(2-4) %left '-' idem pour '*' et '/' en C : A=B=5 == A=(B=5) %right '=' 5+2*4 == 5+(2*4) != (5+2)*4 '*' prioritaire sur '+' 5-2+4 == (5-2)+4 != 5-(2+4) même priorité '-' et '+', %left '-' '+' -3^2 == 9 ou -9 ? '^' prioritaire sur '-' unaire semblerait le bon usage
Cf. exercice ExoBison/"Calculatrice Arithmétique" pour la mise en oeuvre.
On y trouvera quelques commentaires sur la "bonne" priorité des opérateurs usuels
On y trouvera aussi l'utilisation de priorités spécifiques avec la directive %prec.
Quelques codes éventuellement utiles pour la construction d'analyseurs syntaxiques sont fournies : Tools Page.
En particulier, on pourra trouver des implémentations basiques pour la gestion d'Arbres de Syntaxe Abstraite et de Tables de symboles. La mise en oeuvre dans ces 2 cas est illustrée dans les exercices "ExoBison/calculette*"
Le debuging et la résolution de conflit dans le cas d'une Analyse Syntaxique LR n'est que partiellement abordé dans ce cours.
Bison dispose de fonctionnalités de traçage (YYDEBUG, option --debug,..) qui permettent à l'exécution de l'analyseur de tracer chaque appel à yylex(), chaque Shift et chaque Reduce ainsi que l'état de la pile. L'utilisation de ces informations nécessite une bonne compréhension de l'analyse LR et de l'automate construit automatiquement par Bison.
Bison fournit d'autre part l'accès à l'automate LR généré à partir d'une spécification. Ceci s'obtient avec les options "--report", "--report=state" ou "--verbose" de la commande Bison. Ceci produit un fichier "xxx.output" contenant une description textuelle de l'automate à pile d'analyse LR. Suivant les versions, il existe aussi des possibilités de générer une version graphique de l'automate.
Le format détaillé du fichier ".output" est changeant avec les versions de bison ou avec la langue utilisée. On notera que :
$accept, et $end sont des symboles conventionnels pour identifier le début et la fin de fichier. Pour un axiome START, bison produit une règle conventionnelle R0 "$accept : START $end"
$end (EOF), ou $default (ANY token)
Une première utilisation de l'accès à l'automate Bison est illustrée dans l'exercice "3.3 Suppression de conflits" des Exercices de Grammaire ExoGram
Pour plus de détails, Cf. slides du cours sur la définition d'automates LR(0) ou cf. Manuel de Bison.