| blob | 7832f5e5a3b4e7a77f01baf20ea5c29c8564247e |
1 //////////////////////////////////////////////////////////////////////////////
2 // NOTICE:
3 //
4 // ADLib, Prop and their related set of tools and documentation are in the
5 // public domain. The author(s) of this software reserve no copyrights on
6 // the source code and any code generated using the tools. You are encouraged
7 // to use ADLib and Prop to develop software, in both academic and commercial
8 // settings, and are welcomed to incorporate any part of ADLib and Prop into
9 // your programs.
10 //
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
13 //
14 // We also ask that credit be given to us when ADLib and/or Prop are used in
15 // your programs, and that this notice be preserved intact in all the source
16 // code.
17 //
18 // This software is still under development and we welcome(read crave for)
19 // any suggestions and help from the users.
20 //
21 // Allen Leung
22 // 1994
23 //////////////////////////////////////////////////////////////////////////////
25 #include <assert.h>
26 #include <iostream>
27 #include <AD/automata/treegram.ph> // tree grammar
28 #include <AD/automata/treegen.h> // tree automata compiler
29 #include <AD/contain/bitset.h> // bit set
30 #include <AD/hash/dchash.h> // direct chaining hash map
31 #include <AD/contain/vararray.h> // variable sized array
32 #include <AD/contain/slnklist.h> // linked list
33 #include <AD/memory/mempool.h> // memory pool
35 //////////////////////////////////////////////////////////////////////////////
36 // Make hidden types visible
37 //////////////////////////////////////////////////////////////////////////////
38 typedef TreeGrammar::TreeProduction TreeProduction;
39 typedef TreeGrammar::Functor Functor;
40 typedef TreeGrammar::Arity Arity;
41 typedef TreeGrammar::Variable Variable;
42 typedef TreeGrammar::State State;
43 typedef TreeGrammar::Rule Rule;
44 typedef TreeAutomaton::Equiv Equiv;
45 typedef SLinkList<State> StateList;
47 //////////////////////////////////////////////////////////////////////////////
48 // Class TreeGenerator represents the internals of the automata compiler.
49 // This stuff is completely hidden from the interface.
50 //////////////////////////////////////////////////////////////////////////////
51 class TreeGenerator {
53 TreeGenerator(const TreeGenerator&); // no copy constructor
54 void operator = (const TreeGenerator&); // no assignment
56 public:
58 ///////////////////////////////////////////////////////////////////////////
59 // Internal data structures
60 ///////////////////////////////////////////////////////////////////////////
62 TreeGen& treegen;
63 TreeGrammar& G; // the grammar
64 MemPool mem; // memory pool
65 BitSet ** ruleset_map; // non-terminal -> rule set
66 Rule * rule_map; // non-terminal -> rule set
67 DCHashTable<TreeTerm, Variable> non_terminals; // term -> non-terminals map
68 VarArray <TreeTerm> n_states; // non-terminals -> term map
69 DCHashTable<BitSet *, State> state_labels; // non-terminal set -> state mapping
70 DCHashTable<TreeTerm, BitSet *> delta; // term -> non-terminals mapping
71 VarArray <BitSet *> d_states; // state -> non-terminal set
72 VarArray <TreeTerm> d_terms; // state -> term map
73 BitSet *** proj; // projections
74 BitSet ** closure0; // transitive closure of each non-terminal
75 Variable max_non_terminal;
76 State number_of_states;
77 StateList *** representers;
79 ///////////////////////////////////////////////////////////////////////////
80 // Constructor
81 ///////////////////////////////////////////////////////////////////////////
82 TreeGenerator(TreeGen& gen, TreeGrammar& g) :
83 treegen(gen), G(g), mem(4096), non_terminals(1037),
84 state_labels(1037), delta(1037) {}
86 ///////////////////////////////////////////////////////////////////////////
87 // Methods to process various phases of the compilation.
88 ///////////////////////////////////////////////////////////////////////////
89 void assign_non_terminals ();
90 TreeTerm assign_non_terminal ( TreeTerm );
91 void compute_closures ();
92 void compute_projections ();
93 void compute_representers ();
94 void compute_initial_states ();
95 void compute_transitions ();
96 BitSet * compute_transition (BitSet *, TreeTerm, int, int, const BitSet&, State [], int []);
97 void compute_delta (BitSet *, TreeTerm, int, int, const State []);
98 void compute_accept_rules (State);
99 std::ostream& print_report (std::ostream&) const;
100 std::ostream& print_state (std::ostream&, State) const;
101 };
103 //////////////////////////////////////////////////////////////////////////////
104 // The following method is used to assign non-terminal symbols
105 // to each distinct term within the grammar
106 //////////////////////////////////////////////////////////////////////////////
107 void TreeGenerator::assign_non_terminals()
108 {
109 ///////////////////////////////////////////////////////////////////////////
110 // The grammar may already have user defined variable names.
111 // New non-terminals will have encodings right after these variables.
112 ///////////////////////////////////////////////////////////////////////////
113 max_non_terminal = G.max_variable() + 1;
114 non_terminals.insert(wild_term,0);
115 { for (Variable v = max_non_terminal - 1; v >= 0; v--)
116 n_states.At(v) = wild_term;
117 }
119 ///////////////////////////////////////////////////////////////////////////
120 // Traverse thru the grammar and compute the non-terminal numbers.
121 // The tree grammar *IS* destructively altered.
122 ///////////////////////////////////////////////////////////////////////////
123 { for (int i = G.size() - 1; i >= 0; i--)
124 G.update(i,assign_non_terminal( G[i].term ));
125 }
127 ///////////////////////////////////////////////////////////////////////////
128 // Compute the mapping from non-terminal -> accept rule
129 ///////////////////////////////////////////////////////////////////////////
130 ruleset_map = (BitSet **)mem.c_alloc(sizeof(BitSet *) * max_non_terminal);
131 rule_map = (Rule *) mem.c_alloc(sizeof(Rule) * max_non_terminal);
132 { int i;
133 for (i = max_non_terminal - 1; i >= 0; i--) rule_map[i] = -1;
134 for (i = G.size() - 1; i >= 0; i--) {
135 Variable v = non_terminals[G[i].term];
136 if (ruleset_map[v] == 0)
137 ruleset_map[v] = new (mem, max_non_terminal) BitSet;
138 ruleset_map[v]->add(i);
139 rule_map[v] = i;
140 }
141 }
142 }
144 //////////////////////////////////////////////////////////////////////////////
145 // Method to assign non-terminal numbers for a tree term. This is
146 // defined inductive as:
147 //////////////////////////////////////////////////////////////////////////////
148 TreeTerm TreeGenerator::assign_non_terminal( TreeTerm t )
149 {
150 ///////////////////////////////////////////////////////////////////////////
151 // Step (a) recursively fold the terms.
152 ///////////////////////////////////////////////////////////////////////////
153 match (t) {
154 case wild_term: // skip
155 case var_term _: // skip
156 case set_term _: // skip
157 case and_term(x,y): x = assign_non_terminal(x); y = assign_non_terminal(y);
158 case or_term(x,y): x = assign_non_terminal(x); y = assign_non_terminal(y);
159 case not_term(x): x = assign_non_terminal(x);
160 case tree_term(f,n,subterms):
161 for (int i = n - 1; i >= 0; i--)
162 subterms[i] = assign_non_terminal(subterms[i]);
163 }
165 ///////////////////////////////////////////////////////////////////////////
166 // Look it up from the ``non_terminal'' map.
167 ///////////////////////////////////////////////////////////////////////////
168 Ix p = non_terminals.lookup(t);
169 if (p == 0) { // not found!
170 ////////////////////////////////////////////////////////////////////////
171 // Step (b) if it is not found, assign a new non-terminal number.
172 // Notice that ``wild_term'' always gets the non-terminal number of 0.
173 ////////////////////////////////////////////////////////////////////////
174 Variable var;
175 match (t) {
176 case wild_term: var = 0;
177 case var_term v: var = v;
178 case _: var = max_non_terminal++;
179 }
180 non_terminals.insert(t,var); // update map
181 n_states.At(var) = t; // update inverse map
182 } else {
183 t = non_terminals.key(p);
184 }
185 return t;
186 }
188 //////////////////////////////////////////////////////////////////////////////
189 // This is the method for computing transitive closure on a non-terminal
190 // set. Transitive closures apply in the presence of single reductions
191 // X -> Y
192 // or logical connectives:
193 // X -> Y and Z
194 // X -> Y or Z
195 //
196 // We don't support negation yet since it is anti-monotonic.
197 //////////////////////////////////////////////////////////////////////////////
198 void TreeGenerator::compute_closures()
199 {
200 ///////////////////////////////////////////////////////////////////////////
201 // Allocate the array closure0, which maps each non-terminal to
202 // its transitive closure. Closure set are allocated only if
203 // they are non-trivial (i.e. closure0[v] is something other than
204 // { 0, v }.
205 ///////////////////////////////////////////////////////////////////////////
206 closure0 = (BitSet**)mem.c_alloc(sizeof(BitSet*) * max_non_terminal);
208 ///////////////////////////////////////////////////////////////////////////
209 // Allocate closures for user defined non-terminals
210 ///////////////////////////////////////////////////////////////////////////
211 { for (Variable v = G.min_variable(); v <= G.max_variable(); v++) {
212 closure0[v] = new (mem, max_non_terminal) BitSet;
213 closure0[v]->add(0);
214 closure0[v]->add(v);
215 }
216 }
218 ///////////////////////////////////////////////////////////////////////////
219 // Now compute the transitive closure
220 ///////////////////////////////////////////////////////////////////////////
221 Bool changed;
222 BitSet& temp = *new(mem, max_non_terminal) BitSet; // temporary set buffer
223 do {
224 changed = false;
226 /////////////////////////////////////////////////////////////////////////
227 // Propagate closure information.
228 /////////////////////////////////////////////////////////////////////////
229 foreach (p, non_terminals) {
230 TreeTerm term = non_terminals.key(p);
231 Variable var = non_terminals.value(p);
233 /////////////////////////////////////////////////////////////////////
234 // Allocate a new closure set if necessary.
235 /////////////////////////////////////////////////////////////////////
236 match (term) {
237 case (and_term _ || or_term _ || var_term _) where (closure0[var] == 0):
238 closure0[var] = new (mem, max_non_terminal) BitSet;
239 closure0[var]->add(0);
240 closure0[var]->add(var);
241 changed = true;
242 case _:
243 }
245 /////////////////////////////////////////////////////////////////////
246 // Propagate closures sets.
247 /////////////////////////////////////////////////////////////////////
248 match (term) {
249 case and_term(x,y):
250 BitSet * s1 = closure0[ non_terminals[x] ];
251 BitSet * s2 = closure0[ non_terminals[y] ];
252 temp.Intersect(*s1,*s2);
253 if (closure0[var]->Union_if_changed(temp)) changed = true;
254 case or_term(x,y):
255 BitSet * s1 = closure0[ non_terminals[x] ];
256 BitSet * s2 = closure0[ non_terminals[y] ];
257 if (closure0[var]->Union_if_changed(*s1)) changed = true;
258 if (closure0[var]->Union_if_changed(*s2)) changed = true;
259 case var_term(v) | var != v:
260 if (closure0[v]) {
261 if (closure0[var]->Union_if_changed(*closure0[v])) changed = true;
262 } else {
263 if (closure0[var]->add_if_changed(v)) changed = true;
264 }
265 case _: // skip
266 }
267 }
269 /////////////////////////////////////////////////////////////////////////
270 // Propagate closure information to user non-terminals
271 /////////////////////////////////////////////////////////////////////////
272 for (int i = G.size() - 1; i >= 0; i--) {
273 Variable v1 = G[i].var;
274 Variable v2 = non_terminals[G[i].term];
275 // cerr << "[" << v1 << " ";
276 // G.print_variable(cerr,v1) << " <= " << v2 << " ";
277 // G.print(cerr,G[i].term) << "]\n";
278 if (v1 == 0) continue;
279 if (closure0[v2]) {
280 if (closure0[v1]->Union_if_changed(*closure0[v2])) changed = true;
281 } else {
282 if (closure0[v1]->add_if_changed(v2)) changed = true;
283 }
284 }
285 } while (changed);
286 }
288 //////////////////////////////////////////////////////////////////////////////
289 // This is the method for computing projections.
290 // A projection on functor f and arity i (written as proj[f][i]) is
291 // the set of non-terminals that can appear in that position.
292 //////////////////////////////////////////////////////////////////////////////
293 void TreeGenerator::compute_projections()
294 {
295 ///////////////////////////////////////////////////////////////////////////
296 // Allocate the projection array.
297 ///////////////////////////////////////////////////////////////////////////
298 { proj = (BitSet***)mem.c_alloc(sizeof(BitSet**) * (G.max_functor() + 1));
299 for (Functor f = G.min_functor(); f <= G.max_functor(); f++) {
300 if (G.arity(f) == 0) continue;
301 proj[f] = (BitSet**)mem.c_alloc(sizeof(BitSet*) * G.arity(f));
302 for (int i = G.arity(f) - 1; i >= 0; i--) {
303 proj[f][i] = new (mem, max_non_terminal) BitSet;
304 proj[f][i]->add(0);
305 }
306 }
307 }
309 ///////////////////////////////////////////////////////////////////////////
310 // Compute the projections by going over the terms and
311 // looking up the non-terminals at each argument.
312 ///////////////////////////////////////////////////////////////////////////
313 { foreach (p, non_terminals) {
314 match (non_terminals.key(p)) {
315 case tree_term(f,n,subterms):
316 for (int i = n - 1; i >= 0; i--) {
317 Variable v = non_terminals[ subterms[i] ];
318 if (closure0[v]) proj[f][i]->Union(*closure0[v]);
319 else proj[f][i]->add(v);
320 }
321 case _: // skip
322 }
323 }
324 }
325 }
327 //////////////////////////////////////////////////////////////////////////////
328 // Method to allocate the representer state list for each functor at
329 // each arity. ``Representers'' are simply interesting states.
330 //////////////////////////////////////////////////////////////////////////////
331 void TreeGenerator::compute_representers()
332 { representers = (StateList***)mem.c_alloc(sizeof(StateList**) * (G.max_functor() + 1));
333 for (Functor f = G.min_functor(); f <= G.max_functor(); f++)
334 representers[f] =
335 (StateList**)mem.c_alloc(sizeof(StateList*) * G.arity(f));
336 }
338 //////////////////////////////////////////////////////////////////////////////
339 // Method to compute the accept rules of a state
340 //////////////////////////////////////////////////////////////////////////////
341 void TreeGenerator::compute_accept_rules (State s)
342 { register const BitSet& vars = *d_states.Get( s );
343 register BitSet& rules = treegen.accept_rules(s);
344 register Rule min_rule = G.size();
345 register int v;
346 foreach_bit_fast(v,vars) {
347 Rule r = rule_map[v];
348 if (r >= 0 && r < min_rule) min_rule = r;
349 const BitSet * r_set = ruleset_map[v];
350 if (r_set) rules.Union(*r_set);
351 }
352 if (min_rule == G.size()) min_rule = -1;
353 treegen.set_accept1(s, min_rule);
354 }
356 //////////////////////////////////////////////////////////////////////////////
357 // Method to compute the initial states.
358 // These are the ``wildcard'' or no-information state, state 0.
359 // Followed by a state for each unit functor.
360 //////////////////////////////////////////////////////////////////////////////
361 void TreeGenerator::compute_initial_states()
362 {
363 ///////////////////////////////////////////////////////////////////////////
364 // Create the first state corresponding to the wildcard.
365 ///////////////////////////////////////////////////////////////////////////
366 number_of_states = 0;
367 { BitSet * state_zero = new (mem, max_non_terminal) BitSet;
368 state_zero->add (0);
369 state_labels.insert(state_zero, number_of_states);
370 d_states.At( number_of_states ) = state_zero;
371 d_terms .At( number_of_states ) = new(mem) classof set_term(state_zero);
372 treegen.new_state(0);
373 compute_accept_rules(0);
374 number_of_states++;
375 }
377 ///////////////////////////////////////////////////////////////////////////
378 // Generate the rest of the terminal states formed by unit functors.
379 ///////////////////////////////////////////////////////////////////////////
380 { foreach (i, non_terminals) {
381 match (non_terminals.key(i)) {
382 case tree_term(f,0,_): // use terms with arity 0 only
383 BitSet * new_state = new (mem, max_non_terminal) BitSet;
384 Variable v = non_terminals.value(i);
385 new_state->add(0);
386 if (closure0[v]) new_state->Union(*closure0[v]);
387 else new_state->add(v);
388 state_labels.insert(new_state, number_of_states);
389 d_states.At( number_of_states ) = new_state;
390 d_terms .At( number_of_states ) = set_term'(mem)(new_state);
391 treegen.new_state(number_of_states);
392 treegen.add_delta(f,number_of_states);
393 compute_accept_rules(number_of_states);
394 number_of_states++;
395 case _:
396 }
397 }
398 }
399 }
401 //////////////////////////////////////////////////////////////////////////////
402 // Method to compute transitions.
403 //////////////////////////////////////////////////////////////////////////////
404 void TreeGenerator::compute_transitions()
405 {
406 ///////////////////////////////////////////////////////////////////////////
407 // Some temporary buffers used during this process.
408 ///////////////////////////////////////////////////////////////////////////
409 BitSet * projected [256]; // projected states of arity i
410 Bool is_relevant [256]; // is arity i relevant?
411 State inputs [256]; // input state of arity i
412 int equiv_class [256]; // equivalence class of above.
413 BitSet * T = 0; // current result non-terminal set
414 TreeTerm term = new_term(mem, 0, 255); // current term
416 { for (int i = G.max_arity() - 1; i >= 0; i--)
417 projected[i] = new (mem, max_non_terminal) BitSet;
418 }
420 ///////////////////////////////////////////////////////////////////////////
421 // Compute the transitions of the states. We'll start from state 0.
422 ///////////////////////////////////////////////////////////////////////////
423 for (State current = 0; current < number_of_states; current++) {
424 const BitSet& S = *d_states.Get(current);
426 ////////////////////////////////////////////////////////////////////////
427 // Iterate over all the non-unit functors and compute their transition
428 // function on this new state ``current.''
429 ////////////////////////////////////////////////////////////////////////
430 for (Functor f = G.min_functor(); f <= G.max_functor(); f++) {
431 int n; // arity
432 if ((n = G.arity(f)) == 0) continue;
434 match (term)
435 { tree_term(F, N, _): { F = f; N = n; }
436 | _: { assert("bug"); }
437 }
439 /////////////////////////////////////////////////////////////////////
440 // Compute the projections on the arguments.
441 // If the intersection of S with the ith projection is an old state T,
442 // then the transition with respect to arity ith must be the same
443 // as the state T.
444 /////////////////////////////////////////////////////////////////////
445 for (int i = n - 1; i >= 0; i--) {
446 projected[i]->Intersect(S, *proj[f][i]);
447 projected[i]->add(0);
448 Ix old = state_labels.lookup(projected[i]);
449 State mapped = current;
450 if (old && (mapped = state_labels.value(old)) < current) {
451 is_relevant[i] = false;
452 } else {
453 representers[f][i] = new (mem, mapped, representers[f][i]) StateList;
454 is_relevant[i] = true;
455 }
456 //////////////////////////////////////////////////////////////////
457 // Update the index map ``mu.''
458 //////////////////////////////////////////////////////////////////
459 treegen.add_mu(f,i,current,mapped);
460 }
462 /////////////////////////////////////////////////////////////////////
463 // Now compute the transition function of functor f with respect
464 // to the state ``current.'' Check only the arities that can
465 // produce new information. This is done by fixing all ``relevant''
466 // arities to state ``current'' and the rest to the rest of the
467 // representer states.
468 /////////////////////////////////////////////////////////////////////
469 for (int fix = n - 1; fix >= 0; fix--) {
470 if (! is_relevant[fix]) continue;
471 inputs [ fix ] = current;
472 equiv_class [ fix ] = treegen.index_map(f,fix,current);
473 T = compute_transition(T, term, 0, fix, *projected[fix], inputs, equiv_class);
474 }
475 }
476 }
477 }
479 //////////////////////////////////////////////////////////////////////////////
480 // Method to compute a set of transitions functions.
481 // We iterate over all the representer states.
482 //////////////////////////////////////////////////////////////////////////////
483 BitSet * TreeGenerator::compute_transition
484 ( BitSet * T, // temporary bitset
485 TreeTerm term, // temporary term
486 int i, // current arity to consider
487 int fixed, // the fixed arity
488 const BitSet& S, // input state of the fixed arity
489 State inputs[], // input states
490 int equiv [] // equiv class of above
491 )
492 {
493 if (i == fixed) i++; // skip the fixed arity.
494 match (term)
495 { tree_term(f,n,subterms):
496 {
497 if (i < n) {
498 ////////////////////////////////////////////////////////////////////////
499 // Try arity i == wildcard first
500 ////////////////////////////////////////////////////////////////////////
501 subterms[i] = wild_term;
502 inputs[i] = 0;
503 equiv [i] = 0;
504 T = compute_transition(T, term, i+1, fixed, S, inputs, equiv);
506 //////////////////////////////////////////////////////////////////////
507 // Try arity i == a representer state next.
508 ////////////////////////////////////////////////////////////////////////
509 for (StateList * r = representers[f][i]; r; r = r->tail) {
510 inputs[i] = r->head;
511 equiv [i] = treegen.index_map(f,i,r->head);
512 subterms[i] = d_terms.Get( r->head );
513 T = compute_transition(T, term, i+1, fixed, S, inputs, equiv);
514 }
515 } else {
516 ////////////////////////////////////////////////////////////////////////
517 // Compute the non-terminal set corresponding to the new state.
518 ////////////////////////////////////////////////////////////////////////
519 if (T == 0) T = new (mem, max_non_terminal) BitSet;
520 else T->clear();
521 T->add(0);
522 int v;
523 foreach_bit_fast (v, S) {
524 subterms[ fixed ] = n_states[v];
525 compute_delta(T, term, 0, fixed, inputs);
526 }
528 ////////////////////////////////////////////////////////////////////////
529 // Now, lookup the new state to see if it is a new one.
530 // If so, create a new state.
531 ////////////////////////////////////////////////////////////////////////
532 Ix s;
533 State mapped;
534 if ((s = state_labels.lookup(T))) { // old state
535 mapped = state_labels.value(s);
536 } else { // new state
537 d_states[ number_of_states ] = T;
538 d_terms [ number_of_states ] = new(mem) classof set_term(T);
539 state_labels.insert(T, number_of_states);
540 treegen.new_state(number_of_states);
541 compute_accept_rules(number_of_states);
542 T = 0;
543 mapped = number_of_states++;
544 }
546 ////////////////////////////////////////////////////////////////////////
547 // Update the delta table.
548 ////////////////////////////////////////////////////////////////////////
549 treegen.add_delta(f, equiv, mapped);
550 }
551 }
552 | _: { assert("bug"); }
553 }
554 return T;
555 }
557 //////////////////////////////////////////////////////////////////////////////
558 // Method to compute one delta function
559 //////////////////////////////////////////////////////////////////////////////
560 void TreeGenerator::compute_delta
561 ( BitSet * T, // temporary bitset
562 TreeTerm term, // temporary term
563 int i, // current arity to consider
564 int fixed, // the fixed arity
565 const State inputs[] // input states
566 )
567 { Bool first = i == 0;
568 if (i == fixed) i++;
569 Ix p;
571 if ((p = non_terminals.lookup(term))) {
572 ////////////////////////////////////////////////////////////////////////
573 // Found! use the info from the grammar.
574 ////////////////////////////////////////////////////////////////////////
575 Variable v = non_terminals.value(p);
576 if (closure0[v]) T->Union(*closure0[v]);
577 else T->add(v);
578 } else if ((p = delta.lookup(term))) {
579 ////////////////////////////////////////////////////////////////////////
580 // Found! use the info from the delta map.
581 ////////////////////////////////////////////////////////////////////////
582 T->Union(* delta.value(p));
583 } else {
584 ////////////////////////////////////////////////////////////////////////
585 // Split input state s into subcases and compute the union of all of
586 // them. Memorize individual cases into the map ``delta.''
587 ////////////////////////////////////////////////////////////////////////
588 match (term)
589 { tree_term(f,n,subterms):
590 {
591 if (i < n) {
592 const BitSet& U = *d_states[ inputs[i] ];
593 TreeTerm save = subterms[i];
594 BitSet * V;
595 if (first) V = T;
596 else { V = new (mem, max_non_terminal) BitSet; V->add(0); }
598 int v;
599 foreach_bit_fast (v, U) {
600 subterms [i] = n_states[v];
601 compute_delta(V, term, i + 1, fixed, inputs);
602 }
603 subterms[i] = save;
605 if (! first) {
606 TreeTerm n_term = new_term(mem, f, n, subterms);
607 delta.insert(n_term,V);
608 T->Union(*V);
609 }
610 }
611 }
612 | _: { assert ("bug"); }
613 }
614 }
615 }
617 //////////////////////////////////////////////////////////////////////////////
618 // Method to print a report of the generated tables.
619 //////////////////////////////////////////////////////////////////////////////
620 std::ostream& TreeGenerator::print_report(std::ostream& log) const
621 {
622 ///////////////////////////////////////////////////////////////////////////
623 // (1) Print the item set.
624 ///////////////////////////////////////////////////////////////////////////
625 { log << "\nItems:\n";
626 for (Variable v = 0; v < max_non_terminal; v++) {
627 log << '{' << v << "}\t";
628 G.print(log, n_states[v]) << '\n';
629 }
630 }
632 ///////////////////////////////////////////////////////////////////////////
633 // (2) Print each state
634 ///////////////////////////////////////////////////////////////////////////
635 { log << "\nStates:\n";
636 for (State s = 0; s < number_of_states; s++) {
637 print_state(log,s);
638 }
639 }
640 return log;
641 }
643 //////////////////////////////////////////////////////////////////////////////
644 // Method to print a state
645 //////////////////////////////////////////////////////////////////////////////
646 std::ostream& TreeGenerator::print_state(std::ostream& log, State s) const
647 {
648 log << '<' << s << '>';
649 const BitSet& S = *d_states[s];
650 Variable v;
651 foreach_bit(v,S) G.print(log << '\t', n_states[v]) << '\n';
652 if (treegen.is_accept_state(s))
653 log << "\t[accept " << treegen.accept1_rule(s) << "]\n";
654 return log;
655 }
657 //////////////////////////////////////////////////////////////////////////////
658 // Client visible methods follow.
659 // All the work has been down by the class TreeGenerator.
660 // Class TreeGen simply ties things up together.
661 //////////////////////////////////////////////////////////////////////////////
663 //////////////////////////////////////////////////////////////////////////////
664 // Constructors and destructor of the class TreeGen.
665 //////////////////////////////////////////////////////////////////////////////
666 TreeGen:: TreeGen(Mem& m) : TreeAutomaton(m), impl(0) {}
667 TreeGen:: TreeGen(Mem& m, TreeGrammar& Gram)
668 : TreeAutomaton(m), impl(0) { compile(Gram); }
669 TreeGen::~TreeGen() { delete impl; }
671 //////////////////////////////////////////////////////////////////////////////
672 // This is the top level method to compile a tree grammar.
673 //////////////////////////////////////////////////////////////////////////////
674 void TreeGen::compile (TreeGrammar& Gram)
675 {
676 ///////////////////////////////////////////////////////////////////////////
677 // Let our superclass do its stuff first.
678 ///////////////////////////////////////////////////////////////////////////
679 Super::compile(Gram);
681 ///////////////////////////////////////////////////////////////////////////
682 // The internal representation is defined here.
683 ///////////////////////////////////////////////////////////////////////////
684 delete impl;
685 impl = new TreeGenerator(*this,Gram);
687 ///////////////////////////////////////////////////////////////////////////
688 // Now carry out the various steps.
689 ///////////////////////////////////////////////////////////////////////////
690 impl->assign_non_terminals(); // assign unique non-terminal names.
691 impl->compute_closures(); // compute transitive closures of non-terminals.
692 impl->compute_projections(); // compute the projections on functors.
693 impl->compute_representers(); // allocate the representor states.
694 impl->compute_initial_states(); // compute the initial states first.
695 impl->compute_transitions(); // compute the rest of the transitions.
696 }
698 //////////////////////////////////////////////////////////////////////////////
699 // Method to print a report of the generated tables.
700 //////////////////////////////////////////////////////////////////////////////
701 std::ostream& TreeGen::print_report(std::ostream& log) const
702 { Super::print_report(log);
703 if (impl) impl->print_report(log);
704 return log;
705 }
707 //////////////////////////////////////////////////////////////////////////////
708 // Method to print a state of the generated tables.
709 //////////////////////////////////////////////////////////////////////////////
710 std::ostream& TreeGen::print_state(std::ostream& log, State s) const
711 { if (impl) impl->print_state(log,s);
712 return log;
713 }
715 //////////////////////////////////////////////////////////////////////////////
716 // Algorithm name
717 //////////////////////////////////////////////////////////////////////////////
718 const char * TreeGen::algorithm() const { return "TreeGen"; }