lib-src/rewrite/b_rules.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //  This file is generated automatically using Prop (version 2.3.1),
   3 //  last updated on Mar 13, 1997.
   4 //  The original source file is "b_rules.pcc".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #line 1 "b_rules.pcc"
   8 /////////////////////////////////////////////////////////////////////////////
   9 // NOTICE:
  10 //
  11 // ADLib, Prop and their related set of tools and documentation are in the
  12 // public domain.   The author(s) of this software reserve no copyrights on
  13 // the source code and any code generated using the tools.  You are encouraged
  14 // to use ADLib and Prop to develop software, in both academic and commercial
  15 // settings, and are welcomed to incorporate any part of ADLib and Prop into
  16 // your programs.
  17 //
  18 // Although you are under no obligation to do so, we strongly recommend that
  19 // you give away all software developed using our tools.
  20 //
  21 // We also ask that credit be given to us when ADLib and/or Prop are used in
  22 // your programs, and that this notice be preserved intact in all the source
  23 // code.
  24 //
  25 // This software is still under development and we welcome(read crave for)
  26 // any suggestions and help from the users.
  27 //
  28 // Allen Leung
  29 // 1994
  30 //////////////////////////////////////////////////////////////////////////////
  31
  32 #define TreeGrammar_Iterators
  33 #include <iostream.h>
  34 #include <string.h>
  35 #include <AD/automata/treegram.h>
  36 #include <assert.h>
  37 #include <AD/rewrite/b_rules.h>
  38 #include <AD/hash/dchash.h>
  39
  40 //////////////////////////////////////////////////////////////////////////////
  41 //
  42 //  Make hidden types visible for use.
  43 //
  44 //////////////////////////////////////////////////////////////////////////////
  45 typedef TreeGrammar::Functor        Functor;
  46 typedef TreeGrammar::NonTerminal    NonTerminal;
  47 typedef TreeGrammar::Rule           Rule;
  48 typedef TreeGrammar::Cost           Cost;
  49 typedef BURS_RuleSet::LeafReduction LeafReduction;
  50 typedef BURS_RuleSet::Reduction     Reduction;
  51 typedef BURS_RuleSet::ChainRule     ChainRule;
  52
  53 //////////////////////////////////////////////////////////////////////////////
  54 //
  55 //  Hash functions and equality functions for leaf reductions.
  56 //
  57 //////////////////////////////////////////////////////////////////////////////
  58 inline Bool equal (const LeafReduction * a, const LeafReduction * b)
  59 {  return a->f == b->f && a->cost == b->cost && a->rule == b->rule;
  60 }
  61 inline unsigned hash (const LeafReduction * a)
  62 {  return a->f + a->cost + a->rule; }
  63
  64 //////////////////////////////////////////////////////////////////////////////
  65 //
  66 //  Hash functions and equality functions for non-leaf reductions.
  67 //
  68 //////////////////////////////////////////////////////////////////////////////
  69 inline Bool equal (const Reduction * a, const Reduction * b)
  70 {  if (a->f != b->f || a->cost != b->cost ||
  71        a->rule != b->rule || a->n != b->n) return false;
  72    for (int i = a->n - 1; i >= 0; i--)
  73       if (a->rhs[i] != b->rhs[i]) return false;
  74    return true;
  75 }
  76 inline unsigned hash (const Reduction * a)
  77 {  unsigned h = a->f + a->cost + a->rule + a->n;
  78    for (int i = a->n - 1; i >= 0; i--) h += a->rhs[i];
  79    return h;
  80 }
  81
  82 //////////////////////////////////////////////////////////////////////////////
  83 //
  84 //  Hash functions and equality functions for chain reductions.
  85 //
  86 //////////////////////////////////////////////////////////////////////////////
  87 inline Bool equal (const ChainRule * a, const ChainRule * b)
  88 {  return a->rhs == b->rhs && a->cost == b->cost && a->rule == b->rule;
  89 }
  90 inline unsigned hash (const ChainRule * a)
  91 {  return a->rhs + a->cost + a->rule; }
  92
  93 //////////////////////////////////////////////////////////////////////////////
  94 //
  95 // Internal implementation
  96 //
  97 //////////////////////////////////////////////////////////////////////////////
  98 class BURS_RuleSet_Impl {
  99    BURS_RuleSet_Impl(const BURS_RuleSet_Impl&);
 100    void operator = (const BURS_RuleSet_Impl&);
 101 public:
 102    DCHashTable <LeafReduction *, int> leaf_map;
 103    DCHashTable <Reduction *,     int> non_leaf_map;
 104    DCHashTable <ChainRule *,     int> chain_rule_map;
 105    inline  BURS_RuleSet_Impl() {}
 106    inline ~BURS_RuleSet_Impl() {}
 107 };
 108
 109 //////////////////////////////////////////////////////////////////////////////
 110 //
 111 //  Constructor and destructor
 112 //
 113 //////////////////////////////////////////////////////////////////////////////
 114 BURS_RuleSet:: BURS_RuleSet( Mem& mem, const TreeGrammar& g) : G(g)
 115 {
 116     ///////////////////////////////////////////////////////////////////////////
 117     // Create a new set of hash tables.
 118     ///////////////////////////////////////////////////////////////////////////
 119     impl = new BURS_RuleSet_Impl;
 120
 121     ///////////////////////////////////////////////////////////////////////////
 122     //  Count the number of rules of each kind.
 123     ///////////////////////////////////////////////////////////////////////////
 124     leaf_reduction_count = 0;         // e.g.  A -> c
 125     reduction_count      = 0;         // e.g.  A -> f (A_1, A_2, ..., A_n)
 126     chain_rule_count     = G.size();  // e.g.  A -> B
 127     has_wild_card        = false; // assume we don't have wildcard in grammar
 128
 129     {  foreach_production (i, g) count_rules(g[i].term); }
 130
 131     ///////////////////////////////////////////////////////////////////////////
 132     //  Allocate the tables.
 133     ///////////////////////////////////////////////////////////////////////////
 134     leaf_reduction_table  = new LeafReduction [ leaf_reduction_count ];
 135     reduction_table       = new Reduction *   [ reduction_count ];
 136     chain_rule_table      = new ChainRule     [ chain_rule_count ];
 137     int non_term_count = g.max_variable() + 1 + leaf_reduction_count +
 138                             reduction_count + chain_rule_count;
 139     non_term_to_tree      = new TreeTerm [non_term_count];
 140     Bool * var_used = (Bool*)mem.c_alloc(sizeof(Bool) * (g.max_variable()+1));
 141     {  for (int i = 0; i < non_term_count; i++)
 142           non_term_to_tree[i] = wild_term;
 143     }
 144
 145     ///////////////////////////////////////////////////////////////////////////
 146     //  Now normalise the patterns into canonical form.
 147     ///////////////////////////////////////////////////////////////////////////
 148     reduction_count      = 0;
 149     leaf_reduction_count = 0;
 150     chain_rule_count     = 0;
 151     non_terminal_count   = g.max_variable() + 1;
 152
 153     ///////////////////////////////////////////////////////////////////////////
 154     // Compute the reduction rules
 155     ///////////////////////////////////////////////////////////////////////////
 156     {  foreach_production (i, g)
 157        {  NonTerminal v = g[i].var;
 158           NonTerminal rhs = add_reduction(mem, i, g[i].term, g[i].cost);
 159           if (v > 0)
 160           {  chain_rule_table[ chain_rule_count ].rhs   = rhs;
 161              chain_rule_table[ chain_rule_count ].cost  = 0;
 162              chain_rule_table[ chain_rule_count ].rule  = i;
 163              chain_rule_table[ chain_rule_count++ ].lhs = g[i].var;
 164              var_used[v] = true;
 165           }
 166        }
 167     }
 168     ///////////////////////////////////////////////////////////////////////////
 169     //  Compute the chain rules
 170     ///////////////////////////////////////////////////////////////////////////
 171     {  for (NonTerminal v = g.min_variable(); v <= g.max_variable(); v++)
 172        {  if (var_used[v])
 173           {  chain_rule_table[ chain_rule_count ].lhs  = 0;
 174              chain_rule_table[ chain_rule_count ].rhs  = v;
 175              chain_rule_table[ chain_rule_count ].cost = 0;
 176              chain_rule_table[ chain_rule_count ].rule = -1;
 177              chain_rule_count++;
 178           }
 179        }
 180     }
 181
 182     assert(non_terminal_count <= non_term_count);
 183
 184     ///////////////////////////////////////////////////////////////////////////
 185     //  Finally compute the list of non-unit reductions partitioned by
 186     //  the functors.
 187     ///////////////////////////////////////////////////////////////////////////
 188     reductions = new ReductionList * [ g.max_functor() + 1 ];
 189     {  foreach_functor (f,g) reductions[f] = 0; }
 190     {  for (int i = 0; i < reduction_count; i++) {
 191           Functor f = reduction_table[i]->f;
 192           reductions[f] =
 193              new (mem, reduction_table[i], reductions[f]) ReductionList;
 194        }
 195     }
 196
 197     ///////////////////////////////////////////////////////////////////////////
 198     // Clean up
 199     ///////////////////////////////////////////////////////////////////////////
 200     delete impl;
 201 }
 202
 203 //////////////////////////////////////////////////////////////////////////////
 204 //
 205 //  Destructor
 206 //
 207 //////////////////////////////////////////////////////////////////////////////
 208 BURS_RuleSet::~BURS_RuleSet()
 209 {  delete [] reduction_table;
 210    delete [] chain_rule_table;
 211    delete [] leaf_reduction_table;
 212    delete [] reductions;
 213 }
 214
 215 //////////////////////////////////////////////////////////////////////////////
 216 //
 217 // Method to count the number of canonical rules.
 218 //
 219 //////////////////////////////////////////////////////////////////////////////
 220 void BURS_RuleSet::count_rules(TreeTerm t)
 221 {
 222 #line 214 "b_rules.pcc"
 223 #line 222 "b_rules.pcc"
 224 {
 225    if (t) {
 226       switch (t->tag__) {
 227          case a_TreeTerm::tag_tree_term: {
 228             switch (_tree_term(t)->_2) {
 229                case 0: {
 230 #line 217 "b_rules.pcc"
 231               leaf_reduction_count++;
 232
 233 #line 218 "b_rules.pcc"
 234                } break;
 235                default: {
 236 #line 218 "b_rules.pcc"
 237
 238                   for (int i = _tree_term(t)->_2 - 1; i >= 0; i--) count_rules(_tree_term(t)->_3[i]);
 239                   reduction_count++;
 240
 241 #line 221 "b_rules.pcc"
 242                }
 243             }
 244             } break;
 245          case a_TreeTerm::tag_var_term: {
 246 #line 216 "b_rules.pcc"
 247    chain_rule_count++;
 248
 249 #line 217 "b_rules.pcc"
 250             } break;
 251          default: {
 252 #line 221 "b_rules.pcc"
 253         assert("Error in BURS_RuleSet::count_rules");
 254
 255 #line 222 "b_rules.pcc"
 256             } break;
 257       }
 258    } else {
 259 #line 215 "b_rules.pcc"
 260      has_wild_card = true; chain_rule_count++;
 261
 262 #line 216 "b_rules.pcc"
 263    }
 264 }
 265 #line 222 "b_rules.pcc"
 266 #line 222 "b_rules.pcc"
 267
 268 }
 269
 270 //////////////////////////////////////////////////////////////////////////////
 271 //
 272 //  Method to add an reduction rule into the table
 273 //
 274 //////////////////////////////////////////////////////////////////////////////
 275 NonTerminal BURS_RuleSet::add_reduction
 276    (Mem& mem, Rule r, TreeTerm t, Cost cost)
 277 {
 278 #line 232 "b_rules.pcc"
 279 #line 276 "b_rules.pcc"
 280 {
 281    if (t) {
 282       switch (t->tag__) {
 283          case a_TreeTerm::tag_tree_term: {
 284             switch (_tree_term(t)->_2) {
 285                case 0: {
 286 #line 233 "b_rules.pcc"
 287
 288                   leaf_reduction_table[ leaf_reduction_count ].f    = _tree_term(t)->_1;
 289                   leaf_reduction_table[ leaf_reduction_count ].cost = cost;
 290                   leaf_reduction_table[ leaf_reduction_count ].rule = r;
 291                   Ix i = impl->leaf_map.lookup(leaf_reduction_table + leaf_reduction_count);
 292                   if (i) {
 293                      return impl->leaf_map.key(i)->lhs;
 294                   } else {
 295                      impl->leaf_map.insert(leaf_reduction_table + leaf_reduction_count,0);
 296                      NonTerminal T = non_terminal_count++;
 297                      non_term_to_tree[T] = t;
 298                      // cerr << "Non-term " << T << " = "; G.print(cerr,t) << '\n';
 299                      return leaf_reduction_table[ leaf_reduction_count++ ].lhs = T;
 300                   }
 301
 302 #line 247 "b_rules.pcc"
 303                } break;
 304                default: {
 305 #line 247 "b_rules.pcc"
 306
 307                   {  Reduction * red = new (mem, _tree_term(t)->_2) Reduction;
 308                      red->f    = _tree_term(t)->_1;
 309                      red->n    = _tree_term(t)->_2;
 310                      red->cost = cost;
 311                      red->rule = r;
 312                      {  for (int i = 0; i < _tree_term(t)->_2; i++) {
 313
 314 #line 254 "b_rules.pcc"
 315 #line 257 "b_rules.pcc"
 316                   {
 317                      TreeTerm _V1 = _tree_term(t)->_3[i];
 318                      if (_V1) {
 319 #line 256 "b_rules.pcc"
 320                        red->rhs[i] = add_reduction(mem, -1, _tree_term(t)->_3[i], 0);
 321
 322 #line 257 "b_rules.pcc"
 323                      } else {
 324 #line 255 "b_rules.pcc"
 325                        red->rhs[i] = 0;
 326
 327 #line 256 "b_rules.pcc"
 328                      }
 329                   }
 330 #line 257 "b_rules.pcc"
 331 #line 257 "b_rules.pcc"
 332
 333                   }
 334                   }
 335                   Ix i = impl->non_leaf_map.lookup(red);
 336                   if (i) {
 337                   return impl->non_leaf_map.key(i)->lhs;
 338                   } else {
 339                   reduction_table[ reduction_count++ ] = red;
 340                   impl->non_leaf_map.insert(red,0);
 341                   NonTerminal T = non_terminal_count++;
 342                   non_term_to_tree[T] = t;
 343                   // cerr << "Non-term " << T << " = "; G.print(cerr,t) << '\n';
 344                   return red->lhs = T;
 345                   }
 346                   }
 347
 348 #line 272 "b_rules.pcc"
 349                }
 350             }
 351             } break;
 352          case a_TreeTerm::tag_var_term: {
 353 #line 273 "b_rules.pcc"
 354            return _var_term(t)->var_term;
 355
 356 #line 274 "b_rules.pcc"
 357             } break;
 358          default: {
 359 #line 274 "b_rules.pcc"
 360          assert("Error in BURS_RuleSet::add_reduction\n");
 361                         return 0;
 362
 363 #line 276 "b_rules.pcc"
 364             } break;
 365       }
 366    } else {
 367 #line 272 "b_rules.pcc"
 368    return 0;
 369
 370 #line 273 "b_rules.pcc"
 371    }
 372 }
 373 #line 276 "b_rules.pcc"
 374 #line 276 "b_rules.pcc"
 375
 376 }
 377
 378
 379 //////////////////////////////////////////////////////////////////////////////
 380 //
 381 //  Printing methods
 382 //
 383 //////////////////////////////////////////////////////////////////////////////
 384
 385 //////////////////////////////////////////////////////////////////////////////
 386 //
 387 // Print a leaf reduction rule
 388 //
 389 //////////////////////////////////////////////////////////////////////////////
 390 ostream& BURS_RuleSet::print (ostream& f, const BURS_RuleSet::LeafReduction& r) const
 391 {  G.print_variable(f, r.lhs);
 392    f << "\t -> ";
 393    G.print_functor (f, r.f);
 394    if (r.cost > 0) f << "\t(cost " << r.cost << ')';
 395    if (r.rule >= 0) f << "\t[rule " << r.rule << ']';
 396    return f;
 397 }
 398
 399 //////////////////////////////////////////////////////////////////////////////
 400 //
 401 // Print a reduction rule
 402 //
 403 //////////////////////////////////////////////////////////////////////////////
 404 ostream& BURS_RuleSet::print (ostream& f, const BURS_RuleSet::Reduction& r) const
 405 {  G.print_variable(f, r.lhs);
 406    f << "\t -> ";
 407    const char * f_name = G.functor_name(r.f);
 408    if (f_name[0] == '#')
 409    {  char begin_s = f_name[1];
 410       char end_s   = f_name[strlen(f_name)-1];
 411       f << '#' << begin_s;
 412       for (int i = 0; i < r.n; i++) {
 413          print (f, r.rhs[i]);
 414          if (i < r.n - 1) f << " ... ";
 415       }
 416       f << end_s;
 417    } else
 418    {  G.print_functor (f, r.f);
 419       f << '(';
 420       for (int i = 0; i < r.n; i++) {
 421          print (f, r.rhs[i]);
 422          if (i < r.n - 1) f << ',';
 423       }
 424       f << ')';
 425    }
 426    if (r.cost > 0) f << "\t(cost " << r.cost << ')';
 427    if (r.rule >= 0) f << "\t[rule " << r.rule << ']';
 428    return f;
 429 }
 430
 431 //////////////////////////////////////////////////////////////////////////////
 432 //
 433 //  Print a chain rule
 434 //
 435 //////////////////////////////////////////////////////////////////////////////
 436 ostream& BURS_RuleSet::print (ostream& f, const BURS_RuleSet::ChainRule& r) const
 437 {  G.print_variable(f,r.lhs);
 438    f << "\t -> ";
 439    G.print_variable(f,r.rhs);
 440    if (r.cost > 0) f << "\t(cost " << r.cost << ')';
 441    if (r.rule >= 0) f << "\t[rule " << r.rule << ']';
 442    return f;
 443 }
 444
 445 //////////////////////////////////////////////////////////////////////////////
 446 //
 447 //  Print a rule set
 448 //
 449 //////////////////////////////////////////////////////////////////////////////
 450 ostream& operator <<(ostream& f, const BURS_RuleSet& r)
 451 {  int i;
 452    if (r.number_of_leaf_reductions() > 0) f << "Leaf reductions:\n";
 453    for (i = 0; i < r.number_of_leaf_reductions(); i++)
 454       r.print(f,r.leaf(i)) << '\n';
 455    if (r.number_of_reductions() > 0) f << "Non-leaf reductions:\n";
 456    for (i = 0; i < r.number_of_reductions(); i++)
 457       r.print(f,r.reduction(i)) << '\n';
 458    if (r.number_of_chain_rules() > 0) f << "Chain rules:\n";
 459    for (i = 0; i < r.number_of_chain_rules(); i++)
 460       r.print(f,r.chain_rule(i)) << '\n';
 461    return f;
 462 }
 463
 464 //////////////////////////////////////////////////////////////////////////////
 465 //
 466 //  Print a non-terminal
 467 //
 468 //////////////////////////////////////////////////////////////////////////////
 469 ostream& BURS_RuleSet::print (ostream& f, NonTerminal n) const
 470 {  TreeTerm t = non_term_to_tree[n];
 471    if (t != wild_term || n == 0)
 472    {  G.print(f,t);
 473    } else
 474    {  G.print_variable(f,n);
 475    }
 476    return f;
 477 }
 478 #line 379 "b_rules.pcc"
 479 /*
 480 ------------------------------- Statistics -------------------------------
 481 Merge matching rules         = yes
 482 Number of DFA nodes merged   = 15
 483 Number of ifs generated      = 3
 484 Number of switches generated = 4
 485 Number of labels             = 0
 486 Number of gotos              = 0
 487 Adaptive matching            = disabled
 488 Fast string matching         = disabled
 489 Inline downcasts             = disabled
 490 --------------------------------------------------------------------------
 491 */