.. title: Bison et Flex: exemple simple d'analyse syntaxique
   :name: bison-et-flex-exemple-simple-danalyse-syntaxique

`Retour à la page Systèmes <../systeme.html>`__

-  `Motivation <#motivation>`__
-  `Exemple: mini-calculette <#exemple>`__
-  `Pour aller plus loin <#plus>`__

.. _motivation:

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 <http://flex.sourceforge.net/>`__ et
`Bison <http://www.gnu.org/software/bison/>`__.

.. _exemple:

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 ...

.. _calculette.y:

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.

.. code:: text

    %{
    #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.

.. _calc_flex.l:

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 ...``

.. code:: text

    %{
    #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.

.. _ensemble:

Tout mettre ensemble
--------------------

Exemple en environnement Linux:

.. code:: text

    $ 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``:

.. code:: text

    3*4-(7-3)

Place au test:

.. code:: text

    $ ./calculette < valid.txt 
    Resultat: 8

.. _plus:

Pour aller plus loin
--------------------

-  `Exemple brut <http://fhoerni.free.fr/comp/bison_flex.html>`__ pour
   m'inspirer
-  Pour plus de détails `exemple plus
   évolué <http://aquamentus.com/flex_bison.html>`__
-  Exemple `Petit
   interpréteur <http://memphis.compilertools.net/interpreter.html>`__
   (utilise Memphis pour après Lex et Yacc)