parser.c

   1 #include <malloc.h>
   2 #include <math.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 #include "debug.h"
   7
   8 #include "parser.h"
   9
  10 /* global variables */
  11
  12 double answer = 0;
  13
  14 /* compare codes */
  15
  16 int codecmp (char *ref, char *str)
  17 {
  18     int sig;
  19
  20     while (*ref != '\0') {
  21         if (*ref == '\t') {
  22              sig = (*str == '.') ? -1 : ((*str >= '0') && (*str <= '9'));
  23         } else {
  24             sig = *str - *ref;
  25         }
  26         if (sig != 0) {
  27             return (sig > 0) ? 1 : -1;
  28         }
  29         str++;
  30         ref++;
  31     }
  32
  33     return 0;
  34 }
  35
  36 /* allocate new element */
  37
  38 element_t *newelement (func_t function, int nbops, int prio)
  39 {
  40     element_t *new = (element_t *) calloc (1, sizeof (element_t));
  41     if (new == NULL) {
  42         VERBOSE (ERROR, fprintf (stderr, "can't allocate memory\n"));
  43         return NULL;
  44     }
  45     new->func = function;
  46     new->nbops = nbops;
  47     new->prio = prio;
  48
  49     return new;
  50 }
  51
  52 /* desallocate element */
  53
  54 void delelement (element_t *root)
  55 {
  56     int i;
  57     if ((root != NULL) && (root != ERROR_OP)) {
  58         for (i = 0; i < root->nbops; i++) {
  59             if ((root->ops[i] != NULL) && (root->ops[i] != ERROR_OP)) {
  60                 delelement (root->ops[i]);
  61             }
  62         }
  63         free (root);
  64     }
  65 }
  66
  67 /* functions */
  68
  69 #define NB_OPERATORS 6
  70
  71 keyword_t operators[NB_OPERATORS] = {
  72     { "+\t", Add, 2, 1, 1},
  73     { "-\t", Sub, 2, 1, 1},
  74     { "*",   Mul, 2, 1, 2},
  75     { "/",   Div, 2, 1, 2},
  76     { "%",   Mod, 2, 1, 3},
  77     { "^",   Pow, 2, 1, 4}
  78 };
  79
  80 #define NB_FUNCTIONS 9
  81 keyword_t functions[NB_FUNCTIONS] = {
  82     { "sqrt", Sqr, 1, 4, 5},
  83     { "pow",  Pow, 2, 3, 5},
  84     { "cos",  Cos, 1, 3, 5},
  85     { "sin",  Sin, 1, 3, 5},
  86     { "atan", Atan, 1, 4, 5},
  87     { "exp",  Exp, 1, 3, 5},
  88     { "log",  Log, 1, 3, 5},
  89     { "quit", Quit, 0, 4, 5},
  90     { "help", Help, 0, 4, 5}
  91 };
  92
  93 #define NB_CONSTANTS 3
  94 keyword_t constants[NB_CONSTANTS] = {
  95     { "ans", Ans, 0, 3, 5},
  96     { "e",   E, 0, 1, 5},
  97     { "pi",  Pi, 0, 2, 5}
  98 };
  99
 100 /* subparser function */
 101
 102 element_t *subparser (element_t **proot, char **pstr, func_t func, int nbops, int prio)
 103 {
 104     element_t *new = newelement (func, nbops, prio);
 105     if (new == NULL) {
 106         return ERROR_OP;
 107     }
 108     new->ops[0] = *proot;
 109     new->ops[1] = parser (*pstr, pstr, new->prio);
 110     if (new->ops[1] == ERROR_OP) {
 111         delelement (new);
 112         *proot = NULL;
 113         return ERROR_OP;
 114     }
 115     *proot = newelement (Val, 1, 5);
 116     if (*proot == NULL) {
 117         delelement (new);
 118         return ERROR_OP;
 119     }
 120     (*proot)->ops[0] = new;
 121
 122     return *proot;
 123 }
 124
 125 /* parser function */
 126
 127 element_t *parser (char *str, char **next, int prio)
 128 {
 129     element_t *root = NULL;
 130     int i;
 131
 132     VERBOSE (DEBUG, fprintf (stdout, "Starting parsing\n"));
 133
 134     /* main loop */
 135     while (*str != '\0') {
 136         int found = 0;
 137         element_t *new = NULL;
 138         VERBOSE (INFO, fprintf (stdout, "Processing: %s\n", str));
 139
 140         /* skip spaces and tabs */
 141
 142         if ((*str == ' ') || (*str == '\t')) {
 143             str++;
 144             continue;
 145         }
 146
 147         /* check for open bracket */
 148
 149         if (*str == '(') {
 150             VERBOSE (DEBUG, fprintf (stdout, "start processing bracket\n"));
 151             if (root) {
 152                 do {
 153                     found = 0;
 154                     new = parser (str + 1, &str, 0);
 155                     if (new == ERROR_OP) {
 156                         delelement (root);
 157                         return ERROR_OP;
 158                     }
 159                     for (i = 0; i < root->nbops; i++) {
 160                         if (root->ops[i] == NULL) {
 161                             root->ops[i] = new;
 162                             found = 1;
 163                             break;
 164                         }
 165                     }
 166                     if (!found) {
 167                         delelement (new);
 168                         delelement (root);
 169                         return ERROR_OP;
 170                     }
 171                 } while (*str == ',');
 172             } else {
 173                 root = newelement (Val, 1, 5);
 174                 if (root == NULL) {
 175                     return ERROR_OP;
 176                 }
 177                 new = parser (str + 1, &str, 0);
 178                 if ((new == ERROR_OP) || (*str == ',')) {
 179                     delelement (new);
 180                     delelement (root);
 181                     return ERROR_OP;
 182                 }
 183                 root->ops[0] = new;
 184             }
 185             str++;
 186             VERBOSE (DEBUG, fprintf (stdout, "stop processing bracket\n"));
 187             continue;
 188         }
 189
 190         /* check for closing bracket or koma */
 191
 192         if ((*str == ')') || (*str == ',')) {
 193             if (next != NULL) {
 194                 *next = str;
 195             }
 196             return root;
 197         }
 198
 199         /* look for operators */
 200
 201         for (i = 0; i < NB_OPERATORS; i++) {
 202             keyword_t *operator = operators + i;
 203             if (codecmp (operator->keyword, str) == 0) {
 204                 VERBOSE (DEBUG, fprintf (stdout, "start processing operator\n"));
 205                 if (root) {
 206                     if ((prio) && (prio > operator->prio)) {
 207                         VERBOSE (DEBUG, fprintf (stdout, "stop because operator priority\n"));
 208                         *next = str;
 209                         return root;
 210                     }
 211                     str += operator->offset;
 212                     VERBOSE (INFO, fprintf (stdout, "Oper: %d\n", operator->func));
 213                     if (subparser (&root, &str, operator->func, operator->nbops, operator->prio) == ERROR_OP) {
 214                         delelement (root);
 215                         return ERROR_OP;
 216                     }
 217                 } else if (*str == '-') {
 218                     new = newelement (Sig, 1, 9);
 219                     if (new == NULL) {
 220                         return ERROR_OP;
 221                     }
 222                     root = new;
 223                 } else {
 224                     return ERROR_OP;
 225                 }
 226                 found = 1;
 227                 VERBOSE (DEBUG, fprintf (stdout, "stop processing operator\n"));
 228                 break;
 229             }
 230         }
 231         if (found) {
 232             continue;
 233         }
 234
 235         /* look for functions */
 236
 237         for (i = 0; i < NB_FUNCTIONS; i++) {
 238             keyword_t *function = functions + i;
 239             if (codecmp (function->keyword, str) == 0) {
 240                 VERBOSE (DEBUG, fprintf (stdout, "start processing function\n"));
 241                 if (root == NULL) {
 242                     VERBOSE (INFO, fprintf (stdout, "Func: %d\n", function->func));
 243                     new = newelement (function->func, function->nbops, function->prio);
 244                     if (new == NULL) {
 245                         return ERROR_OP;
 246                     }
 247                     root = new;
 248                 } else {
 249                     delelement (root);
 250                     return ERROR_OP;
 251                 }
 252                 str += function->offset;
 253                 found = 1;
 254                 VERBOSE (DEBUG, fprintf (stdout, "stop processing function\n"));
 255                 break;
 256             }
 257         }
 258         if (found) {
 259             continue;
 260         }
 261
 262         /* look for constant */
 263
 264         for (i = 0; i < NB_CONSTANTS; i++) {
 265             keyword_t *constant = constants + i;
 266             if (codecmp (constant->keyword, str) == 0) {
 267                 VERBOSE (DEBUG, fprintf (stdout, "start processing constant\n"));
 268                 if (root == NULL) {
 269                     VERBOSE (INFO, fprintf (stdout, "Const: %d\n", constant->func));
 270                     new = newelement (constant->func, constant->nbops, constant->prio);
 271                     if (new == NULL) {
 272                         return ERROR_OP;
 273                     }
 274                     root = new;
 275                 } else {
 276                     delelement (root);
 277                     return ERROR_OP;
 278                 }
 279                 str += constant->offset;
 280                 found = 1;
 281                 VERBOSE (DEBUG, fprintf (stdout, "stop processing constant\n"));
 282                 break;
 283             }
 284         }
 285         if (found) {
 286             continue;
 287         }
 288
 289         /* look for number */
 290
 291         if (((*str >= '0') && (*str <= '9')) ||
 292             (*str == '.') || (*str == '+') || (*str == '-')) {
 293             VERBOSE (DEBUG, fprintf (stdout, "start processing value\n"));
 294             char *pt;
 295             double value = strtod (str, &pt);
 296             VERBOSE (INFO, fprintf (stdout, "Value: %f\n", value));
 297             if (str != pt) {
 298                 if (root == NULL) {
 299                     new = newelement (Val, 1, 5);
 300                     if (new == NULL) {
 301                         return ERROR_OP;
 302                     }
 303                     new->value = value;
 304                     root = new;
 305                     str = pt;
 306                 } else if (root->func == Val) {
 307                     if ((*str == '+') || (*str == '-')) {
 308                         if ((prio) && (prio > 1)) {
 309                             VERBOSE (DEBUG, fprintf (stdout, "stop because operator priority\n"));
 310                             *next = str;
 311                             return root;
 312                         }
 313                         if (subparser (&root, &str, Add, 2, 1) == ERROR_OP) {
 314                             delelement (root);
 315                             return ERROR_OP;
 316                         }
 317                     } else {
 318                         delelement (root);
 319                         return ERROR_OP;
 320                     }
 321                 } else {
 322                     delelement (root);
 323                     return ERROR_OP;
 324                 }
 325                 found = 1;
 326             }
 327             VERBOSE (DEBUG, fprintf (stdout, "stop processing value\n"));
 328         }
 329
 330         /* error */
 331
 332         if (!found) {
 333             delelement (root);
 334             return ERROR_OP;
 335         }
 336
 337     }
 338
 339     if (next != NULL) {
 340         *next = str;
 341     }
 342
 343     return root;
 344 }
 345
 346 /* print element tree */
 347
 348 void print_element (element_t *root, int level)
 349 {
 350     char *func = NULL;
 351     int i;
 352
 353     if ((root == NULL) || (root == ERROR_OP)) {
 354         return;
 355     }
 356
 357     for (i = 0; i < level; i++) {
 358         fprintf (stdout, " ");
 359     }
 360
 361     switch (root->func) {
 362     case Val: func = "Value"; break;
 363     case Sig: func = "Sign"; break;
 364     case Add: func = "Addition"; break;
 365     case Sub: func = "Subtraction"; break;
 366     case Mul: func = "Multiplication"; break;
 367     case Div: func = "Division"; break;
 368     case Mod: func = "Modulo"; break;
 369     case Pow: func = "Power"; break;
 370     case Sqr: func = "Square Root"; break;
 371     case Cos: func = "Cosine"; break;
 372     case Sin: func = "Sine"; break;
 373     case Atan: func = "Arc Tangent"; break;
 374     case Log: func = "Logarithm"; break;
 375     case Exp: func = "Exponantial"; break;
 376     case Quit: func = "Quit"; break;
 377     case Help: func = "Help"; break;
 378     case Ans: func = "Ans"; break;
 379     case Pi: func = "Pi"; break;
 380     case E: func = "E"; break;
 381     }
 382
 383     fprintf (stdout, "Function: %s\n", func);
 384
 385     if ((root->func == Val) && (root->ops[0] == NULL)) {
 386         for (i = 0; i < level; i++) {
 387             fprintf (stdout, " ");
 388         }
 389         fprintf (stdout, "value: %f\n", root->value);
 390     } else {
 391         for (i = 0; i < root->nbops; i++) {
 392             print_element (root->ops[i], level + 1);
 393         }
 394     }
 395 }
 396
 397 /* quit function */
 398
 399 void quit (void)
 400 {
 401     fprintf (stdout, "bye\n");
 402     exit (0);
 403 }
 404
 405 /* help message */
 406
 407 void help (void)
 408 {
 409     fprintf (stdout, "calc is a simple calculator\n\n");
 410     fprintf (stdout, "supported operators:\n");
 411     fprintf (stdout, " + - * / %% ^\n\n");
 412     fprintf (stdout, "supported functions:\n");
 413     fprintf (stdout, " pow sqrt cos sin atan log exp\n\n");
 414     fprintf (stdout, "miscellaneous functions:\n");
 415     fprintf (stdout, " quit help\n\n");
 416     fprintf (stdout, "supported constants:\n");
 417     fprintf (stdout, " e pi\n");
 418 }
 419
 420 /* evaluate element tree */
 421
 422 #define MASK_SUB 0x1
 423 #define MASK_DIV 0x2
 424
 425 double evaluate_element (element_t *root, char mask)
 426 {
 427     double op0 = 0, op1 = 0;
 428     char nextmask = mask;
 429
 430     if ((root == NULL) || (root == ERROR_OP)) {
 431         VERBOSE (WARNING, fprintf (stdout, "error while evaluating\n"));
 432         return 0;
 433     }
 434
 435     /* mask to manage sub operator sub and div */
 436     switch (root->func) {
 437     case Add:
 438         nextmask &= ~MASK_SUB;
 439         nextmask &= ~MASK_DIV;
 440         break;
 441     case Sub:
 442         nextmask |= MASK_SUB;
 443         nextmask &= ~MASK_DIV;
 444         break;
 445     case Mul:
 446         nextmask &= ~MASK_DIV;
 447         break;
 448     case Div:
 449         nextmask |= MASK_DIV;
 450         break;
 451     default:
 452         nextmask = mask;
 453     }
 454
 455     switch (root->func) {
 456     case Val:
 457     case Sig:
 458         op0 = (root->ops[0]) ? evaluate_element (root->ops[0], nextmask) : root->value;
 459         break;
 460     case Add:
 461     case Sub:
 462     case Mul:
 463     case Div:
 464     case Mod:
 465     case Pow:
 466         if (root->ops[1]) {
 467             op1 = evaluate_element (root->ops[1], nextmask);
 468         } else {
 469             VERBOSE (WARNING, fprintf (stdout, "error while evaluating (op[1])\n"));
 470             return 0;
 471         }
 472         /* fallthrough */
 473     case Sqr:
 474     case Cos:
 475     case Sin:
 476     case Atan:
 477     case Log:
 478     case Exp:
 479         if (root->ops[0]) {
 480             op0 = evaluate_element (root->ops[0], 0);
 481         } else {
 482             VERBOSE (WARNING, fprintf (stdout, "error while evaluating (op[0])\n"));
 483             return 0;
 484         }
 485         break;
 486     case Quit:
 487     case Help:
 488     case Ans:
 489     case Pi:
 490     case E:
 491         break;
 492     }
 493
 494     switch (root->func) {
 495     case Val: return op0;
 496     case Sig: return -op0;
 497     case Add: return ((mask & MASK_SUB) == 0) ? op0 + op1 : op0 - op1;
 498     case Sub: return ((mask & MASK_SUB) == 0) ? op0 - op1 : op0 + op1;
 499     case Mul: return ((mask & MASK_DIV) == 0) ? op0 * op1 : op0 / op1;
 500     case Div: return ((mask & MASK_DIV) == 0) ? op0 / op1 : op0 * op1;
 501     case Mod: return fmod (op0, op1);
 502     case Pow: return pow (op0, op1);
 503     case Sqr: return sqrt (op0);
 504     case Cos: return cos (op0);
 505     case Sin: return sin (op0);
 506     case Atan: return atan (op0);
 507     case Log: return log (op0);
 508     case Exp: return exp (op0);
 509     case Quit: quit (); break;
 510     case Help: help (); break;
 511     case Ans: return answer;
 512     case Pi: return M_PI;
 513     case E: return M_E;
 514     }
 515
 516     return 0;
 517 }
 518
 519 /* vim: set ts=4 sw=4 et: */