1. L'outil Bison:

Afin de réaliser un analyseur syntaxique il faut décrire d'abord l'outil à construire dans un texte, ce texte fourni à l’outil Bison permet d'obtenir ensuite un analyseur syntaxique en langage C qui a pour nom « y.tab.c. »Une fois obtenu cet analyseur il faut le compiler et l'on a alors un exécutable qui effectue l'analyse syntaxique suivant les instructions données dans le fichier Bison dont l'extension est « .y ». Ce fonctionnement peut être schématisé par la figure suivante:

2. Format du fichier de règles Bison:

Le fichier de règles pour Bison est similaire dans sa structure et sa syntaxe à celui de Flex. La différence majeure étant bien entendu que Bison attend une grammaire.

1. La première partie du fichier contient les en-têtes, les macros et les autres déclarations C nécessitant d’être définies avant le code de l’analyseur syntaxique. On y trouve également les déclarations des symboles terminaux de la grammaire (tokens).

2. La seconde partie du fichier décrit la grammaire dans un formalisme proche du BNF.La syntaxe est la suivante :<nom de la variable> : <règle de dérivation 1>

| <règle de dérivation 2>| ...

On regroupe les règles de dérivation partageant la même partie gauche à l’aide du caractère | .

3. Finalement, la dernière partie contient le code principal du parseur grammatical ainsi quedes définitions de procédures si nécessaire.Généralement la forme d’un fichier Bison est donnée comme suite :1 %{2 Ici les déclarations en C3 %}4 % t o k e n <énumération> <des> <symboles> <terminaux>5 %%6 Description de l a grammaire7 %%8 Définition des procédures et du code principal

3. Exemple de fichier Bison :

Nous allons tenter de réaliser un analyseur grammatical qui reconnaît la simple grammaire :S a b c | a b c S.

Le code ci-dessous décrit un tel analyseur grammatical sous la forme d’un fichier de règleDestiné à Bison.Ce qui nous donne le fichier suivant :

1 %{2 # include <stdio.h>3 typedef char* string ; /* les tokens sont des chaînes* /4 # define YYSTYPE string /* le ty pe de la variable de retour de Bison /5 %}6 %token NEED NUMB THING7 %%8 file : record file9 | r e c o r d10 ;11 record : NEED NUMB THING { printf ( ” Tu as besoin de %s %s \n ” , $2 , $3 ) ; }12 ;13 %%14 int yyerror ( char* msg ) {15 printf ( ” Error : %s encountered \n ” , msg );16 }1718 int main ( )19 {20 printf ( ”Taper CTRL+D pour stopper\n” ) ;21 yyparse( ) ;22 return 0 ;23 }

Mini manuel d’utilisation de l’outil Bison

Description syntaxique

Analyseur syntaxique

Description lexicale

Analyseur lexical

Identificateurs des non-terminaux

Analyseur Exécutable

Biso

nony.tab.c

Lex.yy.c

Flex

Fichier.y

Fichier.l

y.tab.h Compilateur C

1. La première partie définit le type string, type utilisé pour les tokens (symboles terminaux)au sein de Bison.Ce type est également celui de la variable yyval au sein du fichier de Lex. On y définit ensuite les symboles terminaux NEED, NUMB et THING.

2. La seconde partie décrit la grammaire et les actions à effectuer lors de l’application des règles de dérivation.

3. La dernière partie permet finalement de définir la fonction principale d’exécution qui lance l’analyseur grammatical.La définition de la fonction yyerror() est nécessaire car elle permet de gérer les éventuelles erreurs d’analyse.

4. Passerelle entre Flex et Bison :

La passerelle entre Flex et Bison se réalise en plusieurs étapes :

– inclusion de l’en-tête généré par Bison au sein du fichier Flex ;

– passage des valeurs reconnues par le biais d’une variable yylval

– retour en fin d’action du nom du token correspondant à l’expression reconnue dans Bison

Ce qui nous donne pour le fichier de règles destiné à Flex :

1 %{2 # include ”essai.tab.h ”3 # include <stdio.h>4 # include <string.h>5 extern YYSTYPE yylval;6 %}7 chars [A-Za-z ]8 numbers ( [0-9]+)9 whitespace ( [ ˆA-Za-z0-9\-]+)10 mot {chars}+11 %%12 ” Il faut ” {yylval = (YYSTYPE) strdup ( yytext ) ; return NEED; }13 {numbers } { yylval = (YYSTYPE) strdup ( yytext ) ; return NUMB; }14 {mot} {yylval = (YYSTYPE) strdup (yytext) ; return THING; }15 {mot}”-”{mot} { yylval = (YYSTYPE) strdup ( yytext ) ; return THING; }16 { whitespace} {}17 %%18 int yywrap ( ) {19 return 1 ;20 }

5. Compilation et tests :

La compilation d’un couple de fichiers Flex et Bison est un peu plus délicate à cause du croisement des dépendances. Cependant cela reste assez simple puisqu’il suffit, dans notre cas, de compiler les deux sources simultanément, Le compilateur C ayant l’intelligence de gérerces dépendances tout seul !Ce qui revient à exécuter les commandes suivantes :

#flex essai.l# bison -d essai.y# cc essai.tab.c lex.yy.c -o essai

Testons maintenant notre tout nouvel analyseur grammatical avec quelques phrases simples :

# ./essai

Taper CTRL+D pour stopper Il faut 1 voitureTu as besoin de 1 voitureIl faut 2 canardsTu as besoin de 2 canards