1 /*==============================================================================
   2 |
   3 |  NAME
   4 |
   5 |     ppParser.cpp
   6 |
   7 |  DESCRIPTION
   8 |
   9 |     Polynomial parser classes.
  10 |
  11 |     User manual and technical documentation are described in detail in my web page at
  12 |     http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html
  13 |
  14 |  LEGAL
  15 |
  16 |     Primpoly Version 16.1 - A Program for Computing Primitive Polynomials.
  17 |     Copyright (C) 1999-2021 by Sean Erik O'Connor.  All Rights Reserved.
  18 |
  19 |     This program is free software: you can redistribute it and/or modify
  20 |     it under the terms of the GNU General Public License as published by
  21 |     the Free Software Foundation, either version 3 of the License, or
  22 |     (at your option) any later version.
  23 |
  24 |     This program is distributed in the hope that it will be useful,
  25 |     but WITHOUT ANY WARRANTY; without even the implied warranty of
  26 |     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  27 |     GNU General Public License for more details.
  28 |
  29 |     You should have received a copy of the GNU General Public License
  30 |     along with this program.  If not, see http://www.gnu.org/licenses/.
  31 |     
  32 |     The author's address is seanerikoconnor!AT!gmail!DOT!com
  33 |     with !DOT! replaced by . and the !AT! replaced by @
  34 |
  35 ==============================================================================*/
  36 
  37 /*------------------------------------------------------------------------------
  38 |                                Include Files                                 |
  39 ------------------------------------------------------------------------------*/
  40 
  41 #include <cstdlib>      // abort()
  42 #include <iostream>     // Basic stream I/O.
  43 #include <new>          // set_new_handler()
  44 #include <limits>       // numeric_limits
  45 #include <cmath>        // Basic math functions e.g. sqrt()
  46 #include <complex>      // Complex data type and operations.
  47 #include <fstream>      // File stream I/O.
  48 #include <sstream>      // String stream I/O.
  49 #include <vector>       // STL vector class.
  50 #include <string>       // STL string class.
  51 #include <algorithm>    // Iterators.
  52 #include <stdexcept>    // Exceptions.
  53 #include <cassert>      // assert()
  54 #include <cstring>      // memset()
  55 
  56 using namespace std ;
  57 
  58 // Current working directory, recursive dir search.
  59 #ifdef USE_EXPERIMENTAL_FILESYSTEM_GNU_CPP
  60     #include <experimental/filesystem>
  61     using namespace experimental::filesystem ;
  62 #else
  63     #include <filesystem>
  64     using namespace filesystem ;
  65 #endif
  66 
  67 #include "ctype.h"       // C string functions.
  68 
  69 
  70 /*------------------------------------------------------------------------------
  71 |                                PP Include Files                              |
  72 ------------------------------------------------------------------------------*/
  73 
  74 #include "Primpoly.h"         // Global functions.
  75 #include "ppArith.h"          // Basic arithmetic functions.
  76 #include "ppBigInt.h"         // Arbitrary precision integer arithmetic.
  77 #include "ppOperationCount.h" // OperationCount collection for factoring and poly finding.
  78 #include "ppFactor.h"         // Prime factorization and Euler Phi.
  79 #include "ppPolynomial.h"     // Polynomial operations and mod polynomial operations.
  80 #include "ppParser.h"         // Parsing of polynomials and I/O services.
  81 #include "ppUnitTest.h"       // Complete unit test.
  82 
  83 
  84 /*------------------------- Parser Helper Classes ----------------------------*/
  85 
  86 
  87 /*=============================================================================
  88  |
  89  | NAME
  90  |
  91  |     Symbol
  92  |
  93  | DESCRIPTION
  94  |
  95  |     Default constructor for a parser symbol, which has a type (terminal or non-terminal)
  96  |     and a state (or production number).
  97  |
  98  +============================================================================*/
  99 
 100 template < typename SymbolType, typename ValueType >
 101 Symbol< SymbolType, ValueType >::Symbol()
 102 : type_(), value_(), state_()
 103 {
 104 }
 105 
 106 
 107 /*=============================================================================
 108  |
 109  | NAME
 110  |
 111  |     Symbol
 112  |
 113  | DESCRIPTION
 114  |
 115  |     Constructor for a parser symbol, which has a type (terminal or non-terminal)
 116  |     and a state (or production number).
 117  |
 118  +============================================================================*/
 119 
 120 template < typename SymbolType, typename ValueType >
 121 Symbol< SymbolType, ValueType >::Symbol( SymbolType type, int state )
 122 : type_( type ), value_(), state_( state )
 123 {
 124 }
 125 
 126 
 127 /*=============================================================================
 128  |
 129  | NAME
 130  |
 131  |     Symbol
 132  |
 133  | DESCRIPTION
 134  |
 135  |     Constructor for a parser symbol, which has a type (terminal or non-terminal)
 136  |     a value (see above) and a state (or production number).
 137  |
 138  +============================================================================*/
 139 
 140 template < typename SymbolType, typename ValueType >
 141 Symbol< SymbolType, ValueType >::Symbol( SymbolType type, int state, ValueType value )
 142 : type_( type ), state_( state ), value_( value )
 143 {
 144 }
 145 
 146 /*=============================================================================
 147  |
 148  | NAME
 149  |
 150  |     Symbol
 151  |
 152  | DESCRIPTION
 153  |
 154  |     Copy constructor.
 155  |
 156  +============================================================================*/
 157 
 158 template < typename SymbolType, typename ValueType >
 159 Symbol< SymbolType, ValueType >::Symbol( const Symbol< SymbolType, ValueType > & s )
 160 : type_( s.type_ )
 161 , value_( s.value_ )
 162 , state_( s.state_ )
 163 {
 164 }
 165 
 166 
 167 /*=============================================================================
 168  |
 169  | NAME
 170  |
 171  |     operator=
 172  |
 173  | DESCRIPTION
 174  |
 175  |     Assignment operator.
 176  |
 177  +============================================================================*/
 178 
 179 template < typename SymbolType, typename ValueType >
 180 Symbol< SymbolType, ValueType > & Symbol< SymbolType, ValueType >::operator=( const Symbol< SymbolType, ValueType > & s )
 181 {
 182     // Check for assigning to oneself:  just pass back a reference to the unchanged object.
 183     if (this == &s)
 184         return *this ;
 185 
 186     type_  = s.type_ ;
 187     value_ = s.value_ ;
 188     state_ = s.state_ ;
 189 
 190     // Pass back the object so we can concatenate assignments.
 191     return *this ;
 192 }
 193 
 194 
 195 /*=============================================================================
 196  |
 197  | NAME
 198  |
 199  |     ActionState
 200  |
 201  | DESCRIPTION
 202  |
 203  |     Default constructor for an action/state pair.  Action is shift, reduce, 
 204  |     etc. and state is a number.
 205  |
 206  +============================================================================*/
 207 
 208 ActionState::ActionState()
 209     : action_( Action::Error )
 210     , state_( 0 )
 211 {
 212 }
 213 
 214 
 215 /*=============================================================================
 216  |
 217  | NAME
 218  |
 219  |     ActionState
 220  |
 221  | DESCRIPTION
 222  |
 223  |     Constructor for an action/state pair.
 224  |
 225  +============================================================================*/
 226 
 227 ActionState::ActionState( Action type, int state )
 228     : action_( type )
 229     , state_( state )
 230 {
 231 }
 232 
 233 
 234 /*=============================================================================
 235  |
 236  | NAME
 237  |
 238  |     ActionState
 239  |
 240  | DESCRIPTION
 241  |
 242  |     Copy constructor for an action/state pair.
 243  |
 244  +============================================================================*/
 245 
 246 ActionState::ActionState( const ActionState & as )
 247     : action_(  as.action_ )
 248     , state_( as.state_ )
 249 {
 250 }
 251 
 252 
 253 /*=============================================================================
 254  |
 255  | NAME
 256  |
 257  |     ActionState
 258  |
 259  | DESCRIPTION
 260  |
 261  |     Assignment operator for an action/state pair.
 262  |
 263  +============================================================================*/
 264 
 265 ActionState & ActionState::operator=( const ActionState & as )
 266 {
 267     // Check for assigning to oneself:  just pass back a reference to the unchanged object.
 268     if (this == &as)
 269         return *this ;
 270 
 271     action_  = as.action_ ;
 272     state_ = as.state_ ;
 273 
 274     // Pass back the object so we can concatenate assignments.
 275     return *this ;
 276 }
 277 
 278 
 279 /*=============================================================================
 280  |
 281  | NAME
 282  |
 283  |     Operator << for ActionState
 284  |
 285  | DESCRIPTION
 286  |
 287  |     Debug print to an output stream for an action state.
 288  |
 289  +============================================================================*/
 290 
 291 ostream & operator<<( ostream & out, const ActionState & as )
 292 {
 293     string s ;
 294 
 295     out << "Action/State: " ;
 296     switch( as.action_ )
 297     {
 298         case Action::Shift:  s = "Shift" ;   break ;
 299         case Action::Reduce: s = "Reduce" ;  break ;
 300         case Action::Accept: s = "Accept" ;  break ;
 301         case Action::Error:  s = "Error" ;   break ;
 302     }
 303     out << s ;
 304     out << " " << as.state_ ;
 305 
 306     return out ;
 307 }
 308 
 309 
 310 /*----------------------------- Parser Base Class ----------------------------*/
 311 
 312 
 313 /*=============================================================================
 314  |
 315  | NAME
 316  |
 317  |     Parser
 318  |
 319  | DESCRIPTION
 320  |
 321  |     Default constructor for the class.
 322  |
 323  +============================================================================*/
 324 
 325 template < typename SymbolType, typename ValueType >
 326 Parser< SymbolType, ValueType >::Parser()
 327     : input_stack_()
 328     , parse_stack_()
 329     , num_states_       ( 0 ) // Includes the 0 state.
 330     , num_productions__  ( 0 ) // Number of productions.
 331     , num_terminals_    ( 0 ) // Number of terminal symbols.
 332     , num_non_terminals_ ( 0 ) // Number of nonterminal symbols.
 333 {
 334 }
 335 
 336 /*=============================================================================
 337  |
 338  | NAME
 339  |
 340  |     ~Parser
 341  |
 342  | DESCRIPTION
 343  |
 344  |     Default deeeestructor for the class.
 345  |
 346  +============================================================================*/
 347 
 348 template < typename SymbolType, typename ValueType >
 349 Parser< SymbolType, ValueType >::~Parser()
 350 {
 351     // Private data destroy themselves.
 352 }
 353 
 354 
 355 /*=============================================================================
 356  |
 357  | NAME
 358  |
 359  |     Parser( const Parser & Parser )
 360  |
 361  | DESCRIPTION
 362  |
 363  |     Copy constructor.
 364  |
 365  +============================================================================*/
 366 
 367 template < typename SymbolType, typename ValueType >
 368 Parser< SymbolType, ValueType >::Parser( const Parser & Parser )
 369 : input_stack_( Parser.input_stack_ )
 370 , parse_stack_( Parser.parse_stack_ )
 371 {
 372 }
 373 
 374 /*=============================================================================
 375  |
 376  | NAME
 377  |
 378  |    operator=( const PolyParser & PolyParser )
 379  |
 380  |
 381  | DESCRIPTION
 382  |
 383  |    Assignment operator.
 384  |
 385  +============================================================================*/
 386 
 387 template < typename SymbolType, typename ValueType >
 388 Parser< SymbolType, ValueType > & Parser< SymbolType, ValueType >::operator=( const Parser & Parser )
 389 {
 390     // Check for assigning to oneself:  just pass back a reference to the unchanged object.
 391     if (this == &Parser)
 392         return *this ;
 393 
 394     input_stack_ = Parser.input_stack_ ;
 395     parse_stack_ = Parser.parse_stack_ ;
 396 
 397     // Return reference to this object.
 398     return *this ;
 399 }
 400 
 401 /*=============================================================================
 402  |
 403  | NAME
 404  |
 405  |     insertAction
 406  |
 407  | DESCRIPTION
 408  |
 409  |     Add a new entry to the Action Table.
 410  |
 411  +============================================================================*/
 412 
 413 template < typename SymbolType, typename ValueType >
 414 void Parser< SymbolType, ValueType >::insertAction( int    state,      SymbolType terminal,
 415              Action actionType, int      actionState )
 416 {
 417     try
 418     {
 419         // Create a new action.
 420         ActionState as( actionType, actionState ) ;
 421 
 422         // Get space for actionTable[ state ] which is an vector<ActionState> indexed by terminal.
 423         action_table_[ static_cast<int>( state ) ].resize( num_terminals_ ) ;
 424 
 425         // Insert it into the ACTION table.
 426         action_table_[ static_cast<int>( state ) ][ static_cast<int>( terminal ) ] = as ;
 427     }
 428     catch( length_error & e )
 429     {
 430         ostringstream os ;
 431         os << "Parser::insertAction had a length_error exception when trying to initialize action tables" ;
 432         throw ParserError( os.str(), __FILE__, __LINE__ ) ;
 433     }
 434 
 435 }
 436 
 437 /*=============================================================================
 438  |
 439  | NAME
 440  |
 441  |    insertGoto
 442  |
 443  | DESCRIPTION
 444  |
 445  |     Add a new entry to the Goto Table.
 446  |
 447  +============================================================================*/
 448 
 449 template < typename SymbolType, typename ValueType >
 450 void Parser< SymbolType, ValueType >::insertGoto( int state, SymbolType nonterm, int newState )
 451 {
 452     try
 453     {
 454         // Insert into the GOTO table.
 455         goto_table_[ static_cast<int>( state ) ].resize( static_cast<int>( PolySymbol::NumSymbols ) ) ;
 456         goto_table_[ static_cast<int>( state ) ][ static_cast<int>( nonterm ) ] = newState ;
 457     }
 458     catch( length_error & e )
 459     {
 460         ostringstream os ;
 461         os << "Parser::insertGoto had a length_error exception while initializing goto tables" ;
 462         throw ParserError( os.str(), __FILE__, __LINE__ ) ;
 463     }
 464 
 465 }
 466 
 467 /*=============================================================================
 468  |
 469  | NAME
 470  |
 471  |    insertProduction
 472  |
 473  | DESCRIPTION
 474  |
 475  |    Add a new entry to the list of productions.
 476  |
 477  +============================================================================*/
 478 
 479 template < typename SymbolType, typename ValueType >
 480 void Parser< SymbolType, ValueType >::insertProduction( int prodNum, SymbolType nonTerm, int rhsLength )
 481 {
 482     // Insert into the production table.
 483     production_[ prodNum ].type_  = nonTerm ;
 484     production_[ prodNum ].state_ = rhsLength ;
 485 }
 486 
 487 /*=============================================================================
 488  |
 489  | NAME
 490  |
 491  |     insertErrorMessage
 492  |
 493  | DESCRIPTION
 494  |
 495  |     Insert an error message into the list.
 496  |
 497  +============================================================================*/
 498 
 499 template < typename SymbolType, typename ValueType >
 500 void Parser< SymbolType, ValueType >::insertErrorMessage( int state, string errorMessage )
 501 {
 502     error_message_[ state ] = errorMessage ;
 503 }
 504 
 505 /*=============================================================================
 506  | 
 507  | NAME
 508  | 
 509  |     parse
 510  | 
 511  | DESCRIPTION
 512  | 
 513  |      Standard LALR(1) parser algorithm, parameterized with the type of
 514  |      symbols and values of its tokens.
 515  |
 516  |      The initial parser configuration is
 517  | 
 518  |             (s0 | a1 ... an $)
 519  | 
 520  |         a1 ... an is the set of input tokens
 521  |         s0 = 0 is the initial state
 522  | 
 523  |         The parse stack is to the left of the bar and the unprocessed
 524  |         input is to the right.  Now suppose the configuration is
 525  | 
 526  |             (s0 X1 ... Xm-r sm-r Xm-r+1 sm-r+1 ... Xm sm   |   ai ai+1 ... an $)
 527  | 
 528  |         There are four possible things we can do:
 529  | 
 530  |         (1)  Shift the input token and push a new state.
 531  | 
 532  |              ACTION[ sm, ai ] = shift s
 533  |
 534  |                  (s0 X1 ... Xm sm ai s   |   ai+1 ... an $)
 535  | 
 536  |         (2)  Reduce.  Pop the stack, push the reduction and new state.
 537  |              Also do a syntax-directed evaluation using the values
 538  |              of the symbols in the production A -> beta which we just reduced.
 539  | 
 540  |              ACTION[ sm, ai ] = reduce( A -> beta = Xm-r+1 ... Xm)
 541  |
 542  |                  (s0 X1 ... Xm-r sm-r A s   |   ai+1 ... an $)
 543  | 
 544  |              where s = GOTO[ sm-r, A ] and r = length( beta )
 545  | 
 546  |         (3)  Accept.  The sentence is in the grammar;  halt.
 547  | 
 548  |              ACTION[ sm, ai ] = accept
 549  | 
 550  |         (4)  Error state.   Produce an error message using the current
 551  |              parsing state and lookahead symbol ai.
 552  | 
 553  |              ACTION[ sm, ai ] = error
 554  | 
 555  +============================================================================*/
 556 
 557 template< typename SymbolType, typename ValueType >
 558 ValueType Parser< SymbolType, ValueType >::parse( string sentence )
 559 {
 560     ValueType retVal ; // Default to f(x) = 0, mod 0.
 561 
 562     // Null string check.
 563     if (sentence.size() == 0)
 564         return retVal ;
 565 
 566     // Tokenize the input string.  This can throw an exception.
 567     tokenize( sentence ) ;
 568 
 569     // Initialize the parse stack to the zero state.
 570     parse_stack_.clear() ;
 571 
 572     Symbol<SymbolType, ValueType> s( SymbolType::S, 0 ) ;
 573     parse_stack_.push_back( s ) ;
 574 
 575     #ifdef DEBUG_PP_PARSER
 576     cout << "Parser:  sentence = " << sentence << endl ;
 577     #endif
 578 
 579     // Parse until we accept, error out or run out of input.
 580     while( input_stack_.size() > 0 )
 581     {
 582         // Grab the current state and the lookahead token.
 583         int                             currentState = parse_stack_.back().state_ ;
 584         Symbol< SymbolType, ValueType > lookahead    = input_stack_.back() ;
 585 
 586 
 587         // Dump the parse and input stacks for debugging.
 588         #ifdef DEBUG_PP_PARSER
 589         cout << endl << "    Parse stack: " << endl ;
 590 
 591         for (auto & i : parse_stack_)
 592             cout << "        " << i << endl ;
 593 
 594         cout << "    --------" << endl ;
 595 
 596         cout << "    Input stack: " << endl ;
 597         auto i = input_stack_.end()-1 ;
 598         while (i >= input_stack_.begin())
 599         {
 600             cout << "        " << *i <<  endl ;
 601             if (i == input_stack_.begin())
 602                 break ;
 603             --i ;
 604         }
 605         #endif
 606 
 607         // Look up the action (shift 3), (reduce 2), etc.
 608         ActionState actionState = action_table_[ currentState ][ static_cast<int>( lookahead.type_ ) ] ;
 609 
 610         // Debug dump the action.
 611         #ifdef DEBUG_PP_PARSER
 612         cout << endl << actionState << endl ;
 613         #endif
 614 
 615         try
 616         {
 617             // Look at the action required.
 618             switch( actionState.action_ )
 619             {
 620                 case Action::Shift:
 621                 {
 622                     //  Shift the next token off the input stack.
 623                     if (input_stack_.size() == 0)
 624                         // Throw a parser error if parse stack is empty (shouldn't get here).
 625                         throw ParserError( "Wanted to shift another token, but the parse stack is empty.", __FILE__, __LINE__ ) ;
 626 
 627                     input_stack_.pop_back() ;
 628 
 629                     //  Push the input symbol and new state onto the parse stack.
 630                     int newState = actionState.state_ ;
 631 
 632                     Symbol< SymbolType, ValueType > s( lookahead.type_, newState, lookahead.value_ ) ;
 633                     parse_stack_.push_back( s ) ;
 634                 }
 635                 break ;
 636 
 637                 case Action::Reduce:
 638                 {
 639                     // Fetch the production A -> beta, beta = Xm-r+1 ... Xm
 640                     int productionNum = actionState.state_ ;
 641 
 642                     // Get the left hand side non-terminal A.
 643                     SymbolType prodNonTerm = production_[ productionNum ].type_ ;
 644 
 645                     // Get r, the length of beta.  If the production is A -> EPSILON, beta = EPSILON, r = 0.
 646                     int rhsProductionLength = production_[ productionNum ].state_ ;
 647 
 648                     // Carry out the syntax directed translation using
 649                     // the symbols of beta and its states
 650                     // which are on the top of the stack and the nonterminal A.
 651 
 652                     // Creat a new symbol/state  A s
 653                     Symbol< SymbolType, ValueType > A( prodNonTerm,  0 ) ;
 654                     int topIndex = static_cast<int>( parse_stack_.size() ) - 1 ;
 655                     int i = 0 ;
 656 
 657                     // Carry out the syntax directed translation f() using the values in the right hand
 658                     // side of the production:
 659                     //     A.value = f( Xm-r+1.value ... Xm.value )
 660                     syntaxDirectedTranslation( productionNum, topIndex, A ) ;
 661 
 662                     // Pop the symbols of beta and its states
 663                     //     Xm-r+1 sm-r+1 ... Xm sm
 664                     // off the stack.
 665                     for (i = 1 ;  i <= rhsProductionLength ;  ++i)
 666                     {
 667                         if (input_stack_.size() == 0)
 668                             return retVal ;
 669                         parse_stack_.pop_back() ;
 670                     }
 671 
 672                     // Get the GOTO state s.
 673                     currentState = parse_stack_.back().state_ ;
 674                     int gotoState = goto_table_[ static_cast<int>( currentState ) ][ static_cast<int>( prodNonTerm ) ] ;
 675 
 676                     // Push nonterminal A and goto state s.
 677                     A.state_ = gotoState ;
 678                     parse_stack_.push_back( A ) ;
 679                 }
 680                 break ;
 681 
 682                 // Parsed successfully.
 683                 case Action::Accept:
 684                     #ifdef DEBUG_PP_PARSER
 685                     cout << "    Accept:  S.value = " << parse_stack_.back().value_ << endl ;
 686                     #endif
 687 
 688                     return parse_stack_.back().value_ ;
 689                 break ;
 690 
 691                 case Action::Error:
 692                 {
 693                     #ifdef DEBUG_PP_PARSER
 694                     cout << "    Error: " << s << endl ;
 695                     #endif
 696 
 697                     // Throw a parser error with an error message based on the current state.
 698                     // Don't need to print the file name and line number since this is more of an
 699                     // error status than a surprise.
 700                     ostringstream os ;
 701                     os << error_message_[ currentState ] << " in sentence " << sentence ;
 702                     throw ParserError( os.str() ) ;
 703 
 704                     return retVal ;
 705                 }
 706                 break ;
 707 
 708                 default:
 709                     // Internal error.
 710                     return retVal ;
 711             }   // end switch
 712 
 713         }
 714         catch( length_error & e )
 715         {
 716             ostringstream os ;
 717             os << "Parser::parse had a length_error exception during resizing poly or power terms" ;
 718             throw ParserError( os.str(), __FILE__, __LINE__ ) ;
 719         }
 720 
 721     } // end while
 722 
 723     // Shouldn't get here.
 724     return retVal ;
 725 }
 726 
 727 
 728 
 729 /*------------------------------- Parser Child Classes ------------------------*/
 730 
 731 
 732 
 733 /*=============================================================================
 734  |
 735  | NAME
 736  |
 737  |     operator=( const PolyValue & v )
 738  |
 739  |
 740  | DESCRIPTION
 741  |
 742  |     Assignment operator for PolyValue.
 743  |
 744  +============================================================================*/
 745 
 746 PolyValue & PolyValue::operator=( const PolyValue & v )
 747 {
 748     // Check for assigning to oneself:  just pass back a reference to the unchanged object.
 749     if (this == &v)
 750         return *this ;
 751 
 752     scalar_ = v.scalar_ ;
 753     f_ = v.f_ ;
 754 
 755     // Pass back the object so we can concatenate assignments.
 756     return *this ;
 757 }
 758 
 759 
 760 /*=============================================================================
 761  |
 762  | NAME
 763  |
 764  |     Operator << for PolyValue
 765  |
 766  | DESCRIPTION
 767  |
 768  |     Print the scalar and polynomial parts of a PolyValue type.
 769  |
 770  +============================================================================*/
 771 
 772 ostream & operator<<( ostream & out, const PolyValue & poly )
 773 {
 774     out << poly.scalar_ << " f( x ) = " ;
 775 
 776     // Convert into a Polynomial type from a vector, then send to output.
 777     Polynomial p( poly.f_ ) ;
 778     out << p ;
 779 
 780     return out ;
 781 }
 782 
 783 
 784 /*=============================================================================
 785  |
 786  | NAME
 787  |
 788  |     PolyValue
 789  |
 790  | DESCRIPTION
 791  |
 792  |     Default constructor for a value which contains a scalar or polynomial.
 793  |
 794  +============================================================================*/
 795 
 796 PolyValue::PolyValue()
 797 : scalar_( 0 )
 798 , f_(1, 0) // f(x) = 0
 799 {
 800 }
 801 
 802 
 803 /*=============================================================================
 804  |
 805  | NAME
 806  |
 807  |     PolyValue
 808  |
 809  | DESCRIPTION
 810  |
 811  |     Copy constructor for PolyValue.
 812  |
 813  +============================================================================*/
 814 
 815 PolyValue::PolyValue( const PolyValue & v )
 816 : scalar_( v.scalar_ )
 817 , f_( v.f_ )
 818 {
 819 }
 820 
 821 
 822 /*=============================================================================
 823 |
 824 | NAME
 825 |
 826 |     PolyParser
 827 |
 828 | DESCRIPTION
 829 |
 830 |     Default constructor for the class.
 831 |
 832 +============================================================================*/
 833 
 834 template < typename SymbolType, typename ValueType >
 835 PolyParser< SymbolType, ValueType >::PolyParser()
 836     : Parser< SymbolType, ValueType >()
 837     , test_polynomial_()
 838     , test_polynomial_for_primitivity_( false )
 839     , list_all_primitive_polynomials_( false )
 840     , print_operation_count_( false )
 841     , print_help_( false )
 842     , slow_confirm_( false )
 843     , p( 0 )
 844     , n( 0 )
 845 {
 846     // Initialize all the parse tables.
 847     initializeTables() ;
 848 }
 849 
 850 /*=============================================================================
 851  | 
 852  | NAME
 853  | 
 854  |     ~PolyParser
 855  | 
 856  | DESCRIPTION
 857  | 
 858  |     Default deeeestructor for the class.
 859  | 
 860  +============================================================================*/
 861 
 862 template < typename SymbolType, typename ValueType >
 863 PolyParser< SymbolType, ValueType >::~PolyParser()
 864 {
 865     // Private data destroy themselves.
 866 }
 867 
 868 
 869 
 870 /*=============================================================================
 871  |
 872  | NAME
 873  |
 874  |     PolyParser( const PolyParser & PolyParser )
 875  |
 876  | DESCRIPTION
 877  |
 878  |     Copy constructor.
 879  |
 880  +============================================================================*/
 881 
 882 template < typename SymbolType, typename ValueType >
 883 PolyParser<SymbolType, ValueType>::PolyParser( const PolyParser< SymbolType, ValueType > & PolyParser )
 884         : Parser<SymbolType, ValueType>( PolyParser )
 885 {
 886 }
 887 
 888 
 889 /*=============================================================================
 890  | 
 891  | NAME
 892  | 
 893  |    operator=( const PolyParser & PolyParser )
 894  | 
 895  | 
 896  | DESCRIPTION
 897  | 
 898  |    Assignment operator.
 899  | 
 900  +============================================================================*/
 901 
 902 template < typename SymbolType, typename ValueType >
 903 PolyParser< SymbolType, ValueType > & PolyParser< SymbolType, ValueType >::operator=( const PolyParser & PolyParser )
 904 {
 905     // Check for assigning to oneself:  just pass back a reference to the unchanged object.
 906     if (this == &PolyParser)
 907              return *this ;
 908 
 909     input_stack_ = PolyParser.input_stack_ ;
 910     parse_stack_ = PolyParser.parse_stack_ ;
 911 
 912     // Return reference to this object.
 913     return *this ;
 914 }
 915 
 916 
 917 /*=============================================================================
 918  | 
 919  | NAME
 920  | 
 921  |     initializeTables
 922  | 
 923  | DESCRIPTION
 924  | 
 925  |     Initialize ACTION, GOTO, and ERROR_MESSAGE tables for an LALR(1) parser.
 926  |     And also information about the productions.
 927  |
 928  +============================================================================*/
 929 
 930 template < typename SymbolType, typename ValueType >
 931     void PolyParser< SymbolType, ValueType >::
 932         initializeTables()
 933 {
 934     // Need these so we can preallocate the vector lengths.  Vector's operator[] is unchecked!
 935     num_states_       = 15 ; // Including the 0 state.
 936     num_productions__  = 11 ;
 937     num_terminals_    = static_cast<int>(PolySymbol::NumTerminals) ;
 938     num_non_terminals_ = static_cast<int>(PolySymbol::NumSymbols) - static_cast<int>(PolySymbol::NumTerminals) - 1 ;  // Don't count NumTerminals enum itself.
 939 
 940     // Expand the rows of the ACTION table to hold all the states.
 941     action_table_.resize( num_states_ ) ;
 942 
 943     // Expand the rows of the GOTO table to hold all the states.
 944     goto_table_.resize( num_states_ ) ;
 945 
 946     // Expand the rows of the ACTION table to hold all the states.
 947     // Allow space in 0th slot (unused).
 948     production_.resize( num_productions__ + 1 ) ;
 949 
 950     error_message_.resize( num_states_ ) ;
 951 
 952     // TODO:  does resize or operator[] throw any exceptions?  use vector.at( i ) for checked access?
 953     try
 954     {
 955         // For each state and each terminal, insert
 956         //    if Shift, the new state to push on the stack,
 957         //    if Reduce, the production number.
 958         insertAction( 0,    PolySymbol::Integer,    Action::Shift,       3 ) ;
 959         insertAction( 0,    PolySymbol::Ecks,       Action::Reduce,      8 ) ;
 960         insertAction( 0,    PolySymbol::Comma,      Action::Reduce,      8 ) ;
 961         insertAction( 0,    PolySymbol::Dollar,     Action::Reduce,      8 ) ;
 962         insertAction( 0,    PolySymbol::Plus,       Action::Reduce,      8 ) ;
 963 
 964         insertAction( 1,    PolySymbol::Dollar,     Action::Accept,      0 ) ;
 965 
 966         insertAction( 2,    PolySymbol::Comma,      Action::Shift,       7 ) ;
 967         insertAction( 2,    PolySymbol::Plus,       Action::Shift,       8 ) ;
 968         insertAction( 2,    PolySymbol::Dollar,     Action::Reduce,      3 ) ;
 969 
 970         insertAction( 3,    PolySymbol::Ecks,       Action::Reduce,      7 ) ;
 971         insertAction( 3,    PolySymbol::Comma,      Action::Reduce,      7 ) ;
 972         insertAction( 3,    PolySymbol::Dollar,     Action::Reduce,      7 ) ;
 973         insertAction( 3,    PolySymbol::Plus,       Action::Reduce,      7 ) ;
 974 
 975         insertAction( 4,    PolySymbol::Comma,      Action::Reduce,      5 ) ;
 976         insertAction( 4,    PolySymbol::Dollar,     Action::Reduce,      5 ) ;
 977         insertAction( 4,    PolySymbol::Plus,       Action::Reduce,      5 ) ;
 978 
 979         insertAction( 5,    PolySymbol::Ecks,       Action::Shift,      10 ) ;
 980         insertAction( 5,    PolySymbol::Comma,      Action::Reduce,     11 ) ;
 981         insertAction( 5,    PolySymbol::Dollar,     Action::Reduce,     11 ) ;
 982         insertAction( 5,    PolySymbol::Plus,       Action::Reduce,     11 ) ;
 983 
 984         insertAction( 6,    PolySymbol::Dollar,     Action::Reduce,      1 ) ;
 985 
 986         insertAction( 7,    PolySymbol::Integer,    Action::Shift,      11 ) ;
 987 
 988         insertAction( 8,    PolySymbol::Integer,    Action::Shift,       3 ) ;
 989         insertAction( 8,    PolySymbol::Ecks,       Action::Reduce,      8 ) ;
 990         insertAction( 8,    PolySymbol::Comma,      Action::Reduce,      8 ) ;
 991         insertAction( 8,    PolySymbol::Dollar,     Action::Reduce,      8 ) ;
 992         insertAction( 8,    PolySymbol::Plus,       Action::Reduce,      8 ) ;
 993 
 994         insertAction( 9,    PolySymbol::Comma,      Action::Reduce,      6 ) ;
 995         insertAction( 9,    PolySymbol::Dollar,     Action::Reduce,      6 ) ;
 996         insertAction( 9,    PolySymbol::Plus,       Action::Reduce,      6 ) ;
 997 
 998         insertAction( 10,   PolySymbol::Comma,      Action::Reduce,      9 ) ;
 999         insertAction( 10,   PolySymbol::Exp,        Action::Shift,      13 ) ;
1000         insertAction( 10,   PolySymbol::Dollar,     Action::Reduce,      9 ) ;
1001         insertAction( 10,   PolySymbol::Plus,       Action::Reduce,      9 ) ;
1002 
1003         insertAction( 11,   PolySymbol::Dollar,     Action::Reduce,      2 ) ;
1004 
1005         insertAction( 12,   PolySymbol::Comma,      Action::Reduce,      4 ) ;
1006         insertAction( 12,   PolySymbol::Dollar,     Action::Reduce,      4 ) ;
1007         insertAction( 12,   PolySymbol::Plus,       Action::Reduce,      4 ) ;
1008 
1009         insertAction( 13,   PolySymbol::Integer,    Action::Shift,      14 ) ;
1010 
1011         insertAction( 14,   PolySymbol::Comma,      Action::Reduce,     10 ) ;
1012         insertAction( 14,   PolySymbol::Dollar,     Action::Reduce,     10 ) ;
1013         insertAction( 14,   PolySymbol::Plus,       Action::Reduce,     10 ) ;
1014 
1015 
1016         // For each state and symbol insert a new state.
1017         insertGoto( 0,  PolySymbol::S,               1 ) ;
1018         insertGoto( 0,  PolySymbol::Poly,            2 ) ;
1019         insertGoto( 0,  PolySymbol::Term,            4 ) ;
1020         insertGoto( 0,  PolySymbol::Multiplier,      5 ) ;
1021 
1022         insertGoto( 2,  PolySymbol::Mod,             6 ) ;
1023 
1024         insertGoto( 5,  PolySymbol::Power,           9 ) ;
1025 
1026         insertGoto( 8,  PolySymbol::Term,           12 ) ;
1027         insertGoto( 8,  PolySymbol::Multiplier,      5 ) ;
1028 
1029 
1030         // For each production (given by a unique number), insert the single nonterminal
1031         // which starts the production, and the length in symbols of the right hand side.
1032         // We'll need to know which production is being reduced so we can apply the syntax
1033         // directed translation, and pop the production off the stack.
1034         insertProduction(  1,      PolySymbol::S,           2 ) ; // S          -> Poly Mod
1035         insertProduction(  2,      PolySymbol::Mod,         2 ) ; // Mod        -> , integer
1036         insertProduction(  3,      PolySymbol::Mod,         0 ) ; // Mod        -> EPSILON
1037         insertProduction(  4,      PolySymbol::Poly,        3 ) ; // Poly       -> Poly + Term
1038         insertProduction(  5,      PolySymbol::Poly,        1 ) ; // Poly       -> Term
1039         insertProduction(  6,      PolySymbol::Term,        2 ) ; // Term       -> Multiplier Power
1040         insertProduction(  7,      PolySymbol::Multiplier,  1 ) ; // Multiplier -> integer
1041         insertProduction(  8,      PolySymbol::Multiplier,  0 ) ; // Multiplier -> EPSILON
1042         insertProduction(  9,      PolySymbol::Power,       1 ) ; // Power      -> x
1043         insertProduction( 10,      PolySymbol::Power,       3 ) ; // Power      -> x ^ integer
1044         insertProduction( 11,      PolySymbol::Power,       0 ) ; // Power      -> EPSILON
1045 
1046         // For each state, provide an error message.
1047         insertErrorMessage(  0, "Expecting to see the start of the polynomial or next term or coefficient" ) ;
1048         insertErrorMessage(  1, "Expecting to see end of the polynomial" ) ;
1049         insertErrorMessage(  2, "Expecting to see mod or + term or , integer or end of polynomial" ) ;
1050         insertErrorMessage(  3, "Expecting to see x or , or end of the polynomial" ) ;
1051         insertErrorMessage(  4, "Expecting to see + or end of the polynomial" ) ;
1052         insertErrorMessage(  5, "Expecting to see a power after a coefficient or x or ," ) ;
1053         insertErrorMessage(  6, "Expecting to see ," ) ;
1054         insertErrorMessage(  7, "Expecting to see mod after ," ) ;
1055         insertErrorMessage(  8, "Expecting to see a term after a + or a term or coefficient" ) ;
1056         insertErrorMessage(  9, "Expecting to see , or end of polynomial after a term" ) ;
1057         insertErrorMessage( 10, "Expecting to see x^ or x or x ^ integer" ) ;
1058         insertErrorMessage( 11, "Expecting to see end of the polynomial after , integer" ) ;
1059         insertErrorMessage( 12, "Expecting to see , end of polynomial or + after a term" ) ;
1060         insertErrorMessage( 13, "Expecting to see an exponent after x ^" ) ;
1061         insertErrorMessage( 14, "Expecting to see , or + end of polynomial after x ^ integer" ) ;
1062     }
1063     catch( length_error & e)
1064     {
1065         ostringstream os ;
1066         os << "PolyParser::initializeTables had a length_error exception while initializing parse tables" ;
1067         throw ParserError( os.str(), __FILE__, __LINE__ ) ;
1068     }
1069 }
1070 
1071 
1072 /*=============================================================================
1073  |
1074  | NAME
1075  |
1076  |    tokenize
1077  |
1078  | DESCRIPTION
1079  |
1080  |    This is the lexical analyzer.  Given an input string, convert it into tokens
1081  |    to fill the input stack.
1082  |
1083  |    Each token has a type, which is a nonterminal symbol, and its value.
1084  |
1085  |    This specific lexer converts a polynomial string.
1086  |
1087  +============================================================================*/
1088 
1089 template < typename SymbolType, typename ValueType >
1090 void PolyParser< SymbolType, ValueType >::tokenize( string sentence )
1091 {
1092     Symbol< SymbolType, ValueType > tok( PolySymbol::NumSymbols, 0 ) ;
1093 
1094     // Starting position to scan.
1095     unsigned int pos = 0 ;
1096 
1097     bool minusSignDetected = false ;
1098 
1099     // Clear the token stack.
1100     input_stack_.clear() ;
1101 
1102     #ifdef DEBUG_PP_PARSER
1103     cout << "Lexical analyzer:  sentence = " << sentence << endl ;
1104     #endif
1105 
1106     // Scan sentence to end.
1107     while( pos < sentence.length() )
1108     {
1109         // Skip whitespace.
1110         while (pos < sentence.length() && iswspace( sentence[ pos ]))
1111             ++pos ; // Advance to next token.
1112 
1113         // Read an integer.
1114         if (pos < sentence.size() && isdigit( sentence[ pos ]))
1115         {
1116             unsigned int num = 0 ;
1117             while( pos < sentence.size() && isdigit( sentence[ pos ]))
1118             {
1119                 char asciiDigit[ 2 ] = "\0" ; asciiDigit[ 0 ] = sentence[ pos ] ;
1120                 int digit = atoi( asciiDigit ) ;
1121 
1122                 // Stop reading the next decimal digit if we're about to overflow.
1123                 // Not really an exception but more of a user input error.
1124                 if (num > (BigInt::getBase() - digit) / 10)
1125                 {
1126                     ostringstream os ;
1127                     os << "Error:  number about to overflow in tokenizer at digit = " << digit ;
1128                     throw ParserError( os.str() ) ;
1129                 }
1130 
1131                 num = 10 * num + digit ;
1132                 ++pos ; // Advance to next token.
1133             }
1134 
1135             tok.type_          = PolySymbol::Integer ;
1136             tok.value_.scalar_ = num ;
1137 
1138             // Apply a minus sign to this number.
1139             if (minusSignDetected)
1140             {
1141                 // Don't allow a minus sign for polynomial coefficients.
1142                 // Not really an exception but more of a user input error.
1143                 ostringstream os ;
1144                 os << "Error:  negative number for a polynomial coefficient = -" << tok.value_.scalar_ << " is not allowed.  Numbers must be >= 0" ;
1145                 throw ParserError( os.str() ) ;
1146 
1147                 // TODO If we do handle negative coefficients in the future, we'll do something like this:
1148                 //     ModP modp( p ) ;
1149                 //     tok.value_.scalar_ = modp( -tok.value_.scalar_ ) ;
1150                 //     minusSignDetected = false ;
1151             }
1152         }
1153         // A non-digit symbol.
1154         else
1155         {
1156             tok.value_.scalar_ = 0 ;
1157 
1158             // Read another type of token.
1159             switch( sentence[ pos ] )
1160             {
1161                 case '+' :
1162                     tok.type_ = PolySymbol::Plus ;
1163                 break ;
1164 
1165                 // Make this look like a plus symbol to the parser:  we'll let this lexer
1166                 // apply it to the next integer we see.  If there isn't an integer following
1167                 // the minus sign, it's an error for the parser anyway!
1168                 case '-' :
1169                     tok.type_ = PolySymbol::Plus ;
1170                     minusSignDetected = true ;
1171                 break ;
1172 
1173                 case '^' :
1174                     tok.type_ = PolySymbol::Exp ;
1175                 break ;
1176 
1177                 case 'x' :
1178                 case 'X' :
1179                     tok.type_ = PolySymbol::Ecks ;
1180                 break ;
1181 
1182                 case ',' :
1183                     tok.type_ = PolySymbol::Comma ;
1184                 break ;
1185 
1186                 default:
1187                     // Throw a parser error of unexpected input if we see a bad symbol.
1188                     // Not really an exception but more of a user input error.
1189                     ostringstream os ;
1190                     os << "Error:  Unexpected symbol in lexical analyzer" << sentence[ pos ] ;
1191                     throw ParserError( os.str() ) ;
1192             }
1193             // ----------------< from user >----------------------
1194 
1195             ++pos ; // Advance to next token.
1196         } // end else
1197 
1198         // Push token on stack.
1199         input_stack_.push_back( tok ) ;
1200 
1201         #ifdef DEBUG_PP_PARSER
1202         cout << "    Push token " << tok << endl ;
1203         #endif
1204 
1205     } // end while
1206 
1207     // At end of input, push the $ terminator symbol.
1208     tok.type_ = PolySymbol::Dollar ;
1209     tok.value_.scalar_ = 0 ;
1210 
1211     input_stack_.push_back( tok ) ;
1212 
1213     #ifdef DEBUG_PP_PARSER
1214     cout << "    Last token " << tok << endl ;
1215     #endif
1216 
1217     // Reverse all the symbols into our preferred order.
1218     reverse( input_stack_.begin(), input_stack_.end() ) ;
1219 }
1220 
1221 /*=============================================================================
1222  |
1223  | NAME
1224  |
1225  |    syntaxDirectedTranslation
1226  |
1227  | DESCRIPTION
1228  |
1229  |     We have a reduce action   
1230  | 
1231  |         ACTION[ sm, ai ] = reduce( A -> beta = Xm-r+1 ... Xm )  
1232  |
1233  |     using the production
1234  |                        
1235  |         A -> Xm-r+1 ... Xm
1236  |                              
1237  |     Here's the stack before the reduction:
1238  |
1239  |                                parse_stack_[ topIndex-1 ]   parse_stack_[ topIndex ]
1240  |                                                        v   v
1241  |                                                        v   v
1242  |         (s0 X1 ...    Xm-r sm-r      Xm-r+1 sm-r+1 ... Xm sm     |     ai ai+1 ... an $)
1243  | 
1244  |     and after the reduction:
1245  |
1246  |         (s0 X1 ...    Xm-r sm-r      A s                         |      ai+1 ... an $)
1247  |
1248  |     Carry out the syntax directed translation f () using the values in the right hand
1249  |     side of the ith production,                i
1250  |
1251  |         A.value = f ( Xm-r+1.value ... Xm.value )
1252  |                    i 
1253  |
1254  +============================================================================*/
1255 
1256 template <typename SymbolType, typename ValueType>
1257 void PolyParser<SymbolType, ValueType>::syntaxDirectedTranslation( int productionNum, int topIndex,
1258                                                                    Symbol<SymbolType,ValueType> & symbol )
1259 {
1260     switch( productionNum )
1261     {
1262         // Reduce (S -> POLY MOD)
1263         case 1:
1264         {
1265             // I'll explain this syntax-directed translation in detail.  The other cases are similar.
1266             // Looking at the production above, we have the right hand side symbols on the parse stack
1267             // along with their values:
1268             //     parse stack = (POLY MOD |
1269             // Now we compute the value of S (denoted by the variable as) from POLY and MOD.
1270             // S is the final result.  Its polynomial value is the value of POLY and its modulus is the
1271             // value of MOD.
1272             symbol.value_.f_      = parse_stack_[ topIndex - 1 ].value_.f_ ;
1273             symbol.value_.scalar_ = parse_stack_[ topIndex     ].value_.scalar_ ;
1274 
1275             // ----------------< debug print from parse tables >----------------
1276             #ifdef DEBUG_PP_PARSER
1277             cout << "    Reduce (S -> POLY MOD)" << " Value = " << symbol.value_ << endl ;
1278             #endif
1279         }
1280         break ;
1281 
1282         // Reduce (MOD -> COMMA INTEGER)
1283         case 2:
1284         {
1285             // The value of MOD is INTEGER (we ignore the comma).
1286             symbol.value_.scalar_ = parse_stack_[ topIndex ].value_.scalar_ ;
1287 
1288             #ifdef DEBUG_PP_PARSER
1289             cout << "    Reduce (MOD -> COMMA INTEGER)" << " Value = " << symbol.value_ << endl ;
1290             #endif
1291         }
1292         break ;
1293 
1294         // Reduce (MOD -> EPSILON)
1295         case 3:
1296         {
1297             // There isn't any value for MOD, so use the default modulus of 2.
1298             symbol.value_.scalar_ = 2 ;
1299 
1300             #ifdef DEBUG_PP_PARSER
1301             cout << "    Reduce (MOD -> EPSILON)" << " Value = " << symbol.value_ << endl ;
1302             #endif
1303         }
1304         break ;
1305 
1306         // Reduce (POLY -> POLY + TERM)
1307         case 4:
1308         {
1309             // A.poly = POLY + TERM
1310 
1311             // Degree of POLY.  e.g. x+1 has degree 1, 3 has degree 0.
1312             int degPoly = static_cast<int>(parse_stack_[ topIndex - 2 ].value_.f_.size()) - 1 ;
1313 
1314             // Degree of TERM
1315             int degTerm = static_cast<int>(parse_stack_[ topIndex ].value_.f_.size()) - 1 ;
1316 
1317             // A.poly = POLY
1318             symbol.value_.f_ = parse_stack_[ topIndex - 2 ].value_.f_ ;
1319 
1320             // Make POLY large enough to handle rhs POLY and TERM.
1321             symbol.value_.f_.resize( degTerm > degPoly ? degTerm+1 : degPoly+1, 0 ) ;
1322 
1323             // A.poly += TERM
1324             for (int i = degTerm ;  i >= 0 ;  --i)
1325             {
1326                 symbol.value_.f_[ i ] +=
1327                     parse_stack_[ topIndex ].value_.f_[ i ] ;
1328             }
1329 
1330             #ifdef DEBUG_PP_PARSER
1331             cout << "    Reduce (POLY -> POLY + TERM)" << " Value = " << symbol.value_ << endl ;
1332             #endif
1333         }
1334         break ;
1335 
1336         // Reduce (POLY -> TERM)
1337         case 5:
1338         {
1339             // Degree of POLY
1340             int degPoly = static_cast<int>(symbol.value_.f_.size()) - 1 ;
1341 
1342             // Degree of TERM
1343             int degTerm = static_cast<int>(parse_stack_[ topIndex ].value_.f_.size()) - 1 ;
1344 
1345             // Make POLY large enough to handle term's power.
1346             symbol.value_.f_.resize( degTerm > degPoly ? degTerm+1 : degPoly+1, 0 ) ;
1347 
1348             // Zero the polynomial.
1349             for (int i = static_cast<int>(symbol.value_.f_.size()) - 1 ;  i >= 0 ;  --i)
1350                 symbol.value_.f_[ i ] = 0 ;
1351 
1352             // Add term.
1353             for (int i = static_cast<int>(symbol.value_.f_.size()) - 1 ;  i >= 0 ;  --i)
1354                 symbol.value_.f_[ i ]  += parse_stack_[ topIndex ].value_.f_[ i ] ;
1355 
1356             #ifdef DEBUG_PP_PARSER
1357             cout << "    Reduce (POLY -> TERM) " << " Value = " << symbol.value_ << endl ;
1358             #endif
1359         }
1360         break ;
1361 
1362         // Reduce (TERM -> MULTIPLIER POWER)
1363         case 6:
1364         {
1365             // Degree of POWER.
1366             unsigned int degPower = static_cast<int>( parse_stack_[ topIndex ].value_.scalar_ ) ;
1367 
1368             // Make TERM large enough to handle the power.
1369             symbol.value_.f_.resize( degPower + 1, 0 ) ;
1370 
1371             // Zero TERM.
1372             for (int i = static_cast<int>(symbol.value_.f_.size()) - 1 ;  i >= 0 ;  --i)
1373                 symbol.value_.f_[ i ] = 0 ;
1374 
1375             // TERM = MULTIPLIER x ^ POWER
1376             symbol.value_.f_[ degPower ] =
1377             static_cast<int>( parse_stack_[ topIndex - 1 ].value_.scalar_ ) ;
1378 
1379             #ifdef DEBUG_PP_PARSER
1380             cout << "    Reduce (TERM -> MULTIPLIER POWER)" << " Value = " << symbol.value_ << endl ;
1381             #endif
1382         }
1383         break ;
1384 
1385         // Reduce (MULTIPLIER -> INTEGER)
1386         case 7:
1387         {
1388             // Set value of MULTIPLIER.
1389             symbol.value_.scalar_ = parse_stack_[ topIndex ].value_.scalar_ ;
1390 
1391             #ifdef DEBUG_PP_PARSER
1392             cout << "    Reduce (MULTIPLIER -> INTEGER)" << " Value = " << symbol.value_ << endl ;
1393             #endif
1394         }
1395         break ;
1396 
1397         // Reduce (MULTIPLIER -> EPSILON)
1398         case 8:
1399         {
1400             // Multiplier default = 1
1401             symbol.value_.scalar_ = 1 ;
1402 
1403             #ifdef DEBUG_PP_PARSER
1404             cout << "    Reduce (MULTIPLIER -> EPSILON)" << " Value = " << symbol.value_ << endl ;
1405             #endif
1406         }
1407         break ;
1408 
1409         // Reduce (POWER -> X)
1410         case 9:
1411         {
1412             // POWER is the exponent of x, so we
1413             // interpret as a scalar.
1414             symbol.value_.scalar_ = 1 ;
1415 
1416             #ifdef DEBUG_PP_PARSER
1417             cout << "    Reduce  (POWER -> X)" << " Value = " << symbol.value_ << endl ;
1418             #endif
1419         }
1420         break ;
1421 
1422         // Reduce (POWER -> X ^ INTEGER)
1423         case 10:
1424         {
1425             // POWER = value of INTEGER.
1426             symbol.value_.scalar_ = parse_stack_[ topIndex ].value_.scalar_ ;
1427 
1428             #ifdef DEBUG_PP_PARSER
1429             cout << "    Reduce (POWER -> X ^ INTEGER)" << " Value = " << symbol.value_ << endl ;
1430             #endif
1431         }
1432         break ;
1433 
1434         // Reduce (POWER -> EPSILON)
1435         case 11:
1436         {
1437             // Default power is 0.
1438             symbol.value_.scalar_ = 0 ;
1439 
1440             #ifdef DEBUG_PP_PARSER
1441             cout << "    Reduce (POWER -> EPSILON)" << "Value = " << symbol.value_ << endl ;
1442             #endif
1443         }
1444         break ;
1445     }
1446 }
1447 
1448 
1449 
1450 /*------------------------------- Parser Child Classes ------------------------*/
1451 
1452 
1453 
1454 /*=============================================================================
1455  |
1456  | NAME
1457  |
1458  |     operator=( const FactorizationValue & v )
1459  |
1460  |
1461  | DESCRIPTION
1462  |
1463  |     Assignment operator for FactorizationValue.
1464  |
1465  +============================================================================*/
1466 
1467 template<typename IntType>
1468 FactorizationValue<IntType> & FactorizationValue<IntType>::operator=( const FactorizationValue<IntType> & v )
1469 {
1470     // Check for assigning to oneself:  just pass back a reference to the unchanged object.
1471     if (this == &v)
1472         return *this ;
1473 
1474     numberString_ = v.numberString_ ;
1475     factor_ = v.factor_ ;
1476 
1477     // Pass back the object so we can concatenate assignments.
1478     return *this ;
1479 }
1480 
1481 
1482 
1483 /*=============================================================================
1484  |
1485  | NAME
1486  |
1487  |     numberStringToInteger
1488  |
1489  |
1490  | DESCRIPTION
1491  |
1492  |     Convert a number string (sequence of decimal digits) to an integer.
1493  |
1494  +============================================================================*/
1495 
1496 template<typename IntType>
1497 IntType FactorizationValue<IntType>::numberStringToInteger( const string & numberString )
1498 {
1499     // First define a generic integer type.
1500     IntType u ;
1501 
1502     // Create a string stream and load it with the number string.
1503     istringstream is ;
1504     is.clear() ;
1505     is.str( numberString ) ;
1506 
1507     // Read the generic integer from the stream using the >> operator which will see IntType and call either of:
1508     //     The BigInt class method for operator>>
1509     //     The C++ language method for the >> operator using the type ppuint which is unsigned long long or unsigned int
1510     is >> u ;
1511 
1512     return u ;
1513 }
1514 
1515 
1516 /*=============================================================================
1517  |
1518  | NAME
1519  |
1520  |     FactorizationValue
1521  |
1522  | DESCRIPTION
1523  |
1524  |     Default constructor for a value which contains a scalar or polynomial.
1525  |
1526  +============================================================================*/
1527 
1528 template<typename IntType>
1529 FactorizationValue<IntType>::FactorizationValue()
1530     : numberString_ { "" }
1531     , factor_ { 0 }
1532 {
1533 }
1534 
1535 
1536 /*=============================================================================
1537  |
1538  | NAME
1539  |
1540  |     FactorizationValue
1541  |
1542  | DESCRIPTION
1543  |
1544  |     Default constructor for a value which contains a scalar or polynomial.
1545  |
1546  +============================================================================*/
1547 
1548 template<typename IntType>
1549 FactorizationValue<IntType>::FactorizationValue( const IntType & p, const int & count )
1550 : numberString_{ "" }
1551 {
1552     PrimeFactor<IntType> factor( p, count ) ;
1553     factor_.clear() ;
1554     factor_.push_back( factor ) ;
1555 }
1556 
1557 
1558 /*=============================================================================
1559  |
1560  | NAME
1561  |
1562  |     FactorizationValue
1563  |
1564  | DESCRIPTION
1565  |
1566  |     Copy constructor for FactorizationValue.
1567  |
1568  +============================================================================*/
1569 
1570 template<typename IntType>
1571 FactorizationValue<IntType>::FactorizationValue( const FactorizationValue<IntType> & v )
1572 : numberString_( v.numberString_ )
1573 , factor_( v.factor_ )
1574 {
1575 }
1576 
1577 
1578 /*=============================================================================
1579 |
1580 | NAME
1581 |
1582 |     FactorizationParser
1583 |
1584 | DESCRIPTION
1585 |
1586 |     Default constructor for the class.
1587 |
1588 +============================================================================*/
1589 
1590 template < typename SymbolType, typename ValueType >
1591 FactorizationParser< SymbolType, ValueType >::FactorizationParser()
1592     : Parser<SymbolType,ValueType>()
1593 {
1594     // Initialize all the parse tables.
1595     initializeTables() ;
1596 }
1597 
1598 
1599 /*=============================================================================
1600  | 
1601  | NAME
1602  | 
1603  |     ~FactorizationParser
1604  | 
1605  | DESCRIPTION
1606  | 
1607  |     Default deeeestructor for the class.
1608  | 
1609  +============================================================================*/
1610 
1611 template < typename SymbolType, typename ValueType >
1612 FactorizationParser< SymbolType, ValueType >::~FactorizationParser()
1613 {
1614     // Private data destroy themselves.
1615 }
1616 
1617 
1618 /*=============================================================================
1619  |
1620  | NAME
1621  |
1622  |     FactorizationParser( const FactorizationParser & FactorizationParser )
1623  |
1624  | DESCRIPTION
1625  |
1626  |     Copy constructor.
1627  |
1628  +============================================================================*/
1629 
1630 template < typename SymbolType, typename ValueType >
1631 FactorizationParser<SymbolType, ValueType>::FactorizationParser( const FactorizationParser< SymbolType, ValueType > & FactorizationParser )
1632         : Parser<SymbolType, ValueType>( FactorizationParser )
1633 {
1634 }
1635 
1636 
1637 /*=============================================================================
1638  | 
1639  | NAME
1640  | 
1641  |    operator=( const FactorizationParser & FactorizationParser )
1642  | 
1643  | 
1644  | DESCRIPTION
1645  | 
1646  |    Assignment operator.
1647  | 
1648  +============================================================================*/
1649 
1650 template < typename SymbolType, typename ValueType >
1651 FactorizationParser< SymbolType, ValueType > & FactorizationParser< SymbolType, ValueType >::operator=( const FactorizationParser & FactorizationParser )
1652 {
1653     // Check for assigning to oneself:  just pass back a reference to the unchanged object.
1654     if (this == &FactorizationParser)
1655              return *this ;
1656 
1657     input_stack_ = FactorizationParser.input_stack_ ;
1658     parse_stack_ = FactorizationParser.parse_stack_ ;
1659 
1660     // Return reference to this object.
1661     return *this ;
1662 }
1663 
1664 
1665 /*=============================================================================
1666  | 
1667  | NAME
1668  | 
1669  |     initializeTables
1670  | 
1671  | DESCRIPTION
1672  | 
1673  |     Initialize ACTION, GOTO, and ERROR_MESSAGE tables for an LALR(1) parser.
1674  |     And also information about the productions.
1675  |
1676  +============================================================================*/
1677 
1678 template < typename SymbolType, typename ValueType >
1679 void FactorizationParser<SymbolType,ValueType>::initializeTables()
1680 {
1681     // Need these so we can preallocate the vector lengths.  Vector's operator[] is unchecked!
1682     num_states_       = 16 ; // Including the 0 state.
1683     num_productions__  =  7 ;
1684     num_terminals_    = static_cast<int>(FactorizationSymbol::NumTerminals) ;
1685     num_non_terminals_ = static_cast<int>(FactorizationSymbol::NumSymbols) - static_cast<int>(FactorizationSymbol::NumTerminals) - 1 ;  // Don't count the NumTerminals enum itself.
1686 
1687     // Expand the rows of the ACTION table to hold all the states.
1688     action_table_.resize( num_states_ ) ;
1689 
1690     // Expand the rows of the GOTO table to hold all the states.
1691     goto_table_.resize( num_states_ ) ;
1692 
1693     // Expand the rows of the ACTION table to hold all the states.
1694     // Allow space in 0th slot (unused).
1695     production_.resize( num_productions__ + 1 ) ;
1696 
1697     error_message_.resize( num_states_ ) ;
1698 
1699     // TODO:  does resize or operator[] throw any exceptions?  use vector.at( i ) for checked access?
1700     try
1701     {
1702         // For each state and each terminal, insert
1703         //    if Shift, the new state to push on the stack,
1704         //    if Reduce, the production number.
1705         insertAction(  0,  FactorizationSymbol::Integer,   Action::Shift,   2 ) ;
1706         insertAction(  1,  FactorizationSymbol::Dollar,    Action::Accept,  0 ) ;
1707         insertAction(  2,  FactorizationSymbol::Integer,   Action::Shift,   3 ) ;
1708         insertAction(  3,  FactorizationSymbol::Integer,   Action::Shift,   4 ) ;
1709 
1710         insertAction(  4,  FactorizationSymbol::Caret,     Action::Reduce,  7 ) ;
1711         insertAction(  4,  FactorizationSymbol::Dollar,    Action::Reduce,  7 ) ;
1712         insertAction(  4,  FactorizationSymbol::Period,    Action::Reduce,  7 ) ;
1713         insertAction(  4,  FactorizationSymbol::Backslash, Action::Reduce,  7 ) ;
1714 
1715         insertAction(  5,  FactorizationSymbol::Dollar,    Action::Reduce,  1 ) ;
1716         insertAction(  5,  FactorizationSymbol::Period,    Action::Shift,   8 ) ;
1717 
1718         insertAction(  6,  FactorizationSymbol::Dollar,    Action::Reduce,  3 ) ;
1719         insertAction(  6,  FactorizationSymbol::Period,    Action::Reduce,  3 ) ;
1720 
1721         insertAction(  7,  FactorizationSymbol::Caret,     Action::Shift,   9 ) ;
1722         insertAction(  7,  FactorizationSymbol::Dollar,    Action::Reduce,  5 ) ;
1723         insertAction(  7,  FactorizationSymbol::Period,    Action::Reduce,  5 ) ;
1724         insertAction(  7,  FactorizationSymbol::Backslash, Action::Shift,  10 ) ;
1725 
1726         insertAction(  8,  FactorizationSymbol::Integer,   Action::Shift,   4 ) ;
1727 
1728         insertAction(  9,  FactorizationSymbol::Integer,   Action::Shift,   4 ) ;
1729 
1730         insertAction( 10,  FactorizationSymbol::Integer,   Action::Shift,  14 ) ;
1731 
1732         insertAction( 11,  FactorizationSymbol::Dollar,    Action::Reduce,  2 ) ;
1733         insertAction( 11,  FactorizationSymbol::Period,    Action::Reduce,  2 ) ;
1734 
1735         insertAction( 13,  FactorizationSymbol::Dollar,    Action::Reduce,  4 ) ;
1736         insertAction( 13,  FactorizationSymbol::Period,    Action::Reduce,  4 ) ;
1737         insertAction( 13,  FactorizationSymbol::Backslash, Action::Shift,  10 ) ;
1738 
1739         insertAction( 14,  FactorizationSymbol::Caret,     Action::Reduce,  6 ) ;
1740         insertAction( 14,  FactorizationSymbol::Dollar,    Action::Reduce,  6 ) ;
1741         insertAction( 14,  FactorizationSymbol::Period,    Action::Reduce,  6 ) ;
1742         insertAction( 14,  FactorizationSymbol::Backslash, Action::Reduce,  6 ) ;
1743 
1744 
1745         // For each state and symbol insert a new state.
1746         insertGoto( 0,  FactorizationSymbol::S,               1 ) ;
1747 
1748         insertGoto( 3,  FactorizationSymbol::Factorization,   5 ) ;
1749         insertGoto( 3,  FactorizationSymbol::Factor,          6 ) ;
1750         insertGoto( 3,  FactorizationSymbol::BigInteger,      7 ) ;
1751 
1752         insertGoto( 8,  FactorizationSymbol::Factor,         11 ) ;
1753         insertGoto( 8,  FactorizationSymbol::BigInteger,      7 ) ;
1754 
1755         insertGoto( 9,  FactorizationSymbol::BigInteger,     13 ) ;
1756 
1757 
1758         // For each production (given by a unique number), insert the single nonterminal
1759         // which starts the production, and the length in symbols of the right hand side.
1760         // We'll need to know which production is being reduced so we can apply the syntax
1761         // directed translation, and pop the production off the stack.
1762         insertProduction(  1,      FactorizationSymbol::S,               3 ) ; // S -> INTEGER INTEGER FACTORIZATION
1763         insertProduction(  2,      FactorizationSymbol::Factorization,   3 ) ; // FACTORIZATION -> FACTORIZATION PERIOD FACTOR
1764         insertProduction(  3,      FactorizationSymbol::Factorization,   1 ) ; // FACTORIZATION -> FACTOR
1765         insertProduction(  4,      FactorizationSymbol::Factor,          3 ) ; // FACTOR -> BIGINTEGER ^ BIGINTEGER
1766         insertProduction(  5,      FactorizationSymbol::Factor,          1 ) ; // FACTOR -> BIGINTEGER
1767         insertProduction(  6,      FactorizationSymbol::BigInteger,      3 ) ; // BIGINTEGER -> BIGINTEGER \ INTEGER
1768         insertProduction(  7,      FactorizationSymbol::BigInteger,      1 ) ; // BIGINTEGER -> INTEGER
1769 
1770         // For each state, provide an error message.
1771         insertErrorMessage(  0, "Expecting to see the power n." ) ;
1772         insertErrorMessage(  1, "Expecting end of input." ) ;
1773         insertErrorMessage(  2, "Expecting to see the number of prime factors." ) ;
1774         insertErrorMessage(  3, "Expecting an integer." ) ;
1775         insertErrorMessage(  4, "Expecting integer continuation \\ or . followed by a factor or ^ followed by a power or end of input." ) ;
1776         insertErrorMessage(  5, "Expecting another factor after the . or the end of the factorization." ) ;
1777         insertErrorMessage(  6, "Expecting a ." ) ;
1778         insertErrorMessage(  7, "Expecting integer continuation \\ or . followed by a factor or a ^ follwed by a power or end of input." ) ;
1779         insertErrorMessage(  8, "Expecting factor or an integer." ) ;
1780         insertErrorMessage(  9, "Expecting an integer." ) ;
1781         insertErrorMessage( 10, "Expecting an integer after the continuation \\." ) ;
1782         insertErrorMessage( 11, "Expecting . and another factor or end of input." ) ;
1783         insertErrorMessage( 13, "Expecting integer continuation \\ or . and next factor or end of input." ) ;
1784         insertErrorMessage( 14, "Expecting . and next factor or ^ and power or end of input after integer continuation \\." ) ;
1785 
1786     }
1787     catch( length_error & e)
1788     {
1789         ostringstream os ;
1790         os << "FactorizationParser::initializeTables had a length_error exception while initializing parse tables" ;
1791         throw ParserError( os.str(), __FILE__, __LINE__ ) ;
1792     }
1793 }
1794 
1795 
1796 /*=============================================================================
1797  |
1798  | NAME
1799  |
1800  |    tokenize
1801  |
1802  | DESCRIPTION
1803  |
1804  |    This is the lexical analyzer.  Given an input string, convert it into tokens
1805  |    to fill the input stack.
1806  |
1807  |    Each token has a type, which is a nonterminal symbol, and its value.
1808  |
1809  |    This specific lexer converts one line of a factorization table.
1810  |
1811  +============================================================================*/
1812 
1813 template <typename SymbolType, typename ValueType>
1814 void FactorizationParser<SymbolType, ValueType>::tokenize( string sentence )
1815 {
1816     Symbol<SymbolType, ValueType> tok( FactorizationSymbol::NumSymbols, 0 ) ;
1817 
1818     // Starting position to scan.
1819     unsigned int pos = 0 ;
1820 
1821     // Clear the token stack.
1822     input_stack_.clear() ;
1823 
1824     // Scan sentence to end.
1825     while( pos < sentence.length() )
1826     {
1827         // Skip whitespace.
1828         while (pos < sentence.length() && iswspace( sentence[ pos ]))
1829             ++pos ; // Advance to next token.
1830 
1831         #ifdef DEBUG_PP_PARSER
1832         cout << "tokenize:  sentence[ " << pos << " ] = " << sentence[ pos ] << endl ;
1833         #endif
1834 
1835         // We see a digit.
1836         if (pos < sentence.size() && isdigit( sentence[ pos ]))
1837         {
1838             string numberString = "" ;
1839 
1840             // Read a sequence of digits until the next non-digit.
1841             while( pos < sentence.size() && isdigit( sentence[ pos ]))
1842             {
1843                 numberString += sentence[ pos ] ;
1844                 ++pos ; // Advance to next token.
1845             }
1846 
1847             tok.type_                = FactorizationSymbol::Integer ;
1848             tok.value_.numberString_ = numberString ;
1849         }
1850         // A non-digit symbol.
1851         else
1852         {
1853             tok.value_.numberString_ = "" ;
1854 
1855             // Read another type of token.
1856             switch( sentence[ pos ] )
1857             {
1858                 case '.' :
1859                     tok.type_ = FactorizationSymbol::Period ;
1860                 break ;
1861 
1862                 case '^' :
1863                     tok.type_ = FactorizationSymbol::Caret ;
1864                 break ;
1865 
1866                 case '\\' :
1867                     tok.type_ = FactorizationSymbol::Backslash ;
1868                 break ;
1869 
1870                 default:
1871                     // Throw a parser error of unexpected input if we see a bad symbol.
1872                     // Not really an exception but more of a user input error.
1873                     ostringstream os ;
1874                     os << "Error:  Unexpected symbol in lexical analyzer" << sentence[ pos ] ;
1875                     throw ParserError( os.str() ) ;
1876             }
1877 
1878             ++pos ; // Advance to next token.
1879         } // end else
1880 
1881         // Push token on stack.
1882         input_stack_.push_back( tok ) ;
1883 
1884         #ifdef DEBUG_PP_PARSER
1885         cout << "    Push token " << tok << endl ;
1886         #endif
1887 
1888     } // end while
1889 
1890     // At end of input, push the $ terminator symbol.
1891     tok.type_ = FactorizationSymbol::Dollar ;
1892     tok.value_.numberString_ = "" ;
1893 
1894     input_stack_.push_back( tok ) ;
1895 
1896     #ifdef DEBUG_PP_PARSER
1897     cout << "    Push last token " << tok << endl ;
1898     #endif
1899 
1900     // Reverse all the symbols into our preferred order.
1901     reverse( input_stack_.begin(), input_stack_.end() ) ;
1902 }
1903 
1904 /*=============================================================================
1905  |
1906  | NAME
1907  |
1908  |    syntaxDirectedTranslation
1909  |
1910  | DESCRIPTION
1911  |
1912  |     We have a reduce action   
1913  | 
1914  |         ACTION[ sm, ai ] = reduce( A -> beta = Xm-r+1 ... Xm )  
1915  |
1916  |     using the production
1917  |                        
1918  |         A -> Xm-r+1 ... Xm
1919  |                              
1920  |     Here's the stack before the reduction:
1921  |
1922  |                                parse_stack_[ topIndex-1 ]   parse_stack_[ topIndex ]
1923  |                                                        v   v
1924  |                                                        v   v
1925  |         (s0 X1 ...    Xm-r sm-r      Xm-r+1 sm-r+1 ... Xm sm     |     ai ai+1 ... an $)
1926  | 
1927  |     and after the reduction:
1928  |
1929  |         (s0 X1 ...    Xm-r sm-r      A s                         |      ai+1 ... an $)
1930  |
1931  |     Carry out the syntax directed translation f () using the values in the right hand
1932  |     side of the ith production,                i
1933  |
1934  |         A.value = f ( Xm-r+1.value ... Xm.value )
1935  |                    i 
1936  |
1937  +============================================================================*/
1938 
1939 template <typename SymbolType, typename ValueType>
1940 void FactorizationParser<SymbolType,ValueType>::
1941          syntaxDirectedTranslation( int productionNum, int topIndex, Symbol<SymbolType,ValueType> & symbol )
1942 {
1943     switch( productionNum )
1944     {
1945         // Reduce (S -> INTEGER INTEGER FACTORIZATION)
1946         case 1:
1947         {
1948             // I'll explain this syntax-directed translation in detail.  The other cases are similar.
1949             // The parse stack contains the right hand side symbols (types and values) of the production:
1950             //     parse stack = (INTEGER INTEGER FACTORIZATION |
1951             // We compute the value of S (denoted by the variable symbol) from the right hand side.
1952             //
1953             symbol.value_.factor_       = parse_stack_[ topIndex     ].value_.factor_ ; // Factorization.
1954             symbol.value_.numberString_ = parse_stack_[ topIndex - 2 ].value_.numberString_ ; // Value of n.
1955 
1956             #ifdef DEBUG_PP_PARSER
1957             cout << "    Reduce (S -> INTEGER INTEGER FACTORIZATION)" << " Value = " << symbol << endl ;
1958             #endif
1959         }
1960         break ;
1961 
1962         // Reduce (FACTORIZATION -> FACTORIZATION PERIOD FACTOR)
1963         case 2:
1964         {
1965             // Append the new prime factor to the end of the factorization.
1966             symbol.value_.factor_ = parse_stack_[ topIndex - 2 ].value_.factor_ ;
1967             symbol.value_.factor_.push_back( parse_stack_[ topIndex ].value_.factor_[ 0 ] ) ;
1968 
1969             #ifdef DEBUG_PP_PARSER
1970             cout << "    Reduce (FACTORIZATION -> FACTORIZATION PERIOD FACTOR)" << " Value = " << symbol.value_ << endl ;
1971             #endif
1972         }
1973         break ;
1974 
1975         // Reduce (FACTORIZATION -> FACTOR)
1976         case 3:
1977         {
1978             // Factorization has only one factor.
1979             symbol.value_.factor_.clear() ;
1980             symbol.value_.factor_.push_back( parse_stack_[ topIndex ].value_.factor_[ 0 ] ) ;
1981 
1982             #ifdef DEBUG_PP_PARSER
1983             cout << "    Reduce (FACTORIZATION -> FACTOR)" << " Value = " << symbol.value_ << endl ;
1984             #endif
1985         }
1986         break ;
1987 
1988         // Reduce (FACTOR -> BIGINTEGER ^ BIGINTEGER)
1989         case 4:
1990         {
1991             // Create a new value and load it with the prime factor and its count.
1992             auto primeFactor = ValueType::numberStringToInteger( parse_stack_[ topIndex - 2 ].value_.numberString_ ) ;
1993             auto primeCount  = static_cast<int>( ValueType::numberStringToInteger( parse_stack_[ topIndex ].value_.numberString_ ) ) ;
1994             ValueType value( primeFactor, primeCount ) ;
1995 
1996             // Factorization has only one factor.
1997             symbol.value_.factor_.clear() ;
1998             symbol.value_.factor_.push_back( value.factor_[ 0 ] ) ;
1999 
2000             #ifdef DEBUG_PP_PARSER
2001             cout << "    Reduce (FACTOR -> BIGINTEGER ^ BIGINTEGER)" << " Value = " << symbol.value_ << endl ;
2002             #endif
2003         }
2004         break ;
2005 
2006         // Reduce (FACTOR -> BIGINTEGER)
2007         case 5:
2008         {
2009             // Create a new value which has a single prime factor.
2010             auto primeFactor = ValueType::numberStringToInteger( parse_stack_[ topIndex ].value_.numberString_ ) ;
2011             ValueType value( primeFactor, 1 ) ;
2012 
2013             // Factorization has only one factor.
2014             symbol.value_.factor_.clear() ;
2015             symbol.value_.factor_.push_back( value.factor_[ 0 ] ) ;
2016 
2017             #ifdef DEBUG_PP_PARSER
2018             cout << "    Reduce (FACTOR -> BIGINTEGER) " << " Value = " << symbol.value_ << endl ;
2019             #endif
2020         }
2021         break ;
2022 
2023         // Reduce (BIGINTEGER -> BIGINTEGER \ INTEGER)
2024         case 6:
2025         {
2026             // Concatenate the number strings.  Remember, the production right hand side is sitting on the parse stack and the rightmost
2027             // token is at the top of the stack.
2028             symbol.value_.numberString_ = parse_stack_[ topIndex - 2 ].value_.numberString_ + parse_stack_[ topIndex ].value_.numberString_ ;
2029 
2030             #ifdef DEBUG_PP_PARSER
2031             cout << "    Reduce (BIGINTEGER -> BIGINTEGER \\ INTEGER)" << " Value = " << symbol.value_ << endl ;
2032             #endif
2033         }
2034         break ;
2035 
2036         // Reduce (BIGINTEGER -> INTEGER)
2037         case 7:
2038         {
2039             // Initial number string.
2040             symbol.value_.numberString_ = parse_stack_[ topIndex ].value_.numberString_ ;
2041 
2042             #ifdef DEBUG_PP_PARSER
2043             cout << "    Reduce (BIGINTEGER -> INTEGER)" << " Value = " << symbol.value_ << endl ;
2044             #endif
2045         }
2046         break ;
2047     }
2048 }
2049 
2050 
2051 
2052 /*=============================================================================
2053  | 
2054  | NAME
2055  | 
2056  |     parseCommandLine
2057  | 
2058  | DESCRIPTION
2059  | 
2060  |      Parse the command line.
2061  | 
2062  | 
2063  | EXAMPLE
2064  | 
2065  |    pp -h
2066  |    pp -s 2 4
2067  |    pp -t 2 4 x^3+x^2+1                 // No blanks, please!  Looks like
2068  |                                        // several command line arguments.
2069  |    pp -t 2 4 "x^  3  +  x ^ 2  +  1"   // Blanks OK now.
2070  | 
2071  +============================================================================*/
2072 
2073 template < typename SymbolType, typename PolyValueType >
2074 void PolyParser< SymbolType, PolyValueType >::parseCommandLine( int argc, const char * argv[] )
2075 {
2076     const char * input_arg_string ;
2077     const char * option_ptr ;
2078 
2079     int          num_arg{ 0 } ;
2080     const char * arg_string[ MAX_NUM_COMMAND_LINE_ARGS ] ;
2081     memset( arg_string, 0, sizeof( arg_string ) ) ;
2082 
2083     /*  Initialize to defaults. */
2084     test_polynomial_for_primitivity_ = false ;
2085     list_all_primitive_polynomials_  = false ;
2086     print_operation_count_          = false ;
2087     print_help_                    = false ;
2088     slow_confirm_                  = false ;
2089     p                             = 0 ;
2090     n                             = 0 ;
2091 
2092     current_working_dir_ = current_path().string() ;
2093 
2094     //  Parse the command line to get the options and their inputs.
2095     for (int input_arg_index = 0 ;  input_arg_index < argc ;
2096          ++input_arg_index)
2097     {
2098         /*  Get next argument string. */
2099         input_arg_string = argv[ input_arg_index ] ;
2100 
2101         /* We have an option:  a hyphen followed by a non-null string. */
2102         if (input_arg_string[ 0 ] == '-' && input_arg_string[ 1 ] != '\0')
2103         {
2104             /* Scan all options. */
2105             for (option_ptr = input_arg_string + 1 ;  *option_ptr != '\0' ;
2106                  ++option_ptr)
2107             {
2108                 switch( *option_ptr )
2109                 {
2110                     /* Test a given polynomial for primitivity. */
2111                     case 't':
2112                         test_polynomial_for_primitivity_ = true ;
2113                     break ;
2114 
2115                     /* List all primitive polynomials.  */
2116                     case 'a':
2117                        list_all_primitive_polynomials_ = true ;
2118                     break ;
2119 
2120                     /* Print statistics on program operation. */
2121                     case 's':
2122                        print_operation_count_ = true ;
2123                     break ;
2124 
2125                     /* Print help. */
2126                     case 'h':
2127                     case 'H':
2128                         print_help_ = true ;
2129                     break ;
2130 
2131                     /* Turn on all self-checking (slow!).  */
2132                     case 'c':
2133                         slow_confirm_ = true ;
2134                     break ;
2135 
2136                     default:
2137                        ostringstream os ;
2138                        os << "Cannot recognize the option" << *option_ptr ;
2139                        throw ParserError( os.str() ) ;
2140                     break ;
2141                 }
2142             }
2143         }
2144         else  /* Not an option, but an argument. */
2145         {
2146             if (num_arg >= MAX_NUM_COMMAND_LINE_ARGS)
2147             {
2148                 ostringstream os ;
2149                 os << "Too many command line arguments = " << num_arg << " >= MAX_NUM_COMMAND_LINE_ARGS = " << MAX_NUM_COMMAND_LINE_ARGS ;
2150                 throw ParserError( os.str() ) ;
2151             }
2152             else
2153                 arg_string[ num_arg++ ] = input_arg_string ;
2154         }
2155     }
2156 
2157     // User specified a polynomial to test.  First argument is program name, next is
2158     // the polynomial.
2159     if (test_polynomial_for_primitivity_)
2160     {
2161         string testPoly ;
2162         testPoly.assign( arg_string[ 1 ] ) ; // stringify it.
2163         test_polynomial_ = testPoly ;         // We've range checked n and p here already.
2164 
2165         n = test_polynomial_.deg() ;
2166         p = test_polynomial_.modulus() ;
2167     }
2168     // We had the arguments arg_string[0] = <programe name>
2169     //                      arg_string[1]= p
2170     //                      arg_string[2]= n
2171     // When we come here num_arg = 3 after the final num_arg++ above.
2172     else if (num_arg == MAX_NUM_COMMAND_LINE_ARGS)
2173     {
2174         // TODO:  convert numeric decimal string to unsigned int with overflow check.
2175         p = atoi( arg_string[ 1 ] ) ;
2176         n = atoi( arg_string[ 2 ] ) ;
2177     }
2178     else
2179     {
2180         ostringstream os{ "ERROR:  Expecting two arguments, p and n.\n\n" } ;
2181         print_help_ = true ;
2182         throw ParserError( os.str() ) ;
2183     }
2184 
2185     // Check ranges on n and p.
2186     if (p < minModulus)
2187     {
2188         ostringstream os ;
2189         os << "Error.  Polynomial modulus p must be >= " << minModulus << endl ;
2190         print_help_ = true ;
2191         throw ParserError( os.str() ) ;
2192     }
2193 
2194     if (p >= BigInt::getBase())
2195     {
2196         ostringstream os ;
2197         os << "Error.  Polynomial modulus p must be < " << BigInt::getBase() << endl ;
2198         print_help_ = true ;
2199         throw ParserError( os.str() ) ;
2200     }
2201 
2202     if (n < minDegree)
2203     {
2204         ostringstream os ;
2205         os << "Error.  Polynomial degree n must be >= " << minDegree << " but n = " << n << endl ;
2206         print_help_ = true ;
2207         throw ParserError( os.str() ) ;
2208     }
2209 
2210     //  Check to see if p is a prime.
2211     if (!isAlmostSurelyPrime( static_cast<ppuint>( p )))
2212         throw ParserError( "ERROR:  p must be a prime number.\n\n" ) ;
2213 }
2214 
2215 
2216 /*=============================================================================
2217  |
2218  | NAME
2219  |
2220  |     enumToString
2221  |
2222  | DESCRIPTION
2223  |
2224  |     Helper functions to translate enum types into human readable format.
2225  |     One generic for any SymbolType, the other two template specializations.
2226  |
2227  +============================================================================*/
2228 
2229 template< typename SymbolType >
2230 string enumToString( const SymbolType & st )
2231 {
2232     ostringstream os ;
2233 
2234     // Just return the integer number of the enumerated type since we have no
2235     // further information.
2236     os << static_cast<int>( st ) ;
2237     return os.str() ;
2238 }
2239 
2240 // Specialized for PolySymbol.
2241 template<>
2242 string enumToString<PolySymbol>( const PolySymbol & st )
2243 {
2244     string name[] { "$", "Integer", ",", "x", "+", "^", "", "S", "Mod", "Poly", "Term", "Multiplier", "Power", "" } ;
2245     return name[ static_cast<int>( st ) ] ;
2246 }
2247 
2248 // Specialized for FactorizationSymbol.
2249 template<>
2250 string enumToString<FactorizationSymbol>( const FactorizationSymbol & st )
2251 {
2252     string name[] { "$", "Integer", ".", "^", "\\", "", "S", "Factorization", "Factor", "BigInteger", "" } ;
2253     return name[ static_cast<int>( st ) ] ;
2254 }
2255 
2256 /*==============================================================================
2257  |                     Forced Template Instantiations                           |
2258  ==============================================================================*/
2259 
2260 // C++ doesn't automatically generate templated classes or functions until they
2261 // are first used.  So depending on the order of compilation, the linker may say
2262 // the templated functions are undefined.
2263 //
2264 // Therefore, explicitly instantiate ALL templates here:
2265 
2266 // General purpose LALR(1) parser.  Template versions for both the polynomial grammar and factorization grammar.
2267 template PolyValue                                                    Parser<PolySymbol, PolyValue>::parse( string s ) ;
2268 template FactorizationValue<BigInt>         Parser<FactorizationSymbol, FactorizationValue<BigInt>>::parse( string s ) ;
2269 template FactorizationValue<ppuint>         Parser<FactorizationSymbol, FactorizationValue<ppuint>>::parse( string s ) ;
2270 
2271 // Generate all symbols for the polynomial grammar.
2272 template                                    Symbol<PolySymbol, PolyValue>::Symbol( PolySymbol, int ) ;
2273 template                                    Symbol<PolySymbol, PolyValue>::Symbol( PolySymbol, int, PolyValue )  ;
2274 template                                    Symbol<PolySymbol, PolyValue>::~Symbol() ;
2275 template                                    Symbol<PolySymbol, PolyValue>::Symbol(    const Symbol< PolySymbol, PolyValue > & ) ;
2276 template Symbol<PolySymbol, PolyValue> &    Symbol<PolySymbol, PolyValue>::operator=( const Symbol< PolySymbol, PolyValue > & ) ;
2277 
2278 // Generate all the symbols for the factorization grammar.
2279 template FactorizationValue<BigInt>::FactorizationValue() ;
2280 template FactorizationValue<BigInt>::FactorizationValue( const FactorizationValue<BigInt> & ) ;
2281 template FactorizationValue<BigInt> & FactorizationValue<BigInt>::operator=( const FactorizationValue<BigInt> & ) ;
2282 template FactorizationValue<ppuint>::FactorizationValue() ;
2283 template FactorizationValue<ppuint>::FactorizationValue( const FactorizationValue<ppuint> & ) ;
2284 template FactorizationValue<ppuint> & FactorizationValue<ppuint>::operator=( const FactorizationValue<ppuint> & ) ;
2285 
2286 template Symbol<FactorizationSymbol, FactorizationValue<BigInt>>::Symbol( FactorizationSymbol, int ) ;
2287 template Symbol<FactorizationSymbol, FactorizationValue<BigInt>>::Symbol( FactorizationSymbol, int, FactorizationValue<BigInt> )  ;
2288 template Symbol<FactorizationSymbol, FactorizationValue<BigInt>>::~Symbol() ;
2289 template Symbol<FactorizationSymbol, FactorizationValue<BigInt>>::Symbol(    const Symbol<FactorizationSymbol, FactorizationValue<BigInt>> & ) ;
2290 template Symbol<FactorizationSymbol, FactorizationValue<BigInt>> &
2291          Symbol<FactorizationSymbol, FactorizationValue<BigInt>>::operator=( const Symbol<FactorizationSymbol, FactorizationValue<BigInt>> & ) ;
2292 template Symbol<FactorizationSymbol, FactorizationValue<ppuint>>::Symbol( FactorizationSymbol, int ) ;
2293 template Symbol<FactorizationSymbol, FactorizationValue<ppuint>>::Symbol( FactorizationSymbol, int, FactorizationValue<ppuint> )  ;
2294 template Symbol<FactorizationSymbol, FactorizationValue<ppuint>>::~Symbol() ;
2295 template Symbol<FactorizationSymbol, FactorizationValue<ppuint>>::Symbol(    const Symbol<FactorizationSymbol, FactorizationValue<ppuint>> & ) ;
2296 template Symbol<FactorizationSymbol, FactorizationValue<ppuint>> &
2297          Symbol<FactorizationSymbol, FactorizationValue<ppuint>>::operator=( const Symbol<FactorizationSymbol, FactorizationValue<ppuint>> & ) ;
2298 
2299 // Generate all child class member functions for the polynomial grammar.
2300 template                                      PolyParser<PolySymbol, PolyValue>::PolyParser() ;
2301 template                                      PolyParser<PolySymbol, PolyValue>::~PolyParser() ;
2302 template                                      PolyParser<PolySymbol, PolyValue>::PolyParser( const PolyParser<PolySymbol, PolyValue> & ) ;
2303 template PolyParser<PolySymbol, PolyValue> &  PolyParser<PolySymbol, PolyValue>::operator=(  const PolyParser<PolySymbol, PolyValue> & ) ;
2304 
2305 template void                                 PolyParser<PolySymbol, PolyValue>::parseCommandLine( int argc, const char * argv[] ) ;
2306 
2307 // Generate all child class member functions for the factorization grammar.
2308 template FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>>::FactorizationParser() ;
2309 template FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>>::~FactorizationParser() ;
2310 template FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>>::FactorizationParser( const FactorizationParser<FactorizationSymbol,
2311                                                                                                           FactorizationValue<BigInt>> & ) ;
2312 template FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>> &
2313          FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>>::operator=(  const FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>> & ) ;
2314 template FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>>::FactorizationParser() ;
2315 template FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>>::~FactorizationParser() ;
2316 template FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>>::FactorizationParser( const FactorizationParser<FactorizationSymbol,
2317                                                                                                           FactorizationValue<ppuint>> & ) ;
2318 template FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>> &
2319          FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>>::operator=(  const FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>> & ) ;
2320 
2321