[BACK]Return to parser.c CVS log [TXT][DIR] Up to [local] / OpenXM / src / kan96xx / Kan

Annotation of OpenXM/src/kan96xx/Kan/parser.c, Revision 1.1.1.1

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

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>