1 #include "parser.h"
2 #include <stdio.h>
3 #include <assert.h>
4 #include "printer.h"
5 #include "field_rationals.h"
6 #include "field_zmodpz.h"
7 #include <vector>
8 #include <string>
9 #include "log.h"
10
11 using namespace std;
12
13
variableIndexToString(int i)14 static string variableIndexToString(int i)
15 {
16 // fprintf(Stderr,"I:%i\n",i);
17 static char s[4];
18 if(i>=0 && i<26)sprintf(s,"%c",i+'a');
19 else if(i>=26 && i<52)sprintf(s,"%c",i+'A'-26);
20 else assert(0);
21 return string(s);
22 }
23
24
25 //--------------------------------------------------
26 // Parser
27 //--------------------------------------------------
28
parserError(const char * expected,char c)29 void Parser::parserError(const char *expected, char c)
30 {
31 fprintf(Stderr,"PARSER ERROR: Expected: \"%s\" Found: \"%c\"\n",expected,c);
32 }
33
34
35 //--------------------------------------------------
36 // CharacterBasedParser
37 //--------------------------------------------------
38
39
40
azAZ(Field const & f,int n)41 PolynomialRing CharacterBasedParser::azAZ(Field const &f, int n)
42 {
43 assert(n<=52);
44 vector<string> na(n);
45 for(int i=0;i<n;i++)
46 {
47 na[i]=variableIndexToString(i);
48 }
49 return PolynomialRing(f,na);
50 }
51
nextNonBlank()52 int CharacterBasedParser::nextNonBlank()
53 {
54 int c=getChar();
55
56 while(c!=0 && (c=='\t' || c==' ' || c=='\n' || c==13 || c==10))c=getChar();
57
58 return c;
59 }
60
61
nextNonBlankDoNotGet()62 int CharacterBasedParser::nextNonBlankDoNotGet()
63 {
64 int k=nextNonBlank();
65 ungetChar(k);
66 return k;
67 }
68
69
70
isLeftBracket(int c)71 bool CharacterBasedParser::isLeftBracket(int c)
72 {
73 return c=='(' || c=='[' || c=='{';
74 }
75
76
isRightBracket(int c)77 bool CharacterBasedParser::isRightBracket(int c)
78 {
79 return c==')' || c==']' || c=='}';
80 }
81
82
parseChar()83 int CharacterBasedParser::parseChar()
84 {
85 return getChar();
86 }
87
88
parseFieldElementFromInteger(Field const & f)89 FieldElement CharacterBasedParser::parseFieldElementFromInteger(Field const &f)
90 {
91 FieldElement ret=f.zHomomorphism(0);
92 int c=getChar();
93
94 while(c!=0 && (c=='\t' || c==' ' || c=='\n' || c==10 || c==13))c=getChar();
95 if(c=='-')return f.zHomomorphism(-1)*parseFieldElementFromInteger(f);
96 while(c!=0)
97 {
98 if(c>='0' && c<='9')
99 {
100 ret=ret*f.zHomomorphism(10)+f.zHomomorphism(c-'0');
101 c=getChar();
102 }
103 else
104 break;
105 }
106 ungetChar(c);
107
108 return ret;
109 }
110
parseInt()111 int CharacterBasedParser::parseInt()
112 {
113 int ret=0;
114 int c=getChar();
115
116 int numberOfDigits=0;
117
118 while(c!=0 && (c=='\t' || c==' ' || c=='\n' || c==10 || c==13))c=getChar();
119 if(c=='-')return -parseInt();
120 if(c=='(')//allow parentheses for Laurent exponents
121 {
122 ungetChar(c);
123 IntegerVector v=parseIntegerVector();
124 assert(v.size()==1);
125 return v[0];
126 }
127 while(c!=0)
128 {
129 if(c>='0' && c<='9')
130 {
131 numberOfDigits++;
132 assert(numberOfDigits<10);
133 ret=ret*10+(c-'0');
134 c=getChar();
135 }
136 else
137 break;
138 }
139 ungetChar(c);
140
141 return ret;
142 }
143
144
parseFloat()145 double CharacterBasedParser::parseFloat()
146 {
147 double ret=0;
148 static char s[64];
149 int i=0;
150
151 int c=nextNonBlank();
152 while(i<64 && ((c>='0' && c<='9') || c=='.' || c=='-') )
153 {
154 s[i++]=c;
155 c=getChar();
156 }
157 assert(i<64);
158 s[i]=0;
159
160 ungetChar(c);
161
162 sscanf(s,"%lf",&ret); //does this work? Are we reading floats or doubles?
163 return ret;
164 }
165
166
parseComplexNumber()167 ComplexNumber CharacterBasedParser::parseComplexNumber()
168 {
169 FloatVector v=parseFloatVector();
170 assert(v.size()==2);
171
172 return ComplexNumber(v[0],v[1]);
173 }
174
175
parseFieldElement(Field const & f)176 FieldElement CharacterBasedParser::parseFieldElement(Field const &f)
177 {
178 // return FieldElement(parseInt());
179 FieldElement a=parseFieldElementFromInteger(f);
180 int c=nextNonBlank();
181 FieldElement b=f.zHomomorphism(1);
182 if(c=='/')
183 b=parseFieldElementFromInteger(f);
184 else
185 ungetChar(c);
186
187 // FieldElement A=Field::staticZHomomorphism(a);
188 // FieldElement B=Field::staticZHomomorphism(b);
189
190 a*=b.inverse();
191
192 return a;
193 }
194
195
isVariable(int c)196 bool CharacterBasedParser::isVariable(int c)
197 {
198 return (c>='a' && c<='z') || (c>='A' && c<='Z');
199 }
200
201
isDigit(int c)202 bool CharacterBasedParser::isDigit(int c)
203 {
204 return (c>='0' && c<='9');
205 }
206
207
variableIndex(int c)208 int CharacterBasedParser::variableIndex(int c)
209 {
210 if(c>='a' && c<='z')return c-'a';
211 if(c>='A' && c<='Z')return c-'A'+26;
212 assert(0);
213 return 0;
214 }
215
isVariableCharacter(int c)216 static bool isVariableCharacter(int c)
217 {
218 return ((c>='a' && c<='z')||(c>='A' && c<='Z')||(c>='0' && c<='9')||(c=='_' || c==']' || c=='['));
219 }
220
parseMonomial(PolynomialRing const & r)221 Monomial CharacterBasedParser::parseMonomial(PolynomialRing const &r)
222 {
223 // fprintf(Stderr,"Atest\n");
224 int dimension=r.getNumberOfVariables();
225 // fprintf(Stderr,"Dim%i\n",dimension);
226 /* Parses a monomial without spaces and without sign */
227
228 // Monomial m(IntegerVector((dimension==-1)?0:dimension));
229 Monomial m(r,IntegerVector(dimension));
230 IntegerVector &ret=m.exponent;
231
232 int c=nextNonBlank();
233 // int c=getChar();
234
235 if(c=='1')return m;
236
237 while(c!=0 && (c=='\t' || c==' ' || c=='\n' || c==10 || c==13))c=getChar();
238 while(c!=0)
239 {
240 string name;
241 while(isVariableCharacter(c))
242 {
243 name+=c;
244 if(r.variableIndex(name)!=-1)break;
245 c=getChar();
246 }
247
248 if(r.variableIndex(name)!=-1)
249 {
250 //fprintf(Stderr,"NAME:%s\n",name.c_str());
251 int index=r.variableIndex(name);
252 int exponent=1;
253 if(dimension==-1)
254 ret.grow(index+1);
255 else
256 assert(index<dimension);
257 // c=getChar();
258 c=nextNonBlank();
259 if(isDigit(c)) // This makes parsing of Singular polynomials possible
260 {
261 ungetChar(c);
262 c='^';
263 }
264 if(c=='^')
265 {
266 exponent=parseInt();
267 //c=getChar();
268 c=nextNonBlank();
269 }
270 // printf("Index:%i, Exponent:%i\n",index,exponent);
271 ret[index]+=exponent;
272 }
273 else if(name.size())
274 {
275 fprintf(Stderr,"Unknown variable:%s\n",name.c_str());
276 assert(0);
277 }
278 else if(c=='*')
279 {
280 // c=getChar();
281 c=nextNonBlank();
282 }
283 else break;
284 }
285 ungetChar(c);
286
287
288 // fprintf(Stderr,"test\n");
289
290 return m;
291 }
292
293
parseTerm(PolynomialRing const & r)294 Term CharacterBasedParser::parseTerm(PolynomialRing const &r)
295 {
296 // fprintf(Stderr,"testC\n");
297 // fprintf(Stderr,"parseTerm - Begin\n");
298 int c=nextNonBlank();
299 if(c=='-')
300 {
301 c=nextNonBlank();
302 ungetChar(c);
303 FieldElement k(r.getField());
304 k=r.getField().zHomomorphism(1);
305 // k=k.one();
306 if(isDigit(c))
307 {
308 k=parseFieldElement(r.getField());
309 }
310 Monomial m=parseMonomial(r);
311 // fprintf(Stderr,"parseTerm - End\n");
312 return Term(-k,m);
313 }
314 else
315 {
316 ungetChar(c);
317 FieldElement k(r.getField());
318 // fprintf(Stderr,"A\n");
319 k=r.getField().zHomomorphism(1);
320 // k=k.one();
321 //fprintf(Stderr,"B\n");
322 if(isDigit(c))
323 {
324 k=parseFieldElement(r.getField());
325 }
326 Monomial m=parseMonomial(r);
327 // fprintf(Stderr,"parseTerm - End\n");
328 return Term(k,m);
329 }
330
331 FieldElement k=parseFieldElement(r.getField());
332 Monomial m=parseMonomial(r);
333
334 // fprintf(Stderr,"parseTerm :");
335 // AsciiPrinter(Stderr).printFieldElement(c);
336 // AsciiPrinter(Stderr).printMonomial(m);
337
338 // fprintf(Stderr,"parseTerm - End\n");
339 return Term(k,m);
340 }
341
342
parsePolynomial(PolynomialRing const & r)343 Polynomial CharacterBasedParser::parsePolynomial(PolynomialRing const &r)
344 {
345 //fprintf(Stderr,"%i\n",r.getNumberOfVariables());
346 // fprintf(Stderr,"parsePolynomial - Begin\n");
347 bool first=true;
348 Polynomial p(r);
349 Monomial firstMonomial(r);
350
351 // fprintf(Stderr,"parsePolynomialBegin\n");
352
353 while(true)
354 {
355 // fprintf(Stderr,"test1\n");
356 int c=nextNonBlank();
357
358 // fprintf(Stderr,"test2\n");
359 ungetChar(c);
360
361 if(isDigit(c)|| c=='+' || c=='-' || isVariable(c))
362 {
363 // fprintf(Stderr,"test3\n");
364 if(c=='+')nextNonBlank();
365 Term t=parseTerm(r);
366 if(!t.c.isZero())
367 {
368 if(first)
369 {
370 firstMonomial=t.m;
371 first=false;
372 }
373 // fprintf(Stderr,"test4\n");
374 Polynomial q=Polynomial(t);
375 // AsciiPrinter(Stderr).printPolynomial(q);
376 //if(q.getNumberOfVariables()>p.getNumberOfVariables())p.changeNumberOfVariables(q.getNumberOfVariables());
377 //if(p.getNumberOfVariables()>q.getNumberOfVariables())q.changeNumberOfVariables(p.getNumberOfVariables());
378 p+=q;
379 // fprintf(Stderr,"test5\n");
380 }
381 }
382 else
383 break;
384 }
385 // fprintf(Stderr,"parsePolynomialEnd\n");
386 // AsciiPrinter(Stderr).printPolynomial(p);
387 // fprintf(Stderr,"parsePolynomialEnd\n");
388
389 if(!first)
390 {
391 firstMonomial.exponent.resize(p.getNumberOfVariables());
392 p.mark(firstMonomial);
393 //AsciiPrinter(Stderr).printVector(firstMonomial.exponent);
394 }
395
396 //fprintf(Stderr,"parsePolynomial - End\n");
397 return p;
398 }
399
400
parsePolynomialSet(PolynomialRing const & r)401 PolynomialSet CharacterBasedParser::parsePolynomialSet(PolynomialRing const &r)
402 {
403 // fprintf(Stderr,"%i\n",r.getNumberOfVariables());
404 PolynomialSet ret(r);
405 int c=nextNonBlank();
406
407 if(!isLeftBracket(c))
408 {
409 parserError("left bracket",c);
410 assert(0);
411 }
412
413 c=nextNonBlank();
414 if(isRightBracket(c))return ret;
415 ungetChar(c);
416 do
417 {
418 ret.push_back(parsePolynomial(r));
419 }
420 while((c=nextNonBlank())==',');
421 assert(isRightBracket(c));
422
423 return ret;
424 }
425
426
parsePolynomialSetList(PolynomialRing const & r)427 PolynomialSetList CharacterBasedParser::parsePolynomialSetList(PolynomialRing const &r)
428 {
429 PolynomialSetList ret;
430 int c=nextNonBlank();
431
432 assert(isLeftBracket(c));
433 do
434 {
435 ret.push_back(parsePolynomialSet(r));
436 }
437 while((c=nextNonBlank())==',');
438 assert(isRightBracket(c));
439
440 return ret;
441 }
442
443
parseIntegerVector()444 IntegerVector CharacterBasedParser::parseIntegerVector()
445 {
446 list<int> temp;
447 int c=nextNonBlank();
448
449 assert(isLeftBracket(c));
450 do
451 temp.push_back(parseInt());
452 while((c=nextNonBlank())==',');
453 assert(isRightBracket(c));
454
455 IntegerVector ret(temp.size());
456
457 {
458 int j=0;
459 for(list<int>::iterator i=temp.begin();i!=temp.end();i++)
460 ret[j++]=*i;
461 }
462
463 return ret;
464 }
465
466
parseFloatVector()467 FloatVector CharacterBasedParser::parseFloatVector()
468 {
469 list<double> temp;
470 int c=nextNonBlank();
471
472 assert(isLeftBracket(c));
473 do
474 temp.push_back(parseFloat());
475 while((c=nextNonBlank())==',');
476 assert(isRightBracket(c));
477
478 FloatVector ret(temp.size());
479
480 {
481 int j=0;
482 for(list<double>::iterator i=temp.begin();i!=temp.end();i++)
483 ret[j++]=*i;
484 }
485 return ret;
486 }
487
488
parseComplexVector()489 ComplexVector CharacterBasedParser::parseComplexVector()
490 {
491 list<ComplexNumber> temp;
492 int c=nextNonBlank();
493
494 assert(isLeftBracket(c));
495 do
496 temp.push_back(parseComplexNumber());
497 while((c=nextNonBlank())==',');
498 assert(isRightBracket(c));
499
500 ComplexVector ret(temp.size());
501
502 {
503 int j=0;
504 for(list<ComplexNumber>::iterator i=temp.begin();i!=temp.end();i++)
505 ret[j++]=*i;
506 }
507 return ret;
508 }
509
510
parseIntegerVectorList()511 IntegerVectorList CharacterBasedParser::parseIntegerVectorList()
512 {
513 IntegerVectorList ret;
514 int c=nextNonBlank();
515
516 assert(isLeftBracket(c));
517 if((c=nextNonBlank())=='}')return ret;
518 ungetChar(c);
519
520 do
521 ret.push_back(parseIntegerVector());
522 while((c=nextNonBlank())==',');
523 assert(isRightBracket(c));
524
525 return ret;
526 }
527
528
parseIntegerVectorList4ti2()529 IntegerVectorList CharacterBasedParser::parseIntegerVectorList4ti2()
530 {
531 IntegerVectorList ret;
532
533 int m=parseInt();
534 int n=parseInt();
535 for(int i=0;i<m;i++)
536 {
537 IntegerVector v(n);
538 for(int j=0;j<n;j++)
539 {
540 v[j]=parseInt();
541 }
542 ret.push_back(v);
543 }
544 return ret;
545 }
546
547
parseIntegerVectorListList()548 IntegerVectorListList CharacterBasedParser::parseIntegerVectorListList()
549 {
550 IntegerVectorListList ret;
551 int c=nextNonBlank();
552
553 assert(isLeftBracket(c));
554 if((c=nextNonBlank())=='}')return ret;
555 ungetChar(c);
556
557 do
558 ret.push_back(parseIntegerVectorList());
559 while((c=nextNonBlank())==',');
560 assert(isRightBracket(c));
561
562 return ret;
563 }
564
565
parseField()566 Field CharacterBasedParser::parseField()
567 {
568 int c=nextNonBlank();
569
570 if(c=='Q')
571 {
572 return Q;
573 }
574
575 if(c=='P')
576 {
577 return QQ;
578 }
579
580 if(c=='Z')
581 {
582 c=nextNonBlank();
583 assert(c=='/');
584 int p=parseInt();
585 c=nextNonBlank();
586 assert(c=='Z');
587
588 return FieldZModPZ(p);
589 }
590
591 parserError("field",c);
592 assert(0);
593 }
594
595
parseVariableName()596 string CharacterBasedParser::parseVariableName()
597 {
598 string name;
599 int c=nextNonBlank();
600 while((c!=',') && (c!=']') && (c!=' ') && (c!='\t') && (c!='\n') && (c!=10) && (c!=13))
601 {
602 name+=c;
603 c=getChar();
604 }
605 ungetChar(c);
606 return name;
607 }
608
609
parseVariableList()610 vector<string> CharacterBasedParser::parseVariableList()
611 {
612 vector<string> ret;
613
614 int c=nextNonBlank();
615 assert(c=='[');
616 c=nextNonBlank();
617 if(c==']') return ret;
618 ungetChar(c);
619 do
620 {
621 ret.push_back(parseVariableName());
622 c=nextNonBlank();
623 }
624 while((c)==',');
625 assert(c==']');
626 return ret;
627 }
628
629
parsePolynomialRing()630 PolynomialRing CharacterBasedParser::parsePolynomialRing()
631 {
632 Field f=parseField();
633 vector<string> variables=parseVariableList();
634
635 return PolynomialRing(f,variables);
636 }
637
638
parsePolynomialWithRing()639 Polynomial CharacterBasedParser::parsePolynomialWithRing()
640 {
641 PolynomialRing theRing=parsePolynomialRing();
642 return parsePolynomial(theRing);
643 }
644
645
parsePolynomialSetWithRing()646 PolynomialSet CharacterBasedParser::parsePolynomialSetWithRing()
647 {
648 // PolynomialSet ret(r);
649 int c=nextNonBlankDoNotGet();
650
651 if(!isLeftBracket(c))
652 {
653 PolynomialRing theRing=parsePolynomialRing();
654 return parsePolynomialSet(theRing);
655 }
656
657 PolynomialRing r=azAZ(Q);
658 // fprintf(Stderr,"%i\n",r.getNumberOfVariables());
659 log3 AsciiPrinter(Stderr).printPolynomialRing(r);
660 //fprintf(Stderr,"a\n");
661 PolynomialSet temp=parsePolynomialSet(r);
662 //fprintf(Stderr,"a\n");
663 int n=temp.numberOfVariablesInUseConsecutive();
664 //fprintf(Stderr,"a\n");
665 PolynomialRing r2=azAZ(Q,n);
666 //fprintf(Stderr,"a\n");
667
668 return temp.embeddedInto(r2);
669 }
670
671
parsePolynomialSetListWithRing()672 PolynomialSetList CharacterBasedParser::parsePolynomialSetListWithRing()
673 {
674 // PolynomialSet ret(r);
675 int c=nextNonBlankDoNotGet();
676
677 if(!isLeftBracket(c))
678 {
679 PolynomialRing theRing=parsePolynomialRing();
680 return parsePolynomialSetList(theRing);
681 }
682
683 PolynomialRing r=azAZ(Q);
684 PolynomialSetList temp=parsePolynomialSetList(r);
685 assert(temp.size());
686 int n=temp.begin()->numberOfVariablesInUseConsecutive();//!!!!!!!
687 PolynomialRing r2=azAZ(Q,n);
688
689 PolynomialSetList ret;
690 for(PolynomialSetList::const_iterator i=temp.begin();i!=temp.end();i++)
691 ret.push_back(i->embeddedInto(r2));
692
693 return ret;
694 }
695
696 //--------------------------------------------------
697 // FileParser
698 //--------------------------------------------------
699
getChar()700 int FileParser::getChar()
701 {
702 int c=getc(f);
703 // fprintf(Stderr,"getChar c=\'%c\',%i\n",c,c);
704 if(c==EOF)return 0;
705
706 return c;
707 }
708
709
ungetChar(int c)710 void FileParser::ungetChar(int c)
711 {
712 ungetc(c,f);
713 }
714
715
FileParser(FILE * f)716 FileParser::FileParser(FILE *f)
717 {
718 this->f=f;
719 }
720
721
722 //--------------------------------------------------
723 // StringParser
724 //--------------------------------------------------
725
getChar()726 int StringParser::getChar()
727 {
728 if(hasUngotten)
729 {
730 hasUngotten=false;
731 return ungotten;
732 }
733 return s[index++];
734 }
735
ungetChar(int c)736 void StringParser::ungetChar(int c)
737 {
738 assert(hasUngotten==false);
739 hasUngotten=true;
740 ungotten=c;
741 }
742
StringParser(const char * s)743 StringParser::StringParser(const char *s):
744 index(0),
745 hasUngotten(false)
746 {
747 this->s=s;
748 }
749