lr_parser_base.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).
 */


/*

While Bison is a parser generator that outputs C source code, this
parser can and must be configured at run-time. This has both
advantages and draw-backs. One adavantage is that the grammer need not
be known at compile-time, and a draw-back is that the parsing tables
needs to be re-created every time your application is re-started.

Other advantages compared to Bison:

- Totally re-entrant (multiple threads may use the same parser
instance to parse different inputs at the same time)

- No memory leak on abrupt termination of the parser

- Semantic actions may throw exceptions to terminate the parser, and
such exceptions travel all the way back to the point where your
application calls the parse method.

- The parser can output various kinds of information while preparing
parsing tables and while running, which may be a great help for
those who try to understand how an LR parser works.

- Lets you choose which of the generally known parser table types to
create: simple, canonical or look-ahead. Bison is fixed to
look-ahead (LALR).


NOTE: When using the special 'concat' method in a grammar action you
must ensure that its arguments always are either null or a
reference to LrParserBase::Attr<ustring> ie. a unicode string
attribute.

Whenever possible make productions left recursive instead of right
recursive as it will keep the stack size (memory usage)
smaller. Eg. for a simple sequence 'seq -> seq item' is prefered over
'seq -> item seq'.

*/

#ifndef ARCHON_UTILITIES_LR_PARSER_BASE_H
#define ARCHON_UTILITIES_LR_PARSER_BASE_H

#include <string>
#include <vector>
#include <typeinfo>

#include <archon/util/exception.H>
#include <archon/util/ref.H>
#include <archon/util/cfg.H>
#include <archon/util/lexer.H>
#include <archon/util/logger.H>

namespace Archon
{
  namespace Utilities
  {
    using namespace std;

    class LrParserBase
    {
    public:
      struct Context
      {
        virtual ~Context() {}
        virtual void parserError() = 0;
      };

      struct Printer
      {
        virtual string print(const RefAnyConst &attribute) const = 0;
        virtual ~Printer() {}
      };

    protected:
      struct CallException: virtual Exception
      {
        int arg;
        const type_info &t;
        CallException(string l, int arg, const type_info &t): Exception(l), arg(arg), t(t) {}
      };

      struct AttributeTypeException: virtual Exception
      {
        AttributeTypeException(string l, string m): Exception(l, m) {}
      };

      struct Production
      {
        int rule;       // index of nonterminal on the left hand side
        int production; // index of production within left hand nonterminal
        vector<int> right; // Right hand side symbols i<0 is nonterminal -1-i, i>=0 is terminal i
        int method; // Method index, -1, -2 & -3 are special methods and -4 is no method
        vector<int> args;

        Production(int rule, int production):
          rule(rule), production(production), method(-4) {}
      };

      struct ActorBase: CFG::Actor
      {
        virtual bool verifyContext(const Context &) const = 0;
        virtual RefAnyConst call(int method, const vector<RefAnyConst> &args, Context &) const = 0;
      };

      CFG grammar;
      vector<Production> productions;

      LrParserBase(CFG &, const ActorBase *, const Printer *);

      virtual int getAction(int state, int terminal) const = 0;

      virtual int getGoto(int state, int nonterminal) const = 0;

    private:
      const ActorBase *actor;
      const Printer *printer;

      void attrTypeError(int arg, int rule, int production,
                         const type_info &actual,
                         const type_info &expected) const;

      RefAnyConst parse(LexerBase &, Context *, Logger *) const;

    public:
      template<class C>
      class Actor: public ActorBase
      {
        struct MethodBase: virtual RefObjectBase
        {
          virtual ~MethodBase() {}
          virtual string getName() const = 0;
          virtual int getArity() const = 0;
          virtual RefAnyConst call(C &context, const vector<RefAnyConst> &) const = 0;
        };

        vector<Ref<const MethodBase> > methods;
        map<string, int> methodMap;      // Maps method names to method indices.

        bool verifyContext(const Context &c) const
        {
          return dynamic_cast<const C *>(&c);
        }

        RefAnyConst call(int method, const vector<RefAnyConst> &args, Context &c) const
        {
          return methods[method]->call(static_cast<C &>(c), args);
        }

        /*
         * The purpose of the following method classes are to convert a
         * general call into a specific real method call. 'MethodV<n>'
         * knows of a method that takes n arguments and return nothing
         * (void). 'Method<n>' knows of a mehod that takes n arguments
         * and return one value.
         *
         * Note: If you need more arguments then just add more classes
         * yourself it is straight foreward.
         */
        class MethodV0;
        template<class> class Method0;
        template<class> class MethodV1;
        template<class, class> class Method1;
        template<class, class> class MethodV2;
        template<class, class, class> class Method2;

        int registerMethod(string name, const MethodBase *m)
        {
          pair<map<string, int>::iterator, bool> r =
            methodMap.insert(make_pair(name, methods.size()));
          if(!r.second)
            ARCHON_THROW1(ArgumentException, "Redefinition of method '" + name + "'");
          methods.push_back(m);
          return methods.size()-1;
        }

      public:
        int getNumberOfMethods() const
        {
          return methods.size();
        }

        int getMethodArity(int i) const
        {
          // Handle the special actions 'null', 'copy' & 'concat'
          return i < -2 ? 2 : i < -1 ? 1 : i < 0 ? 0 : methods[i]->getArity();
        }

        string getMethodName(int i) const
        {
          // Handle the special actions 'null', 'copy' & 'concat'
          return i < -2 ? "<concat>" : i < -1 ? "<copy>" : i < 0 ? "<null>" : methods[i]->getName();
        }

        int registerMethod(string name, void (C::*method)())
        {
          return registerMethod(name, new MethodV0(name, method));
        }

        template<class R>
        int registerMethod(string name, Ref<const R> (C::*method)())
        {
          return registerMethod(name, new Method0<R>(name, method));
        }

        template<class A1>
        int registerMethod(string name,
                           void (C::*method)(const Ref<const A1> &))
        {
          return registerMethod(name, new MethodV1<A1>(name, method));
        }

        template<class R, class A1>
        int registerMethod(string name,
                           Ref<const R> (C::*method)(const Ref<const A1> &))
        {
          return registerMethod(name, new Method1<R, A1>(name, method));
        }

        template<class A1, class A2>
        int registerMethod(string name,
                           void (C::*method)(const Ref<const A1> &,
                                             const Ref<const A2> &))
        {
          return registerMethod(name, new MethodV2<A1, A2>(name, method));
        }

        template<class R, class A1, class A2>
        int registerMethod(string name,
                           Ref<const R> (C::*method)(const Ref<const A1> &,
                                                     const Ref<const A2> &))
        {
          return registerMethod(name, new Method2<R, A1, A2>(name, method));
        }
      };

      virtual ~LrParserBase();

      void parse(LexerBase &lexer, Logger *l=0) const
      {
        parse(lexer, 0, l);
      }

      void parse(LexerBase &lexer, Context &c, Logger *l=0) const
      {
        parse(lexer, &c, l);
      }

      template<class R>
      void parse(LexerBase &lexer, Context &c, Ref<const R> &result, Logger *l=0)
      {
        RefAnyConst r1 = parse(lexer, &c, l);
        const R *r2 = dynamic_cast<const R *>(r1.get());
        if(!r2 && r1)
          ARCHON_THROW1(AttributeTypeException, string("Parser result has type ") +
                        typeid(*r1.get()).name() + " but its type was "
                        "expected to be " + typeid(R).name());
        result = r2;
      }
    };
  }
}

#endif // ARCHON_UTILITIES_LR_PARSER_BASE_H

---