| 1 |
%{ |
| 2 |
/* A simple integer desk calculator using yacc and gmp. |
| 3 |
|
| 4 |
Copyright 2000-2002 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 3 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, see https://www.gnu.org/licenses/. */ |
| 19 |
|
| 20 |
|
| 21 |
/* This is a simple program, meant only to show one way to use GMP for this |
| 22 |
sort of thing. There's few features, and error checking is minimal. |
| 23 |
Standard input is read, calc_help() below shows the inputs accepted. |
| 24 |
|
| 25 |
Expressions are evaluated as they're read. If user defined functions |
| 26 |
were wanted it'd be necessary to build a parse tree like pexpr.c does, or |
| 27 |
a list of operations for a stack based evaluator. That would also make |
| 28 |
it possible to detect and optimize evaluations "mod m" like pexpr.c does. |
| 29 |
|
| 30 |
A stack is used for intermediate values in the expression evaluation, |
| 31 |
separate from the yacc parser stack. This is simple, makes error |
| 32 |
recovery easy, minimizes the junk around mpz calls in the rules, and |
| 33 |
saves initializing or clearing "mpz_t"s during a calculation. A |
| 34 |
disadvantage though is that variables must be copied to the stack to be |
| 35 |
worked on. A more sophisticated calculator or language system might be |
| 36 |
able to avoid that when executing a compiled or semi-compiled form. |
| 37 |
|
| 38 |
Avoiding repeated initializing and clearing of "mpz_t"s is important. In |
| 39 |
this program the time spent parsing is obviously much greater than any |
| 40 |
possible saving from this, but a proper calculator or language should |
| 41 |
take some trouble over it. Don't be surprised if an init/clear takes 3 |
| 42 |
or more times as long as a 10 limb addition, depending on the system (see |
| 43 |
the mpz_init_realloc_clear example in tune/README). */ |
| 44 |
|
| 45 |
|
| 46 |
#include <stdio.h> |
| 47 |
#include <stdlib.h> |
| 48 |
#include <string.h> |
| 49 |
#include "gmp.h" |
| 50 |
#define NO_CALC_H /* because it conflicts with normal calc.c stuff */ |
| 51 |
#include "calc-common.h" |
| 52 |
|
| 53 |
|
| 54 |
#define numberof(x) (sizeof (x) / sizeof ((x)[0])) |
| 55 |
|
| 56 |
|
| 57 |
void |
| 58 |
calc_help (void) |
| 59 |
{ |
| 60 |
printf ("Examples:\n"); |
| 61 |
printf (" 2+3*4 expressions are evaluated\n"); |
| 62 |
printf (" x=5^6 variables a to z can be set and used\n"); |
| 63 |
printf ("Operators:\n"); |
| 64 |
printf (" + - * arithmetic\n"); |
| 65 |
printf (" / %% division and remainder (rounding towards negative infinity)\n"); |
| 66 |
printf (" ^ exponentiation\n"); |
| 67 |
printf (" ! factorial\n"); |
| 68 |
printf (" << >> left and right shifts\n"); |
| 69 |
printf (" <= >= > \\ comparisons, giving 1 if true, 0 if false\n"); |
| 70 |
printf (" == != < /\n"); |
| 71 |
printf (" && || logical and/or, giving 1 if true, 0 if false\n"); |
| 72 |
printf ("Functions:\n"); |
| 73 |
printf (" abs(n) absolute value\n"); |
| 74 |
printf (" bin(n,m) binomial coefficient\n"); |
| 75 |
printf (" fib(n) fibonacci number\n"); |
| 76 |
printf (" gcd(a,b,..) greatest common divisor\n"); |
| 77 |
printf (" kron(a,b) kronecker symbol\n"); |
| 78 |
printf (" lcm(a,b,..) least common multiple\n"); |
| 79 |
printf (" lucnum(n) lucas number\n"); |
| 80 |
printf (" nextprime(n) next prime after n\n"); |
| 81 |
printf (" powm(b,e,m) modulo powering, b^e%%m\n"); |
| 82 |
printf (" root(n,r) r-th root\n"); |
| 83 |
printf (" sqrt(n) square root\n"); |
| 84 |
printf ("Other:\n"); |
| 85 |
printf (" hex \\ set hex or decimal for input and output\n"); |
| 86 |
printf (" decimal / (\"0x\" can be used for hex too)\n"); |
| 87 |
printf (" quit exit program (EOF works too)\n"); |
| 88 |
printf (" ; statements are separated with a ; or newline\n"); |
| 89 |
printf (" \\ continue expressions with \\ before newline\n"); |
| 90 |
printf (" # xxx comments are # though to newline\n"); |
| 91 |
printf ("Hex numbers must be entered in upper case, to distinguish them from the\n"); |
| 92 |
printf ("variables a to f (like in bc).\n"); |
| 93 |
} |
| 94 |
|
| 95 |
|
| 96 |
int ibase = 0; |
| 97 |
int obase = 10; |
| 98 |
|
| 99 |
|
| 100 |
/* The stack is a fixed size, which means there's a limit on the nesting |
| 101 |
allowed in expressions. A more sophisticated program could let it grow |
| 102 |
dynamically. */ |
| 103 |
|
| 104 |
mpz_t stack[100]; |
| 105 |
mpz_ptr sp = stack[0]; |
| 106 |
|
| 107 |
#define CHECK_OVERFLOW() \ |
| 108 |
if (sp >= stack[numberof(stack)]) /* FIXME */ \ |
| 109 |
{ \ |
| 110 |
fprintf (stderr, \ |
| 111 |
"Value stack overflow, too much nesting in expression\n"); \ |
| 112 |
YYERROR; \ |
| 113 |
} |
| 114 |
|
| 115 |
#define CHECK_EMPTY() \ |
| 116 |
if (sp != stack[0]) \ |
| 117 |
{ \ |
| 118 |
fprintf (stderr, "Oops, expected the value stack to be empty\n"); \ |
| 119 |
sp = stack[0]; \ |
| 120 |
} |
| 121 |
|
| 122 |
|
| 123 |
mpz_t variable[26]; |
| 124 |
|
| 125 |
#define CHECK_VARIABLE(var) \ |
| 126 |
if ((var) < 0 || (var) >= numberof (variable)) \ |
| 127 |
{ \ |
| 128 |
fprintf (stderr, "Oops, bad variable somehow: %d\n", var); \ |
| 129 |
YYERROR; \ |
| 130 |
} |
| 131 |
|
| 132 |
|
| 133 |
#define CHECK_UI(name,z) \ |
| 134 |
if (! mpz_fits_ulong_p (z)) \ |
| 135 |
{ \ |
| 136 |
fprintf (stderr, "%s too big\n", name); \ |
| 137 |
YYERROR; \ |
| 138 |
} |
| 139 |
|
| 140 |
%} |
| 141 |
|
| 142 |
%union { |
| 143 |
char *str; |
| 144 |
int var; |
| 145 |
} |
| 146 |
|
| 147 |
%token EOS BAD |
| 148 |
%token HELP HEX DECIMAL QUIT |
| 149 |
%token ABS BIN FIB GCD KRON LCM LUCNUM NEXTPRIME POWM ROOT SQRT |
| 150 |
%token <str> NUMBER |
| 151 |
%token <var> VARIABLE |
| 152 |
|
| 153 |
/* operators, increasing precedence */ |
| 154 |
%left LOR |
| 155 |
%left LAND |
| 156 |
%nonassoc '<' '>' EQ NE LE GE |
| 157 |
%left LSHIFT RSHIFT |
| 158 |
%left '+' '-' |
| 159 |
%left '*' '/' '%' |
| 160 |
%nonassoc UMINUS |
| 161 |
%right '^' |
| 162 |
%nonassoc '!' |
| 163 |
|
| 164 |
%% |
| 165 |
|
| 166 |
top: |
| 167 |
statement |
| 168 |
| statements statement; |
| 169 |
|
| 170 |
statements: |
| 171 |
statement EOS |
| 172 |
| statements statement EOS |
| 173 |
| error EOS { sp = stack[0]; yyerrok; }; |
| 174 |
|
| 175 |
statement: |
| 176 |
/* empty */ |
| 177 |
| e { |
| 178 |
mpz_out_str (stdout, obase, sp); putchar ('\n'); |
| 179 |
sp--; |
| 180 |
CHECK_EMPTY (); |
| 181 |
} |
| 182 |
| VARIABLE '=' e { |
| 183 |
CHECK_VARIABLE ($1); |
| 184 |
mpz_swap (variable[$1], sp); |
| 185 |
sp--; |
| 186 |
CHECK_EMPTY (); |
| 187 |
} |
| 188 |
| HELP { calc_help (); } |
| 189 |
| HEX { ibase = 16; obase = -16; } |
| 190 |
| DECIMAL { ibase = 0; obase = 10; } |
| 191 |
| QUIT { exit (0); }; |
| 192 |
|
| 193 |
/* "e" leaves it's value on the top of the mpz stack. A rule like "e '+' e" |
| 194 |
will have done a reduction for the first "e" first and the second "e" |
| 195 |
second, so the code receives the values in that order on the stack. */ |
| 196 |
e: |
| 197 |
'(' e ')' /* value on stack */ |
| 198 |
| e '+' e { sp--; mpz_add (sp, sp, sp+1); } |
| 199 |
| e '-' e { sp--; mpz_sub (sp, sp, sp+1); } |
| 200 |
| e '*' e { sp--; mpz_mul (sp, sp, sp+1); } |
| 201 |
| e '/' e { sp--; mpz_fdiv_q (sp, sp, sp+1); } |
| 202 |
| e '%' e { sp--; mpz_fdiv_r (sp, sp, sp+1); } |
| 203 |
| e '^' e { CHECK_UI ("Exponent", sp); |
| 204 |
sp--; mpz_pow_ui (sp, sp, mpz_get_ui (sp+1)); } |
| 205 |
| e LSHIFT e { CHECK_UI ("Shift count", sp); |
| 206 |
sp--; mpz_mul_2exp (sp, sp, mpz_get_ui (sp+1)); } |
| 207 |
| e RSHIFT e { CHECK_UI ("Shift count", sp); |
| 208 |
sp--; mpz_fdiv_q_2exp (sp, sp, mpz_get_ui (sp+1)); } |
| 209 |
| e '!' { CHECK_UI ("Factorial", sp); |
| 210 |
mpz_fac_ui (sp, mpz_get_ui (sp)); } |
| 211 |
| '-' e %prec UMINUS { mpz_neg (sp, sp); } |
| 212 |
|
| 213 |
| e '<' e { sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) < 0); } |
| 214 |
| e LE e { sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) <= 0); } |
| 215 |
| e EQ e { sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) == 0); } |
| 216 |
| e NE e { sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) != 0); } |
| 217 |
| e GE e { sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) >= 0); } |
| 218 |
| e '>' e { sp--; mpz_set_ui (sp, mpz_cmp (sp, sp+1) > 0); } |
| 219 |
|
| 220 |
| e LAND e { sp--; mpz_set_ui (sp, mpz_sgn (sp) && mpz_sgn (sp+1)); } |
| 221 |
| e LOR e { sp--; mpz_set_ui (sp, mpz_sgn (sp) || mpz_sgn (sp+1)); } |
| 222 |
|
| 223 |
| ABS '(' e ')' { mpz_abs (sp, sp); } |
| 224 |
| BIN '(' e ',' e ')' { sp--; CHECK_UI ("Binomial base", sp+1); |
| 225 |
mpz_bin_ui (sp, sp, mpz_get_ui (sp+1)); } |
| 226 |
| FIB '(' e ')' { CHECK_UI ("Fibonacci", sp); |
| 227 |
mpz_fib_ui (sp, mpz_get_ui (sp)); } |
| 228 |
| GCD '(' gcdlist ')' /* value on stack */ |
| 229 |
| KRON '(' e ',' e ')' { sp--; mpz_set_si (sp, |
| 230 |
mpz_kronecker (sp, sp+1)); } |
| 231 |
| LCM '(' lcmlist ')' /* value on stack */ |
| 232 |
| LUCNUM '(' e ')' { CHECK_UI ("Lucas number", sp); |
| 233 |
mpz_lucnum_ui (sp, mpz_get_ui (sp)); } |
| 234 |
| NEXTPRIME '(' e ')' { mpz_nextprime (sp, sp); } |
| 235 |
| POWM '(' e ',' e ',' e ')' { sp -= 2; mpz_powm (sp, sp, sp+1, sp+2); } |
| 236 |
| ROOT '(' e ',' e ')' { sp--; CHECK_UI ("Nth-root", sp+1); |
| 237 |
mpz_root (sp, sp, mpz_get_ui (sp+1)); } |
| 238 |
| SQRT '(' e ')' { mpz_sqrt (sp, sp); } |
| 239 |
|
| 240 |
| VARIABLE { |
| 241 |
sp++; |
| 242 |
CHECK_OVERFLOW (); |
| 243 |
CHECK_VARIABLE ($1); |
| 244 |
mpz_set (sp, variable[$1]); |
| 245 |
} |
| 246 |
| NUMBER { |
| 247 |
sp++; |
| 248 |
CHECK_OVERFLOW (); |
| 249 |
if (mpz_set_str (sp, $1, ibase) != 0) |
| 250 |
{ |
| 251 |
fprintf (stderr, "Invalid number: %s\n", $1); |
| 252 |
YYERROR; |
| 253 |
} |
| 254 |
}; |
| 255 |
|
| 256 |
gcdlist: |
| 257 |
e /* value on stack */ |
| 258 |
| gcdlist ',' e { sp--; mpz_gcd (sp, sp, sp+1); }; |
| 259 |
|
| 260 |
lcmlist: |
| 261 |
e /* value on stack */ |
| 262 |
| lcmlist ',' e { sp--; mpz_lcm (sp, sp, sp+1); }; |
| 263 |
|
| 264 |
%% |
| 265 |
|
| 266 |
yyerror (char *s) |
| 267 |
{ |
| 268 |
fprintf (stderr, "%s\n", s); |
| 269 |
} |
| 270 |
|
| 271 |
int calc_option_readline = -1; |
| 272 |
|
| 273 |
int |
| 274 |
main (int argc, char *argv[]) |
| 275 |
{ |
| 276 |
int i; |
| 277 |
|
| 278 |
for (i = 1; i < argc; i++) |
| 279 |
{ |
| 280 |
if (strcmp (argv[i], "--readline") == 0) |
| 281 |
calc_option_readline = 1; |
| 282 |
else if (strcmp (argv[i], "--noreadline") == 0) |
| 283 |
calc_option_readline = 0; |
| 284 |
else if (strcmp (argv[i], "--help") == 0) |
| 285 |
{ |
| 286 |
printf ("Usage: calc [--option]...\n"); |
| 287 |
printf (" --readline use readline\n"); |
| 288 |
printf (" --noreadline don't use readline\n"); |
| 289 |
printf (" --help this message\n"); |
| 290 |
printf ("Readline is only available when compiled in,\n"); |
| 291 |
printf ("and in that case it's the default on a tty.\n"); |
| 292 |
exit (0); |
| 293 |
} |
| 294 |
else |
| 295 |
{ |
| 296 |
fprintf (stderr, "Unrecognised option: %s\n", argv[i]); |
| 297 |
exit (1); |
| 298 |
} |
| 299 |
} |
| 300 |
|
| 301 |
#if WITH_READLINE |
| 302 |
calc_init_readline (); |
| 303 |
#else |
| 304 |
if (calc_option_readline == 1) |
| 305 |
{ |
| 306 |
fprintf (stderr, "Readline support not available\n"); |
| 307 |
exit (1); |
| 308 |
} |
| 309 |
#endif |
| 310 |
|
| 311 |
for (i = 0; i < numberof (variable); i++) |
| 312 |
mpz_init (variable[i]); |
| 313 |
|
| 314 |
for (i = 0; i < numberof (stack); i++) |
| 315 |
mpz_init (stack[i]); |
| 316 |
|
| 317 |
return yyparse (); |
| 318 |
} |