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