--- /dev/null
+/* 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
projects / mirror_edk2.git / blobdiff