4. Un exemple : un mini interprète d'expressions

Cet interprète d'expressions est capable de calculer la valeur de n'importe quelle expression mathématique exprimée à l'aide de nombres réels et des opérateurs "+", "-" (considéré en tant qu'opérateur unaire et binaire, ce qui signifie que "5-3" et "-2" seront des expressions valides), "*", "/", "^" (opérateur puissance). Cet interprète ne pourra pas faire appel à des fonctions ni à des variables.

4.1. Le source Lex du mini-interprète d'expressions

Voici tout d'abord le source complet :

%{

#include "global.h"
#include "calc.h"

#include <stdlib.h>

%}

blancs          [ \t]+

chiffre         [0-9]
entier          {chiffre}+
exposant        [eE][+-]?{entier}

reel            {entier}("."{entier})?{exposant}?

%%

{blancs}        { /* On ignore */ }

{reel}          {
                  yylval=atof(yytext);
                  return(NOMBRE);
                }

"+"           return(PLUS);
"-"           return(MOINS);

"*"           return(FOIS);
"/"           return(DIVISE);

"^"           return(PUISSANCE);

"("           return(PARENTHESE_GAUCHE);
")"           return(PARENTHESE_DROITE);

"\n"  return(FIN);

Explication de texte :

4.2. Le source Yacc du mini-interprète d'expressions

C'est le plus important, et le plus intéressant. Le voici :

%{

#include "global.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

%}

%token  NOMBRE
%token  PLUS    MOINS   FOIS    DIVISE  PUISSANCE
%token  PARENTHESE_GAUCHE       PARENTHESE_DROITE
%token  FIN

%left   PLUS    MOINS
%left   FOIS    DIVISE
%left   NEG
%right  PUISSANCE

%start Input
%%

Input:
          /* Vide */
        | Input Ligne
        ;

Ligne:
          FIN
        | Expression FIN                { printf("Résultat : %f\n",$1); }
        ;

Expression:
          NOMBRE                        { $$=$1; }
        | Expression PLUS Expression    { $$=$1+$3; }
        | Expression MOINS Expression   { $$=$1-$3; }
        | Expression FOIS Expression    { $$=$1*$3; }
        | Expression DIVISE Expression  { $$=$1/$3; }
        | MOINS Expression %prec NEG    { $$=-$2; }
        | Expression PUISSANCE Expression       { $$=pow($1,$3); }
        | PARENTHESE_GAUCHE Expression PARENTHESE_DROITE        { $$=$2; }
        ;

%%

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

int main(void) {
  yyparse();
}

Bon, un peu plus compliqué n'est-ce pas ? En fait, pas tant que ça. Après avoir inclus les fichiers habituels, tu utilises la directive %token pour déclarer les terminaux pouvant être rencontrés. Il n'y a, dans ce cas, aucun ordre à respecter.

Ensuite, ça se complique avec les directives %left et %right. Celle-ci servent à donner l'associativité des opérateurs, ainsi que leur précédences. On définit donc les opérateurs par ordre croissant de priorité. Ainsi 1+2*3 est evalué comme 1+(2*3). D'autre part, le fait que l'on choisisse "left" ou "right" dépend du comportement que tu voudras donner à ton opérateur. Pour un opérateur (ici, "+") associatif à gauche, a+b+c sera évalué comme (a+b)+c. Inversement, pour l'associativité à droite, a^b^c est évalué comme a^(b^c). C'est pas si compliqué, hein ?

On signale ensuite à Yacc que l'axiome de départ sera Input, c'est-à-dire qu'il se place au départ dans un état tel que toute entrée sera considérée comme un Input. A ce sujet, note la récursion dans la définition de Input. Cela permet de traiter une entrée de taille inconnue. Pour des raisons internes à Yacc, il est préférable d'utiliser

Input:
       /* Vide */
     | Input Ligne
     ;

plutôt que :

Input:
       /* Vide */
     | Ligne Input
     ;

(Cela permet une réduction dès que c'est possible).

Passons à la définition de Ligne. Si la définition seule ne pose pas de problème, peut-être es-tu intrigué par le $1 ? C'est simple, $1 fait référence à la valeur renvoyée par la première notion de la production. De la même façon pour $2, $3,... Par contre, $$ est la valeur renvoyé par la production. Ainsi, dans la définition d' Expression, lorsqu'on rencontre Expression "+" Expression on fait l'action $$=$1+$3, qui ne fait qu'ajouter...

Dans un autre ordre d'idée, regarde la ligne définissant le moins unaire. Le %prec sert juste à indiquer que la priorité de ceci est celle de NEG.

Enfin, la troisième partie du fichier est banale, puisqu'elle se contente d'appeler yyparse().

4.3. Comment faire marcher cet exemple...

Si le fichier Lex s'appelle calc.lex et le fichier Yacc calc.y, il suffit de faire la procédure suivante :

bison -d calc.y
mv calc.tab.h calc.h
mv calc.tab.c calc.y.c
flex calc.lex
mv lex.yy.c calc.lex.c
gcc -c calc.lex.c -o calc.lex.o
gcc -c calc.y.c -o calc.y.o
gcc -o calc calc.lex.o calc.y.o -ll -lm [éventuellement -lfl]

Note bien que tu devras créer le fichier global.h pour que cela compile. Ce fichier contiendra :

#define YYSTYPE double
extern YYSTYPE yylval;

Je dispose uniquement de bison et de flex, au lieu de lex et de yacc, mais cela devrait fonctionner de la même façon, à part le nom des fichiers générés.

L'appel à bison (le Yacc de GNU) avec l'option "-d" crée le fichier calc.tab.h pour définir les terminaux. On appelle flex (le Lex de GNU) et on donne des noms un peu plus convenables pour le tout. Il suffit alors de compiler, sans oublier de linker avec la librairie mathématique ("-lm") et la librairie spéciale Lex ("-ll"). On obtient :

$ calc
 1+2*3
 Résultat : 7.000000
 2.5*(3.2-4.1^2)
 Résultat : -34.025000

4.4. Une amélioration possible...

Afin de permettre le rattrapage d'erreurs syntaxiques, et pour ne pas voir le programme s'arrêter sur un "parse error", on peut remplacer

Ligne:
          FIN
        | Expression FIN                { printf("Résultat : %f\n",$1); }
        ;

par

Ligne:
          FIN
        | Expression FIN                { printf("Résultat : %f\n",$1); }
        | error FIN                     { yyerrok; }
        ;

mais ce n'est qu'une possibilité parmi d'autres (utilisation et définition de variables et de fonctions, plusieurs types de données, ...).