lib-src/rewrite/burs_gen.cc

   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 //////////////////////////////////////////////////////////////////////////////
  26 //  In the following we'll implement a bottom up rewrite system (BURS)
  27 //  generator using Proebsting's algorithm(see. PLDI '92).
  28 //  Our implementation is rather by the book, aside from the use of
  29 //  slightly different data structures.
  30 //
  31 //  Here are some of the data structures that we'll be using
  32 //
  33 //  VarArray<T>      --- variable sized array that grows itself automatically.
  34 //  LHashTable<K,V>  --- Hash table with linear probing.
  35 //  BURS_Item        --- an item in the tree grammar.
  36 //  BURS_ItemSet     --- a set of items.
  37 //////////////////////////////////////////////////////////////////////////////
  38 #include <iostream.h>
  39 #define TreeGrammar_Iterators
  40 #include <AD/rewrite/burs_gen.h>   // the BURS generator definition
  41 #include <AD/rewrite/b_items.h>    // the BURS item sets
  42 #include <AD/rewrite/b_rules.h>    // the BURS rule set
  43 #include <AD/contain/vararray.h>   // dynamic arrays
  44 #include <AD/contain/slnklist.h>   // very simple singly linked list
  45 #include <AD/hash/lhash.h>         // linear probing hash tables
  46
  47 //////////////////////////////////////////////////////////////////////////////
  48 //  Make hidden types visible for our use.
  49 //////////////////////////////////////////////////////////////////////////////
  50 typedef BURS_Gen::State              State;          // states in tree automata
  51 typedef BURS_Gen::Functor            Functor;        // functors
  52 typedef BURS_Gen::NonTerminal        NonTerminal;    // nonterminals
  53 typedef BURS_Gen::Arity              Arity;          // functor arities
  54 typedef BURS_Gen::Rule               Rule;           // reduction rules
  55 typedef BURS_Gen::Cost               Cost;           // reduction cost
  56 typedef BURS_ItemSet::NonTerminalSet NonTerminalSet; // a set of non-terminals
  57 typedef BURS_RuleSet::Reduction      Reduction;      // reduction rule
  58 typedef BURS_RuleSet::ReductionList  ReductionList;  // a list of reductions
  59 typedef SLinkList<State>             Reps;           // representer list
  60
  61 //////////////////////////////////////////////////////////////////////////////
  62 //  Internal representation of class BURS_Gen
  63 //////////////////////////////////////////////////////////////////////////////
  64 class BURS_Generator {
  65
  66    BURS_Generator(const BURS_Generator&);   // no copy constructor
  67    void operator = (const BURS_Generator&); // no assignment
  68
  69 private:
  70
  71    ///////////////////////////////////////////////////////////////////////////
  72    //  Internal data structures.
  73    ///////////////////////////////////////////////////////////////////////////
  74    Mem&                               mem;       // The memory pool
  75    const TreeGrammar&                 G;         // The tree grammar
  76    const BURS_RuleSet                 R;         // The rule set
  77    BURS_Gen&                          gen;       // The BURS generator
  78    VarArray<const BURS_ItemSet *>     states;    // State -> BURS_ItemSet
  79    LHashTable<BURS_ItemSet *, State>  state_map; // BURS_ItemSet -> State
  80    NonTerminalSet **                  closure;   // NonTerminal -> NonTerminalSet
  81    NonTerminalSet ***                 proj;      // Functor x Arity -> NonTerminalSet
  82    State                      number_of_states;  // number of states
  83    int                 number_of_non_terminals;  // number of non-terminals
  84    Reps ***                       representers;  // Functor x Arity -> Reps
  85    BURS_ItemSet *                     item_set;  // current item set
  86    BURS_ItemSet *                    delta_set;  // current delta set
  87    int                             inputs[256];  // current input states
  88    int                               mu_s[256];  // current input mu
  89    Bool                               complete;  // rules are complete?
  90
  91 public:
  92
  93    ///////////////////////////////////////////////////////////////////////////
  94    //  Constructor and destructor
  95    ///////////////////////////////////////////////////////////////////////////
  96    BURS_Generator(Mem& m, const TreeGrammar& g, BURS_Gen& gn)
  97       : mem(m),
  98         G(g),
  99         R(m,g),
 100         gen(gn),
 101         state_map(4097,0.4),
 102         number_of_states(0),
 103         number_of_non_terminals(R.number_of_non_terminals()),
 104         item_set(0),
 105         delta_set(0)
 106         {}
 107   ~BURS_Generator() {}
 108
 109    ///////////////////////////////////////////////////////////////////////////
 110    //  Methods for table generation.
 111    ///////////////////////////////////////////////////////////////////////////
 112    void compute_closures        ();
 113    void compute_projections     ();
 114    void allocate_representers   ();
 115    void compute_closure         ( BURS_ItemSet& );
 116    void compute_projection      ( BURS_ItemSet&, Functor, Arity, State);
 117    void compute_accept_rules    ( State, const BURS_ItemSet& );
 118    void compute_leaf_states     ();
 119    void compute_non_leaf_states ();
 120    void compute_transitions     (State);
 121    void compute_transitions     (Functor, Arity, Arity, Arity);
 122    void compute_delta           (Functor, Arity, Arity);
 123    Cost triangular_cost         (Functor, Functor) const;
 124    void trim                    ( BURS_ItemSet& );
 125
 126    ///////////////////////////////////////////////////////////////////////////
 127    //  Check for completeness
 128    ///////////////////////////////////////////////////////////////////////////
 129    inline Bool is_complete() const { return complete; }
 130
 131    ///////////////////////////////////////////////////////////////////////////
 132    //  Methods for printing a report
 133    ///////////////////////////////////////////////////////////////////////////
 134    ostream& print (ostream&, const BURS_ItemSet&) const;
 135    friend ostream& operator << (ostream&, const BURS_Generator&);
 136    ostream& print_state(ostream&, State) const;
 137 };
 138
 139 //////////////////////////////////////////////////////////////////////////////
 140 //  Method to compute closures on all nonterminals.
 141 //  i.e.  for each non-terminal X, compute closure(X).
 142 //  closure(X) = { X } + { A | A -> X in G }
 143 //////////////////////////////////////////////////////////////////////////////
 144 void BURS_Generator::compute_closures()
 145 {
 146    ///////////////////////////////////////////////////////////////////////////
 147    //  First, allocate the closure table.
 148    //  One for each non-terminal in the grammar.
 149    ///////////////////////////////////////////////////////////////////////////
 150    {  closure = (NonTerminalSet **)
 151          mem.c_alloc(sizeof(NonTerminalSet *) * number_of_non_terminals);
 152    }
 153
 154    ///////////////////////////////////////////////////////////////////////////
 155    //  Now, compute the non-terminals closure iteratively over the chain rules
 156    //  until the least fixed point is reached.
 157    ///////////////////////////////////////////////////////////////////////////
 158    {  Bool changed;
 159       do {
 160          changed = false;
 161          for (int r = R.number_of_chain_rules() - 1; r >= 0; r--) {
 162             NonTerminal lhs = R.chain_rule(r).lhs;
 163             NonTerminal rhs = R.chain_rule(r).rhs;
 164             if (closure[rhs] == 0) {
 165                closure[rhs] = new (mem, number_of_non_terminals) NonTerminalSet;
 166                closure[rhs]->add(0);   // the wild card
 167                closure[rhs]->add(rhs); // and itself (duh!)
 168             }
 169             if (closure[lhs]) {
 170                if (closure[rhs]->Union_if_changed(*closure[lhs])) changed = true;
 171             } else {
 172                if (closure[rhs]->add_if_changed(lhs)) changed = true;
 173             }
 174          }
 175       } while (changed);
 176    }
 177 }
 178
 179 //////////////////////////////////////////////////////////////////////////////
 180 //  Method to compute projections on all arities of all functors.
 181 //  For each functor f and arity i, compute
 182 //       closure( { x_i | f ( ...., x_i, .... ) } )
 183 //////////////////////////////////////////////////////////////////////////////
 184 void BURS_Generator::compute_projections()
 185 {
 186    ///////////////////////////////////////////////////////////////////////////
 187    //  First, allocate the projection table.
 188    ///////////////////////////////////////////////////////////////////////////
 189    proj = (NonTerminalSet ***)
 190       mem.c_alloc(sizeof(NonTerminalSet **) * (G.max_functor() + 1));
 191    foreach_non_unit_functor (f,G) {
 192       proj[f] = (NonTerminalSet**)
 193          mem.c_alloc(sizeof(NonTerminalSet*) * G.arity(f));
 194       foreach_arity (i, f, G) {
 195          proj[f][i] = new(mem,number_of_non_terminals) NonTerminalSet;
 196          proj[f][i]->add(0);
 197       }
 198    }
 199
 200    ///////////////////////////////////////////////////////////////////////////
 201    //  Now compute the projection map.
 202    ///////////////////////////////////////////////////////////////////////////
 203    for (int r = R.number_of_reductions() - 1; r >= 0; r--) {
 204       Functor f = R.reduction(r).f;
 205       for (int i = R.reduction(r).n - 1; i >= 0; i--) {
 206          NonTerminal n = R.reduction(r).rhs[i];
 207          //
 208          //  We may have to take the closure of a non-terminal.
 209          //  Notice that if the non-terminal 'n' is in the projection, we
 210          //  don't bother to take the closure of that since it must be already
 211          //  in the set.
 212          //
 213          if (closure[n] && ! proj[f][i]->contains(n))
 214             proj[f][i]->Union (*closure[n]);
 215          else
 216             proj[f][i]->add (n);
 217       }
 218    }
 219 }
 220
 221 //////////////////////////////////////////////////////////////////////////////
 222 //  Method to allocate storage for representer lists, one for
 223 //  each non-unit functor at each arity position.
 224 //////////////////////////////////////////////////////////////////////////////
 225 void BURS_Generator::allocate_representers()
 226 {  representers = (Reps ***)mem.c_alloc(sizeof(Reps**) * (G.max_functor() + 1));
 227    foreach_non_unit_functor (f,G) {
 228       representers[f] = (Reps**)mem.c_alloc(sizeof(Reps*) * G.arity(f));
 229    }
 230 }
 231
 232 //////////////////////////////////////////////////////////////////////////////
 233 //  Method to compute the closure of a state and its least cost reduction
 234 //  using a dynamic programming algorithm.
 235 //////////////////////////////////////////////////////////////////////////////
 236 void BURS_Generator::compute_closure(register BURS_ItemSet& state)
 237 {  Bool changed;
 238    do {
 239       changed = false;
 240       for (int r = 0; r < R.number_of_chain_rules(); r++) {
 241          ////////////////////////////////////////////////////////////////////
 242          // Given a chain rule ``A -> B'' with cost c, we try to
 243          // find a less expensive reduction going back to A from B.
 244          ////////////////////////////////////////////////////////////////////
 245          NonTerminal A = R.chain_rule(r).lhs;
 246          NonTerminal B = R.chain_rule(r).rhs;
 247          Cost cost = R.chain_rule(r).cost + state[ B ].cost;
 248          if (cost < state[ A ].cost) {
 249             state[ A ].cost = cost;
 250             state[ A ].rule = R.chain_rule(r).rule;
 251             changed = true;
 252          }
 253       }
 254    } while (changed);
 255 }
 256
 257 //////////////////////////////////////////////////////////////////////////////
 258 //  Method to compute a projection on a state
 259 //////////////////////////////////////////////////////////////////////////////
 260 void BURS_Generator::compute_projection
 261    ( register BURS_ItemSet& projected, Functor f, Arity i, State s)
 262 {  register const BURS_ItemSet&   state = *states[s];
 263    register const NonTerminalSet& set   = *proj[f][i];
 264    for(register NonTerminal n = state.size() - 1; n >= 0; n--) {
 265       if (set[n]) {
 266          projected[n] = state[n];
 267       } else {
 268          projected[n].cost = BURS_ItemSet::infinite_cost;
 269       }
 270    }
 271 }
 272
 273 //////////////////////////////////////////////////////////////////////////////
 274 //  Method to compute the set of accept rules for each state
 275 //////////////////////////////////////////////////////////////////////////////
 276 void BURS_Generator::compute_accept_rules(State s, const BURS_ItemSet& items)
 277 {
 278    Rule min_cost_rule  = G.size();  // first rule with the minimal cost
 279    Cost min_cost       = BURS_ItemSet::infinite_cost;
 280
 281    BitSet& rules = gen.accept_rules(s);
 282    for (register NonTerminal A = items.size() - 1; A > 0; A--) {
 283       if (items[A].cost != BURS_ItemSet::infinite_cost &&
 284           items[A].rule >= 0) {
 285          rules.add (items[A].rule);
 286          if (items[A].cost <= min_cost && items[A].rule < min_cost_rule) {
 287             min_cost_rule  = items[A].rule;
 288             min_cost       = items[A].cost;
 289          }
 290       }
 291    }
 292
 293    if (min_cost_rule == G.size()) min_cost_rule = -1;
 294    gen.set_accept1(s, min_cost_rule, min_cost);
 295 }
 296
 297 //////////////////////////////////////////////////////////////////////////////
 298 //  Method to generate the initial leaf states.
 299 //////////////////////////////////////////////////////////////////////////////
 300 void BURS_Generator::compute_leaf_states()
 301 {
 302    ///////////////////////////////////////////////////////////////////////////
 303    //  Enter the default error state
 304    ///////////////////////////////////////////////////////////////////////////
 305    {  BURS_ItemSet * error_state = new (mem, number_of_non_terminals) BURS_ItemSet;
 306       gen.new_state(number_of_states);
 307       compute_closure(*error_state);
 308       states[ number_of_states ] = error_state;
 309       state_map.insert(error_state, number_of_states);
 310       compute_accept_rules(number_of_states, *error_state);
 311       number_of_states++;
 312    }
 313
 314    ///////////////////////////////////////////////////////////////////////////
 315    //  Generate all states corresponding to the unit functors
 316    //  (i.e. leaves) in the tree grammar.
 317    ///////////////////////////////////////////////////////////////////////////
 318    foreach_unit_functor (f, G) {
 319       gen.new_state(number_of_states);
 320       BURS_ItemSet * s = new (mem, number_of_non_terminals) BURS_ItemSet;
 321       Bool found = false;
 322       for (int r = R.number_of_leaf_reductions() - 1; r >= 0; r--) {
 323          if (R.leaf(r).f != f) continue;
 324          NonTerminal lhs = R.leaf(r).lhs;
 325          (*s)[lhs].cost = R.leaf(r).cost;
 326          (*s)[lhs].rule = R.leaf(r).rule;
 327          found = true;
 328       }
 329       if (found) {
 330          s->normalise_costs();
 331          compute_closure(*s);
 332          states[ number_of_states ] = s;
 333          state_map.insert(s, number_of_states);
 334          gen.add_delta(f, number_of_states);
 335          compute_accept_rules(number_of_states, *s);
 336          number_of_states++;
 337       } else {
 338          gen.add_delta(f, 0);
 339       }
 340    }
 341 }
 342
 343 //////////////////////////////////////////////////////////////////////////////
 344 //  Method to compute the rest of the states
 345 //////////////////////////////////////////////////////////////////////////////
 346 void BURS_Generator::compute_non_leaf_states()
 347 {
 348    ///////////////////////////////////////////////////////////////////////////
 349    //  First, compute the set of states.
 350    ///////////////////////////////////////////////////////////////////////////
 351    for (State s = 0; s < number_of_states; s++) {
 352       // cerr << "At state " << s << ":\t"; print(cerr,*states[s]);
 353       compute_transitions(s);
 354    }
 355    ///////////////////////////////////////////////////////////////////////////
 356    //  Then check for completeness: i.e. there isn't an empty state item set.
 357    ///////////////////////////////////////////////////////////////////////////
 358    // BURS_ItemSet * empty_set = new (mem, number_of_non_terminals) BURS_ItemSet;
 359    // complete = ! state_map.contains(empty_set);
 360 }
 361
 362 //////////////////////////////////////////////////////////////////////////////
 363 //  Method to compute the transitions from a state.
 364 //////////////////////////////////////////////////////////////////////////////
 365 void BURS_Generator::compute_transitions(State s)
 366 {
 367    // Lookup the item set for the current state
 368    // const BURS_ItemSet& state = *states[s];
 369
 370    //////////////////////////////////////////////////////////////////////////
 371    // Allocate a new item set if we don't already have one.
 372    //////////////////////////////////////////////////////////////////////////
 373    if (item_set == 0) item_set = new (mem, number_of_non_terminals) BURS_ItemSet;
 374    else               item_set->clear();
 375
 376    foreach_functor (f, G) {
 377       int n = G.arity(f);   // arity of f
 378       for (int i = 0; i < n; i++) {
 379          ////////////////////////////////////////////////////////////////////
 380          // Compute the projection on functor f on arity i
 381          ////////////////////////////////////////////////////////////////////
 382          compute_projection(*item_set, f, i, s);
 383
 384          ////////////////////////////////////////////////////////////////////
 385          // Update the representer states if the projection is
 386          // not found to be in our list.
 387          ////////////////////////////////////////////////////////////////////
 388          State d = s;  // delta state
 389          Ix old = state_map.lookup(item_set);
 390          // if (old == 0 || (d = state_map.value(old)) >= s) {
 391          if (old == 0 || (d = state_map.value(old)) == s) {
 392             gen.add_mu(f, i, s, d);
 393             //
 394             // This is an interesting state; update representer list
 395             // and compute transition info.
 396             //
 397             representers[f][i] = new (mem, s, representers[f][i]) Reps;
 398
 399             inputs[i] = s;                      // input state of arity i
 400             mu_s[i]   = gen.index_map(f, i, s); // input state of arity i
 401             compute_transitions(f, i, 0, n);
 402          } else {
 403             gen.add_mu(f, i, s, d);
 404          }
 405       }
 406    }
 407 }
 408
 409 //////////////////////////////////////////////////////////////////////////////
 410 //  Method to compute the transitions of a functor on a state
 411 //  when one of the arity is fixed.
 412 //////////////////////////////////////////////////////////////////////////////
 413 void BURS_Generator::compute_transitions
 414    ( Functor        f,        // functor f
 415      Arity          fixed,    // arity of f to be fixed
 416      Arity          i,        // arity index from 0 to n - 1
 417      Arity          n         // arity of f
 418    )
 419 {  if (i == fixed) i++;
 420    if (i < n) {
 421       for (Reps * l = representers[f][i]; l; l = l->tail) {
 422          mu_s[i] = gen.index_map(f, i, inputs[i] = l->head);
 423          compute_transitions(f, fixed, i + 1, n);
 424       }
 425    } else {
 426       compute_delta(f, fixed, n);
 427    }
 428 }
 429
 430 //////////////////////////////////////////////////////////////////////////////
 431 //  Method to compute the transition state of one input configuration
 432 //////////////////////////////////////////////////////////////////////////////
 433 void BURS_Generator::compute_delta(Functor f, Arity fixed, Arity n)
 434 {  if (delta_set) delta_set->clear();
 435    else delta_set = new (mem, number_of_non_terminals) BURS_ItemSet;
 436
 437    ///////////////////////////////////////////////////////////////////////////
 438    //  Compute the transition state of f, and its associated cost.
 439    ///////////////////////////////////////////////////////////////////////////
 440    for (const ReductionList * rs = R.reductions_of(f); rs; rs = rs->tail) {
 441       const Reduction * r = rs->head;
 442       long cost = r->cost + (*item_set)[ r->rhs[ fixed ] ].cost;
 443       for (int i = 0; i < n; i++)
 444       {  if (i != fixed) cost += (*states[ inputs[i] ])[r->rhs[i]].cost;
 445       }
 446       if (cost < (*delta_set)[r->lhs].cost) {
 447          (*delta_set)[r->lhs].cost = cost;
 448          (*delta_set)[r->lhs].rule = r->rule;
 449       }
 450    }
 451    // cerr << "Delta (" << f << ", " << n << "):\t"; print(cerr,*delta_set);
 452
 453    ///////////////////////////////////////////////////////////////////////////
 454    //  Use triangle trimming to eliminate unnecessary non-terminals.
 455    //  Normalise the cost.
 456    ///////////////////////////////////////////////////////////////////////////
 457    trim( *delta_set );                     // trim unnecessary non-terminals
 458    delta_set->normalise_costs();           // normalise costs
 459    // cerr << "Delta[1] (" << f << ", " << n << "):\t"; print(cerr,*delta_set);
 460    compute_closure( *delta_set );          // compute closure
 461    // cerr << "Delta[2] (" << f << ", " << n << "):\t"; print(cerr,*delta_set);
 462    Ix found = state_map.lookup(delta_set);
 463    State d;
 464
 465    ///////////////////////////////////////////////////////////////////////////
 466    //  If the delta set is not found in the state map, we have a new state
 467    //  to consider.
 468    ///////////////////////////////////////////////////////////////////////////
 469    if (! found) {
 470       // compute_closure( *delta_set );
 471       gen.new_state (number_of_states);
 472       compute_accept_rules(number_of_states, *delta_set);
 473       states[ number_of_states ] = delta_set;
 474       state_map.insert(delta_set, number_of_states);
 475       d = number_of_states++;
 476       // cerr << "State " << d << ":\t"; print(cerr,*delta_set);
 477       delta_set = 0;  // remove it, so that we'll won't accidentally reuse it
 478    } else {
 479       d = state_map.value(found);
 480    }
 481
 482    ///////////////////////////////////////////////////////////////////////////
 483    // Update the delta table
 484    ///////////////////////////////////////////////////////////////////////////
 485    gen.add_delta(f, mu_s, d);
 486 }
 487
 488 //////////////////////////////////////////////////////////////////////////////
 489 //  Method to trim an item set to remove unnecessary non-terminals.
 490 //////////////////////////////////////////////////////////////////////////////
 491 void BURS_Generator::trim (BURS_ItemSet& /*set*/)
 492 {  // optimization (currently unimplemented)
 493 }
 494
 495 //////////////////////////////////////////////////////////////////////////////
 496 //  Method to print an item set.
 497 //  e.g. in format such as:
 498 //    [ A : 1, B : 2, C : 5 ]
 499 //////////////////////////////////////////////////////////////////////////////
 500 ostream& BURS_Generator::print (ostream& f, const BURS_ItemSet& set) const
 501 {  Bool first = true;
 502    for (NonTerminal n = 0; n < set.size(); n++) {
 503       if (set[n].cost != BURS_ItemSet::infinite_cost) {
 504          if (! first) f << '\t';
 505          R.print(f,n);
 506          if (set[n].cost > 0) f << "\t(cost " << set[n].cost << ")";
 507          if (n > 0 && set[n].rule >= 0) f << "\t[rule " << set[n].rule << "]";
 508          f << "\n";
 509          first = false;
 510       }
 511    }
 512    return f;
 513 }
 514
 515 //////////////////////////////////////////////////////////////////////////////
 516 //  Method to print a report on a stream.
 517 //////////////////////////////////////////////////////////////////////////////
 518 ostream& operator << (ostream& f, const BURS_Generator& g)
 519 {
 520    // Print the set of states
 521    f << "Canonical rules:\n" << g.R << '\n'
 522      << "States:\n";
 523    for (State s = 0; s < g.number_of_states; s++) {
 524       g.print_state(f,s);
 525    }
 526    return f;
 527 }
 528
 529 //////////////////////////////////////////////////////////////////////////////
 530 //  Method to print a state on a stream.
 531 //////////////////////////////////////////////////////////////////////////////
 532 ostream& BURS_Generator::print_state(ostream& f, State s) const
 533 {  f << '[' << s << "]\t"; print(f,*states[s]);
 534    if (gen.is_accept_state(s))
 535       f << "\t[accept " << gen.accept1_rule(s) << "]\n";
 536    return f;
 537 }
 538
 539 //////////////////////////////////////////////////////////////////////////////
 540 // In the following section we'll implement the class BURS_Gen.
 541 // Methods within this class just invoke BURS_Generator's methods
 542 // to do the dirty work.  Basically this class just ties all the
 543 // methods things together and check for errors.
 544 //////////////////////////////////////////////////////////////////////////////
 545
 546 //////////////////////////////////////////////////////////////////////////////
 547 //  Constructors and destructor
 548 //////////////////////////////////////////////////////////////////////////////
 549 BURS_Gen:: BURS_Gen( Mem& m ) : Super(m), impl(0) {}
 550 BURS_Gen:: BURS_Gen( Mem& m, TreeGrammar& g) : Super(m), impl(0) { compile(g); }
 551 BURS_Gen::~BURS_Gen() { clear(); }
 552
 553 //////////////////////////////////////////////////////////////////////////////
 554 //  Method to clean up by deleting the internal representation.
 555 //////////////////////////////////////////////////////////////////////////////
 556 void BURS_Gen::clear() { delete impl; impl = 0; }
 557
 558 //////////////////////////////////////////////////////////////////////////////
 559 //  Method to compile a tree grammar
 560 //////////////////////////////////////////////////////////////////////////////
 561 void BURS_Gen::compile(TreeGrammar& g)
 562 {
 563    ///////////////////////////////////////////////////////////////////////////
 564    //  Create a new implementation of the generator.
 565    //  Make sure that if compile() is used again we'll recycle the old
 566    //  implementation..
 567    ///////////////////////////////////////////////////////////////////////////
 568    clear();
 569    impl = new BURS_Generator (mem, g, *this);
 570
 571    ///////////////////////////////////////////////////////////////////////////
 572    //  Call our super class to so that it can do its own work generating
 573    //  the arity and other tables.
 574    ///////////////////////////////////////////////////////////////////////////
 575    Super::compile(g);
 576
 577    ///////////////////////////////////////////////////////////////////////////
 578    //  Compute the states and generate the tables.
 579    ///////////////////////////////////////////////////////////////////////////
 580    impl->compute_closures();        // compute closures of all non-terminals
 581    impl->compute_projections();     // compute projections of all functors
 582    impl->allocate_representers();   // allocate the representer lists
 583    impl->compute_leaf_states();     // compute the leaf states
 584    impl->compute_non_leaf_states(); // now compute the rest
 585 }
 586
 587 //////////////////////////////////////////////////////////////////////////////
 588 //  Method to check whether the set of rewrite rules is complete.
 589 //////////////////////////////////////////////////////////////////////////////
 590 Bool BURS_Gen::is_complete() const
 591 {  return impl && impl->is_complete(); }
 592
 593 //////////////////////////////////////////////////////////////////////////////
 594 //  Method to generate a new report
 595 //////////////////////////////////////////////////////////////////////////////
 596 ostream& BURS_Gen::print_report(ostream& log) const
 597 {  if (impl) {
 598       Super::print_report(log);
 599       log << *impl;
 600    }
 601    return log;
 602 }
 603
 604 //////////////////////////////////////////////////////////////////////////////
 605 //  Method to generate a state
 606 //////////////////////////////////////////////////////////////////////////////
 607 ostream& BURS_Gen::print_state(ostream& log, State s) const
 608 {  if (impl) impl->print_state(log,s);
 609    return log;
 610 }
 611
 612 //////////////////////////////////////////////////////////////////////////////
 613 //  Algorithm name
 614 //////////////////////////////////////////////////////////////////////////////
 615 const char * BURS_Gen::algorithm () const { return "BURS_Gen"; }