/*==============================================================================
|
|  NAME
|
|     ppParser.h
|
|  DESCRIPTION
|
|     Header file for polynomial parser classes.
|
|  LEGAL
|
|     Primpoly Version 9.1 - A Program for Computing Primitive Polynomials.
|     Copyright (C) 1999-2008 by Sean Erik O'Connor.  All Rights Reserved.
|
|     This program is free software; you can redistribute it and/or
|     modify it under the terms of the GNU General Public License
|     as published by the Free Software Foundation;  version 2
|     of the License.
|
|     This program is distributed in the hope that it will be useful,
|     but WITHOUT ANY WARRANTY; without even the implied warranty of
|     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
|     GNU General Public License for more details.
|
|     You should have received a copy of the GNU General Public License
|     along with this program; if not, write to the Free Software
|     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307,
|     USA.
|
|     The author's address is artifex@seanerikoconnor.freeservers.com
|
==============================================================================*/

#ifndef __PPPARSER_H__

/*=============================================================================
|
| NAME
|
|     Parser, Value, ParserError
|
| DESCRIPTION
|
|     Classes for parsing polynomials.
|
| NOTES
|
|       string s ;
|       Value v ;
|
|       // Create a parser and load the parse tables.
|       Parser p ;
|
|        // Parse a polynomial.
|        s = "2 x ^ 3 + 3 x + 4, 5" ;
|
|        try 
|        {
|            v = p.parse( s ) ;
|            cout << "Parsing the string = " << s << endl ;
|            cout << "We have a polynomial = " ;  v.print() ; cout << endl ;
|        }
|        catch( ParserError & e )
|        {
|            cout << "Parser error:  " << e.what() << endl ;
|        }
|
   Here is the LALR(1) grammar,

    (S          -> Poly Mod)
    (Mod        -> comma integer / EPSILON)
    (Poly       -> Poly + Term / Term)
    (Term       -> Multiplier Power)
    (Multiplier -> integer / EPSILON)
    (Power      -> x / x ^ integer / EPSILON )

    Terminal symbols are ( comma + integer ^ x )

|
+============================================================================*/

#define MAX_NUM_COMMAND_LINE_ARGS 3

// Symbol value for syntax directed translation.
// (User defined)
class Value
{
    public:
        Value() ;
        Value( const Value & v ) ;
        Value & operator=( const Value & v ) ;
        void print() const ;

    // Allow direct access to this simple data type for convenience.
    public:
        int           scalar_ ;  // Coeff, power, or modulus.
        vector< int > f_ ;       // Polynomial f(x).
} ;



class ParserError : public runtime_error
{
    public:
        // Throw with an error message.
        ParserError( const string & description )
			: runtime_error( description )
        {
        } ;

        // Default throw with no error message.
        ParserError()
			: runtime_error( "Parser error:  " )
        {
        } ;

} ; // end class ParserError



class Parser
{
    public:
        // Construct the parser.
        Parser() ;                          
        
        // Destructor.
        ~Parser() ;

        // Copy constructor ;
        Parser( const Parser & parser ) ;

        // Assignment operator.
        Parser & operator=( const Parser & parser ) ;

        // Parse an input string.
        Value parse( string s ) throw( ParserError, bad_exception ) ;


    public:
        // Command line argument parsing.
        void parseCommandLine( int argc, char * argv[] )
               throw( ParserError, bad_exception ) ;

        // Allow direct access for convenience.
        bool testPolynomialForPrimitivity ;
        bool listAllPrimitivePolynomials ;
        bool printStatistics ;
        bool printHelp ;
        bool selfCheck ;
        int p ;
        int n ;
        string testPolynomial ;

	private:
        // Terminal symbols or tokens
        // (from parse tables).
		enum SymbolType
        {
            Dollar = 0,
            Integer,
            Comma,
            Ecks,
            Plus,
            Exp,
                           
            // Nonterminal symbols
            // (from parse tables).
            S,
            Mod,
            Poly,
            Term,
            Multiplier,
            Power,
			NumSymbols
        } ;

        // Action types.
        enum Action
        {
            Shift, Reduce, Accept, Error
        } ;

		// Number of symbols
        // (from parse tables).
        enum  { NumStates       = 15 } ;  // Includes the 0 state.
        enum  { NumProductions  = 11 } ;  // Number of productions.
        enum  { NumTerminals    =  6 } ;  // Number of terminal symbols.
        enum  { NumNonTerminals =  6 } ;  // Number of nonterminal symbols. 
     
        // Tokens and other symbols.
        class Symbol
        {
          public:
              Symbol() : type_( Dollar ), value_(), state_( 0 ) {} ;

              Symbol( SymbolType type, int state ) ;

              Symbol( SymbolType type, int state, Value value )  ;

			  Symbol( const Symbol & s ) ;

              Symbol & operator=( const Symbol & s ) ;

              void print() const ;
   
              SymbolType type_ ;  // Type of terminal or nonterminal.
              Value      value_ ; // Value of the symbol.
              int        state_ ; // State or production number.
        } ;

		// Actions:  shift s, reduce p, accept, error.
        class ActionState
        {
            public:
                ActionState() ;

                ActionState( Action type, int state ) ;

              ActionState( const ActionState & as ) ;

			  ActionState & operator=( const ActionState & as ) ;

                void print() const ;

                Action type_ ;
                int    state_ ;
        } ;
        
		// Allow inner classes to access Parser's private data.
       friend class Value ;
       friend class Symbol ;
       friend class ActionState ;
 
	private:
        // Tokenized input string.
        vector< Symbol > inputStack_ ;

        // Parse stack containing symbols and states.
        vector< Symbol > parseStack_ ;

        // Action table.  
        // action = ACTION_TABLE[ <state at top of parse stack>, <next input token> ]
        // (from parse tables).
        vector< vector< ActionState > > actionTable_ ;

        // GOTO table.
        // For reduce actions, gives the new state to push.
        // (from parse tables).
        vector< vector< int > > gotoTable_ ;

        // Error messages.
        // (from parse tables).
        vector< string > errorMessage_ ;
        
        // Productions:  Left side non-terminal symbol + production number.
        // (from parse tables).
        vector< Symbol > production_ ;

        // Parse string into tokens.
        // (User defined)
        void tokenize( string sentence ) ;
        
        // Fill in the ACTION, GOTO, and ERROR_MESSAGE tables.
        inline void initializeTables() ;
        
        // Add a new entry to the Action Table.
        void insertAction( int    state,      SymbolType terminal, 
                                  Action actionType, int      actionState );

        void insertGoto( int state, SymbolType nonterm, int newState ) ;        
        
        void insertProduction( int prodNum, SymbolType nonTerm, int rhsLength );
        
        void insertErrorMessage( int state, string errorMessage ) ;
} ;

#endif // __PPPARSER_H__