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
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];
Plutôt que d'utiliser quatre types de pointeurs différents, on a choisi d'utiliser des indices entiers. La définition typedef int Expression vise uniquement à améliorer la lisibilité du programme : la modification de cette définition implique des modifications substantielles dans le code.
On construit une somme ou un produit dans une expression temporaire, rangée à l'extrémité droite du tableau des cellules ; on simplifie cette expression temporaire, puis on la compare avec les expressions existantes (fonction egalite) : si elle existe déjà, la fonction position retourne son indice, sinon elle alloue la place nécessaire, recopie l'expression temporaire, et retourne l'indice de la nouvelle expression.
La fonction egalite n'est utilisée que pour comparer une nouvelle expression avec les expressions existantes ; dans le reste du programme, la comparaison de deux expressions se réduit à la comparaison de leurs indices.
Il faut prendre deux précautions :
Le produit temporaire ainsi obtenu est ensuite simplifié (et n'est plus un produit s'il reste moins de deux facteurs).
%{ 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 (); }
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