Annotation of OpenXM_contrib/gmp/demos/calc.y, Revision 1.1.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