include/AD/automata/grammar.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 grammar_for_parsers_h
  26 #define grammar_for_parsers_h
  27
  28 #include <iostream>
  29 #include <AD/generic/generic.h>   // Generic definitions
  30 #include <AD/automata/dfatable.h> // DFA tables
  31
  32 //////////////////////////////////////////////////////////////////////////////
  33 //  This class is used to represent a context free grammar.
  34 //
  35 //  The representation is very simple:  each symbol (terminal, non-terminal,
  36 //  or action symbols) are represented as the type |Symbol|.
  37 //  A production is simply an array of Symbol's terminated with the
  38 //  unique constant |Grammar::END_PRODUCTION|.   A grammar is just an
  39 //  array of productions.
  40 //
  41 //  Most simple operations are inline'd for efficiency.
  42 //////////////////////////////////////////////////////////////////////////////
  43
  44 class Grammar : public DFATables {
  45 public:
  46
  47    ///////////////////////////////////////////////////////////////////////////
  48    //  Type definitions
  49    ///////////////////////////////////////////////////////////////////////////
  50    typedef DFATables       Super;
  51    typedef Super::State    State;
  52    typedef Super::Rule     Rule;
  53    typedef Super::Offset   Offset;
  54    typedef Super::Symbol   Symbol;      // a terminal, non-terminal or action symbol
  55    typedef Symbol          Terminal;    // a terminal
  56    typedef Symbol          NonTerminal; // a non-terminal
  57    typedef Symbol          Action;      // an action symbol
  58    typedef Symbol *        Production;  // a production
  59    typedef Super::EquivMap EquivMap;    // equivalence mapping
  60
  61    ///////////////////////////////////////////////////////////////////////////
  62    //  Manifest constants
  63    ///////////////////////////////////////////////////////////////////////////
  64    enum Grammar_constants
  65    {  END_PRODUCTION = EOF - 1, // end-of-production marker
  66       First_action   = END_PRODUCTION - 1
  67    };
  68
  69 protected:
  70
  71    ///////////////////////////////////////////////////////////////////////////
  72    //  Internals
  73    ///////////////////////////////////////////////////////////////////////////
  74
  75    Production *  productions;           // an array of productions
  76    Bool          persistent;            // is the array persistent?
  77    int           number_of_productions; // size of the array
  78    Terminal      minTerminal;           // minimal terminal
  79    Terminal      maxTerminal;           // maximal terminal
  80    NonTerminal   minNonTerminal;        // minimal non-terminal
  81    NonTerminal   maxNonTerminal;        // maximal non-terminal
  82    NonTerminal   maxNormalNonTerminal;  // maximal (normal) non-terminal
  83    NonTerminal   startSymbol;           // the start symbol
  84    Production    startProduction;       // the start production
  85    const char ** symbol_names;          // symbol names mapping
  86    int           equiv_classes_size;    // equivalence class size
  87    EquivMap   *  equiv_classes;         // equivalence class mapping
  88    EquivMap   *  equiv_map;
  89    Rule       *  action_map;            // mapping from action to rule
  90    int           action_map_size;
  91
  92    ///////////////////////////////////////////////////////////////////////////
  93    // Private cleaning method
  94    ///////////////////////////////////////////////////////////////////////////
  95    void clean_up();
  96
  97 public:
  98
  99    //////////////////////////////////////////////////////////////////////////
 100    //  Constructors and destructor
 101    //////////////////////////////////////////////////////////////////////////
 102    Grammar();
 103    Grammar(const Grammar&);
 104    Grammar(Production P[], int n, Symbol min, Symbol max,
 105            NonTerminal start,
 106            const char * names[] = 0,
 107            int = 0, EquivMap [] = 0, EquivMap [] = 0,
 108            Rule [] = 0, int = 0, NonTerminal maxNormal = -1,
 109            Bool persist = true);
 110    virtual ~Grammar();
 111
 112    //////////////////////////////////////////////////////////////////////////
 113    // Assignment
 114    //////////////////////////////////////////////////////////////////////////
 115    Grammar& operator = (const Grammar&);
 116
 117    //////////////////////////////////////////////////////////////////////////
 118    // Testing for symbol type
 119    //////////////////////////////////////////////////////////////////////////
 120    inline Bool isTerminal    (Symbol s) const { return s > END_PRODUCTION && s <= maxTerminal; }
 121    inline Bool isNonTerminal (Symbol s) const { return s > maxTerminal; }
 122    inline Bool isAction      (Symbol s) const { return s < END_PRODUCTION; }
 123
 124    //////////////////////////////////////////////////////////////////////////
 125    //  Productions
 126    //////////////////////////////////////////////////////////////////////////
 127    inline int size()                      const { return number_of_productions; }
 128    int size  (Production)          const; // length
 129    int length(Production)          const; // length without action symbols
 130    inline Production operator [] (int i)  const { return productions[i]; }
 131    inline NonTerminal lhs(int i)          const { return productions[i][0]; }
 132    inline Production  rhs(int i)          const { return productions[i] + 1; }
 133    inline NonTerminal start()             const { return startSymbol; }
 134    inline Production  start_production () const { return startProduction; }
 135
 136    //////////////////////////////////////////////////////////////////////////
 137    //  Symbols ranges
 138    //////////////////////////////////////////////////////////////////////////
 139    inline int number_of_terminals()       const { return maxTerminal - minTerminal + 1; }
 140    inline int number_of_non_terminals()   const { return maxNonTerminal - minNonTerminal + 1; }
 141    inline int number_of_symbols()         const { return maxNonTerminal - minTerminal + 1; }
 142    inline Terminal    min_terminal()      const { return minTerminal; }
 143    inline Terminal    max_terminal()      const { return maxTerminal; }
 144    inline NonTerminal min_non_terminal()  const { return minNonTerminal; }
 145    inline NonTerminal max_non_terminal()  const { return maxNonTerminal; }
 146    inline NonTerminal max_normal_non_terminal()  const
 147       { return maxNormalNonTerminal; }
 148
 149    ///////////////////////////////////////////////////////////////////////////
 150    //  Shift/reduce encoding
 151    ///////////////////////////////////////////////////////////////////////////
 152    inline Bool  isShift          (State s) const { return s < 0x4000; }
 153    inline Bool  isReduce         (State s) const { return s >= 0x8000; }
 154    inline Bool  isSingleReduce   (State s) const { return s >= 0xc000; }
 155    inline Bool  isShiftReduce    (State s) const { return s & 0x4000; }
 156    inline State makeReduce       (State s) const { return s | 0x8000; }
 157    inline State makeSingleReduce (State s) const { return s | 0xc000; }
 158    inline State makeShiftReduce  (State s) const { return s | 0x4000; }
 159    inline Rule  reduceRule       (State s) const { return s & 0x3fff; }
 160
 161    //////////////////////////////////////////////////////////////////////////
 162    //  Conversion
 163    //////////////////////////////////////////////////////////////////////////
 164    Grammar makeCanonical() const;
 165
 166    //////////////////////////////////////////////////////////////////////////
 167    //  Equivalence class mapping
 168    //////////////////////////////////////////////////////////////////////////
 169    inline EquivMap         map (Symbol A) const { return equiv_map[A]; }
 170    inline const EquivMap * map ()         const { return equiv_classes; }
 171    inline int              map_size()     const { return equiv_classes_size; }
 172    inline Rule             rule_of (Action a) const
 173        { return action_map[First_action - a]; }
 174
 175    //////////////////////////////////////////////////////////////////////////
 176    //  Printing
 177    //////////////////////////////////////////////////////////////////////////
 178    std::ostream& print (std::ostream&, Symbol)                  const; // Print a symbol
 179    std::ostream& print (std::ostream&, Production, Bool = true) const; // Print a production
 180    std::ostream& print (std::ostream&, int, Production)         const; // Print an item
 181    friend std::ostream& operator << (std::ostream&, const Grammar&);   // Print a grammar
 182 };
 183
 184 #endif