lib-src/automata/topdowng.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 "topdowng.pcc".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #line 1 "topdowng.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 free 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 any suggestions
  26 // and help from the users.
  27 //
  28 // Allen Leung
  29 // 1994
  30 //////////////////////////////////////////////////////////////////////////////
  31
  32 //////////////////////////////////////////////////////////////////////////////
  33 //  This file implements a top-down tree matcher generator using the algorithm
  34 //  described by O'Donnell et al.  It basically reduces tree matching
  35 //  to the problem of string matching using the Aho-Corasick algorithm.
  36 //  The generator is really simple since most of the complexity of
  37 //  top-down style matching is at runtime.
  38 //////////////////////////////////////////////////////////////////////////////
  39
  40 #include <iostream.h>
  41 #include <assert.h>
  42 #include <AD/automata/treegram.h>
  43 #include <AD/automata/topdowng.h>
  44
  45 //////////////////////////////////////////////////////////////////////////////
  46 //  Make hidden types visible
  47 //////////////////////////////////////////////////////////////////////////////
  48 typedef TreeGrammar::TreeProduction TreeProduction;
  49
  50 //////////////////////////////////////////////////////////////////////////////
  51 //  Constructors and destructor
  52 //////////////////////////////////////////////////////////////////////////////
  53 TopDownGen:: TopDownGen() {}
  54 TopDownGen:: TopDownGen(const TreeGrammar& Gram) { compile(Gram); }
  55 TopDownGen::~TopDownGen() {}
  56
  57 //////////////////////////////////////////////////////////////////////////////
  58 //  Compile a set of tree patterns
  59 //////////////////////////////////////////////////////////////////////////////
  60 void TopDownGen::compile(const TreeGrammar& g)
  61 {
  62    ///////////////////////////////////////////////////////////////////////////
  63    //  Set the tree grammar
  64    ///////////////////////////////////////////////////////////////////////////
  65    G = &g;
  66
  67    ///////////////////////////////////////////////////////////////////////////
  68    //  A temporary buffer for the path string.  You won't have
  69    //  patterns with such deep nesting (512).
  70    ///////////////////////////////////////////////////////////////////////////
  71    Symbol path[ 1024 ];
  72
  73    ///////////////////////////////////////////////////////////////////////////
  74    //  Get the minimum and maximum functor coding within the grammar.
  75    ///////////////////////////////////////////////////////////////////////////
  76    Symbol min = g.min_functor();
  77    Symbol max = g.max_functor();
  78
  79    ///////////////////////////////////////////////////////////////////////////
  80    //  Min and max are the symbol value range for the path strings.
  81    //  Since the arities are also part of the path string, make sure
  82    //  the range covers them.
  83    ///////////////////////////////////////////////////////////////////////////
  84    if (min > 0) min = 0;
  85    if (max < g.max_arity()) max = g.max_arity();
  86
  87    ///////////////////////////////////////////////////////////////////////////
  88    //  Start creating the compressed tables.
  89    ///////////////////////////////////////////////////////////////////////////
  90    start(min,max);
  91
  92    ///////////////////////////////////////////////////////////////////////////
  93    //  Now compile the path strings, one for each pattern in the grammar.
  94    ///////////////////////////////////////////////////////////////////////////
  95    for (int i = 0; i < g.size(); i++)
  96       add_path(i, g[i].term, 0, path);
  97
  98    ///////////////////////////////////////////////////////////////////////////
  99    //  Finish up the table compression process.
 100    ///////////////////////////////////////////////////////////////////////////
 101    finish();
 102 }
 103
 104 //////////////////////////////////////////////////////////////////////////////
 105 //  Compile a tree pattern as a set of path strings, one for each
 106 //  possible branch of the tree.
 107 //  E.g.  a pattern such as  f(g(X,a), b)  is compiled into the path strings
 108 //     f 0 g
 109 //     f 0 g 1 a
 110 //     f 1 b
 111 //////////////////////////////////////////////////////////////////////////////
 112 void TopDownGen::add_path(int rule, const TreeTerm term, int len, Symbol path[])
 113 {
 114
 115 #line 107 "topdowng.pcc"
 116 #line 120 "topdowng.pcc"
 117 {
 118    if (term) {
 119       switch (term->tag__) {
 120          case a_TreeTerm::tag_tree_term: {
 121 #line 109 "topdowng.pcc"
 122
 123             path[len] = _tree_term(term)->_1;
 124             if (_tree_term(term)->_2 > 0) {  // a non-terminal ?
 125                for (int i = 0; i < _tree_term(term)->_2; i++) {
 126                   path[len + 1] = i;
 127                   add_path(rule,_tree_term(term)->_3[i],len+2,path);
 128                }
 129             } else {  // a terminal
 130                add_string(rule, len + 1, path);
 131             }
 132
 133 #line 119 "topdowng.pcc"
 134             } break;
 135          default: {
 136 #line 119 "topdowng.pcc"
 137            assert("Bug in TopDownGen::add_path()");
 138
 139 #line 120 "topdowng.pcc"
 140             } break;
 141       }
 142    } else {
 143 #line 108 "topdowng.pcc"
 144    add_string(rule, len, path);
 145
 146 #line 109 "topdowng.pcc"
 147    }
 148 }
 149 #line 120 "topdowng.pcc"
 150 #line 120 "topdowng.pcc"
 151
 152 }
 153
 154 //////////////////////////////////////////////////////////////////////////////
 155 //
 156 //  Emit C++ code for the tables.
 157 //
 158 //////////////////////////////////////////////////////////////////////////////
 159 ostream& TopDownGen::gen_code(ostream& out, const char name[]) const
 160 {
 161    Super::gen_code(out,name);
 162    return out;
 163 }
 164
 165 //////////////////////////////////////////////////////////////////////////////
 166 //
 167 //  Print report
 168 //
 169 //////////////////////////////////////////////////////////////////////////////
 170 ostream& TopDownGen::print_report(ostream& f) const
 171 {
 172    f << "\nCanonical grammar:\n" << *G << '\n';
 173    return f;
 174 }
 175 #line 144 "topdowng.pcc"
 176 /*
 177 ------------------------------- Statistics -------------------------------
 178 Merge matching rules         = yes
 179 Number of DFA nodes merged   = 5
 180 Number of ifs generated      = 1
 181 Number of switches generated = 1
 182 Number of labels             = 0
 183 Number of gotos              = 0
 184 Adaptive matching            = disabled
 185 Fast string matching         = disabled
 186 Inline downcasts             = disabled
 187 --------------------------------------------------------------------------
 188 */