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.3 - A Program for Computing Primitive Polynomials.
17| Copyright (C) 1999-2024 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
56using 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.hpp" // Global functions.
75#include "ppArith.hpp" // Basic arithmetic functions.
76#include "ppBigInt.hpp" // Arbitrary precision integer arithmetic.
77#include "ppOperationCount.hpp" // OperationCount collection for factoring and poly finding.
78#include "ppFactor.hpp" // Prime factorization and Euler Phi.
79#include "ppPolynomial.hpp" // Polynomial operations and mod polynomial operations.
80#include "ppParser.hpp" // Parsing of polynomials and I/O services.
81#include "ppUnitTest.hpp" // 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
100template < typename SymbolType, typename ValueType >
101Symbol< 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
120template < typename SymbolType, typename ValueType >
121Symbol< 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
140template < typename SymbolType, typename ValueType >
141Symbol< 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
158template < typename SymbolType, typename ValueType >
159Symbol< 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
179template < typename SymbolType, typename ValueType >
180Symbol< 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
208ActionState::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
227ActionState::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
246ActionState::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
265ActionState & 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
291ostream & 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
325template < typename SymbolType, typename ValueType >
326Parser< 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
348template < typename SymbolType, typename ValueType >
349Parser< 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
367template < typename SymbolType, typename ValueType >
368Parser< 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
387template < typename SymbolType, typename ValueType >
388Parser< 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
413template < typename SymbolType, typename ValueType >
414void 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
449template < typename SymbolType, typename ValueType >
450void 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
479template < typename SymbolType, typename ValueType >
480void 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
499template < typename SymbolType, typename ValueType >
500void 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
557template< typename SymbolType, typename ValueType >
558ValueType 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
746PolyValue & 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
772ostream & 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
796PolyValue::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
815PolyValue::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
834template < typename SymbolType, typename ValueType >
835PolyParser< 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
862template < typename SymbolType, typename ValueType >
863PolyParser< 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
882template < typename SymbolType, typename ValueType >
883PolyParser<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
902template < typename SymbolType, typename ValueType >
903PolyParser< 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
930template < 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
1089template < typename SymbolType, typename ValueType >
1090void 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
1256template <typename SymbolType, typename ValueType>
1257void 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
1467template<typename IntType>
1468FactorizationValue<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
1496template<typename IntType>
1497IntType 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
1528template<typename IntType>
1529FactorizationValue<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
1548template<typename IntType>
1549FactorizationValue<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
1570template<typename IntType>
1571FactorizationValue<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
1590template < typename SymbolType, typename ValueType >
1591FactorizationParser< 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
1611template < typename SymbolType, typename ValueType >
1612FactorizationParser< 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
1630template < typename SymbolType, typename ValueType >
1631FactorizationParser<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
1650template < typename SymbolType, typename ValueType >
1651FactorizationParser< 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
1678template < typename SymbolType, typename ValueType >
1679void 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
1813template <typename SymbolType, typename ValueType>
1814void 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
1939template <typename SymbolType, typename ValueType>
1940void 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
2073template < typename SymbolType, typename PolyValueType >
2074void 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
2229template< typename SymbolType >
2230string 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.
2241template<>
2242string 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.
2249template<>
2250string 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.
2267template PolyValue Parser<PolySymbol, PolyValue>::parse( string ) ;
2268template FactorizationValue<BigInt> Parser<FactorizationSymbol, FactorizationValue<BigInt>>::parse( string ) ;
2269template FactorizationValue<ppuint> Parser<FactorizationSymbol, FactorizationValue<ppuint>>::parse( string ) ;
2270
2271// Generate all symbols for the polynomial grammar.
2272template Symbol<PolySymbol, PolyValue>::Symbol( PolySymbol, int ) ;
2273template Symbol<PolySymbol, PolyValue>::Symbol( PolySymbol, int, PolyValue ) ;
2274template Symbol<PolySymbol, PolyValue>::~Symbol() ;
2275template Symbol<PolySymbol, PolyValue>::Symbol( const Symbol< PolySymbol, PolyValue > & ) ;
2276template Symbol<PolySymbol, PolyValue> & Symbol<PolySymbol, PolyValue>::operator=( const Symbol< PolySymbol, PolyValue > & ) ;
2277
2278// Generate all the symbols for the factorization grammar.
2279template FactorizationValue<BigInt>::FactorizationValue() ;
2280template FactorizationValue<BigInt>::FactorizationValue( const FactorizationValue<BigInt> & ) ;
2281template FactorizationValue<BigInt> & FactorizationValue<BigInt>::operator=( const FactorizationValue<BigInt> & ) ;
2282template FactorizationValue<ppuint>::FactorizationValue() ;
2283template FactorizationValue<ppuint>::FactorizationValue( const FactorizationValue<ppuint> & ) ;
2284template FactorizationValue<ppuint> & FactorizationValue<ppuint>::operator=( const FactorizationValue<ppuint> & ) ;
2285
2286template Symbol<FactorizationSymbol, FactorizationValue<BigInt>>::Symbol( FactorizationSymbol, int ) ;
2287template Symbol<FactorizationSymbol, FactorizationValue<BigInt>>::Symbol( FactorizationSymbol, int, FactorizationValue<BigInt> ) ;
2288template Symbol<FactorizationSymbol, FactorizationValue<BigInt>>::~Symbol() ;
2289template Symbol<FactorizationSymbol, FactorizationValue<BigInt>>::Symbol( const Symbol<FactorizationSymbol, FactorizationValue<BigInt>> & ) ;
2290template Symbol<FactorizationSymbol, FactorizationValue<BigInt>> &
2291 Symbol<FactorizationSymbol, FactorizationValue<BigInt>>::operator=( const Symbol<FactorizationSymbol, FactorizationValue<BigInt>> & ) ;
2292template Symbol<FactorizationSymbol, FactorizationValue<ppuint>>::Symbol( FactorizationSymbol, int ) ;
2293template Symbol<FactorizationSymbol, FactorizationValue<ppuint>>::Symbol( FactorizationSymbol, int, FactorizationValue<ppuint> ) ;
2294template Symbol<FactorizationSymbol, FactorizationValue<ppuint>>::~Symbol() ;
2295template Symbol<FactorizationSymbol, FactorizationValue<ppuint>>::Symbol( const Symbol<FactorizationSymbol, FactorizationValue<ppuint>> & ) ;
2296template 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.
2300template PolyParser<PolySymbol, PolyValue>::PolyParser() ;
2301template PolyParser<PolySymbol, PolyValue>::~PolyParser() ;
2302template PolyParser<PolySymbol, PolyValue>::PolyParser( const PolyParser<PolySymbol, PolyValue> & ) ;
2303template PolyParser<PolySymbol, PolyValue> & PolyParser<PolySymbol, PolyValue>::operator=( const PolyParser<PolySymbol, PolyValue> & ) ;
2304
2305template void PolyParser<PolySymbol, PolyValue>::parseCommandLine( int, const char * argv[] ) ;
2306
2307// Generate all child class member functions for the factorization grammar.
2308template FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>>::FactorizationParser() ;
2309template FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>>::~FactorizationParser() ;
2310template FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>>::FactorizationParser( const FactorizationParser<FactorizationSymbol,
2311 FactorizationValue<BigInt>> & ) ;
2312template FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>> &
2313 FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>>::operator=( const FactorizationParser<FactorizationSymbol, FactorizationValue<BigInt>> & ) ;
2314template FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>>::FactorizationParser() ;
2315template FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>>::~FactorizationParser() ;
2316template FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>>::FactorizationParser( const FactorizationParser<FactorizationSymbol,
2317 FactorizationValue<ppuint>> & ) ;
2318template FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>> &
2319 FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>>::operator=( const FactorizationParser<FactorizationSymbol, FactorizationValue<ppuint>> & ) ;