Expressions simplifiées

Dépendances

Voici le fichier Makefile (avec les règles et les macros prédéfinies standard):
CC = gcc
LEX = flex
YACC = bison

ymaple: ymaple.c maplelex.c
	$(CC) -o $@ $@.c -ly -ll

ymaple.c: ymaple.y
	$(YACC) -o $@ $<

maplelex.c: maplelex.l

Analyseur lexical

Fichier maplelex.l :
signe		[\+\-]?
point		[\.]
chiffre		[0-9]
lettre		[a-zA-Z]
entier		{chiffre}+
decimales	({point}{chiffre}*)
mantisse	({entier}{decimales}?|{point}{entier})
exposant	(E{signe}{entier})
reel		{mantisse}{exposant}?
ident		{lettre}({lettre}|{chiffre})*

%%

{ident}		{yylval = expr_variable (yytext); return ID; }
{entier}	{yylval = expr_entiere (atoi (yytext) ); return NUM; }
{reel}		{yylval = expr_reelle (atof (yytext) ); return NUM; }
[ \t]+		;
.|\n		return yytext[0];

Analyseur syntaxique

Fichier ymaple.y :
%{
  typedef int Expression;
  
  /* pour l'analyseur lexical */
  Expression expr_variable (char *nom);
  Expression expr_entiere (int x);
  Expression expr_reelle (double x);

  /* pour l'analyseur syntaxique */
  Expression affectation (Expression gauche, Expression droite);
  Expression somme (Expression gauche, Expression droite);
  Expression difference (Expression gauche, Expression droite);
  Expression produit (Expression gauche, Expression droite);
  Expression quotient (Expression gauche, Expression droite);
  Expression oppose (Expression n);
  Expression puissance (Expression gauche, Expression droite);
  void afficher (Expression n);
%}

%token ID INT DOUBLE

%%
axiome	: axiome expr '\n'	{afficher ($2); printf ("\n"); }
	| axiome '\n'
	| axiome error '\n'
	| /* vide */
	;
	
expr	: ID '=' expr		{$$ = affectation ($1, $3); }
	| expr '+' terme	{$$ = somme ($1, $3); }
	| expr '-' terme	{$$ = difference ($1, $3); }
	| terme
	;
	
terme	: terme '*' facteur	{$$ = produit ($1, $3); }
	| terme '/' facteur	{$$ = quotient ($1, $3); }
	| facteur
	;
	
facteur	: '(' expr ')'		{$$ = $2; }
	| '-' facteur		{$$ = oppose ($2); }
	| facteur '^' INT	{$$ = puissance ($1, $3); }
	| facteur '^' '-' INT	{$$ = puissance ($1, oppose ($4)); }
	| ID
	| INT
	| DOUBLE
	;
%%


/* Types d'expressions */

#define VARIABLE 1
#define ENTIER 10
#define REEL 11
#define SOMME 20
#define PRODUIT 21

#include 
#include "maplelex.c"

#define EMAX 4096
#define IDMAX 1024
#define NMAX 256
#define TMAX 128

typedef struct {
  char type;
  short taille;
} EnTete;

typedef union {
  EnTete tete;
  Expression expr;
} Cellule;

static Expression
  explibre = 0,
  Zero, Un, MoinsUn;

static int
  entlibre = 0,
  reelibre = 0,
  varlibre = 0;

static int entier [NMAX];
static double reel [NMAX];
static char variable [IDMAX];
static Cellule cellule [EMAX + TMAX];

char type (Expression n) {
  return cellule[n].tete.type;
}

int taille (Expression n) {
  return cellule[n].tete.taille;
}

int numerique (Expression n) {
  char t = type (n);
  return (t == ENTIER || t == REEL);
}

/* Gère brutalement les débordements */

void debordement (char *s) {
  printf ("Débordement de la table %s\n", s);
  exit (1);
}

/* Réserve la mémoire pour une expression, et écrit son en-tête */

Expression allouer (int type, int taille) {
  Expression e = explibre;
  
  explibre = e + taille;
  if (explibre >= EMAX)
    debordement ("des expressions");
  cellule[e].tete.type = type;
  cellule[e].tete.taille = taille;
  return e;
}

/*
  Idem pour une expression temporaire.
  Le bloc de mémoire correspondant est géré explicitement,
  en indiquant sa base, et sa taille maximale (voir ajout).
  Le décalage de 2 permet l'insertion d'un nombre en tête.
*/

Expression temporaire (int type, int taille, int base, int max) {
  Expression e = EMAX + base + 2;
  
  if (base + max + 2 >= TMAX)
    debordement ("des expressions temporaires");
  cellule[e].tete.type = type;
  cellule[e].tete.taille = taille;
  return e;
}

/* Copie une expression (destination temporaire) */

void copier (Expression destination, Expression source) {
  int i, p = taille (source);
  
  cellule[destination].tete = cellule[source].tete;
  for (i = 1; i < p; i++)
    cellule[destination + i].expr = cellule[source + i].expr;
}

/*
  Enregistre le nom d'une nouvelle variable,
  et retourne l'indice correspondant dans la table des variables
*/

int allouer_variable (char *nom) {
  int i = varlibre;
    
  varlibre = varlibre + strlen (nom) + 1;
  if (varlibre >= IDMAX)
    debordement ("des variables");
  strcpy (variable + i, nom);
  return i;
}

/* Retourne une expression de type VARIABLE */

Expression expr_variable (char *nom) {
  Expression i;
    
  for (i = 0; i < explibre; i = i + taille (i))
    if (type (i) == VARIABLE &&
        strcmp (nom, variable + cellule[i + 1].expr) == 0)
      return i;
  
  /* nouvelle variable */
  
  i = allouer (VARIABLE, 3);
  cellule[i + 1].expr = allouer_variable (nom);
  cellule[i + 2].expr = -1;	/* pas d'affectation */
  return i;
}

Expression affectation (Expression id, Expression n) {
  cellule[id + 2].expr = n;
  return id;
}

/*
  Enregistre un nouvel entier,
  et retourne l'indice correspondant dans la table des entiers
*/

int allouer_entier (int n) {
  int i = entlibre;
  
  if (++entlibre >= IDMAX)
    debordement ("des entiers");
  entier[i] = n;
  return i;
}

/* Idem pour un réel */

int allouer_reel (double x) {
  int i = reelibre;
  
  if (++reelibre >= IDMAX)
    debordement ("des réels");
  reel[i] = x;
  return i;
}

/* Retourne une expression de type ENTIER */

Expression expr_entiere (int x) {
  Expression i;
  
  for (i = 0; i < explibre; i = i + taille (i))
    if (type (i) == ENTIER && entier [ cellule[i + 1].expr ] == x)
      return i;
  
  /* nouvel entier */
  
  i = allouer (ENTIER, 2);
  cellule[i + 1].expr = allouer_entier (x);
  return i;
}

/* Idem pour une expression de type REEL */

Expression expr_reelle (double x) {
  Expression i;
  
  for (i = 0; i < explibre; i = i + taille (i))
    if (type (i) == REEL && reel [ cellule[i + 1].expr ] == x)
      return i;
  
  /* nouveau réel */
  
  i = allouer (REEL, 2);
  cellule[i + 1].expr = allouer_reel (x);
  return i;
}

/*
  Teste l'égalité de deux expressions.
  Bug : n'utilise pas la commutativité de la somme et du produit.
  Pour une réparation efficace, utiliser un condensé :
  somme des cellules qui composent l'expression.
*/

int egalite (Expression i, Expression j) {
  int k, p = taille (i);
  
  if (type (i) != type (j) || p != taille (j) )
    return 0;  
  for (k = 1; k < p; k++)
    if (cellule[i + k].expr != cellule[j + k].expr)
      return 0;
  return 1;
}

/* Retourne la position définitive d'une expression temporaire */

Expression position (Expression n) {
  Expression i;
  int j, p, q = taille (n);
  char t = type (n);
  
  for (i = 0; i < explibre; i = i + p) {
    p = taille (i);
    if (egalite (i, n) )
      return i;
  }
  
  /* enregistrer la nouvelle expression */
  
  i = allouer (t, q);
  for (j = 1; j < q; j++)
    cellule[i + j].expr = cellule[n + j].expr;
  return i;
}

/* Calcule la somme de deux expressions numériques */

Expression somme_numerique (Expression gauche, Expression droite) {
  char
    tg = type (gauche), td = type (droite);
  Expression
    g = cellule[gauche + 1].expr,
    d = cellule[droite + 1].expr;

  if (tg == ENTIER)
    if (td == ENTIER)
      return expr_entiere (entier[g] + entier[d]);
    else
      return expr_reelle (entier[g] + reel[d]);
  if (tg == REEL)
    if (td == ENTIER)
      return expr_reelle (reel[g] + entier[d]);
    else
      return expr_reelle (reel[g] + reel[d]);
}

/*
  Idem pour le produit.
  Fusionner cette fonction et la précédente,
  en passant l'opérateur en paramètre,
  serait excessivement compliqué, à cause du typage.
*/

Expression produit_numerique (Expression gauche, Expression droite) {
  char
    tg = type (gauche), td = type (droite);
  Expression
    g = cellule[gauche + 1].expr,
    d = cellule[droite + 1].expr;

  if (tg == ENTIER)
    if (td == ENTIER)
      return expr_entiere (entier[g] * entier[d]);
    else
      return expr_reelle (entier[g] * reel[d]);
  if (tg == REEL)
    if (td == ENTIER)
      return expr_reelle (reel[g] * entier[d]);
    else
      return expr_reelle (reel[g] * reel[d]);
}

/*
  Supprime les termes nuls, ou dont le coefficient est nul,
  dans une somme temporaire.
*/

Expression somme_simplifiee (Expression n) {
  int i, j, p = taille (n);
  Expression terme, coeff;
  
  for (i = j = 1; i < p; i = i + 2)
    if (cellule[n + i].expr == Zero || cellule[n + i + 1].expr == Zero)
      cellule[n].tete.taille -= 2;
    else {
      cellule[n + j].expr = cellule[n + i].expr;
      cellule[n + j + 1].expr = cellule[n + i + 1].expr;
      j = j + 2;
    }
  
  /* Est-ce une vraie somme ? */
  
  switch (taille (n)) {
    case 1:
      return Zero;
    
    case 3:
      terme = cellule[n + 1].expr;
      coeff = cellule[n + 2].expr;
      if (coeff == Un)
        return terme;
      else
        return produit (coeff, terme);
    
    default:
      return position (n);
  }
}

/* Idem pour un produit temporaire */

Expression produit_simplifie (Expression n) {
  int i, j, p = taille (n);
  Expression facteur, exposant;
  
  for (i = j = 1; i < p; i = i + 2)
    if (cellule[n + i].expr == Un || cellule[n + i + 1].expr == Zero)
      cellule[n].tete.taille -= 2;
    else {
      cellule[n + j].expr = cellule[n + i].expr;
      cellule[n + j + 1].expr = cellule[n + i + 1].expr;
      j = j + 2;
    }
  
  /* Est-ce un vrai produit ? */
  
  switch (taille (n)) {
    case 1:
      return Un;
    
    case 3:
      facteur = cellule[n + 1].expr;
      exposant = cellule[n + 2].expr;
      if (exposant == Un)
        return facteur;
      /* pas de break */
      
    default:
      return position (n);
  }
}

/*
  Additionne (resp. multiplie) une somme (resp. un produit)
  temporaire avec une expression numérique x.
  Si tmp commence par une expression numérique,
  on effectue l'opération; sinon on insère x en tête.
  Retourne une expression temporaire.
*/

Expression ajouter_numerique (Expression tmp, Expression x) {
  int p = taille (tmp), t = type (tmp);
  Expression y;
  
  y = cellule[tmp + 1].expr;
  if (numerique (y))
    if (t == SOMME)
      cellule[tmp + 1].expr = somme_numerique (x, y);
    else
      cellule[tmp + 1].expr = produit_numerique (x, y);
  else {
    /* placer x en tête */
    tmp = tmp - 2;
    cellule[tmp].tete.type = t;
    cellule[tmp].tete.taille = p + 2;
    cellule[tmp + 1].expr = x;
    cellule[tmp + 2].expr = Un;
  }
  return tmp;
}

/*
  Idem pour ajouter à la liste gauche, temporaire,
  l'expression droite, munie d'un coefficient.
  Si l'expression droite figure déjà dans la liste gauche,
  les coefficients sont additionnés.
*/

void ajouter_expr (Expression gauche, Expression droite, Expression coeff ) {
  int j, p = taille (gauche);
  Expression k, l;
  
  for (j = 1; j < p; j = j + 2) {
    k = cellule[gauche + j].expr;	/* terme ou facteur */
    l = cellule[gauche + j + 1].expr;	/* coefficient ou exposant */
    if (k == droite) {
      cellule[gauche + j + 1].expr = somme_numerique (l, coeff);
      return;
    }
  }
  cellule[gauche].tete.taille += 2;
  cellule[gauche + p].expr = droite;
  cellule[gauche + p + 1].expr = coeff;
}

Expression produit (Expression gauche, Expression droite) {
  int k, p = taille (gauche), q = taille (droite);
  Expression i;
  
  if (gauche == Un)
    return droite;
  if (droite == Un)
    return gauche;
  if (gauche == Zero || droite == Zero)
    return Zero;
  
  if (type(gauche) == PRODUIT) {
    i = temporaire (PRODUIT, p, 0, p + q);
    copier (i, gauche);
  }
  else {
    i = temporaire (PRODUIT, 3, 0, q + 3);
    cellule[i + 1].expr = gauche;
    cellule[i + 2].expr = Un;
  }
  
  switch (type (droite)) {
    case ENTIER:
    case REEL:
      i = ajouter_numerique (i, droite);
      break;
      
    case VARIABLE:
    case SOMME:
      ajouter_expr (i, droite, Un);
      break;
      
    case PRODUIT:
      for (k = 1; k < q; k = k + 2) {
        int facteur = cellule[droite + k].expr;
        int exposant = cellule[droite + k + 1].expr;
        if (numerique (facteur))
          i = ajouter_numerique (i, facteur);
        else
          ajouter_expr (i, facteur, exposant);
      }
      break;
  }
  return produit_simplifie (i);
}

/* L'expression droite est un entier */

Expression puissance (Expression gauche, Expression droite) {
  Expression i = temporaire (PRODUIT, 3, 0, 3);
  
  cellule[i + 1].expr = gauche;
  cellule[i + 2].expr = droite;
  return position (i);
}

Expression inverse (Expression n) {
  Expression i, facteur, exposant;
  int j, p;
  
  switch (type (n)) {
    case ENTIER :
      i = cellule[n + 1].expr;
      return expr_reelle (1 / (double) entier [i]);
      
    case REEL :
      i = cellule[n + 1].expr;
      return expr_reelle (1/reel [i]);
      
    case VARIABLE :
    case SOMME :
      return puissance (n, MoinsUn);

    case PRODUIT :
      p = taille (n);
      i = temporaire (PRODUIT, p, 0, p);
      for (j = 1; j < p; j = j + 2) {
        facteur = cellule[n + j].expr;
        exposant = cellule[n + j + 1].expr;
        if (numerique (facteur)) {
          cellule[i + j].expr = inverse (facteur);
          cellule[i + j + 1].expr = exposant;
        }
        else {
          cellule[i + j].expr = facteur;
          cellule[i + j + 1].expr = oppose (exposant);
        }
      }
      return position (i);
  }
}

Expression quotient (Expression gauche, Expression droite) {
  return produit (gauche, inverse (droite) );
}

/*
  Extrait le facteur numérique (coeff) du produit n;
  après exécution, l'expression temporaire tmp contient
  le produit, débarrassé de coeff.
*/

Expression extraire_coeff (Expression n, Expression tmp) {
  int i, j, p = taille (n);
  Expression facteur, coeff = Un;
  
  for (i = j = 1; i < p; i = i + 2) {
    facteur = cellule[n + i].expr;
    if (numerique (facteur) ) {
      cellule[tmp].tete.taille -= 2;
      coeff = facteur;
    }
    else {
      cellule[tmp + j].expr = facteur;
      cellule[tmp + j + 1].expr = cellule[n + i + 1].expr;
      j = j + 2;
    }
  }    
  return coeff;
}

/* A enchaîner obligatoirement avec la fonction précédente */

Expression extraire_terme (Expression tmp) {
  if (taille (tmp) == 3 && cellule[tmp + 2].expr == Un)
    return cellule[tmp + 1].expr;	/* variable */
  else
    return position (tmp);		/* produit */
}

Expression somme (Expression gauche, Expression droite) {
  int k, p = taille (gauche), q = taille (droite);
  Expression i, j, coeff, terme;
  
  if (gauche == Zero)
    return droite;
  if (droite == Zero)
    return gauche;
  
  switch (type(gauche)) {
    case ENTIER:
    case REEL:
    case VARIABLE:
      i = temporaire (SOMME, 3, 0, q + 3);
      cellule[i + 1].expr = gauche;
      cellule[i + 2].expr = Un;
      break;
      
    case PRODUIT:
      i = temporaire (PRODUIT, p, 0, p);
      coeff = extraire_coeff (gauche, i);
      terme = extraire_terme (i);
      i = temporaire (SOMME, 3, 0, q + 3);
      cellule[i + 1].expr = terme;
      cellule[i + 2].expr = coeff;
      break;
  
    case SOMME:
      i = temporaire (SOMME, p, 0, p + q);
      copier (i, gauche);
      break;
  }
  
  switch (type (droite)) {
    case ENTIER:
    case REEL:
      i = ajouter_numerique (i, droite);
      break;
      
    case VARIABLE:
      ajouter_expr (i, droite, Un);
      break;
      
    case PRODUIT:
      j = temporaire (PRODUIT, q, p + q + 1, q);
      coeff = extraire_coeff (droite, j);
      terme = extraire_terme (j);
      ajouter_expr (i, terme, coeff);
      break;

    case SOMME:
      for (k = 1; k < q; k = k + 2) {
        terme = cellule[droite + k].expr;
        coeff = cellule[droite + k + 1].expr;
        if (numerique (terme))
          i = ajouter_numerique (i, terme);
        else
          ajouter_expr (i, terme, coeff);
      }
      break;
  }
  return somme_simplifiee (i);
}

Expression oppose (Expression n) {
  int j, p;
  Expression i, terme, coeff;
  
  switch (type (n)) {
    case ENTIER :
      i = cellule[n + 1].expr;
      return expr_entiere (-entier [i]);
      
    case REEL :
      i = cellule[n + 1].expr;
      return expr_reelle (-reel [i]);
      
    case VARIABLE :
    case PRODUIT :
      return produit (MoinsUn, n);

    case SOMME :
      p = taille (n);
      i = temporaire (SOMME, p, 0, p);
      for (j = 1; j < p; j = j + 2) {
        terme = cellule[n + j].expr;
        coeff = cellule[n + j + 1].expr;
        if (numerique (terme)) {
          cellule[i + j].expr = oppose (terme);
          cellule[i + j + 1].expr = coeff;
        }
        else {
          cellule[i + j].expr = terme;
          cellule[i + j + 1].expr = oppose (coeff);
        }
      }
      return position (i);
  }
}

Expression difference (Expression gauche, Expression droite) {
  return somme (gauche, oppose (droite) );
}

void afficher (Expression n) {
  Expression i, coeff, terme, exposant, facteur;
  int j, p;
  
  switch (type (n)) {
    case ENTIER :
      i = cellule[n + 1].expr;
      printf (" %d", entier[i], n);
      break;
    case REEL :
      i = cellule[n + 1].expr;
      printf (" %g", reel[i], n);
      break;
    case VARIABLE :
      i = cellule[n + 1].expr;
      printf (" %s", variable + i, n);
      i = cellule[n + 2].expr;
      if (i >=0) {
        printf (" =>");
        afficher (i);
        printf (" <=");
      }
      break;
    case SOMME :
      p = taille (n);
      for (j = 1; j < p; j = j + 2) {
        coeff = cellule[n + j + 1].expr;
        if (coeff != Un) {
          afficher (coeff);
          printf (" *");
        }
        terme = cellule[n + j].expr;
        printf (" [");
        afficher (terme);
        printf (" ]");
        if (j < p - 2)
          printf (" +");
      }
      break;
    case PRODUIT :
      p = taille (n);
      for (j = 1; j < p; j = j + 2) {
        facteur = cellule[n + j].expr;
        printf (" <");
        afficher (facteur);
        printf (" >");
        exposant = cellule[n + j + 1].expr;
        if (exposant != Un) {
          printf (" ^");
          afficher (exposant);
        }
        if (j < p - 2)
          printf (" *");
      }
      break;
  }
}

main () {
  Zero = expr_entiere (0);
  Un = expr_entiere (1);
  MoinsUn = expr_entiere (-1);
  yyparse ();
}

Jeu d'essais

Les lignes ont été numérotées pour permettre les commentaires suivants :
verlaine% ymaple
alpha * beta + alpha
(1) [ < alpha > * < beta > ] + [ alpha ]
 
5 * alpha * 2 + alpha - 3 * x^2
(2) 11 * [ alpha ] + -3 * [ < x > ^ 2 ]

alpha * 3.14 - alpha
(3) < 2.14 > * < alpha >

x*y*z*5 - 3*(2*x + 5*y)*z
(4) 5 * [ < x > * < y > * < z > ] + -3 * [ < 2 * [ x ] + 5 * [ y ] > * < z > ]

x*y*2 + 3*x*y
(5) < 5 > * < x > * < y >

a + 2*x*y + 5 + b - 3*x*y -3
(6) [ 2 ] + [ a ] + -1 * [ < x > * < y > ] + [ b ]

a + 2*x*y + b - 2*x*y
(7) [ a ] + [ b ]

a * (b + c)^3 * a^3 * (b+c)^-3
(8) < a > ^ 4

x*x*2*x*5 + x*y*3 - 4*x*x*x
(9) 6 * [ < x > ^ 3 ] + 3 * [ < x > * < y > ]

x*y - x*y
(10) 0

x*y - y*x
(11) [ < x > * < y > ] + -1 * [ < y > * < x > ]

x * y * (1/x) * (1/y)
(12) 1