demos/calc/calc.y

   1 %{
   2 /* A simple integer desk calculator using yacc and gmp.
   3
   4 Copyright 2000, 2001, 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 http://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 }