Annotation of OpenXM/src/kan96xx/Kan/parser.c, Revision 1.12
1.12 ! takayama 1: /* $OpenXM: OpenXM/src/kan96xx/Kan/parser.c,v 1.11 2015/09/29 01:52:14 takayama Exp $ */
1.1 maekawa 2: /*
1.3 takayama 3: parser.c parser for poly.c
1.1 maekawa 4: */
5:
6: #include <stdio.h>
1.9 ohara 7: #include <string.h>
1.1 maekawa 8: #include "datatype.h"
9: #include "setjmp.h"
10: #include "stackm.h"
11: #include "extern.h"
12: #include "extern2.h"
13:
1.10 takayama 14:
1.1 maekawa 15: #define NUM 1 /* NUM means struct Bignum */
16: #define POL 0
17:
18: static struct ring Ring0;
19:
20: extern int SerialCurrent;
21:
22: union valObject {
23: MP_INT *ival;
24: POLY p;
25: };
26:
1.4 takayama 27: #if defined(__CYGWIN__)
28: static sigjmp_buf EnvOfParser;
29: #else
1.1 maekawa 30: static jmp_buf EnvOfParser;
1.4 takayama 31: #endif
1.1 maekawa 32:
33: static char *String;
34: static int StrPtr = 0; /* String and StrPtr are used in getcharFromStr() */
35: static int Ch = ' ';
36: static int Symbol ;
37: static int Value;
38: static int Spt = 0;
39: static int Spv = 0; /* stack pointer */
40: #define SSIZE 20000
41: static int TagStack[SSIZE];
42: static union valObject ValStack[SSIZE];
43: #define NAME_MAX 2000
44: static char Name[NAME_MAX];
45:
46: static union valObject ValTmp;
47:
48:
49: #define BIGNUM_ILIMIT 10000
50: static char Bwork[BIGNUM_ILIMIT];
51: static int Bp = 0;
52: static MP_INT *BigValue;
53:
54:
55:
56:
57:
58: static int ShowPass0 = 0; /* show the out of parserpass0.c */
59:
60:
61: static int push(int tag,union valObject val);
62: static int tpop(void);
63: static union valObject vpop(void);
64: static int mytolower(int c);
65: static int getcharFromStr(void);
66: static int getoken(void);
67: static void parse(void);
68: static void expr(void);
69: static void term(void);
70: static void factor(void);
71: static void monom(void);
72: static int isSpace(int c);
73: static int isDigit(int c);
74: static int isAlphabetNum(int c);
75: static void errorParser(char *s);
76:
77:
78: static int push(tag,val) int tag; union valObject val; {
79: if (Spv<0) {
80: errorParser(" parser.c stack underflow.\n");
81: }
82: if (Spv != Spt) {
83: errorParser(" parser.c push(). incompatible Spv,Spt values.\n");
84: }
85: TagStack[Spt] = tag;
86: ValStack[Spv] = val;
87: Spv++; Spt++;
88: if (Spv>SSIZE) {
89: errorParser(" parser.c stack overflow.\n");
90: }
91: }
92:
93: static int tpop() {
94: if (Spt<0) {
95: errorParser(" parser.c stack underflow.\n");
96: }
97: return(TagStack[--Spt]);
98: }
99: static union valObject vpop() {
100: if (Spv<0) {
101: errorParser(" parser.c stack underflow.\n");
102: }
103: return(ValStack[--Spv]);
104: }
105: /* Warning. tpop() & vpop(). */
106:
107:
108: POLY stringToPOLY(s,ringp)
1.3 takayama 109: char *s;
110: struct ring *ringp;
1.1 maekawa 111: {
112: /* call init() [ poly.c ] before you use strToPoly(). */
113: POLY ppp;
114: char *ss;
115: int k;
116:
117: /* Important NOTE.
118: Parser assumes that the input is an element of Z[x].
119: modulop() maps the input into R[x] where R=Z, Z/Zp or ringp->next.
120: Z[x] <---> Ring0
121: R[x] <---> ringp
122: So, you cannot use @vname when ringp->next != NULL.
123: */
124: Ring0 = *ringp;
125: Ring0.p = 0;
126: Ring0.next = (struct ring *)NULL;
1.4 takayama 127: #if defined(__CYGWIN__)
1.12 ! takayama 128: if (MYSIGSETJMP(EnvOfParser,1)) {
1.4 takayama 129: #else
1.12 ! takayama 130: if (MYSETJMP(EnvOfParser)) {
1.4 takayama 131: #endif
1.1 maekawa 132: fprintf(stderr,"\nERROR: You have syntax errors in the expression: %s\n",s);
133: errorKan1("%s\n"," parser.c : Syntax error in the input polynomial.");
134: return( POLYNULL ); /* error */
135: } else { }
136:
137: ss = (char *)sGC_malloc( strlen(s)+6 ); /* This parser think that an expression
1.3 takayama 138: -1+.. is error. ---->
139: Improved at 1992/03/04.*/
1.1 maekawa 140: if (ss == (char *)NULL)
141: errorParser("No more space.");
142: k=0; while (s[k] == ' ') k++;
143: /* This method is quite adhoc. */
144: /*
1.3 takayama 145: if (s[k] == '+' || s[k] == '-') {
1.1 maekawa 146: strcpy(ss,"0"); strcat(ss,&(s[k]));
1.3 takayama 147: }else strcpy(ss,&(s[k]));
1.1 maekawa 148: */
149: strcpy(ss,&(s[k])); /* we introduce new parser which recognize unary - */
150: k = strlen(ss);
151: ss[k] = ';'; ss[k+1] = '\0'; /* add ; by ad-hoc method */
152:
153: ss = str2strPass0(ss,&Ring0);
154: if (ShowPass0) {
155: printf("Pass0: %s \n",ss);
156: }
157: /* add * and change names to xn and Dn */
158:
159:
160: String = ss; StrPtr = 0; /* initialization for getcharFromStr() */
161: Ch = ' '; Spt = Spv = 0; /* initializetion for parser globals */
162: getoken();
163: parse();
164: if (tpop()==POL) {
165: ValTmp = vpop();
166: ppp = (ValTmp).p;
167: }else {
168: ValTmp = vpop();
169: ppp = bxx((ValTmp).ival,0,0,&Ring0);
170: }
171:
172: ppp = modulop(ppp,ringp);
173: if (ppp != POLYNULL && ppp->m->ringp != ringp) fprintf(stderr,"???\n");
174:
175: return( ppp );
176: }
177:
178: static int mytolower(c) int c; {
179: /*if (c>='A' && c<= 'Z') return( c + 0x20 );
1.3 takayama 180: else return( c ); */
1.1 maekawa 181: return(c); /* 1992/06/27 : do nothing now. ***/
182: }
183:
184: static int getcharFromStr() {
185: if (String[StrPtr] != '\0')
186: return(mytolower(String[StrPtr++])); /* All symbols are changed to lower*/
187: else
188: return(String[StrPtr]);
189: }
190:
191:
192: static int getoken() {
193: int i;
194: if (Ch == '\0') return( -1 );
195: while (isSpace(Ch)) Ch = getcharFromStr();
1.3 takayama 196: if (isDigit(Ch)) {
1.1 maekawa 197: Symbol = NUM; Bp = 0;
198: do {
199: Bwork[Bp] = Ch; Bwork[Bp+1] = '\0';
200: Ch = getcharFromStr();
201: Bp++;
202: if (Bp >= BIGNUM_ILIMIT-1) {
1.3 takayama 203: errorParser(" Too big big-num. ");
1.1 maekawa 204: }
205: } while (isDigit(Ch));
206: BigValue = newMP_INT();
207: mpz_set_str(BigValue,Bwork,10);
208: /* BigValue = strToBignum(Bwork); */
209: } else if (Ch=='x' || Ch=='d') {
210: Symbol = Ch;
211: Ch = getcharFromStr();
212: if (isDigit(Ch)) {
213: /* Symbol = NUM; Don't do that. */
214: Value = 0;
215: do {
1.3 takayama 216: Value = Value*10+(Ch-'0');
217: Ch = getcharFromStr();
1.1 maekawa 218: } while (isDigit(Ch));
219: }else errorParser(" Number is expected after x or d. ");
220: } else if (Ch == '@') {
221: Symbol = '@';
222: i = 0;
223: do {
224: Name[i] = Ch; Name[i+1] = '\0'; i++;
225: if (i+2 >= NAME_MAX) {
1.3 takayama 226: errorParser("Too long name begining with @.");
1.1 maekawa 227: }
228: Ch = getcharFromStr();
229: } while (isAlphabetNum(Ch));
230: }else {
231: Symbol = Ch;
232: Ch = getcharFromStr();
233: }
234:
235: /***/ /*
1.3 takayama 236: if (Symbol == NUM) {
237: fprintf(stderr,"\nToken type = number");
238: } else {
239: fprintf(stderr,"\nToken type = %c",Symbol);
240: }
241: fprintf(stderr," value is %d ",Value);
242: */
1.1 maekawa 243:
244: }
245:
246: static void parse() {
247: expr();
248: if (Symbol == ';') return;
249: else errorParser(" ; is expected.");
250: }
251:
252: static void expr() {
253: MP_INT *f,*g;
254: int op;
255: union valObject utmp;
256:
257: int gtype, ftype; /* data type. NUM or POL */
258: POLY gp; POLY fp; POLY rp; /* g -> gp, f->fp, r -> rp , if they are
1.3 takayama 259: polynomials */
1.1 maekawa 260: POLY tmpp;
261:
262: term();
263:
264: while (Symbol == '+' || Symbol == '-') {
265: op = Symbol;
266: getoken();
267: term();
268:
269: gtype = tpop(); ftype = tpop();
270: if (gtype == NUM) {
271: ValTmp = vpop();
272: g = (ValTmp).ival;
273: } else if (gtype == POL) {
274: ValTmp = vpop();
275: gp= (ValTmp).p;
276: }else ;
277: if (ftype == NUM) {
278: ValTmp = vpop();
279: f = (ValTmp).ival;
280: } else if (ftype == POL) {
281: ValTmp = vpop();
282: fp= (ValTmp).p;
283: }else ;
284:
1.3 takayama 285: /* debug */
286: /* pWritef(gp,3); printf("\n\n"); sleep(5); */
1.1 maekawa 287:
288: if (op == '+') {
289: if (ftype == NUM && gtype == NUM) {
1.3 takayama 290: mpz_add(f,f,g);
291: utmp.ival = f;
292: push(NUM,utmp);
1.1 maekawa 293: }else if (ftype== POL && gtype == NUM) {
1.3 takayama 294: rp = ppAdd(fp,bxx(g,0,0,&Ring0));
295: utmp.p = rp;
296: push(POL, utmp);
1.1 maekawa 297: }else if (ftype==NUM && gtype == POL) {
1.3 takayama 298: rp = ppAdd(bxx(f,0,0,&Ring0),gp);
299: utmp.p = rp;
300: push(POL,utmp);
1.1 maekawa 301: }else if (ftype==POL && gtype== POL) {
1.3 takayama 302: rp = ppAdd(fp,gp);
303: utmp.p = rp;
304: push(POL,utmp);
1.1 maekawa 305: }else ;
1.3 takayama 306:
1.1 maekawa 307: }else {
308: if (ftype == NUM && gtype == NUM) {
1.3 takayama 309: mpz_sub(f,f,g);
310: utmp.ival = f;
311: push(NUM,utmp);
1.1 maekawa 312: }else if (ftype== POL && gtype == NUM) {
1.3 takayama 313: rp = ppSub(fp,bxx(g,0,0,&Ring0));
314: utmp.p = rp;
315: push(POL, utmp);
1.1 maekawa 316: }else if (ftype==NUM && gtype == POL) {
1.3 takayama 317: rp = ppSub(bxx(f,0,0,&Ring0),gp);
318: utmp.p = rp;
319: push(POL,utmp);
1.1 maekawa 320: }else if (ftype==POL && gtype== POL) {
1.3 takayama 321: rp = ppSub(fp,gp);
322: utmp.p = rp;
323: push(POL,utmp);
1.1 maekawa 324: }else ;
325:
326: }
327:
328: }
329: }
330:
331: static void term() {
332: MP_INT *f,*g;
333: int op;
334: union valObject utmp;
335:
336:
337: int gtype, ftype; /* data type. NUM or POL */
338: POLY gp; POLY fp; POLY rp; /* g -> gp, f->fp, r -> rp , if they are
1.3 takayama 339: polynomials */
1.1 maekawa 340: POLY tmpp;
341:
342:
343: /* Unary + and -. For example -(1+6), -5*3, so on and so forth.
1.3 takayama 344: term : factor |
345: ( + | - )factor |
346: factor ( * | / ) factor ... |
347: ( + | - )factor ( * | / ) factor ...
1.1 maekawa 348: */
349: if (Symbol == '+') {
350: getoken();
351: factor();
352: } else if (Symbol == '-') {
353: getoken();
354: factor();
355: /* We must change the sign */
356: gtype = tpop();
357: if (gtype == NUM) {
358: ValTmp = vpop();
359: g = (ValTmp).ival;
360: mpz_neg(g,g); /* g = -g; */
361: utmp.ival = g;
362: push(NUM,utmp);
363: } else if (gtype == POL) {
364: ValTmp = vpop();
365: gp = (ValTmp).p;
366: gp = ppMult(cxx(-1,0,0,&Ring0),gp);
367: utmp.p = gp;
368: push(POL,utmp);
369: } else ;
370: } else {
371: factor();
372: }
373: while (Symbol=='*' || Symbol=='/') {
374: op = Symbol;
375: getoken();
376: factor();
377:
378: gtype = tpop(); ftype = tpop();
379: if (gtype == NUM) {
380: ValTmp = vpop();
381: g = (ValTmp).ival;
382: }else if (gtype == POL) {
383: ValTmp = vpop();
384: gp= (ValTmp).p;
385: }else ;
386: if (ftype == NUM) {
387: ValTmp = vpop();
388: f = (ValTmp).ival;
389: }else if (ftype == POL) {
390: ValTmp = vpop();
391: fp= (ValTmp).p;
392: }else ;
393:
394: if (op == '*') {
395: if (ftype == NUM && gtype == NUM) {
1.3 takayama 396: mpz_mul(f,f,g);
397: utmp.ival = f;
398: push(NUM,utmp);
1.1 maekawa 399: }else if (ftype== POL && gtype == NUM) {
1.3 takayama 400: fp = ppMult(bxx(g,0,0,&Ring0),fp);
401: utmp.p = fp;
402: push(POL, utmp);
1.1 maekawa 403: }else if (ftype==NUM && gtype == POL) {
1.3 takayama 404: gp = ppMult(bxx(f,0,0,&Ring0),gp);
405: utmp.p = gp;
406: push(POL,utmp);
1.1 maekawa 407: }else if (ftype==POL && gtype== POL) {
1.3 takayama 408: rp = ppMult(fp,gp);
409: utmp.p = rp;
410: push(POL,utmp);
1.1 maekawa 411: }else ;
1.3 takayama 412:
1.1 maekawa 413: }else {
414: if (ftype == NUM && gtype == NUM) {
1.6 takayama 415: errorParser("num/num is not supported yet.\n");
1.3 takayama 416: mpz_div(f,f,g);
417: utmp.ival = f;
418: push(NUM,utmp);
1.1 maekawa 419: }else if (ftype== POL && gtype == NUM) {
1.3 takayama 420: errorParser("POLY / num is not supported yet.\n");
421: /*pvCoeffDiv(BbToCoeff(g),fp);
422: utmp.p = fp;
423: push(POL, utmp);*/
1.1 maekawa 424: }else if (ftype==NUM && gtype == POL) {
1.3 takayama 425: errorParser(" / POLY is not supported yet.\n");
1.1 maekawa 426: }else if (ftype==POL && gtype== POL) {
1.3 takayama 427: errorParser(" / POLY is not supported yet.\n");
1.1 maekawa 428: }else ;
429:
430: }
431:
432:
433: }
434: }
435:
436: static void factor() {
437: MP_INT *f,*g;
438:
439: int gtype, ftype; /* data type. NUM or POL */
440: POLY gp; POLY fp; POLY rp; /* g -> gp, f->fp, r -> rp , if they are
1.3 takayama 441: polynomials */
1.1 maekawa 442: POLY tmpp;
443: union valObject utmp;
444:
445: monom();
446: while (Symbol == '^') {
447: getoken();
448: monom();
449:
450: gtype = tpop(); ftype = tpop();
451: if (gtype == NUM) {
452: ValTmp = vpop();
453: g = (ValTmp).ival;
454: }else if (gtype == POL) {
455: ValTmp = vpop();
456: gp= (ValTmp).p;
457: }else ;
458: if (ftype == NUM) {
459: ValTmp = vpop();
460: f = (ValTmp).ival;
461: }else if (ftype == POL) {
462: ValTmp = vpop();
463: fp= (ValTmp).p;
464: }else ;
465:
466: if (1) {
467: if (ftype == NUM && gtype == NUM) {
1.3 takayama 468: /* printf("\nf=");mpz_out_str(stdout,10,f);
469: printf("\ng=");mpz_out_str(stdout,10,g); */
470: mpz_pow_ui(f,f,(unsigned long int) mpz_get_si(g));
471: utmp.ival = f;
472: push(NUM,utmp);
1.1 maekawa 473: }else if (ftype== POL && gtype == NUM) {
1.3 takayama 474: rp = pPower(fp,(int)mpz_get_si(g));
475: utmp.p = rp;
476: push(POL,utmp);
1.1 maekawa 477: }else if (ftype==NUM && gtype == POL) {
1.3 takayama 478: errorParser("( ) ^ Polynomial is not supported yet.\n");
1.1 maekawa 479: }else if (ftype==POL && gtype== POL) {
1.3 takayama 480: errorParser("( ) ^ Polynomial is not supported yet.\n");
1.1 maekawa 481: }else ;
482:
483: }
484:
485:
486: }
487: }
488:
489: static void monom() {
490: union valObject utmp;
1.8 takayama 491: struct object obj = OINIT;
1.1 maekawa 492: POLY f;
493: extern struct context *CurrentContextp;
494: if (Symbol == 'x' || Symbol == 'd') {
495: if (Symbol == 'x') {
496: utmp.p = cxx(1,Value,1,&Ring0);
497: push(POL,utmp);
498: }else {
499: utmp.p = cdd(1,Value,1,&Ring0);
500: push(POL,utmp);
501: }
502:
503: getoken();
504:
505: }else if (Symbol == '@') {
506: obj = findUserDictionary(&(Name[1]),hash0(&(Name[1])),hash1(&(Name[1])),
1.3 takayama 507: CurrentContextp);
1.1 maekawa 508: if (isNullObject(obj)) {
509: fprintf(stderr,"%s",Name);
510: errorParser(" cannot be found in the user dictionary.");
511: }
512: if (obj.tag != Spoly) {
513: fprintf(stderr,"%s",Name);
514: errorParser(" must be polynomial object.");
515: }
516: f = pcmCopy(obj.lc.poly);
517: if (f==POLYNULL) {
518: utmp.p = f;
519: push(POL,utmp);
520: }else{
521: if (f->m->ringp->n != Ring0.n) {
1.3 takayama 522: fprintf(stderr,"%s ",Name);
523: errorParser("should be a polynomial in the current ring.\n");
1.1 maekawa 524: }
525: utmp.p = modulo0(f,&Ring0);
526: push(POL,utmp);
527: }
528:
529: getoken();
530:
531: }else if (Symbol == NUM) {
532:
533: utmp.ival = BigValue;
534: push(NUM,utmp);
535:
536: getoken();
537: }else if (Symbol=='(') {
538: getoken();
539: expr();
540: if (Symbol != ')')
541: errorParser(" ) is expectected. ");
542: getoken();
543: }else errorParser(" error in monom().");
544: }
545:
546:
547: static int isSpace(c) int c; {
548: if (c == ' ' || c == '\t' || c == '\n') return( 1 );
549: else return( 0 );
550: }
551:
552: static int isDigit(c) int c; {
553: if (c >='0' && c <= '9') return(1);
554: else return(0);
555: }
556:
557: static int isAlphabetNum(c) int c; {
558: if (c>='A' && c<='Z') return(1);
559: if (c>='a' && c<='z') return(1);
560: if (c>='0' && c<='9') return(1);
561: return(0);
562: }
563:
564:
565:
566:
567: static void errorParser(s) char s[]; {
568: int i;
569: extern char *GotoLabel;
570: extern int GotoP;
571: extern int ErrorMessageMode;
1.7 takayama 572: extern int RestrictedMode, RestrictedMode_saved;
1.1 maekawa 573: int j;
574: char tmpc[1024];
1.7 takayama 575: RestrictedMode = RestrictedMode_saved;
1.5 takayama 576: cancelAlarm();
1.1 maekawa 577: if (ErrorMessageMode == 1 || ErrorMessageMode == 2) {
578: sprintf(tmpc,"\nError(parser.c): ");
579: if (strlen(s) < 1000-strlen(tmpc)) {
580: strcat(tmpc,s);
581: }
582: strcat(tmpc," The error occured around: ");
583: j = strlen(tmpc);
584: for (i=(((StrPtr-5) >= 0)?StrPtr-5:0) ;
1.3 takayama 585: (i<StrPtr+10) && (String[i] != '\0'); i++) {
1.1 maekawa 586: tmpc[j] = String[i]; j++;
587: tmpc[j] = '\0';
588: if (j >= 1023) break;
589: }
590: pushErrorStack(KnewErrorPacket(SerialCurrent,-1,tmpc));
591: }
592: if (ErrorMessageMode != 1) {
593: fprintf(stderr,"%s\n",s);
594: fprintf(stderr,"The error occured around: ");
595: for (i=(((StrPtr-5) >= 0)?StrPtr-5:0) ;
1.3 takayama 596: (i<StrPtr+10) && (String[i] != '\0'); i++)
1.1 maekawa 597: fprintf(stderr,"%c",String[i]);
598: fprintf(stderr," ..... \n");
599: }
600: if (GotoP) {
601: fprintf(Fstack,"The interpreter was looking for the label <<%s>>. It is also aborted.\n",GotoLabel);
602: GotoP = 0;
603: }
1.4 takayama 604: #if defined(__CYGWIN__)
1.12 ! takayama 605: MYSIGLONGJMP(EnvOfParser,1);
1.4 takayama 606: #else
1.12 ! takayama 607: MYLONGJMP(EnvOfParser,1);
1.4 takayama 608: #endif
1.1 maekawa 609: }
610:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to parser.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / src / kan96xx / Kan