Tools/Source/TianoTools/Pccts/dlg/relabel.c

   1 /* This group of functions does the character class compression.
   2    It goes over the dfa and relabels the arcs with the partitions
   3    of characters in the NFA.  The partitions are stored in the
   4    array class.
   5
   6  *
   7  * SOFTWARE RIGHTS
   8  *
   9  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  10  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  11  * company may do whatever they wish with source code distributed with
  12  * PCCTS or the code generated by PCCTS, including the incorporation of
  13  * PCCTS, or its output, into commerical software.
  14  *
  15  * We encourage users to develop software with PCCTS.  However, we do ask
  16  * that credit is given to us for developing PCCTS.  By "credit",
  17  * we mean that if you incorporate our source code into one of your
  18  * programs (commercial product, research project, or otherwise) that you
  19  * acknowledge this fact somewhere in the documentation, research report,
  20  * etc...  If you like PCCTS and have developed a nice tool with the
  21  * output, please mention that you developed it using PCCTS.  In
  22  * addition, we ask that this header remain intact in our source code.
  23  * As long as these guidelines are kept, we expect to continue enhancing
  24  * this system and expect to make other tools available as they are
  25  * completed.
  26  *
  27  * DLG 1.33
  28  * Will Cohen
  29  * With mods by Terence Parr; AHPCRC, University of Minnesota
  30  * 1989-2001
  31  */
  32
  33 #include <stdio.h>
  34 #include "dlg.h"
  35 #ifdef MEMCHK
  36 #include "trax.h"
  37 #else
  38 #ifdef __STDC__
  39 #include <stdlib.h>
  40 #else
  41 #include <malloc.h>
  42 #endif /* __STDC__ */
  43 #endif
  44
  45 int     class_no = CHAR_RANGE;  /* number of classes for labels */
  46 int     first_el[CHAR_RANGE];   /* first element in each class partition */
  47 set     class_sets[CHAR_RANGE]; /* array holds partitions from class */
  48                                 /* compression */
  49
  50 /* goes through labels on NFA graph and partitions the characters into
  51  * character classes.  This reduces the amount of space required for each
  52  * dfa node, since only one arc is required each class instead of one arc
  53  * for each character
  54  * level:
  55  * 0 no compression done
  56  * 1 remove unused characters from classes
  57  * 2 compress equivalent characters into same class
  58  *
  59  * returns the number of character classes required
  60  */
  61 #ifdef __USE_PROTOS
  62 int relabel(nfa_node* start,int level)
  63 #else
  64 int relabel(start,level)
  65 int level;
  66 nfa_node *start;
  67 #endif
  68 {
  69         if (level){
  70                 set_free(used_classes);
  71                 partition(start,level);
  72                 label_with_classes(start);
  73         }else{
  74                 /* classes equivalent to all characters in alphabet */
  75                 class_no = CHAR_RANGE;
  76         }
  77         return class_no;
  78 }
  79
  80 /* makes character class sets for new labels */
  81 #ifdef __USE_PROTOS
  82 void partition(nfa_node* start,int level)
  83 #else
  84 void partition(start,level)
  85 nfa_node        *start; /* beginning of nfa graph */
  86 int             level;  /* compression level to uses */
  87 #endif
  88 {
  89         set current_class;
  90         set unpart_chars;
  91         set temp;
  92
  93         unpart_chars = set_dup(used_chars);
  94 #if 0
  95         /* EOF (-1+1) alway in class 0 */
  96         class_sets[0] = set_of(0);
  97         first_el[0] = 0;
  98         used_classes = set_of(0);
  99         temp = set_dif(unpart_chars, class_sets[0]);
 100         set_free(unpart_chars);
 101         unpart_chars = temp;
 102         class_no = 1;
 103 #else
 104         class_no = 0;
 105 #endif
 106         while (!set_nil(unpart_chars)){
 107                 /* don't look for equivalent labels if c <= 1 */
 108                 if (level <= 1){
 109                         current_class = set_of(set_int(unpart_chars));
 110                 }else{
 111                         current_class = set_dup(unpart_chars);
 112                         intersect_nfa_labels(start,&current_class);
 113                 }
 114                 set_orel(class_no,&used_classes);
 115                 first_el[class_no] = set_int(current_class);
 116                 class_sets[class_no] = current_class;
 117                 temp = set_dif(unpart_chars,current_class);
 118                 set_free(unpart_chars);
 119                 unpart_chars = temp;
 120                 ++class_no;
 121         }
 122
 123         /* free unpart_chars -ATG 5/6/95 */
 124         set_free(unpart_chars);
 125
 126 #if 0
 127         /* group all the other unused characters into a class */
 128         set_orel(class_no,&used_classes);
 129         first_el[class_no] = set_int(current_class);
 130         class_sets[class_no] = set_dif(normal_chars,used_chars);
 131         ++class_no;
 132 #endif
 133 }
 134
 135
 136 /* given pointer to beginning of graph and recursively walks it trying
 137  * to find a maximal partition.  This partion in returned in maximal_class
 138  */
 139 #ifdef __USE_PROTOS
 140 void intersect_nfa_labels(nfa_node* start,set* maximal_class)
 141 #else
 142 void intersect_nfa_labels(start,maximal_class)
 143 nfa_node *start;
 144 set *maximal_class;
 145 #endif
 146 {
 147         /* pick a new operation number */
 148         ++operation_no;
 149         r_intersect(start,maximal_class);
 150 }
 151
 152 #ifdef __USE_PROTOS
 153 void r_intersect(nfa_node* start,set* maximal_class)
 154 #else
 155 void r_intersect(start,maximal_class)
 156 nfa_node *start;
 157 set * maximal_class;
 158 #endif
 159 {
 160         set temp;
 161
 162         if(start && start->nfa_set != operation_no)
 163         {
 164                 start->nfa_set = operation_no;
 165                 temp = set_and(*maximal_class,start->label);
 166                 if (!set_nil(temp))
 167                 {
 168                         set_free(*maximal_class);
 169                         *maximal_class = temp;
 170                 }else{
 171                         set_free(temp);
 172                 }
 173                 r_intersect(start->trans[0],maximal_class);
 174                 r_intersect(start->trans[1],maximal_class);
 175         }
 176 }
 177
 178
 179 /* puts class labels in place of old character labels */
 180 #ifdef __USE_PROTOS
 181 void label_with_classes(nfa_node* start)
 182 #else
 183 void label_with_classes(start)
 184 nfa_node *start;
 185 #endif
 186 {
 187         ++operation_no;
 188         label_node(start);
 189 }
 190
 191 #ifdef __USE_PROTOS
 192 void label_node(nfa_node *start)
 193 #else
 194 void label_node(start)
 195 nfa_node *start;
 196 #endif
 197 {
 198         set new_label;
 199         register int i;
 200
 201         /* only do node if it hasn't been done before */
 202         if (start && start->nfa_set != operation_no){
 203                 start->nfa_set = operation_no;
 204                 new_label = empty;
 205                 for (i = 0; i<class_no; ++i){
 206                         /* if one element of class in old_label,
 207                            all elements are. */
 208                         if (set_el(first_el[i],start->label))
 209                                 set_orel(i,&new_label);
 210                 }
 211                 set_free(start->label);
 212                 start->label = new_label;
 213                 /* do any nodes that can be reached from this one */
 214                 label_node(start->trans[0]);
 215                 label_node(start->trans[1]);
 216         }
 217 }