home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts.zip / pccts / dlg / relabel.c < prev    next >
C/C++ Source or Header  |  1994-03-31  |  5KB  |  190 lines
  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.20
  28.  * Will Cohen
  29.  * With mods by Terence Parr; AHPCRC, University of Minnesota
  30.  * 1989-1994
  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[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[0] = set_of(0);
  89.     first_el[0] = 0;
  90.     used_classes = set_of(0);
  91.     temp = set_dif(unpart_chars, class[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,¤t_class);
  105.         }
  106.         set_orel(class_no,&used_classes);
  107.         first_el[class_no] = set_int(current_class);
  108.         class[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. #if 0
  115.     /* group all the other unused characters into a class */
  116.     set_orel(class_no,&used_classes);
  117.     first_el[class_no] = set_int(current_class);
  118.     class[class_no] = set_dif(normal_chars,used_chars);
  119.     ++class_no;
  120. #endif
  121. }
  122.  
  123.  
  124. /* given pointer to beginning of graph and recursively walks it trying
  125.  * to find a maximal partition.  This partion in returned in maximal_class
  126.  */
  127. intersect_nfa_labels(start,maximal_class)
  128. nfa_node *start;
  129. set *maximal_class;
  130. {
  131.     /* pick a new operation number */
  132.     ++operation_no;
  133.     r_intersect(start,maximal_class);    
  134. }
  135.  
  136. r_intersect(start,maximal_class)
  137. nfa_node *start;
  138. set * maximal_class;
  139. {
  140.     set temp;
  141.  
  142.     if(start && start->nfa_set != operation_no)
  143.     {
  144.         start->nfa_set = operation_no;
  145.         temp = set_and(*maximal_class,start->label);
  146.         if (!set_nil(temp))
  147.         {
  148.             set_free(*maximal_class);
  149.             *maximal_class = temp;
  150.         }else{
  151.             set_free(temp);
  152.         }
  153.         r_intersect(start->trans[0],maximal_class);
  154.         r_intersect(start->trans[1],maximal_class);
  155.     }
  156. }
  157.  
  158.  
  159. /* puts class labels in place of old character labels */
  160. label_with_classes(start)
  161. nfa_node *start;
  162. {
  163.     ++operation_no;
  164.     label_node(start);
  165. }
  166.  
  167. label_node(start)
  168. nfa_node *start;
  169. {
  170.     set new_label;
  171.     register int i;
  172.  
  173.     /* only do node if it hasn't been done before */
  174.     if (start && start->nfa_set != operation_no){
  175.         start->nfa_set = operation_no;
  176.         new_label = empty;
  177.         for (i = 0; i<class_no; ++i){
  178.             /* if one element of class in old_label,
  179.                all elements are. */
  180.             if (set_el(first_el[i],start->label))
  181.                 set_orel(i,&new_label);
  182.         }
  183.         set_free(start->label);
  184.         start->label = new_label;
  185.         /* do any nodes that can be reached from this one */
  186.         label_node(start->trans[0]);
  187.         label_node(start->trans[1]);
  188.     }
  189. }
  190.