]>
git.proxmox.com Git - mirror_edk2.git/blob - Tools/Source/TianoTools/Pccts/dlg/automata.c
1 /* Automata conversion functions for DLG
5 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
6 * Set (PCCTS) -- PCCTS is in the public domain. An individual or
7 * company may do whatever they wish with source code distributed with
8 * PCCTS or the code generated by PCCTS, including the incorporation of
9 * PCCTS, or its output, into commerical software.
11 * We encourage users to develop software with PCCTS. However, we do ask
12 * that credit is given to us for developing PCCTS. By "credit",
13 * we mean that if you incorporate our source code into one of your
14 * programs (commercial product, research project, or otherwise) that you
15 * acknowledge this fact somewhere in the documentation, research report,
16 * etc... If you like PCCTS and have developed a nice tool with the
17 * output, please mention that you developed it using PCCTS. In
18 * addition, we ask that this header remain intact in our source code.
19 * As long as these guidelines are kept, we expect to continue enhancing
20 * this system and expect to make other tools available as they are
25 * With mods by Terence Parr; AHPCRC, University of Minnesota
42 #define hash_list struct _hash_list_
44 hash_list
*next
; /* next thing in list */
48 int dfa_allocated
= 0; /* keeps track of number of dfa nodes */
49 dfa_node
**dfa_array
; /* root of binary tree that stores dfa array */
50 dfa_node
*dfa_model_node
;
51 hash_list
*dfa_hash
[HASH_SIZE
]; /* used to quickly find */
52 /* desired dfa node */
56 make_dfa_model_node(int width
)
58 make_dfa_model_node(width
)
63 dfa_model_node
= (dfa_node
*) malloc(sizeof(dfa_node
)
65 dfa_model_node
->node_no
= -1; /* impossible value for real dfa node */
66 dfa_model_node
->dfa_set
= 0;
67 dfa_model_node
->alternatives
= FALSE
;
68 dfa_model_node
->done
= FALSE
;
69 dfa_model_node
->nfa_states
= empty
;
70 for(i
= 0; i
<width
; i
++){
71 dfa_model_node
->trans
[i
] = NIL_INDEX
;
76 /* adds a new nfa to the binary tree and returns a pointer to it */
79 new_dfa_node(set nfa_states
)
81 new_dfa_node(nfa_states
)
87 static int dfa_size
=0; /* elements dfa_array[] can hold */
90 if (dfa_size
<=dfa_allocated
){
91 /* need to redo array */
93 /* need some to do inital allocation */
94 dfa_size
=dfa_allocated
+DFA_MIN
;
95 dfa_array
=(dfa_node
**) malloc(sizeof(dfa_node
*)*
99 dfa_size
=2*(dfa_allocated
+1);
100 dfa_array
=(dfa_node
**) realloc(dfa_array
,
101 sizeof(dfa_node
*)*dfa_size
);
104 /* fill out entry in array */
105 t
= (dfa_node
*) malloc(sizeof(nfa_node
)+sizeof(int)*class_no
);
106 *t
= *dfa_model_node
;
107 for (j
=0; j
<class_no
; ++j
)
108 t
->trans
[j
] = NIL_INDEX
;
109 t
->node_no
= dfa_allocated
;
110 t
->nfa_states
= set_dup(nfa_states
);
111 dfa_array
[dfa_allocated
] = t
;
116 /* past a pointer to the start start of the nfa graph
117 * nfa_to_dfa convers this graph to dfa. The function returns
118 * a pointer to the first dfa state.
119 * NOTE: The function that prints out the table will have to figure out how
120 * to find the other dfa states given the first dfa_state and the number of dfa
125 nfa_to_dfa(nfa_node
*start
)
131 register dfa_node
*d_state
, *trans_d_state
;
136 unsigned *reach_list
;
138 reach_list
= (unsigned *) malloc((2+nfa_allocated
)*sizeof(unsigned));
139 if (!start
) return NULL
;
140 t
= set_of(NFA_NO(start
));
141 _set_pdq(t
,reach_list
);
142 closure(&t
,reach_list
);
143 /* Make t a dfa state */
144 d_state
= dfastate(t
);
145 last_done
= DFA_NO(d_state
);
148 /* Mark dfa state x as "done" */
149 d_state
->done
= TRUE
;
150 nfa_list
= set_pdq(d_state
->nfa_states
);
151 for (a
= 0; a
<class_no
; ++a
) {
152 /* Add NFA states reached by a from d_state */
153 reach(nfa_list
,a
,reach_list
);
154 /* Were any states found? */
155 if ((*reach_list
)!=nil
) {
158 /* yes, compute closure */
159 closure(&t
,reach_list
);
160 /* Make DFA state of it ... */
161 trans_d_state
= dfastate(t
);
162 /* And make transition x->t, labeled with a */
163 d_state
->trans
[a
] = DFA_NO(trans_d_state
);
164 d_state
->alternatives
= TRUE
;
168 ++last_done
; /* move forward in queue */
169 /* And so forth until nothing isn't done */
170 d_state
= DFA(last_done
);
171 } while (last_done
<=dfa_allocated
);
176 /* returns pointer to the array that holds the automaton */
189 for(i
=0; i
<HASH_SIZE
; ++i
)
196 fprint_hash_stats(FILE *f
)
202 register hash_list
*p
;
207 for(i
=0; i
<HASH_SIZE
; ++i
){
215 fprintf(f
,"bin[%d] has %d\n",i
,j
);
217 fprintf(f
,"total = %d\n",total
);
221 /* Returns a pointer to a dfa node that has the same nfa nodes in it.
222 * This may or maynot be a newly created node.
226 dfastate(set nfa_states
)
232 register hash_list
*p
;
235 /* hash using set and see if it exists */
236 bin
= set_hash(nfa_states
,HASH_SIZE
);
238 while(p
&& !set_equ(nfa_states
,(p
->node
)->nfa_states
)){
242 /* next state to add to hash table */
243 p
= (hash_list
*)malloc(sizeof(hash_list
));
244 p
->node
= new_dfa_node(nfa_states
);
245 p
->next
= dfa_hash
[bin
];
252 /* this reach assumes the closure has been done already on set */
255 reach(unsigned *nfa_list
, register int a
, unsigned *reach_list
)
257 reach(nfa_list
, a
, reach_list
)
260 unsigned *reach_list
;
263 register unsigned *e
;
264 register nfa_node
*node
;
271 if (set_el(a
,node
->label
)){
273 *reach_list
=NFA_NO(node
->trans
[0]);
283 /* finds all the nodes that can be reached by epsilon transitions
284 from the set of a nodes and returns puts them back in set b */
287 closure(set
*b
, unsigned *reach_list
)
289 closure(b
, reach_list
)
291 unsigned *reach_list
;
294 register nfa_node
*node
,*n
; /* current node being examined */
295 register unsigned *e
;
305 set_orel(NFA_NO(node
),b
);
307 node
->nfa_set
= operation_no
;
308 if ((n
=node
->trans
[0]) != NIL_INDEX
&& set_nil(node
->label
) &&
309 (n
->nfa_set
!= operation_no
)){
311 set_orel(NFA_NO(n
),b
);
312 close1(n
,operation_no
,b
);
314 if ((n
=node
->trans
[1]) != NIL_INDEX
&&
315 (n
->nfa_set
!= operation_no
)){
317 set_orel(NFA_NO(node
->trans
[1]),b
);
318 close1(n
,operation_no
,b
);
329 void close1(nfa_node
*node
, int o
, set
*b
)
331 void close1(node
,o
,b
)
333 int o
; /* marker to avoid cycles */
337 register nfa_node
*n
; /* current node being examined */
341 if ((n
=node
->trans
[0]) != NIL_INDEX
&& set_nil(node
->label
) &&
344 set_orel(NFA_NO(n
),b
);
347 if ((n
=node
->trans
[1]) != NIL_INDEX
&&
350 set_orel(NFA_NO(node
->trans
[1]),b
);