lib-src/rewrite/b_rules.pcc.old

   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 #define TreeGrammar_Iterators
  26 #include <iostream.h>
  27 #include <string.h>
  28 #include <AD/automata/treegram.ph>
  29 #include <assert.h>
  30 #include <AD/rewrite/b_rules.h>
  31 #include <AD/hash/dchash.h>
  32
  33 //////////////////////////////////////////////////////////////////////////////
  34 //
  35 //  Make hidden types visible for use.
  36 //
  37 //////////////////////////////////////////////////////////////////////////////
  38 typedef TreeGrammar::Functor        Functor;
  39 typedef TreeGrammar::NonTerminal    NonTerminal;
  40 typedef TreeGrammar::Rule           Rule;
  41 typedef TreeGrammar::Cost           Cost;
  42 typedef BURS_RuleSet::LeafReduction LeafReduction;
  43 typedef BURS_RuleSet::Reduction     Reduction;
  44 typedef BURS_RuleSet::ChainRule     ChainRule;
  45
  46 //////////////////////////////////////////////////////////////////////////////
  47 //
  48 //  Hash functions and equality functions for leaf reductions.
  49 //
  50 //////////////////////////////////////////////////////////////////////////////
  51 inline Bool equal (const LeafReduction * a, const LeafReduction * b)
  52 {  return a->f == b->f && a->cost == b->cost && a->rule == b->rule;
  53 }
  54 inline unsigned hash (const LeafReduction * a)
  55 {  return a->f + a->cost + a->rule; }
  56
  57 //////////////////////////////////////////////////////////////////////////////
  58 //
  59 //  Hash functions and equality functions for non-leaf reductions.
  60 //
  61 //////////////////////////////////////////////////////////////////////////////
  62 inline Bool equal (const Reduction * a, const Reduction * b)
  63 {  if (a->f != b->f || a->cost != b->cost ||
  64        a->rule != b->rule || a->n != b->n) return false;
  65    for (int i = a->n - 1; i >= 0; i--)
  66       if (a->rhs[i] != b->rhs[i]) return false;
  67    return true;
  68 }
  69 inline unsigned hash (const Reduction * a)
  70 {  unsigned h = a->f + a->cost + a->rule + a->n;
  71    for (int i = a->n - 1; i >= 0; i--) h += a->rhs[i];
  72    return h;
  73 }
  74
  75 //////////////////////////////////////////////////////////////////////////////
  76 //
  77 //  Hash functions and equality functions for chain reductions.
  78 //
  79 //////////////////////////////////////////////////////////////////////////////
  80 inline Bool equal (const ChainRule * a, const ChainRule * b)
  81 {  return a->rhs == b->rhs && a->cost == b->cost && a->rule == b->rule;
  82 }
  83 inline unsigned hash (const ChainRule * a)
  84 {  return a->rhs + a->cost + a->rule; }
  85
  86 //////////////////////////////////////////////////////////////////////////////
  87 //
  88 // Internal implementation
  89 //
  90 //////////////////////////////////////////////////////////////////////////////
  91 class BURS_RuleSet_Impl {
  92    BURS_RuleSet_Impl(const BURS_RuleSet_Impl&);
  93    void operator = (const BURS_RuleSet_Impl&);
  94 public:
  95    DCHashTable <LeafReduction *, int> leaf_map;
  96    DCHashTable <Reduction *,     int> non_leaf_map;
  97    DCHashTable <ChainRule *,     int> chain_rule_map;
  98    inline  BURS_RuleSet_Impl() {}
  99    inline ~BURS_RuleSet_Impl() {}
 100 };
 101
 102 //////////////////////////////////////////////////////////////////////////////
 103 //
 104 //  Constructor and destructor
 105 //
 106 //////////////////////////////////////////////////////////////////////////////
 107 BURS_RuleSet:: BURS_RuleSet( Mem& mem, const TreeGrammar& g) : G(g)
 108 {
 109     ///////////////////////////////////////////////////////////////////////////
 110     // Create a new set of hash tables.
 111     ///////////////////////////////////////////////////////////////////////////
 112     impl = new BURS_RuleSet_Impl;
 113
 114     ///////////////////////////////////////////////////////////////////////////
 115     //  Count the number of rules of each kind.
 116     ///////////////////////////////////////////////////////////////////////////
 117     leaf_reduction_count = 0;     // e.g.  A -> c
 118     reduction_count      = 0;     // e.g.  A -> f (A_1, A_2, ..., A_n)
 119     chain_rule_count     = 0;     // e.g.  A -> B
 120     has_wild_card        = false; // assume we don't have wildcard in grammar
 121
 122     {  foreach_production (i, g) count_rules(g[i].term); }
 123
 124     ///////////////////////////////////////////////////////////////////////////
 125     //  Allocate the tables.
 126     ///////////////////////////////////////////////////////////////////////////
 127     leaf_reduction_table  = new LeafReduction [ leaf_reduction_count ];
 128     reduction_table       = new Reduction *   [ reduction_count ];
 129     chain_rule_table      = new ChainRule     [ chain_rule_count ];
 130     int non_term_count = g.max_variable() + 1 + leaf_reduction_count +
 131                             reduction_count + chain_rule_count;
 132     non_term_to_tree      = new TreeTerm [non_term_count];
 133     {  for (int i = 0; i < non_term_count; i++)
 134           non_term_to_tree[i] = wild_term;
 135     }
 136
 137     ///////////////////////////////////////////////////////////////////////////
 138     //  Now normalise the patterns into canonical form.
 139     ///////////////////////////////////////////////////////////////////////////
 140     reduction_count      = 0;
 141     leaf_reduction_count = 0;
 142     chain_rule_count     = 0;
 143     non_terminal_count   = g.max_variable() + 1;
 144
 145     {  foreach_production (i, g)
 146           add_reduction(mem, i, g[i].var, g[i].term, g[i].cost);
 147     }
 148     assert(non_terminal_count <= non_term_count);
 149
 150     ///////////////////////////////////////////////////////////////////////////
 151     //  Finally compute the list of non-unit reductions partitioned by
 152     //  the functors.
 153     ///////////////////////////////////////////////////////////////////////////
 154     reductions = new ReductionList * [ g.max_functor() + 1 ];
 155     {  foreach_functor (f,g) reductions[f] = 0; }
 156     {  for (int i = 0; i < reduction_count; i++) {
 157           Functor f = reduction_table[i]->f;
 158           reductions[f] =
 159              new (mem, reduction_table[i], reductions[f]) ReductionList;
 160        }
 161     }
 162
 163     ///////////////////////////////////////////////////////////////////////////
 164     // Clean up
 165     ///////////////////////////////////////////////////////////////////////////
 166     delete impl;
 167 }
 168
 169 //////////////////////////////////////////////////////////////////////////////
 170 //
 171 //  Destructor
 172 //
 173 //////////////////////////////////////////////////////////////////////////////
 174 BURS_RuleSet::~BURS_RuleSet()
 175 {  delete [] reduction_table;
 176    delete [] chain_rule_table;
 177    delete [] leaf_reduction_table;
 178    delete [] reductions;
 179 }
 180
 181 //////////////////////////////////////////////////////////////////////////////
 182 //
 183 // Method to count the number of canonical rules.
 184 //
 185 //////////////////////////////////////////////////////////////////////////////
 186 void BURS_RuleSet::count_rules(TreeTerm t)
 187 {  match (t) {
 188       case wild_term:           has_wild_card = true; chain_rule_count++;
 189       case var_term(v):         chain_rule_count++;
 190       case tree_term(_,0,_):    leaf_reduction_count++;
 191       case tree_term(_,n,subterms):
 192          for (int i = n - 1; i >= 0; i--) count_rules(subterms[i]);
 193          reduction_count++;
 194       case _:    assert("Error in BURS_RuleSet::count_rules");
 195    }
 196 }
 197
 198 //////////////////////////////////////////////////////////////////////////////
 199 //
 200 //  Method to add an reduction rule into the table
 201 //
 202 //////////////////////////////////////////////////////////////////////////////
 203 NonTerminal BURS_RuleSet::add_reduction
 204   (Mem& mem, Rule r, NonTerminal lhs, TreeTerm t, Cost cost)
 205 {  match (t) {
 206       case tree_term(F,0,_):
 207          leaf_reduction_table[ leaf_reduction_count ].f    = F;
 208          leaf_reduction_table[ leaf_reduction_count ].cost = cost;
 209          leaf_reduction_table[ leaf_reduction_count ].rule = r;
 210          Ix i = impl->leaf_map.lookup(leaf_reduction_table + leaf_reduction_count);
 211          if (i) {
 212             return impl->leaf_map.key(i)->lhs;
 213          } else {
 214             impl->leaf_map.insert(leaf_reduction_table + leaf_reduction_count,0);
 215             if (lhs >= 0)
 216             {  non_term_to_tree[lhs] = t;
 217                return leaf_reduction_table[ leaf_reduction_count++ ].lhs = lhs;
 218             } else {
 219                NonTerminal T = non_terminal_count++;
 220                non_term_to_tree[T] = t;
 221                return leaf_reduction_table[ leaf_reduction_count++ ].lhs = T;
 222             }
 223          }
 224       case tree_term(F,N,S):
 225          {  Reduction * red = new (mem, N) Reduction;
 226             red->f    = F;
 227             red->n    = N;
 228             red->cost = cost;
 229             red->rule = r;
 230             {  for (int i = 0; i < N; i++) {
 231                   match (S[i]) {
 232                      case wild_term: red->rhs[i] = 0;
 233                      case _:
 234                         red->rhs[i] = add_reduction(mem, -1, -1, S[i], 0);
 235                   }
 236                }
 237             }
 238             Ix i = impl->non_leaf_map.lookup(red);
 239             if (i) {
 240                return impl->non_leaf_map.key(i)->lhs;
 241             } else {
 242                reduction_table[ reduction_count++ ] = red;
 243                impl->non_leaf_map.insert(red,0);
 244                if (lhs >= 0)
 245                {  non_term_to_tree[lhs] = t;
 246                   return red->lhs = lhs;
 247                } else {
 248                   NonTerminal T = non_terminal_count++;
 249                   non_term_to_tree[T] = t;
 250                   return red->lhs = T;
 251                }
 252             }
 253          }
 254       case wild_term:
 255          chain_rule_table[ chain_rule_count ].rhs  = 0;
 256          chain_rule_table[ chain_rule_count ].cost = cost;
 257          chain_rule_table[ chain_rule_count ].rule = r;
 258          Ix i = impl->chain_rule_map.lookup(chain_rule_table + chain_rule_count);
 259          if (i) {
 260             return impl->chain_rule_map.key(i)->lhs;
 261          } else {
 262             impl->chain_rule_map.insert(chain_rule_table + chain_rule_count,0);
 263             if (lhs >= 0)
 264             {  non_term_to_tree[lhs] = t;
 265                return chain_rule_table[ chain_rule_count++ ].lhs = lhs;
 266             } else {
 267                NonTerminal T = non_terminal_count++;
 268                non_term_to_tree[T] = t;
 269                return chain_rule_table[ chain_rule_count++ ].lhs = T;
 270             }
 271          }
 272       case var_term(v):
 273          chain_rule_table[ chain_rule_count ].rhs  = v;
 274          chain_rule_table[ chain_rule_count ].cost = cost;
 275          chain_rule_table[ chain_rule_count ].rule = r;
 276          Ix i = impl->chain_rule_map.lookup(chain_rule_table + chain_rule_count);
 277          if (i) {
 278             return impl->chain_rule_map.key(i)->lhs;
 279          } else {
 280             impl->chain_rule_map.insert(chain_rule_table + chain_rule_count,0);
 281             if (lhs >= 0)
 282             {  non_term_to_tree[lhs] = t;
 283                return chain_rule_table[ chain_rule_count++ ].lhs = lhs;
 284             } else {
 285                NonTerminal T = v; // non_terminal_count++;
 286                non_term_to_tree[T] = t;
 287                return chain_rule_table[ chain_rule_count++ ].lhs = T;
 288             }
 289          }
 290       case _:   assert("Error in BURS_RuleSet::add_reduction\n");
 291    }
 292 }
 293
 294
 295 //////////////////////////////////////////////////////////////////////////////
 296 //
 297 //  Printing methods
 298 //
 299 //////////////////////////////////////////////////////////////////////////////
 300
 301 //////////////////////////////////////////////////////////////////////////////
 302 //
 303 // Print a leaf reduction rule
 304 //
 305 //////////////////////////////////////////////////////////////////////////////
 306 ostream& BURS_RuleSet::print (ostream& f, const BURS_RuleSet::LeafReduction& r) const
 307 {  G.print_variable(f, r.lhs);
 308    f << "\t -> ";
 309    G.print_functor (f, r.f);
 310    if (r.cost > 0) f << "\t(" << r.cost << ')';
 311    return f;
 312 }
 313
 314 //////////////////////////////////////////////////////////////////////////////
 315 //
 316 // Print a reduction rule
 317 //
 318 //////////////////////////////////////////////////////////////////////////////
 319 ostream& BURS_RuleSet::print (ostream& f, const BURS_RuleSet::Reduction& r) const
 320 {  G.print_variable(f, r.lhs);
 321    f << "\t -> ";
 322    const char * f_name = G.functor_name(r.f);
 323    if (f_name[0] == '#')
 324    {  char begin_s = f_name[1];
 325       char end_s   = f_name[strlen(f_name)-1];
 326       f << '#' << begin_s;
 327       for (int i = 0; i < r.n; i++) {
 328          print (f, r.rhs[i]);
 329          if (i < r.n - 1) f << " ... ";
 330       }
 331       f << end_s;
 332    } else
 333    {  G.print_functor (f, r.f);
 334       f << '(';
 335       for (int i = 0; i < r.n; i++) {
 336          print (f, r.rhs[i]);
 337          if (i < r.n - 1) f << ',';
 338       }
 339       f << ')';
 340    }
 341    if (r.cost > 0) f << "\t(" << r.cost << ')';
 342    return f;
 343 }
 344
 345 //////////////////////////////////////////////////////////////////////////////
 346 //
 347 //  Print a chain rule
 348 //
 349 //////////////////////////////////////////////////////////////////////////////
 350 ostream& BURS_RuleSet::print (ostream& f, const BURS_RuleSet::ChainRule& r) const
 351 {  G.print_variable(f,r.lhs);
 352    f << "\t -> ";
 353    print(f,r.rhs);
 354    if (r.cost > 0) f << "\t(" << r.cost << ')';
 355    return f;
 356 }
 357
 358 //////////////////////////////////////////////////////////////////////////////
 359 //
 360 //  Print a rule set
 361 //
 362 //////////////////////////////////////////////////////////////////////////////
 363 ostream& operator <<(ostream& f, const BURS_RuleSet& r)
 364 {  int i;
 365    for (i = 0; i < r.number_of_leaf_reductions(); i++)
 366       r.print(f,r.leaf(i)) << '\n';
 367    for (i = 0; i < r.number_of_reductions(); i++)
 368       r.print(f,r.reduction(i)) << '\n';
 369    for (i = 0; i < r.number_of_chain_rules(); i++)
 370       r.print(f,r.chain_rule(i)) << '\n';
 371    return f;
 372 }
 373
 374 //////////////////////////////////////////////////////////////////////////////
 375 //
 376 //  Print a non-terminal
 377 //
 378 //////////////////////////////////////////////////////////////////////////////
 379 ostream& BURS_RuleSet::print (ostream& f, NonTerminal n) const
 380 {  return G.print(f,non_term_to_tree[n]); }