Bison et Flex: exemple simple d'analyse syntaxique

Retour à la page Systèmes

Motivation

Ce mini-tutorial s'adresse à ceux qui connaissent déjà les principes de l'analyse lexicale et syntaxique, et qui ont simplement besoin d'un résumé des commandes élémentaires pour les mettre en œuvre avec Flex et Bison.

Exemple: mini-calculette

Le travail se décompose typiquement comme suit:

  • décrire la grammaire et les actions de l'analyseur syntaxique dans un fichier calculette.y.
  • décrire la grammaire et les actions de l'analyseur lexical dans un fichier calc_flex.l

Ensuite tout est automatique:

  • Bison produit un fichier calculette.c (et un fichier calculette.h) à partir de calculette.y.
  • Flex produit un fichier calc_flex.c à partir de calc_flex.l.
  • On peut compiler et lier les deux fichiers grâce à calculette.h. Ensuite, place aux tests ...

Le fichier calculette.y pour Bison

Les fichiers C produits par bison s'attendent par défaut à ce que l'on ait déclaré quelque-part:

  • Le prototype de yyparse(): c'est l'analyseur syntaxique dont Bison va fournir l'implémentation dans quelques instants...
  • Le prototype de yylex(): Bison s'adressera à cette fonction pour récupérer les symboles de la grammaire. On pourrait l'implémenter, mais on va laisser flex la fournir (voir calc_flex.l plus loin)
  • Le prototype de yyerror(): fonction appelée par Bison en cas de mauvaise nouvelle...
  • Un type de données symbolisé par la constante YYSTYPE, pour stocker les attributs des symboles dans les variables $$, $1, $2, etc. associées aux éléments de chaque règle de production.
%{
#include <stdio.h>
#define YYSTYPE int
int yyparse();
int yylex();
int yyerror(char *s);
%}

//Symboles terminaux qui seront fournis par yylex()
%token ENTIER
%left PLUS
%left MOINS
%left FOIS
%left DIVISE
%token OUVRIR
%token FERMER

%%

Total: Calcul { printf("Resultat: %d\n", $1); }

Calcul: ENTIER | Add | Moins | Fois | Divise | Paren { $$ = $1; }

Paren : OUVRIR Calcul FERMER { $$ = $2; }

Add : Calcul PLUS Calcul { $$ = $1 + $3; }

Moins : Calcul MOINS Calcul { $$ = $1 - $3; }

Fois : Calcul FOIS Calcul { $$ = $1 * $3; }

Divise : Calcul DIVISE Calcul { $$ = $1 / $3; }

%%

int yyerror(char *s) {
    printf("yyerror : %s\n",s);
    return 0;
}

int main(void) {
    yyparse();
    return 0;
}

On remarquera dans la syntaxe du fichier:

  • Les trois sections déclarations / grammaire / code C séparées par %%.
  • Dans la section du haut, la partie %{ ... %} est copiée telle quelle vers le fichier calculette.h.
  • Les symboles terminaux ne sont pas copiés littéralement de la sorte. Ils sont exploités de deux façons:
    • Ils seront reportés dans calculette.h pour que l'analyseur lexical sache signaler les symboles terminaux.
    • Les mots-clefs %left,%right ne concernent que l'analyseur syntaxique, pour résoudre les conflits de priorité shift/reduce.

Le fichier calc_flex.l pour Flex

Entre autres choses que le fichier C produit par Flex s'attend à trouver dans le fichier calculette.h produit par Bison:

  • Le type YYSTYPE pour la variable yylval qu'il remplit à chaque terminal trouvé. Selon les cas, le parseur produit par Bison se chargera de le traduire en $$ $1 $2 ...
  • Les valeurs numériques que Bison a attribuées aux symboles terminaux qu'on lui a indiqués, i.e. ENTIER PLUS MOINS ...
%{
#include "calculette.h"
%}

%option noyywrap

blanks          [ \t\n]+
entier      [0-9]+
plus        \+
moins       \-
fois        \*
divise      \/
ouvrir      \(
fermer      \)

%%

{blanks}        { /* ignore */ }

{entier}    { yylval = atoi(yytext); return(ENTIER); }
{plus}      { return(PLUS); }
{moins}     { return(MOINS); }
{fois}      { return(FOIS); }
{divise}    { return(DIVISE); }
{ouvrir}    { return(OUVRIR); }
{fermer}    { return(FERMER); }

Quelques remarques:

  • L'option noyywrap fournie en début de fichier évite de s'embêter avec la fonction yywrap (seulement utile lorsque l'entrée est répartie sur plusieurs fichiers).
  • La variable yytext contient l'identifiant reconnu.
  • Si aucune expression n'est reconnue par l'analyseur lexical, yylex() renverra juste le code ASCII du prochain caractère lu.

Tout mettre ensemble

Exemple en environnement Linux:

$ bison calculette.y --defines=calculette.h -o calculette.c
$ gcc -c -Wall calculette.c
$ flex -o calc_flex.c calc_flex.l
$ gcc -c -Wall calc_flex.c
$ gcc -Wall calculette.o calc_flex.o -o calculette

Un exemple d'expression à calculer dans un fichier valid.txt:

3*4-(7-3)

Place au test:

$ ./calculette < valid.txt
Resultat: 8

Pour aller plus loin