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