Annotation of OpenXM_contrib/gmp/demos/calc.y, Revision 1.1
1.1 ! maekawa 1: /* A simple integer desk calculator using yacc and gmp. */
! 2:
! 3: /*
! 4: Copyright (C) 2000 Free Software Foundation, Inc.
! 5:
! 6: This file is part of the GNU MP Library.
! 7:
! 8: This program is free software; you can redistribute it and/or modify it under
! 9: the terms of the GNU General Public License as published by the Free Software
! 10: Foundation; either version 2 of the License, or (at your option) any later
! 11: version.
! 12:
! 13: This program is distributed in the hope that it will be useful, but WITHOUT ANY
! 14: WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
! 15: PARTICULAR PURPOSE. See the GNU General Public License for more details.
! 16:
! 17: You should have received a copy of the GNU General Public License along with
! 18: this program; if not, write to the Free Software Foundation, Inc., 59 Temple
! 19: Place - Suite 330, Boston, MA 02111-1307, USA.
! 20: */
! 21:
! 22:
! 23: /* This is a simple program, meant only to show one way to use GMP for this
! 24: sort of thing. There's few features, and error checking is minimal.
! 25: Standard input is read, there's no command line options.
! 26:
! 27: Examples:
! 28: 2+3*4 expressions are evaluated
! 29: x=5^6 variables a to z can be set and used
! 30:
! 31: Operators:
! 32: + - * arithmetic
! 33: / % division and remainder (rounding towards negative infinity)
! 34: ^ exponentiation
! 35: ! factorial
! 36: << >> left and right shifts
! 37: <= >= > \ comparisons, giving 1 if true, 0 if false
! 38: == != < /
! 39: && || logical and/or, giving 1 if true, 0 if false
! 40:
! 41: Functions:
! 42: abs(n) absolute value
! 43: bin(n,m) binomial coefficient
! 44: fib(n) fibonacci number
! 45: gcd(a,b,..) greatest common divisor
! 46: lcm(a,b,..) least common multiple
! 47: nextprime(n) next prime after n
! 48: powm(b,e,m) modulo powering, b^e%m
! 49: root(n,r) r-th root (rounded down)
! 50: sqrt(n) square root (rounded down)
! 51:
! 52: Other:
! 53: hex \ set hex or decimal for input and output
! 54: decimal / ("0x" can be used for hex too)
! 55: quit exit program (EOF works too)
! 56: ; statements are separated with a ; or newline
! 57: \ continue expressions with \ before newline
! 58: # xxx comments are # though to newline
! 59:
! 60: Hex numbers must be entered in upper case, to distinguish them from the
! 61: variables a to f (like in bc).
! 62:
! 63:
! 64: Expressions are evaluated as they're read. If user defined functions
! 65: were wanted it'd be necessary to build a parse tree like pexpr.c does, or
! 66: a list of operations for a stack based evaluator. That would also make
! 67: it possible to detect and optimize evaluations "mod m" like pexpr.c does.
! 68:
! 69: A stack is used for intermediate values in the expression evaluation,
! 70: separate from the yacc parser stack. This is simple, makes error
! 71: recovery easy, minimizes the junk around mpz calls in the rules, and
! 72: saves initializing or clearing "mpz_t"s during a calculation. A
! 73: disadvantage though is that variables must be copied to the stack to be
! 74: worked on. A more sophisticated calculator or language system might be
! 75: able to avoid that when executing a compiled or semi-compiled form.
! 76:
! 77: Avoiding repeated initializing and clearing of "mpz_t"s is important. In
! 78: this program the time spent parsing is obviously much greater than any
! 79: possible saving from this, but a proper calculator or language should
! 80: take some trouble over it. Don't be surprised if an init/clear takes 3
! 81: or more times as long as a 10 limb addition, depending on the system (see
! 82: the mpz_init_realloc_clear example in tune/README).
! 83:
! 84: In a calculator or language using dynamic memory allocation, a good idea
! 85: would be to keep some "mpz_t"s on a free list. A structure like the
! 86: following is effectively an "mpz_t" with an extra field tacked on the end
! 87: for that purpose.
! 88:
! 89: struct foo {
! 90: mpz_t z;
! 91: struct foo *next;
! 92: };
! 93:
! 94: A pointer "struct foo *p" used as "p->z" will be just a type-safe cast.
! 95: With care a free list could be made thread safe, and it should never be
! 96: larger than the deepest nested calculation. */
! 97:
! 98:
! 99: %{
! 100: #include <stdio.h>
! 101: #include <stdlib.h>
! 102:
! 103: #include "gmp.h"
! 104:
! 105: #define numberof(x) (sizeof (x) / sizeof ((x)[0]))
! 106:
! 107:
! 108: int ibase = 0;
! 109: int obase = 10;
! 110:
! 111:
! 112: /* The stack is a fixed size, which means there's a limit on the nesting
! 113: allowed in expressions. A more sophisticated program could let it grow
! 114: dynamically. */
! 115:
! 116: mpz_t stack[100];
! 117: mpz_ptr sp = stack[0];
! 118:
! 119: #define CHECK_OVERFLOW() \
! 120: if (sp >= stack[numberof(stack)]) \
! 121: { \
! 122: fprintf (stderr, \
! 123: "Value stack overflow, too much nesting in expression\n"); \
! 124: YYERROR; \
! 125: }
! 126:
! 127: #define CHECK_EMPTY() \
! 128: if (sp != stack[0]) \
! 129: { \
! 130: fprintf (stderr, "Oops, expected the value stack to be empty\n"); \
! 131: sp = stack[0]; \
! 132: }
! 133:
! 134:
! 135: mpz_t variable[26];
! 136:
! 137: #define CHECK_VARIABLE(var) \
! 138: if ((var) < 0 || (var) >= numberof (variable)) \
! 139: { \
! 140: fprintf (stderr, "Oops, bad variable somehow: %d\n", var); \
! 141: YYERROR; \
! 142: }
! 143:
! 144:
! 145: #define CHECK_UI(name,z) \
! 146: if (! mpz_fits_ulong_p (z)) \
! 147: { \
! 148: fprintf (stderr, \
! 149: "Operand must fit in an \"unsigned long\" for %s\n", name); \
! 150: YYERROR; \
! 151: }
! 152:
! 153: %}
! 154:
! 155: %union {
! 156: char *str;
! 157: int var;
! 158: }
! 159:
! 160: %token EOS BAD
! 161: %token HEX DECIMAL QUIT
! 162: %token ABS BIN FIB GCD LCM NEXTPRIME POWM ROOT SQRT
! 163: %token <str> NUMBER
! 164: %token <var> VARIABLE
! 165:
! 166: /* operators, increasing precedence */
! 167: %left LOR
! 168: %left LAND
! 169: %nonassoc '<' '>' EQ NE LE GE
! 170: %left LSHIFT RSHIFT
! 171: %left '+' '-'
! 172: %left '*' '/' '%'
! 173: %nonassoc UMINUS
! 174: %right '^'
! 175: %nonassoc '!'
! 176:
! 177: %%
! 178:
! 179: top:
! 180: statement
! 181: | statements statement
! 182:
! 183: statements:
! 184: statement EOS
! 185: | statements statement EOS
! 186: | error EOS ={ sp = stack[0]; yyerrok; }
! 187:
! 188: statement:
! 189: /* empty */
! 190: | e ={
! 191: mpz_out_str (stdout, obase, sp); putchar ('\n');
! 192: sp--;
! 193: CHECK_EMPTY ();
! 194: }
! 195: | VARIABLE '=' e ={
! 196: CHECK_VARIABLE ($1);
! 197: mpz_swap (variable[$1], sp);
! 198: sp--;
! 199: CHECK_EMPTY ();
! 200: }
! 201: | HEX ={ ibase = 16; obase = -16; }
! 202: | DECIMAL ={ ibase = 0; obase = 10; }
! 203: | QUIT ={ exit (0); }
! 204:
! 205: /* "e" leaves it's value on the top of the mpz stack. A rule like "e '+' e"
! 206: will have done a reduction for the first "e" first and the second "e"
! 207: second, so the code receives the values in that order on the stack. */
! 208: e:
! 209: '(' e ')' /* value on stack */
! 210: | e '+' e ={ sp--; mpz_add (sp, sp, sp+1); }
! 211: | e '-' e ={ sp--; mpz_sub (sp, sp, sp+1); }
! 212: | e '*' e ={ sp--; mpz_mul (sp, sp, sp+1); }
! 213: | e '/' e ={ sp--; mpz_fdiv_q (sp, sp, sp+1); }
! 214: | e '%' e ={ sp--; mpz_fdiv_r (sp, sp, sp+1); }
! 215: | e '^' e ={ CHECK_UI ("exponentiation", sp);
! 216: sp--; mpz_pow_ui (sp, sp, mpz_get_ui (sp+1)); }
! 217: | e LSHIFT e ={ CHECK_UI ("lshift", sp);
! 218: sp--; mpz_mul_2exp (sp, sp, mpz_get_ui (sp+1)); }
! 219: | e RSHIFT e ={ CHECK_UI ("rshift", sp);
! 220: sp--; mpz_fdiv_q_2exp (sp, sp, mpz_get_ui (sp+1)); }
! 221: | e '!' ={ CHECK_UI ("factorial", sp);
! 222: mpz_fac_ui (sp, mpz_get_ui (sp)); }
! 223: | '-' e %prec UMINUS ={ mpz_neg (sp, sp); }
! 224:
! 225: | e '<' e ={ sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) < 0); }
! 226: | e LE e ={ sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) <= 0); }
! 227: | e EQ e ={ sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) == 0); }
! 228: | e NE e ={ sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) != 0); }
! 229: | e GE e ={ sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) >= 0); }
! 230: | e '>' e ={ sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) > 0); }
! 231:
! 232: | e LAND e ={ sp--; mpz_set_ui (sp, mpz_sgn (sp) && mpz_sgn (sp+1)); }
! 233: | e LOR e ={ sp--; mpz_set_ui (sp, mpz_sgn (sp) || mpz_sgn (sp+1)); }
! 234:
! 235: | ABS '(' e ')' ={ mpz_abs (sp, sp); }
! 236: | BIN '(' e ',' e ')' ={ sp--; CHECK_UI ("binomial", sp+1);
! 237: mpz_bin_ui (sp, sp, mpz_get_ui (sp+1)); }
! 238: | FIB '(' e ')' ={ CHECK_UI ("fibonacci", sp);
! 239: mpz_fib_ui (sp, mpz_get_ui (sp)); }
! 240: | GCD '(' gcdlist ')' /* value on stack */
! 241: | LCM '(' lcmlist ')' /* value on stack */
! 242: | NEXTPRIME '(' e ')' ={ mpz_nextprime (sp, sp); }
! 243: | POWM '(' e ',' e ',' e ')' ={ sp -= 2; mpz_powm (sp, sp, sp+1, sp+2); }
! 244: | ROOT '(' e ',' e ')' ={ sp--; CHECK_UI ("nth-root", sp+1);
! 245: mpz_root (sp, sp, mpz_get_ui (sp+1)); }
! 246: | SQRT '(' e ')' ={ mpz_sqrt (sp, sp); }
! 247:
! 248: | VARIABLE ={
! 249: sp++;
! 250: CHECK_OVERFLOW ();
! 251: CHECK_VARIABLE ($1);
! 252: mpz_set (sp, variable[$1]);
! 253: }
! 254: | NUMBER ={
! 255: sp++;
! 256: CHECK_OVERFLOW ();
! 257: if (mpz_set_str (sp, $1, ibase) != 0)
! 258: {
! 259: fprintf (stderr, "Invalid number: %s\n", $1);
! 260: YYERROR;
! 261: }
! 262: }
! 263:
! 264: gcdlist:
! 265: e /* value on stack */
! 266: | gcdlist ',' e ={ sp--; mpz_gcd (sp, sp, sp+1); }
! 267:
! 268: lcmlist:
! 269: e /* value on stack */
! 270: | lcmlist ',' e ={ sp--; mpz_lcm (sp, sp, sp+1); }
! 271:
! 272: %%
! 273:
! 274: yyerror (char *s)
! 275: {
! 276: fprintf (stderr, "%s\n", s);
! 277: }
! 278:
! 279: int
! 280: main (void)
! 281: {
! 282: int i;
! 283:
! 284: for (i = 0; i < numberof (variable); i++)
! 285: mpz_init (variable[i]);
! 286:
! 287: for (i = 0; i < numberof (stack); i++)
! 288: mpz_init (stack[i]);
! 289:
! 290: return yyparse ();
! 291: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to calc.y CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp / demos