xref: /dports/devel/glrparser/glrparser-1.4/glr/glrNode.h

#ifndef GLRNODE

#define GLRNODE

#include <glr/glrGuard.h>
#include <glr/glrSymbolTable.h>
#include <glr/glrGrammar.h>

#ifdef DEBUG_FOREST
extern glrSymbolTable *globalSymbols;
#endif

#include <deque>

typedef enum {glrTerminalNode, glrNonterminalNode, glrEpsilonNode} glrNodeClass;

/**
 *
 * The <tt>glrEdge</tt> class is used internally by the parser to represent the edge
 * of the graph structured stack which goes from some vertex to the vertex assiciated
 * with some active state.
 */
class glrEdge {
  private:
    class glrStateVertex *fromStack;
    class glrState *toState;
  public:
    /**
     *
     * Constructor is the only way to initialize the object.
     */
    glrEdge(class glrStateVertex *fromStackA,class glrState* toStateA){
      fromStack = fromStackA;
      toState = toStateA;
    }

    /**
     *
     * The <tt>from</tt> function returns the vertex which is the edge going from.
     * In fact this vertex is remembered by the vertex asociated witch state stored in
     * this object -- I thing the names of the <tt>from</tt> and <tt>to</tt> functions
     * are a bit missleading.
     */
    class glrStateVertex* const& from() const {
      return fromStack;
    }

    /**
     *
     * The <tt>to</tt> function returns the state witch is the vertex with the <tt>from</tt>
     * vertex as the predcessor associated with.
     */
    class glrState* const& to() const {
      return toState;
    }
};

/**
 *
 * Just a comparing functor to make possible to store the <tt>glrEdge</tt> -- type objects in
 * the STL <tt>set</tt> based classes.
 */
class glrEdgeCompare {
  public:
    bool operator () (const glrEdge &x,const glrEdge &y) const {
      return (x.from()<y.from())||((x.from()==y.from())&&(x.to()<y.to()));
    }
};

/**
 *
 * A set of an edges.
 */
class glrEdgeSet : public set<glrEdge,glrEdgeCompare> {
  public:
    /**
     *
     * This function returns <tt>true</tt> iff this object contains the <tt>subset</tt>
     * set of edges as its subset.
     */
    bool containsSubset(glrEdgeSet const& subset) const {
      if(subset.size()>size()) return false;
      for(glrEdgeSet::iterator iEdge = subset.begin(); iEdge!=subset.end(); ++iEdge){
        if(find(*iEdge)==end()) return false;
      }
      return true;
    }

    /**
     *
     * The set substraction. The function removes from this set of edges the edges
     * contained in the <tt>subset</tt> set of edges.
     */
    void substract(glrEdgeSet const& subset){
      if(empty()) return;
      for(glrEdgeSet::iterator iEdge = subset.begin(); iEdge!=subset.end(); ++iEdge) erase(*iEdge);
    }
};

/**
 *
 * Class <tt>glrNode</tt> is intended to be a the base class for any user defined class(es) that will represent
 * nodes of packed shared forest. You should derive this class to create the class which instances
 * will the parser use to represent the nonterminal nodes of the packed shared forest and specify
 * it as the first argument to the <tt>glrParser</tt> template. Read the quickstart manual to make
 * this clear.
 *
 * You need also to
 * create a <tt>glrNode</tt> -- drived class to represent the terminal nodes. You should instant
 * this class in your overrided <tt>glrParser::readToken</tt> function.
 *
 * Read documantation of <tt>glrGuard</tt> class which is the base class to the <tt>glrNode</tt> class!
 *
 * @see glrGuard
 * @see glrParser
 */
class glrNode : public glrGuard {
  private:
    glrSymbolTable::glrSymbol symbol;
    glrNodeClass type;
    glrEdgeSet edges;

    #ifdef DEBUG
    static int maxNodeId;
    int nodeId;
    #endif
  public:

    #ifdef DEBUG
    int const& getId() const {
      return nodeId;
    }
    #endif

    /**
     *
     * This function is used internally by the parser. It return the stored set of edges where this
     * node is shared in the graph structured stack.
     */
    const glrEdgeSet &edgeSet(){
      return edges;
    }

    /**
     *
     * This function adds an edge to the set of stored edges. It is used internally by the parser.
     */
    void addEdge(class glrStateVertex* fromStackA, class glrState *toStateA){
      edges.insert(glrEdge(fromStackA,toStateA));
    }

    /**
     *
     * This constructor should be called when the instance of the class which
     * represents terminal in the forest is created. You should call it in the head
     * of constructor of such class. <tt>symbolA</tt> is the symbol of the grammar
     * which represents appropriate preterminal.
     */
    glrNode(const glrSymbolTable::glrSymbol &symbolA) : glrGuard() {
      #ifdef DEBUG_FOREST
      nodeId = maxNodeId++;
      cerr << "creating new terminal node with symbol ,," << globalSymbols->getStringFromSymbol(symbolA) << "'' [" << nodeId << "]" << endl;
      #endif
      symbol=symbolA;
      type=glrTerminalNode;
    }

    /**
     *
     * This constructor should be called to create node in the forest in consequence of
     * reduction by the epsilon rule. You should create same constructor
     * in the class you specify as the first argument to the <tt>glrParser</tt> template
     * and call this constructor in it's head. The reduction is according to the
     * rule <tt>ruleA</tt>.
     */
    glrNode(const glrRule* const &ruleA) : glrGuard() {
      #ifdef DEBUG_FOREST
      nodeId = maxNodeId++;
      cerr << "creating new epsilon node [" << nodeId << "] along rule ,,";
      ruleA->print(*globalSymbols,cerr);
      cerr << "''" << endl;
      #endif
      symbol=ruleA->getLeft();
      type=glrEpsilonNode;
    }

    /**
     *
     * This constructor should be called to create node in the forest in consequence of
     * reduction by the nonepsilon rule. You should create same constructor
     * in the class you specify as the first argument to the <tt>glrParser</tt> template
     * and call this constructor in it's head. Reduction is accroding to
     * the rule <tt>ruleA</tt>. <tt>succA</tt> are the appropriate childern nodes
     * coresponding to the symbols at the right side of the rule.
     */
    glrNode(const glrRule* const &ruleA,const deque<glrNode*> &succA) : glrGuard() {
      #ifdef DEBUG_FOREST
      nodeId = maxNodeId++;
      cerr << "creating new nonterminal node [" << nodeId << "] along rule ,,";
      ruleA->print(*globalSymbols,cerr);
      cerr << "''" << endl;
      #endif
      symbol=ruleA->getLeft();
      type=glrNonterminalNode;
    }

    /**
     *
     * You should override the destructor in your <tt>glrNode</tt> -- drived classes
     * and call the <tt>release()</tt> function of remembered <tt>glrGuard</tt> derived
     * objects.
     */
    virtual ~glrNode(){
      #ifdef DEBUG_FOREST
      cerr << "deleting node [" << nodeId << "]" << endl;
      #endif
    }

    /**
     *
     * This function is called by the parser to add other subtree to existing
     * nonterminal node of the forest.
     * You should override it in the class you
     * specify as the first argument to the <tt>glrParser</tt> tamplate. Reduction
     * is according to the rule <tt>ruleA</tt>. <tt>succA</tt> are the appropriate childern nodes
     * coresponding to the symbols at the right side of the rule.
     */
    virtual void addSubtree(const glrRule* const &ruleA,const deque<glrNode*> &succA) {}

    /**
     *
     * Function <tt>getSymbol</tt> returns the symbol particular to this node.
     */
    const glrSymbolTable::glrSymbol &getSymbol() const { return symbol; }

    /**
     *
     * Function <tt>getType()</tt> returns the type of the node. It can be either
     * <tt>glrTerminalNode</tt>, <tt>glrNonterminalNode</tt> or <tt>glrEpsilonNode</tt>.
     */
    const glrNodeClass &getType() const { return type; }
};

/**
 *
 * The <tt>glrNodeSet</tt> class is used internally by the parser to represent the
 * set of the nodes.
 */
class glrNodeSet : public set<glrNode*> {
  public:
    /**
     *
     * This function inserts the nodes cotained in the <tt>nodes</tt> vector to this set.
     */
    void insert(vector<glrNode*> const& nodes){
      for(vector<glrNode*>::const_iterator iNode = nodes.begin(); iNode!=nodes.end(); ++iNode){
        set<glrNode*>::insert(*iNode);
      }
    }
};

#endif