7a9f9885318585f31c4cf4a16fd1da186a0c32fb
[calc.git] / 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 #define STORAGE_SIZE 10
15 double storage[STORAGE_SIZE] = {0};
16
17 /* compare codes */
18
19 int codecmp (char *ref, char *str)
20 {
21 int sig;
22
23 while (*ref != '\0') {
24 if (*ref == '\t') {
25 sig = (*str == '.') ? -1 : ((*str >= '0') && (*str <= '9'));
26 } else {
27 sig = *str - *ref;
28 }
29 if (sig != 0) {
30 return (sig > 0) ? 1 : -1;
31 }
32 str++;
33 ref++;
34 }
35
36 return 0;
37 }
38
39 /* allocate new element */
40
41 element_t *newelement (func_t function, int nbops, int prio)
42 {
43 element_t *new = (element_t *) calloc (1, sizeof (element_t));
44 if (new == NULL) {
45 VERBOSE (ERROR, fprintf (stderr, "can't allocate memory\n"));
46 return NULL;
47 }
48 new->ops = (element_t **) calloc (1, sizeof (element_t *));
49 if (new->ops == NULL) {
50 free (new);
51 VERBOSE (ERROR, fprintf (stderr, "can't allocate memory\n"));
52 return NULL;
53 }
54 new->func = function;
55 new->nbops = nbops;
56 new->prio = prio;
57
58 return new;
59 }
60
61 /* desallocate element */
62
63 void delelement (element_t *root)
64 {
65 if ((root != NULL) && (root != ERROR_OP)) {
66 int i;
67 for (i = 0; i < root->nbops; i++) {
68 if ((root->ops[i] != NULL) && (root->ops[i] != ERROR_OP)) {
69 delelement (root->ops[i]);
70 }
71 }
72 if (root->nbops) {
73 free (root->ops);
74 }
75 free (root);
76 }
77 }
78
79 /* duplicate element */
80
81 element_t *dupelement (element_t *root)
82 {
83 element_t *tmp = NULL;
84 int i;
85
86 if ((root == NULL) || (root == ERROR_OP)) {
87 return root;
88 }
89 tmp = newelement (root->func, root->nbops, root->prio);
90 if (tmp == NULL) {
91 return ERROR_OP;
92 }
93 tmp->value = root->value;
94 for (i = 0; i < root->nbops; i++) {
95 tmp->ops[i] = dupelement (root->ops[i]);
96 if (tmp->ops[i] == ERROR_OP) {
97 delelement (tmp);
98 return ERROR_OP;
99 }
100 }
101 return tmp;
102 }
103
104 /* functions */
105
106 #define NB_OPERATORS 14
107 keyword_t operators[NB_OPERATORS] = {
108 { "+\t", Add, 2, 1, 1},
109 { "-\t", Sub, 2, 1, 1},
110 { "*", Mul, 2, 1, 2},
111 { "/", Div, 2, 1, 2},
112 { "%", Mod, 2, 1, 3},
113 { "^", Pow, 2, 1, 4},
114 { "==", Equal, 2, 2, -1},
115 { "!=", Diff, 2, 2, -1},
116 { ">=", Ge, 2, 2, -1},
117 { "<=", Le, 2, 2, -1},
118 { ">", Gt, 2, 1, -1},
119 { "<", Lt, 2, 1, -1},
120 { "&", And, 2, 1, -2},
121 { "|", Or, 2, 1, -2}
122 };
123
124 #define NB_FUNCTIONS 17
125 keyword_t functions[NB_FUNCTIONS] = {
126 { "sqrt", Sqr, 1, 4, 5},
127 { "pow", Pow, 2, 3, 5},
128 { "cos", Cos, 1, 3, 5},
129 { "sin", Sin, 1, 3, 5},
130 { "atan", Atan, 1, 4, 5},
131 { "exp", Exp, 1, 3, 5},
132 { "log", Log, 1, 3, 5},
133 { "sto", Store, 2, 3, 5},
134 { "rcl", Recall, 1, 3, 5},
135 { "inc", Inc, 1, 3, 5},
136 { "dec", Dec, 1, 3, 5},
137 { "disp", Disp, 0, 4, 9},
138 { "quit", Quit, 0, 4, 9},
139 { "help", Help, 0, 4, 9},
140 { "!", Not, 1, 1, 6},
141 { "cond", Cond, 3, 4, 5},
142 { "whl", While, 2, 3, 5}
143 };
144
145 #define NB_CONSTANTS 3
146 keyword_t constants[NB_CONSTANTS] = {
147 { "ans", Ans, 0, 3, 5},
148 { "e", E, 0, 1, 5},
149 { "pi", Pi, 0, 2, 5}
150 };
151
152 /* subparser function */
153
154 element_t *subparser (element_t **proot, char **pstr, func_t func, int nbops, int prio)
155 {
156 element_t *new = newelement (func, nbops, prio);
157 if (new == NULL) {
158 return ERROR_OP;
159 }
160 new->ops[0] = *proot;
161 new->ops[1] = parser (*pstr, pstr, new->prio);
162 if ((new->ops[1] == NULL) || ((new->ops[1] != ERROR_OP) && (new->ops[1]->prio == 9))) {
163 delelement (new->ops[1]);
164 new->ops[1] = ERROR_OP;
165 }
166 if (new->ops[1] == ERROR_OP) {
167 delelement (new);
168 *proot = NULL;
169 return ERROR_OP;
170 }
171 *proot = newelement (Val, 1, 5);
172 if (*proot == NULL) {
173 delelement (new);
174 return ERROR_OP;
175 }
176 (*proot)->ops[0] = new;
177
178 return *proot;
179 }
180
181 /* parser function */
182
183 element_t *parser (char *str, char **next, int prio)
184 {
185 element_t *root = NULL;
186 int i;
187
188 VERBOSE (DEBUG, fprintf (stdout, "Starting parsing\n"));
189
190 /* main loop */
191 while (*str != '\0') {
192 int found = 0;
193 element_t *new = NULL;
194 VERBOSE (INFO, fprintf (stdout, "Processing: %s\n", str));
195
196 /* skip spaces and tabs */
197
198 if ((*str == ' ') || (*str == '\t')) {
199 str++;
200 continue;
201 }
202
203 /* check for open bracket */
204
205 if (*str == '(') {
206 VERBOSE (DEBUG, fprintf (stdout, "start processing bracket\n"));
207 if (root) {
208 do {
209 found = 0;
210 new = parser (str + 1, &str, 0);
211 if ((new == NULL) || ((new != ERROR_OP) && (new->prio == 9))) {
212 delelement (new);
213 new = ERROR_OP;
214 }
215 if ((new == NULL) || (new == ERROR_OP)) {
216 delelement (root);
217 return ERROR_OP;
218 }
219 for (i = 0; i < root->nbops; i++) {
220 if (root->ops[i] == NULL) {
221 root->ops[i] = new;
222 found = 1;
223 break;
224 }
225 }
226 if (!found) {
227 delelement (new);
228 delelement (root);
229 return ERROR_OP;
230 }
231 } while (*str == ',');
232 } else {
233 root = newelement (Val, 1, 5);
234 if (root == NULL) {
235 return ERROR_OP;
236 }
237 new = parser (str + 1, &str, 0);
238 if ((new == NULL) || ((new != ERROR_OP) && (new->prio == 9))) {
239 delelement (new);
240 new = ERROR_OP;
241 }
242 if ((new == NULL) || (new == ERROR_OP) || (*str == ',')) {
243 delelement (new);
244 delelement (root);
245 return ERROR_OP;
246 }
247 root->ops[0] = new;
248 }
249 if (*str != ')') {
250 delelement (root);
251 return ERROR_OP;
252 }
253 str++;
254 VERBOSE (DEBUG, fprintf (stdout, "stop processing bracket\n"));
255 continue;
256 }
257
258 /* check for closing bracket or koma */
259
260 if ((*str == ')') || (*str == ',')) {
261 if (next != NULL) {
262 *next = str;
263 }
264 return root;
265 }
266
267 /* look for operators */
268
269 for (i = 0; i < NB_OPERATORS; i++) {
270 keyword_t *operator = operators + i;
271 if (codecmp (operator->keyword, str) == 0) {
272 VERBOSE (DEBUG, fprintf (stdout, "start processing operator\n"));
273 if (root) {
274 if ((prio) && (prio > operator->prio)) {
275 VERBOSE (DEBUG, fprintf (stdout, "stop because operator priority\n"));
276 *next = str;
277 return root;
278 }
279 str += operator->offset;
280 VERBOSE (INFO, fprintf (stdout, "Oper: %d\n", operator->func));
281 if (subparser (&root, &str, operator->func, operator->nbops, operator->prio) == ERROR_OP) {
282 delelement (root);
283 return ERROR_OP;
284 }
285 } else if (*str == '-') {
286 new = newelement (Sig, 1, 9);
287 if (new == NULL) {
288 return ERROR_OP;
289 }
290 root = new;
291 } else {
292 return ERROR_OP;
293 }
294 found = 1;
295 VERBOSE (DEBUG, fprintf (stdout, "stop processing operator\n"));
296 break;
297 }
298 }
299 if (found) {
300 continue;
301 }
302
303 /* look for functions */
304
305 for (i = 0; i < NB_FUNCTIONS; i++) {
306 keyword_t *function = functions + i;
307 if (codecmp (function->keyword, str) == 0) {
308 VERBOSE (DEBUG, fprintf (stdout, "start processing function\n"));
309 if (root == NULL) {
310 VERBOSE (INFO, fprintf (stdout, "Func: %d\n", function->func));
311 new = newelement (function->func, function->nbops, function->prio);
312 if (new == NULL) {
313 return ERROR_OP;
314 }
315 root = new;
316 } else {
317 delelement (root);
318 return ERROR_OP;
319 }
320 str += function->offset;
321 found = 1;
322 VERBOSE (DEBUG, fprintf (stdout, "stop processing function\n"));
323 break;
324 }
325 }
326 if (found) {
327 continue;
328 }
329
330 /* look for constant */
331
332 for (i = 0; i < NB_CONSTANTS; i++) {
333 keyword_t *constant = constants + i;
334 if (codecmp (constant->keyword, str) == 0) {
335 VERBOSE (DEBUG, fprintf (stdout, "start processing constant\n"));
336 if (root == NULL) {
337 VERBOSE (INFO, fprintf (stdout, "Const: %d\n", constant->func));
338 new = newelement (constant->func, constant->nbops, constant->prio);
339 if (new == NULL) {
340 return ERROR_OP;
341 }
342 root = new;
343 } else {
344 delelement (root);
345 return ERROR_OP;
346 }
347 str += constant->offset;
348 found = 1;
349 VERBOSE (DEBUG, fprintf (stdout, "stop processing constant\n"));
350 break;
351 }
352 }
353 if (found) {
354 continue;
355 }
356
357 /* look for number */
358
359 if (((*str >= '0') && (*str <= '9')) ||
360 (*str == '.') || (*str == '+') || (*str == '-')) {
361 VERBOSE (DEBUG, fprintf (stdout, "start processing value\n"));
362 char *pt;
363 double value = strtod (str, &pt);
364 VERBOSE (INFO, fprintf (stdout, "Value: %f\n", value));
365 if (str != pt) {
366 if ((root == NULL) || (root->prio == 6)) {
367 new = newelement (Val, 1, 5);
368 if (new == NULL) {
369 return ERROR_OP;
370 }
371 new->value = value;
372 if (root == NULL) {
373 root = new;
374 } else {
375 for (i = 0; i < root->nbops; i++) {
376 if (root->ops[i] == NULL) {
377 root->ops[i] = new;
378 found = 1;
379 break;
380 }
381 }
382 if (!found) {
383 delelement (new);
384 delelement (root);
385 return ERROR_OP;
386 }
387 }
388 str = pt;
389 } else if ((*str == '+') || (*str == '-')) {
390 if ((prio) && (prio > 1)) {
391 VERBOSE (DEBUG, fprintf (stdout, "stop because operator priority\n"));
392 *next = str;
393 return root;
394 }
395 if (subparser (&root, &str, Add, 2, 1) == ERROR_OP) {
396 delelement (root);
397 return ERROR_OP;
398 }
399 } else {
400 delelement (root);
401 return ERROR_OP;
402 }
403 found = 1;
404 }
405 VERBOSE (DEBUG, fprintf (stdout, "stop processing value\n"));
406 }
407
408 /* error */
409
410 if (!found) {
411 delelement (root);
412 return ERROR_OP;
413 }
414
415 }
416
417 if (next != NULL) {
418 *next = str;
419 }
420
421 return root;
422 }
423
424 /* print element tree */
425
426 void print_element (element_t *root, int level)
427 {
428 char *func = NULL;
429 int i;
430
431 if ((root == NULL) || (root == ERROR_OP)) {
432 return;
433 }
434
435 for (i = 0; i < level; i++) {
436 fprintf (stdout, " ");
437 }
438
439 switch (root->func) {
440 case Val: func = "Value"; break;
441 case Sig: func = "Sign"; break;
442 case Add: func = "Addition"; break;
443 case Sub: func = "Subtraction"; break;
444 case Mul: func = "Multiplication"; break;
445 case Div: func = "Division"; break;
446 case Mod: func = "Modulo"; break;
447 case Pow: func = "Power"; break;
448 case Sqr: func = "Square Root"; break;
449 case Cos: func = "Cosine"; break;
450 case Sin: func = "Sine"; break;
451 case Atan: func = "Arc Tangent"; break;
452 case Log: func = "Logarithm"; break;
453 case Exp: func = "Exponantial"; break;
454 case Store: func = "Store"; break;
455 case Recall: func = "Recall"; break;
456 case Inc: func = "Increase"; break;
457 case Dec: func = "Decrease"; break;
458 case Disp: func = "Display"; break;
459 case Quit: func = "Quit"; break;
460 case Help: func = "Help"; break;
461 case Ans: func = "Ans"; break;
462 case Pi: func = "Pi"; break;
463 case E: func = "E"; break;
464 case Equal: func = "Equal"; break;
465 case Diff: func = "Different"; break;
466 case Ge: func = "Greater or equal"; break;
467 case Le: func = "Lesser or equal"; break;
468 case Gt: func = "Greater"; break;
469 case Lt: func = "Lesser"; break;
470 case And: func = "And"; break;
471 case Or: func = "Or"; break;
472 case Not: func = "Not"; break;
473 case Cond: func = "Condition"; break;
474 case While: func = "While"; break;
475 }
476
477 fprintf (stdout, "Function: %s\n", func);
478
479 if ((root->func == Val) && (root->ops[0] == NULL)) {
480 for (i = 0; i < level; i++) {
481 fprintf (stdout, " ");
482 }
483 fprintf (stdout, "value: %f\n", root->value);
484 } else {
485 for (i = 0; i < root->nbops; i++) {
486 print_element (root->ops[i], level + 1);
487 }
488 }
489 }
490
491 /* storage functions */
492
493 double store (int index, double value)
494 {
495 if ((index > 0) && (index <= STORAGE_SIZE)) {
496 storage[index - 1] = value;
497 } else {
498 VERBOSE (WARNING, fprintf (stdout, "invalid index (%d) [1, %d]\n", index, STORAGE_SIZE));
499 }
500 return value;
501 }
502
503 double recall (int index)
504 {
505 if ((index > 0) && (index <= STORAGE_SIZE)) {
506 return storage[index - 1];
507 } else {
508 VERBOSE (WARNING, fprintf (stdout, "invalid index (%d) [1, %d]\n", index, STORAGE_SIZE));
509 }
510 return 0;
511 }
512
513 double increase (int index)
514 {
515 if ((index > 0) && (index <= STORAGE_SIZE)) {
516 return storage[index - 1]++;
517 } else {
518 VERBOSE (WARNING, fprintf (stdout, "invalid index (%d) [1, %d]\n", index, STORAGE_SIZE));
519 }
520 return 0;
521 }
522
523 double decrease (int index)
524 {
525 if ((index > 0) && (index <= STORAGE_SIZE)) {
526 return storage[index - 1]--;
527 } else {
528 VERBOSE (WARNING, fprintf (stdout, "invalid index (%d) [1, %d]\n", index, STORAGE_SIZE));
529 }
530 return 0;
531 }
532
533 void display (void)
534 {
535 int i;
536 fprintf (stdout, "storage:");
537 for (i = 0; i < STORAGE_SIZE; i++) {
538 fprintf (stdout, " %g", storage[i]);
539 }
540 fprintf (stdout, "\n");
541 }
542
543 /* While do function */
544
545 double while_do (element_t *cond, element_t *action)
546 {
547 double ret = 0;
548 element_t *temp = NULL;
549
550 VERBOSE (DEBUG, fprintf (stdout, "starting while loop\n"));
551 if (cond == NULL) {
552 return ret;
553 }
554 while (1) {
555 VERBOSE (DEBUG, fprintf (stdout, "loop...\n"));
556
557 temp = dupelement (cond);
558 if (!evaluate_element (temp, 0)) {
559 break;
560 }
561 if (action) {
562 temp = dupelement (action);
563 ret = evaluate_element (temp, 0);
564 }
565 }
566
567 VERBOSE (DEBUG, fprintf (stdout, "ending while loop\n"));
568
569 return ret;
570 }
571
572 /* quit function */
573
574 void quit (void)
575 {
576 fprintf (stdout, "bye\n");
577 exit (0);
578 }
579
580 /* help message */
581
582 void help (void)
583 {
584 fprintf (stdout, "calc is a simple calculator\n\n");
585 fprintf (stdout, "supported operators:");
586 fprintf (stdout, " + - * / %% ^\n");
587 fprintf (stdout, "camparison operators:");
588 fprintf (stdout, " == != >= <= > <\n");
589 fprintf (stdout, "logical operators:");
590 fprintf (stdout, " & | !\n");
591 fprintf (stdout, "supported functions:");
592 fprintf (stdout, " pow sqrt cos sin atan log exp\n");
593 fprintf (stdout, "storage functions:");
594 fprintf (stdout, " sto rcl inc dec\n");
595 fprintf (stdout, "conditional functions:");
596 fprintf (stdout, " cond\n");
597 fprintf (stdout, "miscellaneous functions:");
598 fprintf (stdout, " quit help\n");
599 fprintf (stdout, "supported constants:");
600 fprintf (stdout, " e pi\n");
601 }
602
603 /* evaluate element tree */
604
605 #define MASK_SUB 0x1
606 #define MASK_DIV 0x2
607
608 double evaluate_element (element_t *root, char mask)
609 {
610 double op0 = 0, op1 = 0;
611 char nextmask = mask;
612
613 if ((root == NULL) || (root == ERROR_OP)) {
614 VERBOSE (WARNING, fprintf (stdout, "error while evaluating\n"));
615 return 0;
616 }
617
618 /* mask to manage sub operator sub and div */
619 switch (root->func) {
620 case Add:
621 nextmask &= ~MASK_SUB;
622 nextmask &= ~MASK_DIV;
623 break;
624 case Sub:
625 nextmask |= MASK_SUB;
626 nextmask &= ~MASK_DIV;
627 break;
628 case Mul:
629 nextmask &= ~MASK_DIV;
630 break;
631 case Div:
632 nextmask |= MASK_DIV;
633 break;
634 default:
635 nextmask = mask;
636 }
637
638 switch (root->func) {
639 case Val:
640 case Sig:
641 op0 = (root->ops[0]) ? evaluate_element (root->ops[0], nextmask) : root->value;
642 break;
643 case Add:
644 case Sub:
645 case Mul:
646 case Div:
647 case Mod:
648 case Pow:
649 case Store:
650 case Equal:
651 case Diff:
652 case Ge:
653 case Le:
654 case Gt:
655 case Lt:
656 case And:
657 case Or:
658 if (root->ops[1]) {
659 op1 = evaluate_element (root->ops[1], nextmask);
660 } else if (root->func != Store) {
661 VERBOSE (WARNING, fprintf (stdout, "error while evaluating (op[1])\n"));
662 return 0;
663 }
664 /* fallthrough */
665 case Sqr:
666 case Cos:
667 case Sin:
668 case Atan:
669 case Log:
670 case Exp:
671 case Recall:
672 case Inc:
673 case Dec:
674 case Not:
675 case Cond:
676 if (root->ops[0]) {
677 op0 = evaluate_element (root->ops[0], 0);
678 } else {
679 VERBOSE (WARNING, fprintf (stdout, "error while evaluating (op[0])\n"));
680 return 0;
681 }
682 break;
683 case Disp:
684 case Quit:
685 case Help:
686 case Ans:
687 case Pi:
688 case E:
689 break;
690 case While:
691 if (root->ops[0] == NULL) {
692 VERBOSE (WARNING, fprintf (stdout, "error while evaluating (op[0])\n"));
693 return 0;
694 }
695 break;
696 }
697
698 switch (root->func) {
699 case Val: return op0;
700 case Sig: return -op0;
701 case Add: return ((mask & MASK_SUB) == 0) ? op0 + op1 : op0 - op1;
702 case Sub: return ((mask & MASK_SUB) == 0) ? op0 - op1 : op0 + op1;
703 case Mul: return ((mask & MASK_DIV) == 0) ? op0 * op1 : op0 / op1;
704 case Div: return ((mask & MASK_DIV) == 0) ? op0 / op1 : op0 * op1;
705 case Mod: return fmod (op0, op1);
706 case Pow: return pow (op0, op1);
707 case Sqr: return sqrt (op0);
708 case Cos: return cos (op0);
709 case Sin: return sin (op0);
710 case Atan: return atan (op0);
711 case Log: return log (op0);
712 case Exp: return exp (op0);
713 case Store: return store ((int)op0, (op1) ? op1 : answer);
714 case Recall: return recall ((int)op0);
715 case Inc: return increase ((int)op0);
716 case Dec: return decrease ((int)op0);
717 case Disp: display (); break;
718 case Quit: quit (); break;
719 case Help: help (); break;
720 case Ans: return answer;
721 case Pi: return M_PI;
722 case E: return M_E;
723 case Equal: return op0 == op1;
724 case Diff: return op0 != op1;
725 case Ge: return op0 >= op1;
726 case Le: return op0 <= op1;
727 case Gt: return op0 > op1;
728 case Lt: return op0 < op1;
729 case And: return (op0 != 0) && (op1 != 0);
730 case Or: return (op0 != 0) || (op1 != 0);
731 case Not: return (op0 == 0);
732 case Cond:
733 if ((op0) && (root->ops[1])) {
734 return evaluate_element (root->ops[1], 0);
735 } else if ((!op0) && (root->ops[2])) {
736 return evaluate_element (root->ops[2], 0);
737 } else {
738 return 0;
739 }
740 case While: return while_do (root->ops[0], root->ops[1]);
741 }
742
743 return 0;
744 }
745
746 /* vim: set ts=4 sw=4 et: */