fish/eval/parse.c

   1 /*
   2 **
   3 ** PARSE.C     Divides an input string into tokens and evaluates an
   4 **             expression.
   5 **
   6 ** Originally written 5/89 in ANSI C
   7 **
   8 ** Eval is a floating point expression evaluator.
   9 ** This is version 1.12
  10 ** Copyright (C) 1993  Will Menninger
  11 **
  12 ** This program is free software; you can redistribute it and/or modify it
  13 ** under the terms of the GNU General Public License as published by the
  14 ** Free Software Foundation; either version 2 of the License, or any
  15 ** later version.
  16 **
  17 ** This program is distributed in the hope that it will be useful, but
  18 ** WITHOUT ANY WARRANTY; without even the implied warranty of
  19 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20 ** General Public License for more details.
  21 **
  22 ** You should have received a copy of the GNU General Public License along
  23 ** with this program; if not, write to the Free Software Foundation, Inc.,
  24 ** 675 Mass Ave, Cambridge, MA 02139, USA.
  25 **
  26 ** The author until 9/93 can be contacted at:
  27 ** e-mail:     willus@ilm.pfc.mit.edu
  28 ** U.S. mail:  Will Menninger, 45 River St., #2, Boston, MA 02108-1124
  29 **
  30 **
  31 */
  32
  33 #include   "eval.h"
  34
  35
  36 /* modes */
  37 #define     M_UNARY     1
  38 #define     M_BINARY    2
  39 #define     M_FUNCTION  3
  40
  41 static double   last_value=0.0;
  42 static int      base;
  43
  44 static int     is_binary     (char *s);
  45 static int     is_unary      (char c);
  46 static int     instr         (char c,char *s);
  47 static BOOLEAN legal         (char *s);
  48 static BOOLEAN is_digit      (char c);
  49 static BOOLEAN is_exp        (char c);
  50 static BOOLEAN get_token     (int mode,char *s,int *n,TOKENPTR t,VARPTR vlist,
  51                               VARPTR clist,char *newname);
  52 static BOOLEAN assign_as_var (char *s,int *n,TOKENPTR t,VARPTR vlist,
  53                               VARPTR clist,char *newname);
  54 static BOOLEAN assign_as_num (char *s,int *n,TOKENPTR t,int max,int base);
  55 static BOOLEAN get_value     (char *s,VARPTR vlist,VARPTR clist,
  56                               double *ret_val);
  57 static int     base_override (char *s,int *n);
  58 static int     rank          (int operator);
  59
  60
  61 static int is_binary(char *s)
  62
  63     {
  64     if (s[0]=='<' && s[1]=='<')
  65         return(SHLEFT);
  66     if (s[0]=='>' && s[1]=='>')
  67         return(SHRIGHT);
  68     return(instr(s[0],BSTRING));
  69     }
  70
  71
  72 static int is_unary(char c)
  73
  74     {
  75     return(instr(c,USTRING));
  76     }
  77
  78
  79 static int instr(char c,char *s)
  80
  81     {
  82     int    i;
  83
  84     for (i=0;s[i]!=EOS && s[i]!=c;i++);
  85     return(s[i]==EOS ? 0 : i+1);
  86     }
  87
  88
  89 static BOOLEAN legal(char *s)
  90
  91     {
  92     int     c;
  93
  94     c=s[0];
  95     return(c!=EOS && c!='(' && c!=')' && c!=','
  96             && c!='=' && !isspace(c) && !is_binary(s));
  97     }
  98
  99
 100 static BOOLEAN is_digit(char c)
 101
 102     {
 103     c=tolower((int)c);
 104     if (base>10)
 105         return((c>='0' && c<='9') || (c>='a' && c<='a'+base-11));
 106     return(c>='0' && c<='0'+base-1);
 107     }
 108
 109
 110 static BOOLEAN is_exp(char c)
 111
 112     {
 113     return((base > 14) ? (c=='\\') : (c=='\\' || c=='e' || c=='E'));
 114     }
 115
 116 /*
 117 ** get_token(int mode,char *s,int *n,TOKENPTR t,VARPTR vlist,
 118 **           VARPTR clist,char *newname)
 119 **
 120 ** Figures out what the next token in the string s is, starting at (*n).
 121 ** (*n) is returned pointing to the part of the string just after the
 122 ** evaluated token.  vlist and clist are used to search through in case
 123 ** the token is a variable or constant.  newname is assigned if the token
 124 ** is a variable name not found in any of the lists.
 125 **
 126 ** Returns 0 for end of string, 1 for valid token found
 127 **
 128 */
 129
 130 static BOOLEAN get_token(int mode,char *s,int *n,TOKENPTR t,VARPTR vlist,
 131                          VARPTR clist,char *newname)
 132
 133     {
 134     int     i,c,h;
 135
 136     t->type=0;
 137     t->code=0;
 138     t->value=0;
 139     for (i=(*n);isspace(s[i]);i++);
 140     (*n)=i;
 141     if (s[i]==EOS)
 142         {
 143         (*n)=i;
 144         return(0);
 145         }
 146     t->type=0;
 147     if (mode==M_UNARY && is_unary(s[i]))
 148         {
 149         t->type=UNARY;
 150         t->code=is_unary(s[i]);
 151         (*n)=(*n)+1;
 152         return(1);
 153         }
 154     if (is_binary(&s[i]) && (mode!=M_UNARY || s[i]!='&'))
 155         {
 156         t->type=BINARY;
 157         t->code=is_binary(&s[i]);
 158         if (t->code==SHLEFT || t->code==SHRIGHT)
 159             (*n)=(*n)+1;
 160         }
 161     else
 162         {
 163         t->type=instr(s[i],"(),=");
 164         if (t->type>0)
 165                 t->type+=LEFT_PAREN-1;
 166         }
 167     if (t->type!=0)
 168         {
 169         (*n)=(*n)+1;
 170         return(1);
 171         }
 172     if (s[i]=='!')
 173         return(assign_as_var(s,n,t,vlist,clist,newname));
 174     base=getibase();
 175     c=base_override(&s[i],&h);
 176     if (c)
 177         {
 178         base=c;
 179         i+=h;
 180         }
 181     if (!is_digit(s[i]) && s[i]!='.')
 182         return(assign_as_var(s,n,t,vlist,clist,newname));
 183     if (s[i]=='.' && !is_digit(s[i+1]))
 184         return(assign_as_var(s,n,t,vlist,clist,newname));
 185     for (;legal(&s[i]);i++)
 186         {
 187         if (s[i]=='.' || is_exp(s[i]))
 188             break;
 189         if (!is_digit(s[i]))
 190                 return(assign_as_var(s,n,t,vlist,clist,newname));
 191         }
 192     if (!legal(&s[i]))
 193         {
 194         (*n)=(*n)+h;
 195         return(assign_as_num(s,n,t,i,base));
 196         }
 197     if (s[i]=='.')
 198         for (i++;legal(&s[i]);i++)
 199                 {
 200                 if (is_exp(s[i]))
 201                     break;
 202                 if (!is_digit(s[i]))
 203                     return(assign_as_var(s,n,t,vlist,clist,newname));
 204                 }
 205     if (!legal(&s[i]))
 206         {
 207         (*n)=(*n)+h;
 208         return(assign_as_num(s,n,t,i,base));
 209         }
 210     if (s[i+1]=='+' || s[i+1]=='-')
 211         i++;
 212     if (!is_digit(s[i+1]))
 213         return(assign_as_var(s,n,t,vlist,clist,newname));
 214     for (i++;legal(&s[i]);i++)
 215         {
 216         if (!is_digit(s[i]))
 217                 return(assign_as_var(s,n,t,vlist,clist,newname));
 218         }
 219     (*n)=(*n)+h;
 220     return(assign_as_num(s,n,t,i,base));
 221     }
 222
 223
 224 static BOOLEAN assign_as_var(char *s,int *n,TOKENPTR t,VARPTR vlist,
 225                              VARPTR clist,char *newname)
 226
 227     {
 228     VAR     v;
 229     char    vname[MAXINPUT+1];
 230     int     l,i,j;
 231
 232     i=(*n);
 233     l=(s[i]=='!');
 234     if (l)
 235         i++;
 236     for (j=0;legal(&s[i]) || (!j && s[i]=='&');i++,j++)
 237         vname[j]=s[i];
 238     if (!j && l)
 239         vname[j++]='!';
 240     (*n)=i;
 241     vname[j]=EOS;
 242     if (strlen(vname)>MAXNAMELEN)
 243         vname[MAXNAMELEN]=EOS;
 244     strcpy(newname,vname);
 245     if (vname[0]=='\"' && vname[1]==EOS)
 246         {
 247         t->value=last_value;
 248         t->type=QUOTE;
 249         return(1);
 250         }
 251     if (strlen(vname)<=MAXFLEN && (i=func_code(vname))!=0)
 252         {
 253         t->code=i;
 254         t->type=FUNCTION;
 255         }
 256     else
 257         {
 258         strcpy(v.name,vname);
 259         if (search_varlist(&v,clist,&i,MAXC))
 260                 {
 261                 t->code=i;
 262                 t->type=CONSTANT;
 263                 t->value=clist[i].value;
 264                 }
 265         else
 266                 {
 267                 t->type=VARIABLE;
 268                 if (search_varlist(&v,vlist,&i,MAXV))
 269                     {
 270                     t->code=i;
 271                     t->value=vlist[i].value;
 272                     }
 273                 else
 274                     t->code=-1;
 275                 }
 276         }
 277     return(1);
 278     }
 279
 280
 281 static BOOLEAN assign_as_num(char *s,int *n,TOKENPTR t,int max,int base)
 282
 283     {
 284     char    num[MAXINPUT+1];
 285     int     i,j;
 286
 287     for (i=(*n),j=0;i<max;i++,j++)
 288         num[j]=s[i];
 289     (*n)=i;
 290     num[j]=EOS;
 291     t->type=NUMBER;
 292     t->value=asciiconv(base,num);
 293     return(1);
 294     }
 295
 296
 297 /*
 298 ** evaluate(char *s,int showout,VARPTR vlist,VARPTR clist)
 299 **
 300 ** Evaluate parses the input string looking for help queries or an "equals"
 301 ** sign that divides the string into an assignment variable and its
 302 ** assigned expression.  To evaluate the actual expression, get_value is
 303 ** called.
 304 **
 305 ** Returns nothing
 306 **
 307 */
 308
 309 void evaluate(char *s,int showout,VARPTR vlist,VARPTR clist)
 310
 311     {
 312     char    varname[MAXINPUT+1];
 313     int     i,j,n,vn;
 314     VAR     x;
 315     TOKEN   t;
 316     int     checked,outbase,oldbase;
 317     char    bigbuf[MAXOUTLEN];
 318
 319
 320     oldbase=getobase();
 321     outbase=base_override(s,&j);
 322     checked=0;
 323     if (outbase && isspace(s[j]))
 324         {
 325         j++;
 326         checked=1;
 327         }
 328     else
 329         {
 330         j=0;
 331         outbase=oldbase;
 332         }
 333     for (i=j;s[i]!=EOS && s[i]!='=';i++);
 334     if (s[i]!=EOS)
 335         {
 336         strcpy(varname,&s[j]);
 337         varname[i++]=EOS;
 338         fixup(varname);
 339         n=0;
 340         j=get_token(M_UNARY,varname,&n,&t,vlist,clist,x.name);
 341         if (!j)
 342                 {
 343                 printf("There must be valid variable name on the left side of the '='.\n");
 344                 return;
 345                 }
 346         if (varname[n]!=EOS || (t.type!=VARIABLE && t.type!=CONSTANT))
 347                 {
 348                 printf("\"%s\" is not a valid variable name.\n",varname);
 349                 return;
 350                 }
 351         if (t.type==CONSTANT)
 352                 {
 353                 printf("\"%s\" is a pre-assigned constant.  It cannot be reassigned.\n",x.name);
 354                 return;
 355                 }
 356         vn=(t.type==VARIABLE);
 357         }
 358     else
 359         {
 360         vn=0;
 361         i=j;
 362         }
 363     if (!checked)
 364         {
 365         outbase=base_override(&s[i],&j);
 366         if (outbase && isspace(s[i+j]))
 367             j++;
 368         else
 369             {
 370             j=0;
 371             outbase=oldbase;
 372             }
 373         i+=j;
 374         }
 375     if (!get_value(&s[i],vlist,clist,&x.value))
 376         return;
 377     last_value=x.value;
 378     if (outbase!=oldbase)
 379         setobase(outbase);
 380     baseconv(x.value,bigbuf);
 381     if (showout)
 382         printf("%s\n",bigbuf);
 383     if (outbase!=oldbase)
 384         setobase(oldbase);
 385     if (vn)
 386         {
 387         if (!insert_var(&x,vlist))
 388             printf("No more variables can be assigned!  Limit = %d.\n",MAXV);
 389         }
 390     }
 391
 392
 393 /*
 394 ** get_value(char *s,VARPTR vlist,VARPTR clist)
 395 **
 396 ** get_value evaluates an expression string by parsing it into tokens
 397 ** (using get_token) and converting the string of tokens to a table that
 398 ** contains tokens in reverse polish order.  table_value is then called
 399 ** to evaluate the final value of the reverse polish table of tokens.
 400 ** That value is returned by get_value.
 401 **
 402 */
 403
 404 static BOOLEAN get_value(char *s,VARPTR vlist,VARPTR clist,double *ret_val)
 405
 406     {
 407     char    nn[MAXNAMELEN+1];
 408     TOKEN   t,t2,t3;
 409     int     spos,mode;
 410     char    argcount[MAXINPUT+1];
 411     int     argptr;
 412
 413     clear_stack();
 414     clear_table();
 415     spos=0;
 416     argptr=-1;
 417     mode=M_UNARY;
 418     while (get_token(mode,s,&spos,&t,vlist,clist,nn))
 419         {
 420         if (t.type==ILLEGAL)
 421             return(eerror("The '=' character is not allowed in expressions."));
 422         if (mode==M_UNARY && (t.type==BINARY || t.type==COMMA ||
 423                               t.type==RIGHT_PAREN))
 424             return(eerror("Operand expected in expression."));
 425         if (mode==M_BINARY && (t.type==UNARY || t.type==CONSTANT ||
 426                                t.type==VARIABLE || t.type==FUNCTION ||
 427                                t.type==NUMBER || t.type==LEFT_PAREN ||
 428                                t.type==QUOTE))
 429             return(eerror("Operator expected in expression."));
 430         if (t.type==VARIABLE && t.code<0)
 431             {
 432             printf("\"%s\" is an unassigned variable.\n",nn);
 433             return(0);
 434             }
 435         if (mode==M_FUNCTION && t.type!=LEFT_PAREN)
 436             return(eerror("Function names must be immediately followed "
 437                           "by a left parenthesis."));
 438         switch(t.type)
 439             {
 440             case NUMBER:
 441             case VARIABLE:
 442             case CONSTANT:
 443             case QUOTE:
 444                 if (!add_token(&t))
 445                     return(0);
 446                 mode=M_BINARY;
 447                 break;
 448             case LEFT_PAREN:
 449                 if (!push_token(&t))
 450                     return(0);
 451                 mode=M_UNARY;
 452                 break;
 453             case UNARY:
 454                 if (!push_token(&t))
 455                     return(0);
 456                 mode=M_UNARY;
 457                 break;
 458             case BINARY:
 459                 while (top_of_stack(&t2))
 460                     {
 461                     if (t2.type==BINARY && rank(t.code) > rank(t2.code))
 462                         break;
 463                     if (t2.type==LEFT_PAREN)
 464                         break;
 465                     pop_token(&t2);
 466                     if (!add_token(&t2))
 467                         return(0);
 468                     }
 469                 if (!push_token(&t))
 470                     return(0);
 471                 mode=M_UNARY;
 472                 break;
 473             case FUNCTION:
 474                 if (!push_token(&t))
 475                     return(0);
 476                 argptr++;
 477                 argcount[argptr]=0;
 478                 mode=M_FUNCTION;
 479                 break;
 480             case RIGHT_PAREN:
 481                 while (pop_token(&t2) && t2.type!=LEFT_PAREN)
 482                     if (!add_token(&t2))
 483                         return(0);
 484                 if (t2.type!=LEFT_PAREN)
 485                     return(eerror("Unmatched parentheses in expression."));
 486                 if (top_of_stack(&t2) && t2.type==FUNCTION)
 487                     {
 488                     pop_token(&t2);
 489                     if (!add_token(&t2))
 490                         return(0);
 491                     if (func_nargs(t2.code)!=argcount[argptr]+1)
 492                         {
 493                         printf("Incorrect number of arguments "
 494                                "specified for function %s.\n",
 495                                func_name(t2.code));
 496                         return(0);
 497                         }
 498                     argptr--;
 499                     }
 500                 mode=M_BINARY;
 501                 break;
 502             case COMMA:
 503                 while (pop_token(&t2) && t2.type!=LEFT_PAREN)
 504                     if (!add_token(&t2))
 505                         return(0);
 506                 if (t2.type!=LEFT_PAREN || !top_of_stack(&t3) ||
 507                     t3.type!=FUNCTION)
 508                     return(eerror("Misplaced comma in expression."));
 509                 if (!push_token(&t2))
 510                     return(0);
 511                 mode=M_UNARY;
 512                 argcount[argptr]++;
 513                 break;
 514             }
 515         }
 516     if (mode==M_UNARY)
 517         return(eerror("Expression is improperly terminated."));
 518     while (pop_token(&t2))
 519         {
 520         if (t2.type==LEFT_PAREN)
 521             return(eerror("Unmatched parentheses in expression."));
 522         if (!add_token(&t2))
 523             return(0);
 524         }
 525     return(table_value(ret_val));
 526     }
 527
 528
 529 BOOLEAN eerror(char *message)
 530
 531     {
 532     printf("%s\n",message);
 533     return(0);
 534     }
 535
 536
 537 static int rank(int operator)
 538
 539     {
 540     switch (operator)
 541         {
 542         case POWER:
 543             return(10);
 544         case DIVIDE:
 545         case MULTIPLY:
 546         case MOD:
 547             return(9);
 548         case ADD:
 549         case SUBTRACT:
 550             return(8);
 551         case SHRIGHT:
 552         case SHLEFT:
 553             return(7);
 554         case AND:
 555             return(6);
 556         case XOR:
 557             return(5);
 558         case OR:
 559             return(4);
 560         }
 561     return(0);
 562     }
 563
 564
 565 static int base_override(char *s,int *n)
 566
 567     {
 568     int     base;
 569     int     c;
 570
 571     (*n)=0;
 572     base=0;
 573     if (s[0]=='&')
 574         {
 575         if (s[1]!=EOS)
 576             {
 577             c=tolower((int)s[1]);
 578             if (c=='h' || c=='o' || c=='b' || c=='d')
 579                 {
 580                 base= c=='h' ? 16 : (c=='o' ? 8 :(c=='b' ? 2 : 10));
 581                 (*n)=2;
 582                 }
 583             }
 584         }
 585     else if (s[0]=='0' && (s[1]=='x' || s[1]=='X'))
 586         {
 587         base=16;
 588         (*n)=2;
 589         }
 590 /* Assuming base 8 for a leading zero removed because of
 591    confusion with floating point numbers */
 592     else if (s[0]=='\\')
 593         {
 594         c=tolower((int)s[1]);
 595         if (c=='0' || (c>='2' && c<='9') || (c>='a' && c<='z'))
 596             {
 597             base= c=='0' ? 10:((c>='2'&&c<='9')?c-'0':c-'a'+11);
 598             (*n)=2;
 599             }
 600         }
 601     else if (s[0]=='$')
 602         {
 603         base=16;
 604         (*n)=1;
 605         }
 606     return(base);
 607     }
 608
 609
 610 void tokcpy(TOKENPTR dest,TOKENPTR source)
 611
 612     {
 613     dest->type=source->type;
 614     dest->code=source->code;
 615     dest->value=source->value;
 616     }