-/* This group of functions does the character class compression.\r
- It goes over the dfa and relabels the arcs with the partitions\r
- of characters in the NFA. The partitions are stored in the\r
- array class.\r
-\r
- *\r
- * SOFTWARE RIGHTS\r
- *\r
- * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
- * Set (PCCTS) -- PCCTS is in the public domain. An individual or\r
- * company may do whatever they wish with source code distributed with\r
- * PCCTS or the code generated by PCCTS, including the incorporation of\r
- * PCCTS, or its output, into commerical software.\r
- *\r
- * We encourage users to develop software with PCCTS. However, we do ask\r
- * that credit is given to us for developing PCCTS. By "credit",\r
- * we mean that if you incorporate our source code into one of your\r
- * programs (commercial product, research project, or otherwise) that you\r
- * acknowledge this fact somewhere in the documentation, research report,\r
- * etc... If you like PCCTS and have developed a nice tool with the\r
- * output, please mention that you developed it using PCCTS. In\r
- * addition, we ask that this header remain intact in our source code.\r
- * As long as these guidelines are kept, we expect to continue enhancing\r
- * this system and expect to make other tools available as they are\r
- * completed.\r
- *\r
- * DLG 1.33\r
- * Will Cohen\r
- * With mods by Terence Parr; AHPCRC, University of Minnesota\r
- * 1989-2001\r
- */\r
-\r
-#include <stdio.h>\r
-#include "dlg.h"\r
-#ifdef MEMCHK\r
-#include "trax.h"\r
-#else\r
-#ifdef __STDC__\r
-#include <stdlib.h>\r
-#else\r
-#include <malloc.h>\r
-#endif /* __STDC__ */\r
-#endif\r
-\r
-int class_no = CHAR_RANGE; /* number of classes for labels */\r
-int first_el[CHAR_RANGE]; /* first element in each class partition */\r
-set class_sets[CHAR_RANGE]; /* array holds partitions from class */\r
- /* compression */\r
-\r
-/* goes through labels on NFA graph and partitions the characters into\r
- * character classes. This reduces the amount of space required for each\r
- * dfa node, since only one arc is required each class instead of one arc\r
- * for each character\r
- * level:\r
- * 0 no compression done\r
- * 1 remove unused characters from classes\r
- * 2 compress equivalent characters into same class\r
- *\r
- * returns the number of character classes required\r
- */\r
-#ifdef __USE_PROTOS\r
-int relabel(nfa_node* start,int level)\r
-#else\r
-int relabel(start,level)\r
-int level;\r
-nfa_node *start;\r
-#endif\r
-{\r
- if (level){\r
- set_free(used_classes); \r
- partition(start,level);\r
- label_with_classes(start);\r
- }else{\r
- /* classes equivalent to all characters in alphabet */\r
- class_no = CHAR_RANGE;\r
- }\r
- return class_no;\r
-}\r
-\r
-/* makes character class sets for new labels */\r
-#ifdef __USE_PROTOS\r
-void partition(nfa_node* start,int level)\r
-#else\r
-void partition(start,level)\r
-nfa_node *start; /* beginning of nfa graph */\r
-int level; /* compression level to uses */\r
-#endif\r
-{\r
- set current_class;\r
- set unpart_chars;\r
- set temp;\r
-\r
- unpart_chars = set_dup(used_chars);\r
-#if 0\r
- /* EOF (-1+1) alway in class 0 */\r
- class_sets[0] = set_of(0);\r
- first_el[0] = 0;\r
- used_classes = set_of(0);\r
- temp = set_dif(unpart_chars, class_sets[0]);\r
- set_free(unpart_chars);\r
- unpart_chars = temp;\r
- class_no = 1;\r
-#else\r
- class_no = 0;\r
-#endif\r
- while (!set_nil(unpart_chars)){\r
- /* don't look for equivalent labels if c <= 1 */\r
- if (level <= 1){\r
- current_class = set_of(set_int(unpart_chars));\r
- }else{\r
- current_class = set_dup(unpart_chars);\r
- intersect_nfa_labels(start,¤t_class);\r
- }\r
- set_orel(class_no,&used_classes);\r
- first_el[class_no] = set_int(current_class);\r
- class_sets[class_no] = current_class;\r
- temp = set_dif(unpart_chars,current_class);\r
- set_free(unpart_chars);\r
- unpart_chars = temp;\r
- ++class_no;\r
- }\r
-\r
- /* free unpart_chars -ATG 5/6/95 */\r
- set_free(unpart_chars);\r
-\r
-#if 0\r
- /* group all the other unused characters into a class */\r
- set_orel(class_no,&used_classes);\r
- first_el[class_no] = set_int(current_class);\r
- class_sets[class_no] = set_dif(normal_chars,used_chars);\r
- ++class_no;\r
-#endif\r
-}\r
-\r
-\r
-/* given pointer to beginning of graph and recursively walks it trying\r
- * to find a maximal partition. This partion in returned in maximal_class\r
- */\r
-#ifdef __USE_PROTOS\r
-void intersect_nfa_labels(nfa_node* start,set* maximal_class)\r
-#else\r
-void intersect_nfa_labels(start,maximal_class)\r
-nfa_node *start;\r
-set *maximal_class;\r
-#endif\r
-{\r
- /* pick a new operation number */\r
- ++operation_no;\r
- r_intersect(start,maximal_class); \r
-}\r
-\r
-#ifdef __USE_PROTOS\r
-void r_intersect(nfa_node* start,set* maximal_class)\r
-#else\r
-void r_intersect(start,maximal_class)\r
-nfa_node *start;\r
-set * maximal_class;\r
-#endif\r
-{\r
- set temp;\r
-\r
- if(start && start->nfa_set != operation_no)\r
- {\r
- start->nfa_set = operation_no;\r
- temp = set_and(*maximal_class,start->label);\r
- if (!set_nil(temp))\r
- {\r
- set_free(*maximal_class);\r
- *maximal_class = temp;\r
- }else{\r
- set_free(temp);\r
- }\r
- r_intersect(start->trans[0],maximal_class);\r
- r_intersect(start->trans[1],maximal_class);\r
- }\r
-}\r
-\r
-\r
-/* puts class labels in place of old character labels */\r
-#ifdef __USE_PROTOS\r
-void label_with_classes(nfa_node* start)\r
-#else\r
-void label_with_classes(start)\r
-nfa_node *start;\r
-#endif\r
-{\r
- ++operation_no;\r
- label_node(start);\r
-}\r
-\r
-#ifdef __USE_PROTOS\r
-void label_node(nfa_node *start)\r
-#else\r
-void label_node(start)\r
-nfa_node *start;\r
-#endif\r
-{\r
- set new_label;\r
- register int i;\r
-\r
- /* only do node if it hasn't been done before */\r
- if (start && start->nfa_set != operation_no){\r
- start->nfa_set = operation_no;\r
- new_label = empty;\r
- for (i = 0; i<class_no; ++i){\r
- /* if one element of class in old_label,\r
- all elements are. */\r
- if (set_el(first_el[i],start->label))\r
- set_orel(i,&new_label);\r
- }\r
- set_free(start->label);\r
- start->label = new_label;\r
- /* do any nodes that can be reached from this one */\r
- label_node(start->trans[0]);\r
- label_node(start->trans[1]);\r
- }\r
-}\r