lib-src/automata/treegen.pcc

   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 //////////////////////////////////////////////////////////////////////////////
  24
  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
  34
  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;
  46
  47 //////////////////////////////////////////////////////////////////////////////
  48 //  Class TreeGenerator represents the internals of the automata compiler.
  49 //  This stuff is completely hidden from the interface.
  50 //////////////////////////////////////////////////////////////////////////////
  51 class TreeGenerator {
  52
  53    TreeGenerator(const TreeGenerator&);    // no copy constructor
  54    void operator = (const TreeGenerator&); // no assignment
  55
  56 public:
  57
  58    ///////////////////////////////////////////////////////////////////////////
  59    //  Internal data structures
  60    ///////////////////////////////////////////////////////////////////////////
  61
  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;
  78
  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) {}
  85
  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 };
 102
 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    }
 118
 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    }
 126
 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 }
 143
 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    }
 164
 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 }
 187
 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);
 207
 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    }
 217
 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;
 225
 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);
 232
 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          }
 244
 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       }
 268
 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 }
 287
 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    }
 308
 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 }
 326
 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 }
 337
 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 }
 355
 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    }
 376
 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 }
 400
 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
 415
 416    {  for (int i = G.max_arity() - 1; i >= 0; i--)
 417          projected[i] = new (mem, max_non_terminal) BitSet;
 418    }
 419
 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);
 425
 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;
 433
 434          match (term)
 435          {  tree_term(F, N, _): {  F = f; N = n; }
 436          |  _:                  {  assert("bug"); }
 437          }
 438
 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          }
 461
 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 }
 478
 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);
 505
 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          }
 527
 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          }
 545
 546          ////////////////////////////////////////////////////////////////////////
 547          //  Update the delta table.
 548          ////////////////////////////////////////////////////////////////////////
 549          treegen.add_delta(f, equiv, mapped);
 550       }
 551    }
 552    | _:  { assert("bug"); }
 553    }
 554    return T;
 555 }
 556
 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;
 570
 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); }
 597
 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;
 604
 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 }
 616
 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    }
 631
 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 }
 642
 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 }
 656
 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 //////////////////////////////////////////////////////////////////////////////
 662
 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; }
 670
 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);
 680
 681    ///////////////////////////////////////////////////////////////////////////
 682    //  The internal representation is defined here.
 683    ///////////////////////////////////////////////////////////////////////////
 684    delete impl;
 685    impl = new TreeGenerator(*this,Gram);
 686
 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 }
 697
 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 }
 706
 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 }
 714
 715 //////////////////////////////////////////////////////////////////////////////
 716 //  Algorithm name
 717 //////////////////////////////////////////////////////////////////////////////
 718 const char * TreeGen::algorithm() const { return "TreeGen"; }