include/AD/automata/topdowng.h

   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 free 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 any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef top_down_tree_matching_automata_generator_h
  26 #define top_down_tree_matching_automata_generator_h
  27
  28 #include <AD/automata/acgen.h>    // Aho-Corasick string matching generator
  29 #include <AD/automata/treegram.h> // Tree grammars
  30
  31 //////////////////////////////////////////////////////////////////////////////
  32 //
  33 //  The top-down tree matching algorithm\cite{tree-matching, AC}
  34 // reduces the problem of tree matching to the problem of string matching
  35 // a set of path strings.
  36 //
  37 //////////////////////////////////////////////////////////////////////////////
  38
  39 class TopDownGen : public ACGen {
  40
  41    TopDownGen(const TopDownGen&);           // no copy constructor
  42    void operator = (const TopDownGen&);     // no assignment
  43
  44 public:
  45
  46    ///////////////////////////////////////////////////////////////////////////
  47    // Inherit some types
  48    ///////////////////////////////////////////////////////////////////////////
  49    typedef ACGen                       Super;
  50    typedef Super::Symbol               Symbol;
  51    typedef Super::Rule                 Rule;
  52    typedef Super::Offset               Offset;
  53    typedef Super::State                State;
  54    typedef TreeGrammar::TreeProduction TreeProduction;
  55
  56 private:
  57    ///////////////////////////////////////////////////////////////////////////
  58    //  The current tree grammar
  59    ///////////////////////////////////////////////////////////////////////////
  60    const TreeGrammar * G;
  61
  62    ///////////////////////////////////////////////////////////////////////////
  63    //  Private method to add a path string to the trie
  64    ///////////////////////////////////////////////////////////////////////////
  65    void add_path(int, const TreeTerm, int, Symbol []);
  66
  67 public:
  68
  69    ///////////////////////////////////////////////////////////////////////////
  70    //  Constructors and destructor
  71    ///////////////////////////////////////////////////////////////////////////
  72    TopDownGen();
  73    TopDownGen(const TreeGrammar&);
  74   ~TopDownGen();
  75
  76    ///////////////////////////////////////////////////////////////////////////
  77    //  Selectors
  78    ///////////////////////////////////////////////////////////////////////////
  79    inline int   size()        const { return Super::size(); }
  80    inline State start_state() const { return 0; }
  81
  82    ///////////////////////////////////////////////////////////////////////////
  83    //  Compilation and code emission
  84    ///////////////////////////////////////////////////////////////////////////
  85            void     compile  (const TreeGrammar&);
  86    virtual ostream& gen_code (ostream&, const char name[]) const;
  87    virtual ostream& print_report (ostream&) const;
  88
  89    ///////////////////////////////////////////////////////////////////////////
  90    // Advance one state within the tree matching automaton
  91    ///////////////////////////////////////////////////////////////////////////
  92    inline State go (register State s, register int branch, register Symbol c) const
  93       { return Super::go( Super::go(s,branch), c); }
  94 };
  95
  96 #endif