cfg.H

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

#ifndef ARCHON_UTILITIES_CFG_H
#define ARCHON_UTILITIES_CFG_H

#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>

#include <archon/util/exception.H>
#include <archon/util/ref.H>
#include <archon/util/text.H>

namespace Archon
{
  namespace Utilities
  {
    using namespace std;

    class CFG
    {
    public:
      struct Rule;
      struct FirstSets;
      struct FollowSets;

      struct Item
      {
        int rule;
        int production;
        int position;
        Item(int rule, int production, int position):
          rule(rule), production(production), position(position) {}
      };

      struct Symbol
      {
        friend class CFG;
        friend class FirstSets;
        friend class FollowSets;

      public:
        enum Type
        {
          nil = 0,
          terminal,
          nonterminal,
          action
        };

      private:
        Type type;
        int index; // -1 is 'null', -2 is 'copy' and -3 is 'concat'
        vector<int> args; // For actions only

        Symbol(): type(nil) {}
        Symbol(Type type, int index): type(type), index(index) {}
        Symbol(int index, vector<int> args):
          type(action), index(index), args(args) {}

      public:
        Type getType() const { return type; }
        int getIndex() const { return index; }
        const vector<int> &getArgs() const { return args; }
      };

      class Production
      {
        friend class CFG;
        friend class Rule;
        friend class FirstSets;
        friend class FollowSets;

        vector<Symbol> symbols;

        Production() {}
        Production(const vector<Symbol> &symbols): symbols(symbols) {}

      public:
        int getNumberOfSymbols() const { return symbols.size(); }
        const Symbol &getSymbol(int i) const { return symbols[i]; }
      };

      class Rule
      {
        friend class CFG;
        friend class FirstSets;
        friend class FollowSets;

        string name;
        vector<Production> productions;

        Rule(string name): name(name) {}

        void addProduction(const vector<Symbol> &symbols)
        {
          productions.push_back(Production(symbols));
        }

      public:
        int getNumberOfProductions() const { return productions.size(); }
        const Production &getProduction(int i) const { return productions[i]; }
      };

      struct Actor
      {
        virtual ~Actor() {}

        virtual int getNumberOfMethods() const = 0;

        virtual int getMethodArity(int methodIndex) const = 0;

        virtual string getMethodName(int methodIndex) const = 0;
      };

    private:
      vector<string> terminals;
      vector<Rule> rules;

      map<string, int> terminalMap;    // Maps terminal names to terminal indices.
      map<string, int> nonterminalMap; // Maps non-terminal names to rule indices.

      const Actor *actor; // Defines the known methods and knows how to call them. Is optional.

      void updateRuleIndices(vector<int>);
      string chooseUniqueName(string, int);
      void findNullableNonTerminals(vector<bool> &, vector<vector<int> > &);
      void addNullableCombinations(unsigned, bool,
                                   const Production &,
                                   const vector<bool> &,
                                   const vector<vector<int> > &,
                                   vector<Symbol> &,
                                   vector<Production> &);
      int eliminateCyclesVisit(int, vector<int> &, list<pair<int, int> > &);
      string printProductionRightSide(const Production &, int mark=-1) const;

    public:
      CFG(const Actor *a=0): actor(a) {}
      ~CFG();

      int getNumberOfTerminals() const { return terminals.size(); }
      int getNumberOfRules() const { return rules.size(); }
      const Rule &getRule(int i) const { return rules[i]; }

      int defineTerminal(string name);
      int defineNonterminal(string name);

      static const Symbol &nil();

      void addProd(int nontermIndex, const vector<Symbol> &);
      void addProd(int nontermIndex, Symbol=nil(), Symbol=nil(),
                   Symbol=nil(), Symbol=nil(), Symbol=nil(),
                   Symbol=nil(), Symbol=nil(), Symbol=nil());

      static Symbol term(int terminalIndex)
      {
        return Symbol(Symbol::terminal, terminalIndex);
      }

      static Symbol nont(int nonterminalIndex)
      {
        return Symbol(Symbol::nonterminal, nonterminalIndex);
      }

      static Symbol act(int methodIndex,
                        int arg1 = -2, int arg2 = -2, int arg3 = -2,
                        int arg4 = -2, int arg5 = -2, int arg6 = -2,
                        int arg7 = -2);

      static Symbol null() { return act(-1); }

      static Symbol copy(int arg) { return act(-2, arg); }

      static Symbol concat(int arg1, int arg2) { return act(-3, arg1, arg2); }

      class FirstSets
      {
        friend struct FollowSets;

        const CFG &grammar;
        vector<set<int> > terminals; // One entry per nonterminal
        vector<bool> nullable; // One entry per nonterminal

      public:
        FirstSets(const CFG &);

        bool includeFirstSet(const Item &, set<int> &) const;

        string print(int width = 0) const;
      };

      class FollowSets
      {
        const CFG &grammar;
        vector<set<int> > terminals; // -1 represents EOI

      public:
        FollowSets(const FirstSets &);
        const set<int> &get(int i) const { return terminals[i]; }
        string print(int width = 0) const;
      };

      string printTerminal(int index) const;

      string printNonterminal(int index) const;
      string printProduction(int rule, int production) const;
      string printItem(const Item &) const;
      string print(int width = 0) const;

      void introduceNewStartSymbol();

      void eliminateEpsilonProductions();

      void eliminateCycles();

      // void eliminateDeadNonTerminals();

      void eliminateMidRuleActions();
    };
  }
}

#endif // ARCHON_UTILITIES_CFG_H

---