include/AD/automata/item.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 parse_item_h
  26 #define parse_item_h
  27
  28 #include <new>
  29 #include <AD/generic/ordering.h>
  30 #include <AD/automata/grammar.h>
  31 #include <AD/automata/operprec.h>
  32 #include <AD/memory/mem.h>
  33
  34 //////////////////////////////////////////////////////////////////////////////
  35 //  Class |LRItem| represents a item (or configuration) during
  36 //  the shift/reduce parser generation.
  37 //////////////////////////////////////////////////////////////////////////////
  38 struct LRItem {
  39 public:
  40
  41    ///////////////////////////////////////////////////////////////////////////
  42    //  Imported types
  43    ///////////////////////////////////////////////////////////////////////////
  44    typedef Grammar::Symbol      Symbol;
  45    typedef Grammar::Terminal    Terminal;
  46    typedef Grammar::NonTerminal NonTerminal;
  47    typedef Grammar::Production  Production;
  48    typedef OpPrecedence::Associativity Associativity;
  49    typedef OpPrecedence::Precedence    Precedence;
  50
  51    Production    P;
  52    int           pos;
  53    Associativity associativity;
  54    Precedence    precedence;
  55
  56 public:
  57
  58    ///////////////////////////////////////////////////////////////////////////
  59    //  Constructor and destructor
  60    ///////////////////////////////////////////////////////////////////////////
  61
  62    ///////////////////////////////////////////////////////////////////////////
  63    //  Allocation
  64    ///////////////////////////////////////////////////////////////////////////
  65    inline void * operator new
  66       (size_t size, Mem& pool, const Grammar& G, int production_num,
  67        Production p, int n, const OpPrecedence& prec)
  68       {  LRItem * item = (LRItem*) pool.m_alloc(size);
  69          item->P = p; item->pos = n;
  70          // Scan backwards to find the operator symbol
  71          // (used in operator precedence parsing)
  72          for (int pos = n; pos > 0; pos--)
  73          {  if (G.isTerminal(p[pos]))
  74             { item->associativity = prec.associativity(p[pos]);
  75               item->precedence    = prec.precedence(p[pos]);
  76               return item;
  77             }
  78          }
  79          item->associativity = prec.p_associativity(production_num);
  80          item->precedence    = prec.p_precedence(production_num);
  81          return item;
  82       }
  83    ///////////////////////////////////////////////////////////////////////////
  84    //  Length (with or without terminals)
  85    ///////////////////////////////////////////////////////////////////////////
  86    inline int len () const { return pos; } // prefix length
  87    int ncount (const Grammar&) const; // non-terminal count
  88
  89    ///////////////////////////////////////////////////////////////////////////
  90    //  Testing for predicting and reducing items
  91    ///////////////////////////////////////////////////////////////////////////
  92    inline Bool isPredicting() const { return pos == 0; }
  93    inline Bool isReducing()   const { return P[pos+1] <= Grammar::END_PRODUCTION; }
  94
  95    ///////////////////////////////////////////////////////////////////////////
  96    //  Comparison and hashing
  97    ///////////////////////////////////////////////////////////////////////////
  98    inline friend Bool equal(const LRItem * a, const LRItem * b)
  99       { return a->P == b->P && a->pos == b->pos; }
 100    inline friend unsigned int hash(const LRItem * a)
 101       { return (unsigned int)a->P + a->pos; }
 102 };
 103
 104 #endif