pd.if.org Git - pccts/blob - 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-1995
  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 int relabel(start,level)
  62 int level;
  63 nfa_node *start;
  64 {
  65         if (level){
  66                 set_free(used_classes);
  67                 partition(start,level);
  68                 label_with_classes(start);
  69         }else{
  70                 /* classes equivalent to all characters in alphabet */
  71                 class_no = CHAR_RANGE;
  72         }
  73         return class_no;
  74 }
  75
  76 /* makes character class sets for new labels */
  77 partition(start,level)
  78 nfa_node        *start; /* beginning of nfa graph */
  79 int             level;  /* compression level to uses */
  80 {
  81         set current_class;
  82         set unpart_chars;
  83         set temp;
  84
  85         unpart_chars = set_dup(used_chars);
  86 #if 0
  87         /* EOF (-1+1) alway in class 0 */
  88         class_sets[0] = set_of(0);
  89         first_el[0] = 0;
  90         used_classes = set_of(0);
  91         temp = set_dif(unpart_chars, class_sets[0]);
  92         set_free(unpart_chars);
  93         unpart_chars = temp;
  94         class_no = 1;
  95 #else
  96         class_no = 0;
  97 #endif
  98         while (!set_nil(unpart_chars)){
  99                 /* don't look for equivalent labels if c <= 1 */
 100                 if (level <= 1){
 101                         current_class = set_of(set_int(unpart_chars));
 102                 }else{
 103                         current_class = set_dup(unpart_chars);
 104                         intersect_nfa_labels(start,&current_class);
 105                 }
 106                 set_orel(class_no,&used_classes);
 107                 first_el[class_no] = set_int(current_class);
 108                 class_sets[class_no] = current_class;
 109                 temp = set_dif(unpart_chars,current_class);
 110                 set_free(unpart_chars);
 111                 unpart_chars = temp;
 112                 ++class_no;
 113         }
 114
 115         /* free unpart_chars -ATG 5/6/95 */
 116         set_free(unpart_chars);
 117
 118 #if 0
 119         /* group all the other unused characters into a class */
 120         set_orel(class_no,&used_classes);
 121         first_el[class_no] = set_int(current_class);
 122         class_sets[class_no] = set_dif(normal_chars,used_chars);
 123         ++class_no;
 124 #endif
 125 }
 126
 127
 128 /* given pointer to beginning of graph and recursively walks it trying
 129  * to find a maximal partition.  This partion in returned in maximal_class
 130  */
 131 intersect_nfa_labels(start,maximal_class)
 132 nfa_node *start;
 133 set *maximal_class;
 134 {
 135         /* pick a new operation number */
 136         ++operation_no;
 137         r_intersect(start,maximal_class);
 138 }
 139
 140 r_intersect(start,maximal_class)
 141 nfa_node *start;
 142 set * maximal_class;
 143 {
 144         set temp;
 145
 146         if(start && start->nfa_set != operation_no)
 147         {
 148                 start->nfa_set = operation_no;
 149                 temp = set_and(*maximal_class,start->label);
 150                 if (!set_nil(temp))
 151                 {
 152                         set_free(*maximal_class);
 153                         *maximal_class = temp;
 154                 }else{
 155                         set_free(temp);
 156                 }
 157                 r_intersect(start->trans[0],maximal_class);
 158                 r_intersect(start->trans[1],maximal_class);
 159         }
 160 }
 161
 162
 163 /* puts class labels in place of old character labels */
 164 label_with_classes(start)
 165 nfa_node *start;
 166 {
 167         ++operation_no;
 168         label_node(start);
 169 }
 170
 171 label_node(start)
 172 nfa_node *start;
 173 {
 174         set new_label;
 175         register int i;
 176
 177         /* only do node if it hasn't been done before */
 178         if (start && start->nfa_set != operation_no){
 179                 start->nfa_set = operation_no;
 180                 new_label = empty;
 181                 for (i = 0; i<class_no; ++i){
 182                         /* if one element of class in old_label,
 183                            all elements are. */
 184                         if (set_el(first_el[i],start->label))
 185                                 set_orel(i,&new_label);
 186                 }
 187                 set_free(start->label);
 188                 start->label = new_label;
 189                 /* do any nodes that can be reached from this one */
 190                 label_node(start->trans[0]);
 191                 label_node(start->trans[1]);
 192         }
 193 }