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 :

1. La première partie du fichier permet d'inclure le fichier calc.h, qui sera généré plus tard par Yacc et qui contiendra la définition des identificateurs NOMBRE, PLUS, MOINS, etc... On en profite au passage pour inclure la librairie stdlib, qui contient l'en-tête de la fonction atof(), utilisée par la suite. On déclare la notion "réel" qui sera utilisée plus bas. On peut aussi signaler que les structures manipulées seront du type double, par une directive #define YYSTYPE double, faite dans le fichier global.h. D'ailleurs, yylval est du type YYSTYPE.
2. La deuxième partie sert à signaler à l'analyseur syntaxique quel terminal a été rencontré. S'il s'agit d'un NOMBRE, alors il faut stocker sa valeur dans la variable yylval, afin qu'elle puisse être utilisée ultérieurement.
3. Enfin, la troisième partie n'existe pas, puisqu'on ne veut pas que Lex mette un main() dans le texte source créé. Le main() sera fait dans la partie sur Yacc.

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("Resultat : %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
    ;

Input:
                  /* Vide */
                | Ligne Input
                ;

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 [eventuellement -lfl]

Veuillez noter que vous devez 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
 Resultat : 7.000000
 2.5*(3.2-4.1^2)
 Resultat : -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("Resultat : %f\n",$1); }
  ;

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