1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 #include <cstdlib>
42 #include <iostream>
43 #include <new>
44 #include <limits>
45 #include <cmath>
46 #include <complex>
47 #include <fstream>
48 #include <sstream>
49 #include <vector>
50 #include <string>
51 #include <algorithm>
52 #include <stdexcept>
53 #include <cassert>
54 #include <cstring>
55
56 using namespace std ;
57
58
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"
68
69
70
71
72
73
74 #include "Primpoly.h"
75 #include "ppArith.h"
76 #include "ppBigInt.h"
77 #include "ppOperationCount.h"
78 #include "ppFactor.h"
79 #include "ppPolynomial.h"
80 #include "ppParser.h"
81 #include "ppUnitTest.h"
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
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
110
111
112
113
114
115
116
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
130
131
132
133
134
135
136
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
149
150
151
152
153
154
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
170
171
172
173
174
175
176
177
178
179 template < typename SymbolType, typename ValueType >
180 Symbol< SymbolType, ValueType > & Symbol< SymbolType, ValueType >::operator=( const Symbol< SymbolType, ValueType > & s )
181 {
182
183 if (this == &s)
184 return *this ;
185
186 type_ = s.type_ ;
187 value_ = s.value_ ;
188 state_ = s.state_ ;
189
190
191 return *this ;
192 }
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208 ActionState::ActionState()
209 : action_( Action::Error )
210 , state_( 0 )
211 {
212 }
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227 ActionState::ActionState( Action type, int state )
228 : action_( type )
229 , state_( state )
230 {
231 }
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246 ActionState::ActionState( const ActionState & as )
247 : action_( as.action_ )
248 , state_( as.state_ )
249 {
250 }
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265 ActionState & ActionState::operator=( const ActionState & as )
266 {
267
268 if (this == &as)
269 return *this ;
270
271 action_ = as.action_ ;
272 state_ = as.state_ ;
273
274
275 return *this ;
276 }
277
278
279
280
281
282
283
284
285
286
287
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
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325 template < typename SymbolType, typename ValueType >
326 Parser< SymbolType, ValueType >::Parser()
327 : input_stack_()
328 , parse_stack_()
329 , num_states_ ( 0 )
330 , num_productions__ ( 0 )
331 , num_terminals_ ( 0 )
332 , num_non_terminals_ ( 0 )
333 {
334 }
335
336
337
338
339
340
341
342
343
344
345
346
347
348 template < typename SymbolType, typename ValueType >
349 Parser< SymbolType, ValueType >::~Parser()
350 {
351
352 }
353
354
355
356
357
358
359
360
361
362
363
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
377
378
379
380
381
382
383
384
385
386
387 template < typename SymbolType, typename ValueType >
388 Parser< SymbolType, ValueType > & Parser< SymbolType, ValueType >::operator=( const Parser & Parser )
389 {
390
391 if (this == &Parser)
392 return *this ;
393
394 input_stack_ = Parser.input_stack_ ;
395 parse_stack_ = Parser.parse_stack_ ;
396
397
398 return *this ;
399 }
400
401
402
403
404
405
406
407
408
409
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
420 ActionState as( actionType, actionState ) ;
421
422
423 action_table_[ static_cast<int>( state ) ].resize( num_terminals_ ) ;
424
425
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
440
441
442
443
444
445
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
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
470
471
472
473
474
475
476
477
478
479 template < typename SymbolType, typename ValueType >
480 void Parser< SymbolType, ValueType >::insertProduction( int prodNum, SymbolType nonTerm, int rhsLength )
481 {
482
483 production_[ prodNum ].type_ = nonTerm ;
484 production_[ prodNum ].state_ = rhsLength ;
485 }
486
487
488
489
490
491
492
493
494
495
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
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557 template< typename SymbolType, typename ValueType >
558 ValueType Parser< SymbolType, ValueType >::parse( string sentence )
559 {
560 ValueType retVal ;
561
562
563 if (sentence.size() == 0)
564 return retVal ;
565
566
567 tokenize( sentence ) ;
568
569
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
580 while( input_stack_.size() > 0 )
581 {
582
583 int currentState = parse_stack_.back().state_ ;
584 Symbol< SymbolType, ValueType > lookahead = input_stack_.back() ;
585
586
587
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
608 ActionState actionState = action_table_[ currentState ][ static_cast<int>( lookahead.type_ ) ] ;
609
610
611 #ifdef DEBUG_PP_PARSER
612 cout << endl << actionState << endl ;
613 #endif
614
615 try
616 {
617
618 switch( actionState.action_ )
619 {
620 case Action::Shift:
621 {
622
623 if (input_stack_.size() == 0)
624
625 throw ParserError( "Wanted to shift another token, but the parse stack is empty.", __FILE__, __LINE__ ) ;
626
627 input_stack_.pop_back() ;
628
629
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
640 int productionNum = actionState.state_ ;
641
642
643 SymbolType prodNonTerm = production_[ productionNum ].type_ ;
644
645
646 int rhsProductionLength = production_[ productionNum ].state_ ;
647
648
649
650
651
652
653 Symbol< SymbolType, ValueType > A( prodNonTerm, 0 ) ;
654 int topIndex = static_cast<int>( parse_stack_.size() ) - 1 ;
655 int i = 0 ;
656
657
658
659
660 syntaxDirectedTranslation( productionNum, topIndex, A ) ;
661
662
663
664
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
673 currentState = parse_stack_.back().state_ ;
674 int gotoState = goto_table_[ static_cast<int>( currentState ) ][ static_cast<int>( prodNonTerm ) ] ;
675
676
677 A.state_ = gotoState ;
678 parse_stack_.push_back( A ) ;
679 }
680 break ;
681
682
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
698
699
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
710 return retVal ;
711 }
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 }
722
723
724 return retVal ;
725 }
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746 PolyValue & PolyValue::operator=( const PolyValue & v )
747 {
748
749 if (this == &v)
750 return *this ;
751
752 scalar_ = v.scalar_ ;
753 f_ = v.f_ ;
754
755
756 return *this ;
757 }
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772 ostream & operator<<( ostream & out, const PolyValue & poly )
773 {
774 out << poly.scalar_ << " f( x ) = " ;
775
776
777 Polynomial p( poly.f_ ) ;
778 out << p ;
779
780 return out ;
781 }
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796 PolyValue::PolyValue()
797 : scalar_( 0 )
798 , f_(1, 0)
799 {
800 }
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815 PolyValue::PolyValue( const PolyValue & v )
816 : scalar_( v.scalar_ )
817 , f_( v.f_ )
818 {
819 }
820
821
822
823
824
825
826
827
828
829
830
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
847 initializeTables() ;
848 }
849
850
851
852
853
854
855
856
857
858
859
860
861
862 template < typename SymbolType, typename ValueType >
863 PolyParser< SymbolType, ValueType >::~PolyParser()
864 {
865
866 }
867
868
869
870
871
872
873
874
875
876
877
878
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
892
893
894
895
896
897
898
899
900
901
902 template < typename SymbolType, typename ValueType >
903 PolyParser< SymbolType, ValueType > & PolyParser< SymbolType, ValueType >::operator=( const PolyParser & PolyParser )
904 {
905
906 if (this == &PolyParser)
907 return *this ;
908
909 input_stack_ = PolyParser.input_stack_ ;
910 parse_stack_ = PolyParser.parse_stack_ ;
911
912
913 return *this ;
914 }
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930 template < typename SymbolType, typename ValueType >
931 void PolyParser< SymbolType, ValueType >::
932 initializeTables()
933 {
934
935 num_states_ = 15 ;
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 ;
939
940
941 action_table_.resize( num_states_ ) ;
942
943
944 goto_table_.resize( num_states_ ) ;
945
946
947
948 production_.resize( num_productions__ + 1 ) ;
949
950 error_message_.resize( num_states_ ) ;
951
952 TODO
953 try
954 {
955
956
957
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
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
1031
1032
1033
1034 insertProduction( 1, PolySymbol::S, 2 ) ;
1035 insertProduction( 2, PolySymbol::Mod, 2 ) ;
1036 insertProduction( 3, PolySymbol::Mod, 0 ) ;
1037 insertProduction( 4, PolySymbol::Poly, 3 ) ;
1038 insertProduction( 5, PolySymbol::Poly, 1 ) ;
1039 insertProduction( 6, PolySymbol::Term, 2 ) ;
1040 insertProduction( 7, PolySymbol::Multiplier, 1 ) ;
1041 insertProduction( 8, PolySymbol::Multiplier, 0 ) ;
1042 insertProduction( 9, PolySymbol::Power, 1 ) ;
1043 insertProduction( 10, PolySymbol::Power, 3 ) ;
1044 insertProduction( 11, PolySymbol::Power, 0 ) ;
1045
1046
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
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
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
1095 unsigned int pos = 0 ;
1096
1097 bool minusSignDetected = false ;
1098
1099
1100 input_stack_.clear() ;
1101
1102 #ifdef DEBUG_PP_PARSER
1103 cout << "Lexical analyzer: sentence = " << sentence << endl ;
1104 #endif
1105
1106
1107 while( pos < sentence.length() )
1108 {
1109
1110 while (pos < sentence.length() && iswspace( sentence[ pos ]))
1111 ++pos ;
1112
1113
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
1123
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 ;
1133 }
1134
1135 tok.type_ = PolySymbol::Integer ;
1136 tok.value_.scalar_ = num ;
1137
1138
1139 if (minusSignDetected)
1140 {
1141
1142
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
1148
1149
1150
1151 }
1152 }
1153
1154 else
1155 {
1156 tok.value_.scalar_ = 0 ;
1157
1158
1159 switch( sentence[ pos ] )
1160 {
1161 case '+' :
1162 tok.type_ = PolySymbol::Plus ;
1163 break ;
1164
1165
1166
1167
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
1188
1189 ostringstream os ;
1190 os << "Error: Unexpected symbol in lexical analyzer" << sentence[ pos ] ;
1191 throw ParserError( os.str() ) ;
1192 }
1193
1194
1195 ++pos ;
1196 }
1197
1198
1199 input_stack_.push_back( tok ) ;
1200
1201 #ifdef DEBUG_PP_PARSER
1202 cout << " Push token " << tok << endl ;
1203 #endif
1204
1205 }
1206
1207
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
1218 reverse( input_stack_.begin(), input_stack_.end() ) ;
1219 }
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
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
1263 case 1:
1264 {
1265
1266
1267
1268
1269
1270
1271
1272 symbol.value_.f_ = parse_stack_[ topIndex - 1 ].value_.f_ ;
1273 symbol.value_.scalar_ = parse_stack_[ topIndex ].value_.scalar_ ;
1274
1275
1276 #ifdef DEBUG_PP_PARSER
1277 cout << " Reduce (S -> POLY MOD)" << " Value = " << symbol.value_ << endl ;
1278 #endif
1279 }
1280 break ;
1281
1282
1283 case 2:
1284 {
1285
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
1295 case 3:
1296 {
1297
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
1307 case 4:
1308 {
1309
1310
1311
1312 int degPoly = static_cast<int>(parse_stack_[ topIndex - 2 ].value_.f_.size()) - 1 ;
1313
1314
1315 int degTerm = static_cast<int>(parse_stack_[ topIndex ].value_.f_.size()) - 1 ;
1316
1317
1318 symbol.value_.f_ = parse_stack_[ topIndex - 2 ].value_.f_ ;
1319
1320
1321 symbol.value_.f_.resize( degTerm > degPoly ? degTerm+1 : degPoly+1, 0 ) ;
1322
1323
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
1337 case 5:
1338 {
1339
1340 int degPoly = static_cast<int>(symbol.value_.f_.size()) - 1 ;
1341
1342
1343 int degTerm = static_cast<int>(parse_stack_[ topIndex ].value_.f_.size()) - 1 ;
1344
1345
1346 symbol.value_.f_.resize( degTerm > degPoly ? degTerm+1 : degPoly+1, 0 ) ;
1347
1348
1349 for (int i = static_cast<int>(symbol.value_.f_.size()) - 1 ; i >= 0 ; --i)
1350 symbol.value_.f_[ i ] = 0 ;
1351
1352
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
1363 case 6:
1364 {
1365
1366 unsigned int degPower = static_cast<int>( parse_stack_[ topIndex ].value_.scalar_ ) ;
1367
1368
1369 symbol.value_.f_.resize( degPower + 1, 0 ) ;
1370
1371
1372 for (int i = static_cast<int>(symbol.value_.f_.size()) - 1 ; i >= 0 ; --i)
1373 symbol.value_.f_[ i ] = 0 ;
1374
1375
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
1386 case 7:
1387 {
1388
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
1398 case 8:
1399 {
1400
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
1410 case 9:
1411 {
1412
1413
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
1423 case 10:
1424 {
1425
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
1435 case 11:
1436 {
1437
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
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467 template<typename IntType>
1468 FactorizationValue<IntType> & FactorizationValue<IntType>::operator=( const FactorizationValue<IntType> & v )
1469 {
1470
1471 if (this == &v)
1472 return *this ;
1473
1474 numberString_ = v.numberString_ ;
1475 factor_ = v.factor_ ;
1476
1477
1478 return *this ;
1479 }
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496 template<typename IntType>
1497 IntType FactorizationValue<IntType>::numberStringToInteger( const string & numberString )
1498 {
1499
1500 IntType u ;
1501
1502
1503 istringstream is ;
1504 is.clear() ;
1505 is.str( numberString ) ;
1506
1507
1508
1509
1510 is >> u ;
1511
1512 return u ;
1513 }
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528 template<typename IntType>
1529 FactorizationValue<IntType>::FactorizationValue()
1530 : numberString_ { "" }
1531 , factor_ { 0 }
1532 {
1533 }
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
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
1561
1562
1563
1564
1565
1566
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
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590 template < typename SymbolType, typename ValueType >
1591 FactorizationParser< SymbolType, ValueType >::FactorizationParser()
1592 : Parser<SymbolType,ValueType>()
1593 {
1594
1595 initializeTables() ;
1596 }
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611 template < typename SymbolType, typename ValueType >
1612 FactorizationParser< SymbolType, ValueType >::~FactorizationParser()
1613 {
1614
1615 }
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
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
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650 template < typename SymbolType, typename ValueType >
1651 FactorizationParser< SymbolType, ValueType > & FactorizationParser< SymbolType, ValueType >::operator=( const FactorizationParser & FactorizationParser )
1652 {
1653
1654 if (this == &FactorizationParser)
1655 return *this ;
1656
1657 input_stack_ = FactorizationParser.input_stack_ ;
1658 parse_stack_ = FactorizationParser.parse_stack_ ;
1659
1660
1661 return *this ;
1662 }
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678 template < typename SymbolType, typename ValueType >
1679 void FactorizationParser<SymbolType,ValueType>::initializeTables()
1680 {
1681
1682 num_states_ = 16 ;
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 ;
1686
1687
1688 action_table_.resize( num_states_ ) ;
1689
1690
1691 goto_table_.resize( num_states_ ) ;
1692
1693
1694
1695 production_.resize( num_productions__ + 1 ) ;
1696
1697 error_message_.resize( num_states_ ) ;
1698
1699 TODO
1700 try
1701 {
1702
1703
1704
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
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
1759
1760
1761
1762 insertProduction( 1, FactorizationSymbol::S, 3 ) ;
1763 insertProduction( 2, FactorizationSymbol::Factorization, 3 ) ;
1764 insertProduction( 3, FactorizationSymbol::Factorization, 1 ) ;
1765 insertProduction( 4, FactorizationSymbol::Factor, 3 ) ;
1766 insertProduction( 5, FactorizationSymbol::Factor, 1 ) ;
1767 insertProduction( 6, FactorizationSymbol::BigInteger, 3 ) ;
1768 insertProduction( 7, FactorizationSymbol::BigInteger, 1 ) ;
1769
1770
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
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
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
1819 unsigned int pos = 0 ;
1820
1821
1822 input_stack_.clear() ;
1823
1824
1825 while( pos < sentence.length() )
1826 {
1827
1828 while (pos < sentence.length() && iswspace( sentence[ pos ]))
1829 ++pos ;
1830
1831 #ifdef DEBUG_PP_PARSER
1832 cout << "tokenize: sentence[ " << pos << " ] = " << sentence[ pos ] << endl ;
1833 #endif
1834
1835
1836 if (pos < sentence.size() && isdigit( sentence[ pos ]))
1837 {
1838 string numberString = "" ;
1839
1840
1841 while( pos < sentence.size() && isdigit( sentence[ pos ]))
1842 {
1843 numberString += sentence[ pos ] ;
1844 ++pos ;
1845 }
1846
1847 tok.type_ = FactorizationSymbol::Integer ;
1848 tok.value_.numberString_ = numberString ;
1849 }
1850
1851 else
1852 {
1853 tok.value_.numberString_ = "" ;
1854
1855
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
1872
1873 ostringstream os ;
1874 os << "Error: Unexpected symbol in lexical analyzer" << sentence[ pos ] ;
1875 throw ParserError( os.str() ) ;
1876 }
1877
1878 ++pos ;
1879 }
1880
1881
1882 input_stack_.push_back( tok ) ;
1883
1884 #ifdef DEBUG_PP_PARSER
1885 cout << " Push token " << tok << endl ;
1886 #endif
1887
1888 }
1889
1890
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
1901 reverse( input_stack_.begin(), input_stack_.end() ) ;
1902 }
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
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
1946 case 1:
1947 {
1948
1949
1950
1951
1952
1953 symbol.value_.factor_ = parse_stack_[ topIndex ].value_.factor_ ;
1954 symbol.value_.numberString_ = parse_stack_[ topIndex - 2 ].value_.numberString_ ;
1955
1956 #ifdef DEBUG_PP_PARSER
1957 cout << " Reduce (S -> INTEGER INTEGER FACTORIZATION)" << " Value = " << symbol << endl ;
1958 #endif
1959 }
1960 break ;
1961
1962
1963 case 2:
1964 {
1965
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
1976 case 3:
1977 {
1978
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
1989 case 4:
1990 {
1991
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
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
2007 case 5:
2008 {
2009
2010 auto primeFactor = ValueType::numberStringToInteger( parse_stack_[ topIndex ].value_.numberString_ ) ;
2011 ValueType value( primeFactor, 1 ) ;
2012
2013
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
2024 case 6:
2025 {
2026
2027
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
2037 case 7:
2038 {
2039
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
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
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
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
2095 for (int input_arg_index = 0 ; input_arg_index < argc ;
2096 ++input_arg_index)
2097 {
2098
2099 input_arg_string = argv[ input_arg_index ] ;
2100
2101
2102 if (input_arg_string[ 0 ] == '-' && input_arg_string[ 1 ] != '\0')
2103 {
2104
2105 for (option_ptr = input_arg_string + 1 ; *option_ptr != '\0' ;
2106 ++option_ptr)
2107 {
2108 switch( *option_ptr )
2109 {
2110
2111 case 't':
2112 test_polynomial_for_primitivity_ = true ;
2113 break ;
2114
2115
2116 case 'a':
2117 list_all_primitive_polynomials_ = true ;
2118 break ;
2119
2120
2121 case 's':
2122 print_operation_count_ = true ;
2123 break ;
2124
2125
2126 case 'h':
2127 case 'H':
2128 print_help_ = true ;
2129 break ;
2130
2131
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
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
2158
2159 if (test_polynomial_for_primitivity_)
2160 {
2161 string testPoly ;
2162 testPoly.assign( arg_string[ 1 ] ) ;
2163 test_polynomial_ = testPoly ;
2164
2165 n = test_polynomial_.deg() ;
2166 p = test_polynomial_.modulus() ;
2167 }
2168
2169
2170
2171
2172 else if (num_arg == MAX_NUM_COMMAND_LINE_ARGS)
2173 {
2174 TODO
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
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
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
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229 template< typename SymbolType >
2230 string enumToString( const SymbolType & st )
2231 {
2232 ostringstream os ;
2233
2234
2235
2236 os << static_cast<int>( st ) ;
2237 return os.str() ;
2238 }
2239
2240
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
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
2258
2259
2260
2261
2262
2263
2264
2265
2266
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
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
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
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
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