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