Annotation of rpl/src/simplification.c, revision 1.69
1.1 bertrand 1: /*
2: ================================================================================
1.68 bertrand 3: RPL/2 (R) version 4.1.32
1.66 bertrand 4: Copyright (C) 1989-2019 Dr. BERTRAND Joël
1.1 bertrand 5:
6: This file is part of RPL/2.
7:
8: RPL/2 is free software; you can redistribute it and/or modify it
9: under the terms of the CeCILL V2 License as published by the french
10: CEA, CNRS and INRIA.
11:
12: RPL/2 is distributed in the hope that it will be useful, but WITHOUT
13: ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14: FITNESS FOR A PARTICULAR PURPOSE. See the CeCILL V2 License
15: for more details.
16:
17: You should have received a copy of the CeCILL License
18: along with RPL/2. If not, write to info@cecill.info.
19: ================================================================================
20: */
21:
22:
1.11 bertrand 23: #include "rpl-conv.h"
1.1 bertrand 24:
25:
26: /*
27: ================================================================================
1.69 ! bertrand 28: Fonction d'affichage d'un arbre q-aire
! 29: ================================================================================
! 30: Entrées : pointeur sur une structure struct_processus
! 31: --------------------------------------------------------------------------------
! 32: Sorties :
! 33: --------------------------------------------------------------------------------
! 34: Effets de bord : néant
! 35: ================================================================================
! 36: */
! 37:
! 38: static void
! 39: affichage_arbre(struct_processus *s_etat_processus, struct_arbre *s_arbre,
! 40: int niveau)
! 41: {
! 42: int i;
! 43:
! 44: integer8 branche;
! 45:
! 46: struct_liste_chainee *l_element_courant;
! 47:
! 48: unsigned char *chaine;
! 49:
! 50: if (niveau == 0)
! 51: {
! 52: printf("Arbre $%016X\n", s_arbre);
! 53: }
! 54:
! 55: // Affichage de la feuille (fonction ou donnée générale s'il n'y
! 56: // a pas de branche)
! 57:
! 58: l_element_courant = (*s_arbre).feuille;
! 59:
! 60: while(l_element_courant != NULL)
! 61: {
! 62: if ((chaine = formateur(s_etat_processus, 0,
! 63: (*l_element_courant).donnee)) == NULL)
! 64: {
! 65: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
! 66: return;
! 67: }
! 68:
! 69: for(i = 0; i < niveau; i++)
! 70: {
! 71: printf(" ");
! 72: }
! 73:
! 74: printf("%s\n", chaine);
! 75: free(chaine);
! 76:
! 77: l_element_courant = (*l_element_courant).suivant;
! 78: }
! 79:
! 80: // Affichage des branches (arguments de la fonction dans la feuille)
! 81:
! 82: for(branche = 0; branche < (*s_arbre).nombre_branches; branche++)
! 83: {
! 84: affichage_arbre(s_etat_processus, (*s_arbre).branches[branche],
! 85: niveau + 1);
! 86: }
! 87:
! 88: if (niveau == 0)
! 89: {
! 90: printf("---\n");
! 91: }
! 92:
! 93: return;
! 94: }
! 95:
! 96:
! 97: /*
! 98: ================================================================================
1.50 bertrand 99: Fonction de transcription d'un arbre en liste chaînée
1.1 bertrand 100: ================================================================================
101: Entrées : pointeur sur une structure struct_processus
102: --------------------------------------------------------------------------------
103: Sorties :
104: --------------------------------------------------------------------------------
105: Effets de bord : néant
106: ================================================================================
107: */
108:
1.50 bertrand 109: static struct_liste_chainee *
110: transcription_arbre(struct_processus *s_etat_processus, struct_arbre *s_arbre)
1.1 bertrand 111: {
1.50 bertrand 112: integer8 i;
1.1 bertrand 113:
114: struct_liste_chainee *l_element_courant;
1.50 bertrand 115: struct_liste_chainee *l_liste;
116: struct_liste_chainee *l_nouvelle_pile_locale;
117: struct_liste_chainee *l_pile_locale;
1.1 bertrand 118:
1.50 bertrand 119: l_pile_locale = NULL;
1.1 bertrand 120:
1.50 bertrand 121: for(i = 0; i < (*s_arbre).nombre_branches; i++)
1.1 bertrand 122: {
1.50 bertrand 123: if ((l_nouvelle_pile_locale = allocation_maillon(s_etat_processus))
124: == NULL)
125: {
126: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
127: return(NULL);
128: }
1.1 bertrand 129:
1.50 bertrand 130: (*l_nouvelle_pile_locale).suivant = l_pile_locale;
131: l_pile_locale = l_nouvelle_pile_locale;
1.1 bertrand 132:
1.50 bertrand 133: if (((*l_pile_locale).donnee = (void *) transcription_arbre(
134: s_etat_processus, (*s_arbre).branches[i])) == NULL)
1.1 bertrand 135: {
1.50 bertrand 136: return(NULL);
1.1 bertrand 137: }
1.50 bertrand 138: }
139:
1.52 bertrand 140: // Ajout des fonctions
1.1 bertrand 141:
1.52 bertrand 142: l_liste = (*s_arbre).feuille;
1.50 bertrand 143:
144: free((*s_arbre).branches);
145: free(s_arbre);
146:
147: // Chaînage des arguments
148:
149: while(l_pile_locale != NULL)
150: {
151: l_element_courant = (void *) (*l_pile_locale).donnee;
152:
153: if (l_element_courant == NULL)
1.1 bertrand 154: {
1.50 bertrand 155: (*s_etat_processus).erreur_systeme = d_es_pile_vide;
1.1 bertrand 156: return(NULL);
157: }
158:
1.50 bertrand 159: while((*l_element_courant).suivant != NULL)
1.1 bertrand 160: {
161: l_element_courant = (*l_element_courant).suivant;
162: }
163:
1.50 bertrand 164: (*l_element_courant).suivant = l_liste;
165: l_liste = (void *) (*l_pile_locale).donnee;
1.1 bertrand 166:
1.50 bertrand 167: l_nouvelle_pile_locale = (*l_pile_locale).suivant;
168: liberation_maillon(s_etat_processus, l_pile_locale);
169: l_pile_locale = l_nouvelle_pile_locale;
1.1 bertrand 170: }
171:
1.50 bertrand 172: return(l_liste);
1.1 bertrand 173: }
174:
175:
176: /*
177: ================================================================================
1.51 bertrand 178: Fonction de simplification d'un arbre
179: ================================================================================
180: Entrées : pointeur sur une structure struct_processus
181: --------------------------------------------------------------------------------
182: Sorties :
183: --------------------------------------------------------------------------------
184: Effets de bord : néant
185: ================================================================================
186: */
187:
188: static void
189: inversion_fonctions_arbre(struct_arbre *s_arbre)
190: {
191: return;
192: }
193:
194:
195: static void
196: simplification_arbre(struct_processus *s_etat_processus,
1.52 bertrand 197: struct_arbre *s_arbre)
1.51 bertrand 198: {
1.52 bertrand 199: integer8 i;
200:
201: if ((*(*(*s_arbre).feuille).donnee).type != FCT)
202: {
203: // L'objet formant le noeud n'est pas une fonction. Il n'y a aucune
204: // simplification possible.
205:
206: return;
207: }
208:
209: if ((strcmp((*((struct_fonction *) (*(*(*s_arbre).feuille).donnee).objet))
210: .nom_fonction, "+") == 0) || (strcmp((*((struct_fonction *)
211: (*(*(*s_arbre).feuille).donnee).objet)).nom_fonction, "-") == 0))
212: {
213: for(i = 0; i < (*s_arbre).nombre_branches; i++)
214: {
215: }
216: }
217: else if ((strcmp((*((struct_fonction *) (*(*(*s_arbre).feuille).donnee)
218: .objet)).nom_fonction, "*") == 0) || (strcmp((*((struct_fonction *)
219: (*(*(*s_arbre).feuille).donnee).objet)).nom_fonction, "/") == 0))
220: {
221: for(i = 0; i < (*s_arbre).nombre_branches; i++)
222: {
223: }
224: }
225:
1.51 bertrand 226: return;
227: }
228:
229:
230: /*
231: ================================================================================
1.50 bertrand 232: Fonction 'simplification' (ne libère pas les paramètres)
1.1 bertrand 233: ================================================================================
1.50 bertrand 234: Entrées : pointeur sur une structure struct_processus
1.1 bertrand 235: --------------------------------------------------------------------------------
236: Sorties :
237: --------------------------------------------------------------------------------
238: Effets de bord : néant
239: ================================================================================
240: */
241:
1.50 bertrand 242: struct_objet *
243: simplification(struct_processus *s_etat_processus, struct_objet *s_objet)
1.1 bertrand 244: {
1.50 bertrand 245: struct_objet *s_objet_simplifie;
246:
247: integer8 i;
248: integer8 nombre_arguments;
249:
250: struct_arbre *s_arbre;
251:
252: struct_liste_chainee *l_element_courant;
253:
254: // Attention : l_liste_locale et l_ancienne_liste_locale ne contiennent pas
255: // un pointeur sur une struct_objet, mais sur une struct_arbre.
1.1 bertrand 256:
1.50 bertrand 257: struct_liste_chainee *l_liste_locale;
258: struct_liste_chainee *l_ancienne_liste_locale;
1.1 bertrand 259:
1.50 bertrand 260: if ((*s_objet).type == ALG)
1.1 bertrand 261: {
1.50 bertrand 262: /*
263: * Transcription de l'expression algébrique en arbre q-aire
264: */
1.1 bertrand 265:
1.50 bertrand 266: l_liste_locale = NULL;
267: l_element_courant = (*s_objet).objet;
1.1 bertrand 268:
1.50 bertrand 269: while(l_element_courant != NULL)
1.1 bertrand 270: {
1.50 bertrand 271: switch((*(*l_element_courant).donnee).type)
272: {
273: // Toutes les fonctions (intrinsèques, extrinsèques et
274: // utilisateurs).
275:
276: case FCT:
277: {
278: // Il s'agit d'un objet de type ALG. Nous pouvons donc
279: // sauter les délimiteurs d'expression.
280:
281: if ((l_element_courant != (*s_objet).objet) &&
282: ((*l_element_courant).suivant != NULL))
283: {
284: nombre_arguments = (*((struct_fonction *)
285: (*(*l_element_courant).donnee).objet))
286: .nombre_arguments;
287:
288: // Si le nombre d'arguments vaut 0, la fonction
289: // apparaît en notation algébrique comme une fonction
290: // infixe.
291:
292: if (nombre_arguments == 0)
293: {
294: nombre_arguments = 2;
295: }
296:
297: if ((s_arbre = malloc(sizeof(struct_arbre))) == NULL)
298: {
299: (*s_etat_processus).erreur_systeme =
300: d_es_allocation_memoire;
301: return(NULL);
302: }
303:
304: (*s_arbre).nombre_branches = nombre_arguments;
1.52 bertrand 305:
306: if (((*s_arbre).feuille = allocation_maillon(
307: s_etat_processus)) == NULL)
308: {
309: (*s_etat_processus).erreur_systeme =
310: d_es_allocation_memoire;
311: return(NULL);
312: }
313:
314: (*(*s_arbre).feuille).donnee = copie_objet(
315: s_etat_processus, (*l_element_courant).donnee,
316: 'P');
317: (*(*s_arbre).feuille).suivant = NULL;
1.50 bertrand 318:
319: if (((*s_arbre).branches = malloc(((size_t) (*s_arbre)
320: .nombre_branches) * sizeof(struct_arbre *)))
321: == NULL)
322: {
323: (*s_etat_processus).erreur_systeme =
324: d_es_allocation_memoire;
325: return(NULL);
326: }
327:
1.51 bertrand 328: for(i = nombre_arguments - 1; i >= 0; i--)
1.50 bertrand 329: {
330: if (l_liste_locale == NULL)
331: {
332: (*s_etat_processus).erreur_execution =
333: d_ex_manque_argument;
334: return(NULL);
335: }
336:
1.51 bertrand 337: (*s_arbre).branches[i] = (struct_arbre *)
1.50 bertrand 338: (*l_liste_locale).donnee;
339:
340: l_ancienne_liste_locale = l_liste_locale;
341: l_liste_locale = (*l_liste_locale).suivant;
342:
343: liberation_maillon(s_etat_processus,
344: l_ancienne_liste_locale);
345: }
346:
347: // Introduction de l'arbre dans la pile locale
348:
349: l_ancienne_liste_locale = l_liste_locale;
350:
351: if ((l_liste_locale = allocation_maillon(
352: s_etat_processus)) == NULL)
353: {
354: (*s_etat_processus).erreur_systeme =
355: d_es_allocation_memoire;
356: return(NULL);
357: }
358:
359: (*l_liste_locale).suivant = l_ancienne_liste_locale;
360: (*l_liste_locale).donnee = (void *) s_arbre;
361: }
1.1 bertrand 362:
1.50 bertrand 363: break;
364: }
1.1 bertrand 365:
1.50 bertrand 366: default:
1.1 bertrand 367: {
1.50 bertrand 368: l_ancienne_liste_locale = l_liste_locale;
369:
370: if ((l_liste_locale = allocation_maillon(s_etat_processus))
371: == NULL)
372: {
373: (*s_etat_processus).erreur_systeme =
374: d_es_allocation_memoire;
375: return(NULL);
376: }
377:
378: (*l_liste_locale).suivant = l_ancienne_liste_locale;
379:
380: if ((s_arbre = malloc(sizeof(struct_arbre))) == NULL)
381: {
382: (*s_etat_processus).erreur_systeme =
383: d_es_allocation_memoire;
384: return(NULL);
385: }
386:
1.52 bertrand 387: if (((*s_arbre).feuille = allocation_maillon(
388: s_etat_processus)) == NULL)
389: {
390: (*s_etat_processus).erreur_systeme =
391: d_es_allocation_memoire;
392: return(NULL);
393: }
394:
395: (*(*s_arbre).feuille).donnee = copie_objet(
396: s_etat_processus, (*l_element_courant).donnee, 'P');
397: (*(*s_arbre).feuille).suivant = NULL;
1.50 bertrand 398: (*s_arbre).nombre_branches = 0;
399: (*s_arbre).branches = NULL;
400:
401: (*l_liste_locale).donnee = (void *) s_arbre;
402: break;
1.1 bertrand 403: }
404: }
1.50 bertrand 405:
406: l_element_courant = (*l_element_courant).suivant;
1.1 bertrand 407: }
408:
1.50 bertrand 409: // Toute l'expression a été balayée. On ne doit plus avoir qu'un
410: // seul niveau dans la pile locale, ce niveau contenant l'arbre
411: // à réduire.
412:
413: if (l_liste_locale == NULL)
414: {
415: (*s_etat_processus).erreur_execution = d_ex_erreur_evaluation;
416: return(NULL);
417: }
418: else if ((*l_liste_locale).suivant != NULL)
419: {
420: (*s_etat_processus).erreur_execution = d_ex_erreur_evaluation;
421: return(NULL);
422: }
423:
424: s_arbre = (void *) (*l_liste_locale).donnee;
425:
426: liberation_maillon(s_etat_processus, l_liste_locale);
427: l_liste_locale = NULL;
428:
429: /*
430: * Simplification de l'arbre
431: */
432:
1.69 ! bertrand 433: affichage_arbre(s_etat_processus, s_arbre, 0);
! 434:
1.51 bertrand 435: # ifdef EXPERIMENTAL_CODE
1.52 bertrand 436: simplification_arbre(s_etat_processus, s_arbre);
1.51 bertrand 437:
438: if ((*s_etat_processus).erreur_systeme != d_es)
439: {
440: return(NULL);
441: }
1.50 bertrand 442: # endif
443:
444: /*
445: * Transcription de l'arbre q-aire simplifié en expression algébrique.
446: * Seule une fonction récursive permet de faire cette conversion
447: * simplement.
448: */
449:
450: l_liste_locale = transcription_arbre(s_etat_processus, s_arbre);
1.1 bertrand 451:
1.50 bertrand 452: if ((s_objet_simplifie = allocation(s_etat_processus, ALG))
453: == NULL)
454: {
455: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
456: return(NULL);
457: }
1.1 bertrand 458:
1.50 bertrand 459: // Ajout des délimiteurs '<<' et '>>' à la liste d'instructions
1.1 bertrand 460:
1.50 bertrand 461: if (((*s_objet_simplifie).objet = allocation_maillon(s_etat_processus))
462: == NULL)
1.1 bertrand 463: {
1.50 bertrand 464: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
465: return(NULL);
466: }
1.1 bertrand 467:
1.50 bertrand 468: l_element_courant = (*s_objet_simplifie).objet;
1.1 bertrand 469:
1.50 bertrand 470: if (((*l_element_courant).donnee = allocation(s_etat_processus,
471: FCT)) == NULL)
472: {
473: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
474: return(NULL);
1.1 bertrand 475: }
476:
1.50 bertrand 477: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
478: .nombre_arguments = 0;
479: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
480: .fonction = instruction_vers_niveau_superieur;
1.1 bertrand 481:
1.50 bertrand 482: if (((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
483: .nom_fonction = malloc(3 * sizeof(unsigned char))) == NULL)
484: {
485: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
486: return(NULL);
487: }
1.1 bertrand 488:
1.50 bertrand 489: strcpy((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
490: .nom_fonction, "<<");
1.1 bertrand 491:
1.50 bertrand 492: (*l_element_courant).suivant = l_liste_locale;
1.1 bertrand 493:
1.50 bertrand 494: while((*l_element_courant).suivant != NULL)
1.1 bertrand 495: {
1.50 bertrand 496: l_element_courant = (*l_element_courant).suivant;
1.1 bertrand 497: }
498:
1.50 bertrand 499: if (((*l_element_courant).suivant =
500: allocation_maillon(s_etat_processus)) == NULL)
501: {
502: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
503: return(NULL);
504: }
1.1 bertrand 505:
1.50 bertrand 506: l_element_courant = (*l_element_courant).suivant;
507: (*l_element_courant).suivant = NULL;
1.1 bertrand 508:
1.50 bertrand 509: if (((*l_element_courant).donnee = allocation(s_etat_processus,
510: FCT)) == NULL)
511: {
512: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
513: return(NULL);
514: }
1.1 bertrand 515:
1.50 bertrand 516: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
517: .nombre_arguments = 0;
518: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
519: .fonction = instruction_vers_niveau_inferieur;
1.1 bertrand 520:
1.50 bertrand 521: if (((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
522: .nom_fonction = malloc(3 * sizeof(unsigned char))) == NULL)
1.1 bertrand 523: {
1.50 bertrand 524: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
525: return(NULL);
1.1 bertrand 526: }
1.50 bertrand 527:
528: strcpy((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
529: .nom_fonction, ">>");
530: }
531: else
532: {
533: s_objet_simplifie = copie_objet(s_etat_processus, s_objet, 'P');
1.1 bertrand 534: }
535:
1.50 bertrand 536: return(s_objet_simplifie);
1.1 bertrand 537: }
538:
539: // vim: ts=4
CVSweb interface <joel.bertrand@systella.fr>