/*==============================================================================
|
|  NAME
|
|     ppParser.cpp
|
|  DESCRIPTION
|
|     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.
|
==============================================================================*/

/*------------------------------------------------------------------------------
|                                Include Files                                 |
------------------------------------------------------------------------------*/

#include <cstdlib>      // abort()
#include <iostream>     // Basic stream I/O.
#include <new>          // set_new_handler()
#include <cmath>        // Basic math functions e.g. sqrt()
#include <complex>      // Complex data type and operations.
#include <fstream>      // File stream I/O.
#include <sstream>      // String stream I/O.
#include <vector>       // STL vector class.
#include <string>       // STL string class.
#include <algorithm>    // Iterators.
#include <stdexcept>    // Exceptions.
#include <cassert>      // assert()

using namespace std;

#include "ctype.h"       // C string functions.


/*------------------------------------------------------------------------------
|                                PP Include Files                              |
------------------------------------------------------------------------------*/

#include "Primpoly.h"       // Global functions.
#include "ppArith.h"        // Basic arithmetic functions.
#include "ppBigInt.h"       // Arbitrary precision integer arithmetic.
#include "ppStatistics.h"   // Statistics collection for factoring and poly finding.
#include "ppFactor.h"       // Prime factorization and Euler Phi.
#include "ppParser.h"	       // Parsing of polynomials and I/O services.
#include "ppPolynomial.h"	  // Polynomial operations and mod polynomial operations.
#include "ppUnitTest.h"     // Complete unit test.


/*=============================================================================
|
| NAME
|
|     Parser
|
| DESCRIPTION
|
|     Class for multiprecision integer arithmetic.
|
|     Here are the operations supported where B is a multiprecision
|     integer and d is an integer, and s is a decimal ascii string.
|
| NOTES
|
|     The member functions and friends are documented in detail ppBigInt.cpp
|
+============================================================================*/

// Default constructor.
Parser::Parser()
    : inputStack_()
    , parseStack_()
	, testPolynomial( "" )
{
    initializeTables() ;

    // TODO use initializer list.
        testPolynomialForPrimitivity = false,  // Test a given input polnomial for primitivity?
        listAllPrimitivePolynomials  = false,  // Print ALL primitive polynomials?
        printStatistics              = false,  // Print statistics?
        printHelp                    = false,  // Print help information?
        selfCheck                    = false ; // Do a self-check?  Time consuming!
}



// Destructor
Parser::~Parser()
{
    // Private data destroy themselves.
}


// Copy constructor
Parser::Parser( const Parser & parser )
    : inputStack_( parser.inputStack_ )
    , parseStack_( parser.parseStack_ )
{
}



Parser & Parser::operator=( const Parser & parser )
{
    // Check for self-assignment.
    if (this == &parser)
             return *this ;

    //
    inputStack_ = parser.inputStack_ ;
    parseStack_ = parser.parseStack_ ;

    // Return reference to this object.
    return *this ;
}


Value::Value( const Value & v )
                    : scalar_( v.scalar_ )
                    , f_( v.f_ )
                {
} ;


Value & Value::operator=( const Value & v )
                {
                    // Check for initializing to oneself:  pass back a reference to
                    // the unchanged object.
                    if (this == &v)
                        return *this ;

                    scalar_ = v.scalar_ ;
                    f_ = v.f_ ;

                    // Pass back the object so we can concatenate assignments.
                    return *this ;
                }


Value::Value()
                       : scalar_( 0 )
                       , f_(1, 0) // f(x) = 0
                       {
                       }

// Debug print.
// (from user)
void Value::print() const
				{
					 cout << "(scalar: " << scalar_ ;
                     cout << " : poly, deg " << f_.size()-1 << " f( x ) = " ;

                     // Special case of f(x) = const.
                     if (f_.size() == 1)
                         cout << f_[ 0 ] << endl ;
                     else
                     {
                         // Print from high to low degree.
                         for (int deg = f_.size() - 1 ;  deg >= 0 ;  --deg)
                         {
                             // x^n has a nonzero coefficient.
                             if (f_[ deg ] != 0)
                             {
                                 int coeff = f_[ deg ] ;

                                 // Print coeff unless it is 1.
                                 if (coeff != 1)
                                     cout << coeff ;

                                 // Print x term.
                                 if (deg == 1)
                                     cout << " x " ;

                                 // Print x ^ 2 ... x ^ n terms
                                 else if (deg != 0)
                                     cout << " x ^ " << deg << " " ;

                                // Print +, but only when followed by a lower degree term or constant.
                                // e.g. x^2 + 2 x, x + 3
                                if ( (deg >= 2 && f_[ deg - 1 ] != 0) ||
                                     (deg == 1 && f_[ 0 ] != 0) )

                                    cout << " + " ;
                              }
                         }

                     } // end f(x) = 0

					 return ;
				} ;



              Parser::Symbol::Symbol( SymbolType type, int state )
                  : type_( type ), value_(), state_( state ) {} ;

              Parser::Symbol::Symbol( SymbolType type, int state, Value value )
                  : type_( type ), state_( state ), value_( value ) {} ;

Parser::Symbol::Symbol( const Symbol & s )
                    : type_( s.type_ )
                    , value_( s.value_ )
                    , state_( s.state_ )
                {
} ;

Parser::Symbol & Parser::Symbol::operator=( const Symbol & s )
              {
                    // Check for initializing to oneself:  pass back a reference to
                    // the unchanged object.
                    if (this == &s)
                        return *this ;

                    type_  = s.type_ ;
                    value_ = s.value_ ;
                    state_ = s.state_ ;

                    // Pass back the object so we can concatenate assignments.
                    return *this ;
} ;


Parser::ActionState::ActionState() : type_( Error ), state_( 0 ) {}

Parser::ActionState::ActionState( Action type, int state )
                      : type_( type ), state_( state ) {}

Parser::ActionState::ActionState( const ActionState & as )
                    : type_(  as.type_ )
                    , state_( as.state_ )
                {
                }

Parser::ActionState & Parser::ActionState::operator=( const ActionState & as )
              {
                    // Check for initializing to oneself:  pass back a reference to
                    // the unchanged object.
                    if (this == &as)
                        return *this ;

                    type_  = as.type_ ;
                    state_ = as.state_ ;

                    // Pass back the object so we can concatenate assignments.
                    return *this ;
                }


// Debug print.
// (from user)
void Parser::ActionState::print() const
				{
                    string s ;
			        cout << "action( " ;
                    switch( type_ )
                     {
                         case Shift:  s = "shift" ;   break ;
                         case Reduce: s = "reduce" ;  break ;
                         case Accept: s = "accept" ;  break ;
                         case Error:  s = "error" ;   break ;
                     }
                     cout << s ;
                     cout << state_ << " )" ;

					 return ;
				} ;

// Debug print.
// (from user)
void Parser::Symbol::print() const
				{
					 cout << "sym(name:  " ;
                     string name ;
                     switch( type_ )
                     {
                         case Dollar:       name = "$" ; break ;
                         case Integer:      name = "Int" ; break ;
                         case Comma:        name = "," ; break ;
                         case Ecks:         name = "x" ; break ;
                         case Plus:         name = "+" ; break ;
                         case Exp:          name = "^" ; break ;
                         case S:            name = "S" ; break ;
                         case Mod:          name = "mod" ; break ;
                         case Poly:         name = "Poly" ; break ;
                         case Term:         name = "Term" ; break ;
                         case Multiplier:   name = "Multiplier" ; break ;
                         case Power:        name = "Power" ; break ;
                     }
                     cout << name << " |state: " << state_  << " |value: " ;
					 value_.print() ;
					 cout << ")" ;

					 return ;
				} ;

// Initialize ACTION, GOTO, and ERROR_MESSAGE tables
// (from parse tables).
void Parser::initializeTables()
{
    // Expand the rows of the ACTION table to hold all the states.
    actionTable_.resize( NumStates ) ;

    // For state = 0, for each terminal, insert an action and a state.
    // (from parse tables)
    insertAction( 0,    Integer,    Shift,      3 ) ;
    insertAction( 0,    Ecks,       Reduce,     8 ) ;
    insertAction( 0,    Comma,      Reduce,     8 ) ;
    insertAction( 0,    Dollar,     Reduce,     8 ) ;
    insertAction( 0,    Plus,       Reduce,     8 ) ;

    insertAction( 1,    Dollar,     Accept,     0 ) ;

    insertAction( 2,    Comma,      Shift,      7 ) ;
    insertAction( 2,    Plus,       Shift,      8 ) ;
    insertAction( 2,    Dollar,     Reduce,     3 ) ;

    insertAction( 3,    Ecks,       Reduce,     7 ) ;
    insertAction( 3,    Comma,      Reduce,     7 ) ;
    insertAction( 3,    Dollar,     Reduce,     7 ) ;
    insertAction( 3,    Plus,       Reduce,     7 ) ;

    insertAction( 4,    Comma,      Reduce,     5 ) ;
    insertAction( 4,    Dollar,     Reduce,     5 ) ;
    insertAction( 4,    Plus,       Reduce,     5 ) ;

    insertAction( 5,    Ecks,       Shift,      10 ) ;
    insertAction( 5,    Comma,      Reduce,     11 ) ;
    insertAction( 5,    Dollar,     Reduce,     11 ) ;
    insertAction( 5,    Plus,       Reduce,     11 ) ;

    insertAction( 6,    Dollar,     Reduce,     1 ) ;

    insertAction( 7,    Integer,    Shift,      11 ) ;

    insertAction( 8,    Integer,    Shift,      3 ) ;
    insertAction( 8,    Ecks,       Reduce,     8 ) ;
    insertAction( 8,    Comma,      Reduce,     8 ) ;
    insertAction( 8,    Dollar,     Reduce,     8 ) ;
    insertAction( 8,    Plus,       Reduce,     8 ) ;

    insertAction( 9,    Comma,      Reduce,     6 ) ;
    insertAction( 9,    Dollar,     Reduce,     6 ) ;
    insertAction( 9,    Plus,       Reduce,     6 ) ;

    insertAction( 10,    Comma,      Reduce,    9 ) ;
    insertAction( 10,    Exp,        Shift,    13 ) ;
    insertAction( 10,    Dollar,     Reduce,    9 ) ;
    insertAction( 10,    Plus,       Reduce,    9 ) ;

    insertAction( 11,    Dollar,     Reduce,    2 ) ;

    insertAction( 12,    Comma,      Reduce,    4 ) ;
    insertAction( 12,    Dollar,     Reduce,    4 ) ;
    insertAction( 12,    Plus,       Reduce,    4 ) ;

    insertAction( 13,    Integer,    Shift,    14 ) ;

    insertAction( 14,    Comma,      Reduce,   10 ) ;
    insertAction( 14,    Dollar,     Reduce,   10 ) ;
    insertAction( 14,    Plus,       Reduce,   10 ) ;


    // Expand the rows of the GOTO table to hold all the states.
    gotoTable_.resize( NumStates ) ;

    // Insert GOTOs for state 0.
    // (from parse tables)
    insertGoto( 0,  S,              1 ) ;
    insertGoto( 0,  Poly,           2 ) ;
    insertGoto( 0,  Term,           4 ) ;
    insertGoto( 0,  Multiplier,     5 ) ;

    insertGoto( 2,  Mod,            6 ) ;

    insertGoto( 5,  Power,          9 ) ;

    insertGoto( 8,  Term,           12 ) ;
    insertGoto( 8,  Multiplier,     5 ) ;



    // Expand the rows of the ACTION table to hold all the states.
    // Allow space in 0th slot (unused).
    production_.resize( NumProductions + 1 ) ;

    // Insert the productions.
    // (from parse tables)
    insertProduction(  1,      S,           2 ) ; // S   -> Poly Mod
    insertProduction(  2,      Mod,         2 ) ; // Mod -> , integer
    insertProduction(  3,      Mod,         0 ) ; // Mod -> EPSILON
    insertProduction(  4,      Poly,        3 ) ; // Poly -> Poly + Term
    insertProduction(  5,      Poly,        1 ) ; // Poly -> Term
    insertProduction(  6,      Term,        2 ) ; // Term -> Multiplier Power
    insertProduction(  7,      Multiplier,  1 ) ; // Multiplier -> integer
    insertProduction(  8,      Multiplier,  0 ) ; // Multiplier -> EPSILON
    insertProduction(  9,      Power,       1 ) ; // Power -> x
    insertProduction( 10,      Power,       3 ) ; // Power -> x ^ integer
    insertProduction( 11,      Power,       0 ) ; // Power -> EPSILON

    errorMessage_.resize( NumStates ) ;
    insertErrorMessage(  1, "Expecting to see end of the polynomial" ) ;
    insertErrorMessage(  4, "Expecting to see + or end of the polynomial" ) ;
    insertErrorMessage(  7, "Expecting to see mod after ," ) ;
    insertErrorMessage(  6, "Expecting to see ," ) ;
    insertErrorMessage( 13, "Expecting to see an exponent after x ^" ) ;
    insertErrorMessage(  3, "Expecting to see x or , or end of the polynomial" ) ;
    insertErrorMessage( 10, "Expecting to see x^ or x or x ^ integer" ) ;
    insertErrorMessage( 11, "Expecting to see end of the polynomial after , integer" ) ;
    insertErrorMessage( 12, "Expecting to see , end of polynomial or + after a term" ) ;
    insertErrorMessage( 14, "Expecting to see , or + end of polynomial after x ^ integer" ) ;
    insertErrorMessage(  9, "Expecting to see , or end of polynomial after a term" ) ;
    insertErrorMessage(  2, "Expecting to see mod or + term or , integer or end of polynomial" ) ;
    insertErrorMessage(  5, "Expecting to see a power after a coefficient or x or ," ) ;
    insertErrorMessage(  8, "Expecting to see a term after a + or a term or coefficient" ) ;
    insertErrorMessage(  0, "Expecting to see the start of the polynomial or next term or coefficient" ) ;
}

        // Add a new entry to the Action Table.
        void Parser::insertAction( int    state,      SymbolType terminal,
                                  Action actionType, int      actionState )
        {
            // Create a new action.
            ActionState as( actionType, actionState ) ;

            // Insert it into the ACTION table.
            actionTable_[ state ].resize( NumTerminals ) ;
            actionTable_[ state ][ terminal ] = as ;
        } ;

        void Parser::insertGoto( int state, SymbolType nonterm, int newState )
        {
            // Insert into the GOTO table.
            gotoTable_[ state ].resize( NumSymbols ) ;
            gotoTable_[ state ][ nonterm ] = newState ;
        } ;

        void Parser::insertProduction( int prodNum, SymbolType nonTerm, int rhsLength )
        {
            // Insert into the production table.
            production_[ prodNum ].type_  = nonTerm ;
            production_[ prodNum ].state_ = rhsLength ;
        } ;

        void Parser::insertErrorMessage( int state, string errorMessage )
        {
             errorMessage_[ state ] = errorMessage ;
        }


// Return the next token from the input string to be parsed
void Parser::tokenize( string sentence )
{
	Symbol tok ;

    // Starting position to scan.
    int pos = 0 ;

    bool minusSignDetected = false ;

    // Clear the token stack.
    inputStack_.clear() ;

    // Scan sentence to end.
    while( pos < sentence.length() )
    {
        // Skip whitespace.
        while ( iswspace( sentence[ pos ]) && pos < sentence.length() )
            ++pos ; // Advance to next token.

        // ----------------< from user >----------------------
        #ifdef DEBUG_PP_PARSER
        cout << "tokenize:  sentence[ " << pos << " ] = " << sentence[ pos ] << endl ;
        #endif

        // Read an integer.
        if (isdigit( sentence[ pos ]) && pos < sentence.size())
        {
            // TODO how to handle overflow?
            int num = 0 ;
            while( isdigit( sentence[ pos ]) && pos < sentence.size())
            {
				char asciiDigit[ 2 ] = "\0" ; asciiDigit[ 0 ] = sentence[ pos ] ;
                num = 10 * num + atoi( asciiDigit ) ;
                ++pos ; // Advance to next token.
            }

            tok.type_          = Integer ;
            tok.value_.scalar_ = num ;

            // Apply a minus sign to this number.
            if (minusSignDetected)
            {
                tok.value_.scalar_ = -tok.value_.scalar_ ;
                minusSignDetected = false ;
            }
        }
        else
        {
            tok.value_.scalar_ = 0 ;

            // Read another type of token.
            switch( sentence[ pos ] )
            {
                case '+' :
                    tok.type_ = Plus ;
                break ;

                // Make this look like a plus symbol to the parser:  we'll let this lexer
                // apply it to the next integer we see.  If there isn't an integer following
                // the minus sign, it's an error for the parser anyway!
                case '-' :
                    tok.type_ = Plus ;
                    minusSignDetected = true ;
                break ;

                case '^' :
                    tok.type_ = Exp ;
                break ;

                case 'x' :
                case 'X' :
                    tok.type_ = Ecks ;
                break ;

                case ',' :
                    tok.type_ = Comma ;
                break ;

                case '$' :
                     tok.type_ = Dollar ;
                 break ;

                default:
                    tok.type_ = Dollar ; // TODO should be error.
            } ;
            // ----------------< from user >----------------------

            ++pos ; // Advance to next token.
        } // end else

        // Push token on stack.
        inputStack_.push_back( tok ) ;

        #ifdef DEBUG_PP_PARSER
        cout << "    Push token " ; tok.print() ; cout << endl ;
        #endif

    } // end while

    // At end of input, push the $ terminator symbol.
    tok.type_ = Dollar ;
    tok.value_.scalar_ = 0 ;

    inputStack_.push_back( tok ) ;

    #ifdef DEBUG_PP_PARSER
    cout << "    Push last token " ; tok.print() ; cout << endl ;
    #endif

    reverse( inputStack_.begin(), inputStack_.end() ) ;
}

// Standard LALR(1) parser algorithm.
// Syntax directed translation (User defined).
/*
       The initial parser configuration is

            (s0 | a1 ... an $)

        a1 ... an is the set of input tokens
        s0 = 0 is the initial state

        The parse stack is to the left of the bar and the unprocessed
        input is to the right.  Now suppose the configuration is

            (s0 X1 ... Xm-r sm-r Xm-r+1 sm-r+1 ... xm sm | ai ai+1 ... an $)

        There are four possible things we can do:

        (1)  Shift the input token and push a new state.

             ACTION[ sm, ai ] = shift s
             (s0 X1 ... Xm sm ai s | ai+1 ... an $)

        (2)  Reduce.  Pop the stack, push the reduction and new state.
             Also do a syntax-directed evaluation using the values
             of the symbols in the production A -> beta which we just reduced.

             ACTION[ sm, ai ] = reduce( A -> beta = Xm-r+1 ... Xm)
             (s0 X1 ... Xm-r sm-r A s | ai+1 ... an $)

             where s = GOTO[ sm-r, A ] and r = length( beta )

        (3)  Accept.  The sentence is in the grammar;  halt.

             ACTION[ sm, ai ] = accept

        (4)  Error state.   Produce an error message using the current
             parsing state and lookahead symbol ai.

             ACTION[ sm, ai ] = error

*/
Value Parser::parse( string sentence )
             throw( ParserError, bad_exception )
{
    Value retVal ; // Default to f(x) = 0, mod 0.

    // Null string check.
    if (sentence.size() == 0)
        return retVal ;

    // Tokenize the input string.
    tokenize( sentence ) ;

    // Initialize the parse stack to the zero state.
    parseStack_.clear() ;

    Symbol s( S, 0 ) ;
    parseStack_.push_back( s ) ;

    #ifdef DEBUG_PP_PARSER
    cout << endl << endl << "parser:  begin parsing" << endl ;
    cout << "    the sentence = " << sentence << endl ;
    #endif

    // Parse until we accept, error out or run out of input.
    while( inputStack_.size() > 0 )
    {
        // Grab the current state and the lookahead token.
        int        currentState = parseStack_.back().state_ ;
        Symbol     lookahead    = inputStack_.back() ;


        // Dump the parse and input stacks for debugging.
        #ifdef DEBUG_PP_PARSER
        vector< Symbol >::const_iterator i ;

        cout << endl << endl << "    parse stack = " << endl ;

        for (i = parseStack_.begin() ;  i != parseStack_.end() ;  ++i)
        {
            (*i).print() ;
            cout << endl ;
        }

        cout << endl << "    input stack = " << endl ;
		i = inputStack_.end()-1 ;
        while (i >= inputStack_.begin())
        {
            (*i).print() ;
            cout << endl ;
			if (i == inputStack_.begin())
			    break ;
			--i ;
        }
        #endif

        // Look up the action (shift 3), (reduce 2), etc.
        ActionState actionState = actionTable_[ currentState ][ lookahead.type_ ] ;

        // Debug dump the action.
        #ifdef DEBUG_PP_PARSER
        cout << endl << "    action = " ;
	    actionState.print() ;
	    cout << endl ;
        #endif

        // Look at the action required.
        switch( actionState.type_ )
        {
            case Shift:
            {
                //  Shift the next token off the input stack.
                if (inputStack_.size() == 0)
                    // Throw a parser error of unexpected input.
                    // (Shouldn't get here).
                    throw ParserError( errorMessage_[ 0 ] ) ;

                inputStack_.pop_back() ;

                //  Push the input symbol and new state onto the parse stack.
                int newState = actionState.state_ ;

                Symbol s( lookahead.type_, newState, lookahead.value_ ) ;
                parseStack_.push_back( s ) ;
            }
            break ;

            case Reduce:
            {
                // Fetch the production A -> beta, where beta = Xm-r+1 ... Xm)
                int productionNum = actionState.state_ ;

                // Get the left hand side non-terminal A.
                SymbolType prodNonTerm = production_[ productionNum ].type_ ;

                // Get r, the length of beta.
                // If the production is A -> EPSILON, beta = EPSILON, r = 0.
                int rhsProductionLength = production_[ productionNum ].state_ ;

                // Carry out the syntax directed translation using
                // the symbols of beta and its states
                //     Xm-r+1 sm-r+1 ... Xm sm
                // which are on the top of the stack and the nonterminal A.
                // (User defined)
                #ifdef DEBUG_PP_PARSER
                cout << "    (reduce " << productionNum << " )" << endl ;
                #endif

                // The symbol/state  A s to be pushed onto the parse
                // stack after reduction.  A.value_ is the syntax-directed
                // value after parsing the reduction in the switch statements
                // below.
                Symbol as( prodNonTerm,  0 ) ;
                int topIndex = parseStack_.size() - 1 ;
                int i = 0 ;

                switch( productionNum )
                {
                    // ----------------< case from parse tables >----------------
                    // Reduce (S -> POLY MOD)
                    case 1:
                    {
                        // ------------< Syntax directed translation from user >-----------
                        // parse stack = (POLY MOD |
                        // A.poly = POLY and A.scalar = MOD
                        as.value_.f_      = parseStack_[ topIndex - 1 ].value_.f_ ;
                        as.value_.scalar_ = parseStack_[ topIndex     ].value_.scalar_ ;

                        // ----------------< debug print from parse tables >----------------
                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce (S -> POLY MOD)" << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;

                    // Reduce (MOD -> COMMA INTEGER)
                    case 2:
                    {
                        // A.scalar = INTEGER
                        as.value_.scalar_ = parseStack_[ topIndex ].value_.scalar_ ;

                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce (MOD -> COMMA INTEGER)" << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;

                    // Reduce (MOD -> EPSILON)
                    case 3:
                    {
                        // TODO Default modulus is 2.
                        as.value_.scalar_ = 2 ;

                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce (MOD -> EPSILON)" << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;

                    // Reduce (POLY -> POLY + TERM)
                    case 4:
                    {
                        // A.poly = POLY + TERM

                        // Degree of POLY.  e.g. x+1 has degree 1, 3 has degree 0.
                        int degPoly = parseStack_[ topIndex - 2 ].value_.f_.size() - 1 ;

                        // Degree of TERM
                        int degTerm = parseStack_[ topIndex ].value_.f_.size() - 1 ;

                        // A.poly = POLY
                        as.value_.f_ = parseStack_[ topIndex - 2 ].value_.f_ ;

                        // Make POLY large enough to handle rhs POLY and TERM.
                        as.value_.f_.resize( degTerm > degPoly ? degTerm+1 : degPoly+1, 0 ) ;

                        degPoly = parseStack_[ topIndex - 2 ].value_.f_.size() - 1 ;

                        // A.poly += TERM
                        for (i = degTerm ;  i >= 0 ;  --i)
                        {
                            as.value_.f_[ i ] +=
                                parseStack_[ topIndex ].value_.f_[ i ] ;
                        }

                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce (POLY -> POLY + TERM)" << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;

                    // Reduce (POLY -> TERM)
                    case 5:
                    {
                        // Degree of POLY
                        int degPoly = as.value_.f_.size() - 1 ;

                        // Degree of TERM
                        int degTerm = parseStack_[ topIndex ].value_.f_.size() - 1 ;

                        // Make POLY large enough to handle term's power.
                        as.value_.f_.resize( degTerm > degPoly ? degTerm+1 : degPoly+1, 0 ) ;

                        // Zero the polynomial.
                        for (i = as.value_.f_.size() - 1 ;  i >= 0 ;  --i)
                            as.value_.f_[ i ] = 0 ;

                        // Add term.
                        for (i = as.value_.f_.size() - 1 ;  i >= 0 ;  --i)
                            as.value_.f_[ i ]  += parseStack_[ topIndex ].value_.f_[ i ] ;

                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce (POLY -> TERM) " << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;

                    // Reduce (TERM -> MULTIPLIER POWER)
                    case 6:
                    {
                        // Degree of POWER.
                        int degPower = parseStack_[ topIndex ].value_.scalar_ ;

                        // Make TERM large enough to handle the power.
                        as.value_.f_.resize( degPower + 1, 0 ) ;

                        // Zero TERM.
                        for (i = as.value_.f_.size() - 1 ;  i >= 0 ;  --i)
                            as.value_.f_[ i ] = 0 ;

                        // TERM = MULTIPLIER x ^ POWER
                        as.value_.f_[ degPower ] =
                        parseStack_[ topIndex - 1 ].value_.scalar_ ;

                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce (TERM -> MULTIPLIER POWER)" << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;

                    // Reduce (MULTIPLIER -> INTEGER)
                    case 7:
                    {
                        // Set value of MULTIPLIER.
                        as.value_.scalar_ = parseStack_[ topIndex ].value_.scalar_ ;

                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce (MULTIPLIER -> INTEGER)" << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;

                    // Reduce (MULTIPLIER -> EPSILON)
                    case 8:
                    {
                        // Multiplier default = 1
                        as.value_.scalar_ = 1 ;

                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce (MULTIPLIER -> EPSILON)" << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;

                    // Reduce (POWER -> X)
                    case 9:
                    {
                        // POWER is the exponent of x, so we
                        // interpret as a scalar.
                        as.value_.scalar_ = 1 ;

                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce  (POWER -> X)" << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;

                    // Reduce (POWER -> X ^ INTEGER)
                    case 10:
                    {
                        // POWER = value of INTEGER.
                        as.value_.scalar_ = parseStack_[ topIndex ].value_.scalar_ ;

                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce (POWER -> X ^ INTEGER)" << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;

                    // Reduce (POWER -> EPSILON)
                    case 11:
                    {
                        // Default power is 0.
                        as.value_.scalar_ = 0 ;

                        #ifdef DEBUG_PP_PARSER
                        cout << "    Reduce (POWER -> EPSILON)" << endl ;
                        cout << "    Value = " ;
                        as.value_.print() ;
                        cout << endl ;
                        #endif
                    }
                    break ;
                }

                // Pop the symbols of beta and its states
                //     Xm-r+1 sm-r+1 ... Xm sm
                // off the stack.
                for (i = 1 ;  i <= rhsProductionLength ;  ++i)
                {
                    if (inputStack_.size() == 0)
                        return retVal ;
                    parseStack_.pop_back() ;
                }

                // Get the GOTO state.
                currentState = parseStack_.back().state_ ;
                int gotoState = gotoTable_[ currentState ][ prodNonTerm ] ;

                // Push nonterminal A and the goto state s.
                as.state_ = gotoState ;
                parseStack_.push_back( as ) ;
            }
            break ;

            // Parsed successfully.
            case Accept:
                #ifdef DEBUG_PP_PARSER
                cout << "    Accept" << endl ;
                cout << "    Top of parse stack:  Value = " ;
                parseStack_.back().value_.print() ;
                cout << endl ;
                #endif

                return parseStack_.back().value_ ;
            break ;

            case Error:
            {
                //cout << "    throwing bad exception" << endl ;
                //throw "bad" ;

                // Halt with error message based on current state and
                // lookahead.
                // ----------------< from user >----------------------
                // Throw a parser error with the error message.
                throw ParserError( errorMessage_[ currentState ] ) ;

                #ifdef DEBUG_PP_PARSER
                cout << "    error: " ;
                s.print() ;
                cout << endl ;
                #endif

                return retVal ;
            }
            break ;

            default:
                // Internal error.
                return retVal ;
        } ; // end switch
    } // end while

    // Shouldn't get here.
    return retVal ;
}




/*==============================================================================
|                               parse_command_line                             |
================================================================================

DESCRIPTION

     Parse the command line.

INPUT
                                                                     n
     a[]  (int *)  Coefficients of the nth degree polynomial a(x) = a x  + ...
                                                                     n
                   + a  x  +  a.    a  is stored at array location a[i],
                      1        0     i
                   0 <= i < n .

     n    (int)    The polynomial's degree.

OUTPUT

  testPolynomialForPrimitivity


EXAMPLE CALLING SEQUENCE

   pp -h
   pp -s 2 4
   pp -t 2 4 x^3+x^2+1  No blanks, please!

--------------------------------------------------------------------------------
|                                Function Call                                 |
------------------------------------------------------------------------------*/

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

int    input_arg_index ;
const char * input_arg_string ;
const char * option_ptr ;

int    num_arg ;
const char * arg_string[ MAX_NUM_COMMAND_LINE_ARGS ] ;

/*  Initialize to defaults. */
testPolynomialForPrimitivity = false ;
listAllPrimitivePolynomials  = false ;
printStatistics              = false ;
printHelp                    = false ;
bool selfCheck               = false ;
p                            = 0 ;
n                            = 0 ;


//
//  Parse the command line to get the options and their inputs.
//
for (input_arg_index = 0, num_arg = 0 ;  input_arg_index < argc ;
     ++input_arg_index)
{
    /*  Get next argument string. */
    input_arg_string = argv[ input_arg_index ] ;

    /* We have an option:  a hyphen followed by a non-null string. */
    if (input_arg_string[ 0 ] == '-' && input_arg_string[ 1 ] != '\0')
    {
        /* Scan all options. */
        for (option_ptr = input_arg_string + 1 ;  *option_ptr != '\0' ;
             ++option_ptr)
        {
            switch( *option_ptr )
            {
                /* Test a given polynomial for primitivity. */
                case 't':
                    testPolynomialForPrimitivity = true ;
                break ;

                /* List all primitive polynomials.  */
                case 'a':
                   listAllPrimitivePolynomials = true ;
                break ;

                /* Print statistics on program operation. */
                case 's':
                   printStatistics = true ;
                break ;

                /* Print help. */
                case 'h':
				case 'H':
                    printHelp = true ;
                break ;

                /* Turn on all self-checking (slow!).  */
                case 'c':
					selfCheck = true ;
                break ;

                default:
                   ostringstream os ;
                   os << "Cannot recognize the option" << *option_ptr ;
                   throw ParserError( os.str() ) ;
                break ;
            }
        }
    }
    else  /* Not an option, but an argument. */
    {
        arg_string[ num_arg++ ] = input_arg_string ;
    }
}

// User specified a polynomial to test.  First argument is program name, next is
// the polynomial.
if (testPolynomialForPrimitivity)
{
    testPolynomial.assign( arg_string[ 1 ] ) ;
	return ;
}


/* Assume the next two arguments are p and n. */
if (num_arg == MAX_NUM_COMMAND_LINE_ARGS)
{
    p = atoi( arg_string[ 1 ] ) ;
    n = atoi( arg_string[ 2 ] ) ;

}
else
{
    ostringstream os ;
    os << "ERROR:  Expecting two arguments, p and n.\n\n" ;
	printHelp = true ;
    throw ParserError( os.str() ) ;
}

if (p < 2)
{
    ostringstream os ;
    os << "ERROR:  p must be 2 or more.\n\n" ;
	printHelp = true ;
    throw ParserError( os.str() ) ;
}

if (n < 2)
{
    ostringstream os ;
    os << "ERROR: n must be 2 or more.\n\n" ;
	printHelp = true ;
    throw ParserError( os.str() ) ;
}

} /* ================ end of function parseCommandLine ==================== */