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