dc282383a405876e30eecde9275e02be2ac22c45
[ginac.git] / ginsh / ginsh_parser.yy
1 /** @file ginsh_parser.yy
2  *
3  *  Input grammar definition for ginsh.
4  *  This file must be processed with yacc/bison.
5  *
6  *  GiNaC Copyright (C) 1999 Johannes Gutenberg University Mainz, Germany
7  *
8  *  This program is free software; you can redistribute it and/or modify
9  *  it under the terms of the GNU General Public License as published by
10  *  the Free Software Foundation; either version 2 of the License, or
11  *  (at your option) any later version.
12  *
13  *  This program is distributed in the hope that it will be useful,
14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  *  GNU General Public License for more details.
17  *
18  *  You should have received a copy of the GNU General Public License
19  *  along with this program; if not, write to the Free Software
20  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
21  */
22
23
24 /*
25  *  Definitions
26  */
27
28 %{
29 #include "config.h"
30
31 #include <sys/resource.h>
32
33 #if HAVE_UNISTD_H
34 #include <sys/types.h>
35 #include <unistd.h>
36 #endif
37
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <string.h>
41
42 extern "C" {
43 #include <readline/readline.h>
44 #include <readline/history.h>
45 }
46
47 #include <map>
48 #include <string>
49 #include <stdexcept>
50
51 #include <ginac/ginac.h>
52 #include "ginsh.h"
53
54 // Original readline settings
55 static int orig_completion_append_character;
56 static char *orig_basic_word_break_characters;
57
58 // Expression stack for ", "" and """
59 static void push(const ex &e);
60 static ex exstack[3];
61
62 // Start and end time for the time() function
63 static struct rusage start_time, end_time;
64
65 // Table of functions (a multimap, because one function may appear with different
66 // numbers of parameters)
67 typedef ex (*fcnp)(const exprseq &e);
68 typedef ex (*fcnp2)(const exprseq &e, int serial);
69
70 struct fcn_desc {
71         fcn_desc() : p(NULL), num_params(0) {}
72         fcn_desc(fcnp func, int num) : p(func), num_params(num), is_ginac(false) {}
73         fcn_desc(fcnp2 func, int num, int ser) : p((fcnp)func), num_params(num), is_ginac(true), serial(ser) {}
74
75         fcnp p;         // Pointer to function
76         int num_params; // Number of parameters (0 = arbitrary)
77         bool is_ginac;  // Flag: function is GiNaC function
78         int serial;     // GiNaC function serial number (if is_ginac == true)
79 };
80
81 typedef multimap<string, fcn_desc> fcn_tab;
82 static fcn_tab fcns;
83
84 static fcn_tab::const_iterator find_function(const ex &sym, int req_params);
85
86 static ex lst2matrix(const ex &l);
87 %}
88
89 /* Tokens (T_LITERAL means a literal value returned by the parser, but not
90    of class numeric or symbol (e.g. a constant or the FAIL object)) */
91 %token T_NUMBER T_SYMBOL T_LITERAL T_DIGITS T_QUOTE T_QUOTE2 T_QUOTE3
92 %token T_EQUAL T_NOTEQ T_LESSEQ T_GREATEREQ T_MATRIX_BEGIN T_MATRIX_END
93
94 %token T_QUIT T_PRINT T_TIME T_XYZZY T_INVENTORY T_LOOK T_SCORE
95
96 /* Operator precedence and associativity */
97 %right '='
98 %left T_EQUAL T_NOTEQ
99 %left '<' '>' T_LESSEQ T_GREATEREQ
100 %left '+' '-'
101 %left '*' '/' '%'
102 %nonassoc NEG
103 %right '^'
104 %nonassoc '!'
105
106 %start input
107
108
109 /*
110  *  Grammar rules
111  */
112
113 %%
114 input   : /* empty */
115         | input line
116         ;
117
118 line    : ';'
119         | exp ';'
120                 {
121                         try {
122                                 cout << $1 << endl;
123                                 push($1);
124                         } catch (exception &e) {
125                                 cerr << e.what() << endl;
126                                 YYERROR;
127                         }
128                 }
129         | exp ':'
130                 {
131                         try {
132                                 push($1);
133                         } catch (exception &e) {
134                                 cerr << e.what() << endl;
135                                 YYERROR;
136                         }
137                 }
138         | T_PRINT '(' exp ')' ';'
139                 {
140                         try {
141                                 $3.printtree(cout);
142                         } catch (exception &e) {
143                                 cerr << e.what() << endl;
144                                 YYERROR;
145                         }
146                 }
147         | T_QUIT                {YYACCEPT;}
148         | T_XYZZY               {cout << "Nothing happens.\n";}
149         | T_INVENTORY           {cout << "You're not carrying anything.\n";}
150         | T_LOOK                {cout << "You're in a twisty little maze of passages, all alike.\n";}
151         | T_SCORE
152                 {
153                         cout << "If you were to quit now, you would score ";
154                         cout << (syms.size() > 350 ? 350 : syms.size());
155                         cout << " out of a possible 350.\n";
156                 }
157         | error ';'             {yyclearin; yyerrok;}
158         | error ':'             {yyclearin; yyerrok;}
159         ;
160
161 exp     : T_NUMBER              {$$ = $1;}
162         | T_SYMBOL              {$$ = $1.eval();}
163         | '\'' T_SYMBOL '\''    {$$ = $2;}
164         | T_LITERAL             {$$ = $1;}
165         | T_DIGITS              {$$ = $1;}
166         | T_QUOTE               {$$ = exstack[0];}
167         | T_QUOTE2              {$$ = exstack[1];}
168         | T_QUOTE3              {$$ = exstack[2];}
169         | T_TIME {getrusage(RUSAGE_SELF, &start_time);} '(' exp ')'
170                 {
171                         getrusage(RUSAGE_SELF, &end_time);
172                         $$ = (end_time.ru_utime.tv_sec - start_time.ru_utime.tv_sec) +
173                              (end_time.ru_stime.tv_sec - start_time.ru_stime.tv_sec) +
174                              double(end_time.ru_utime.tv_usec - start_time.ru_utime.tv_usec) / 1e6 +
175                              double(end_time.ru_stime.tv_usec - start_time.ru_stime.tv_usec) / 1e6;
176                 }
177         | T_SYMBOL '(' exprseq ')'
178                 {
179                         fcn_tab::const_iterator i = find_function($1, $3.nops());
180                         if (i->second.is_ginac) {
181                                 $$ = ((fcnp2)(i->second.p))(static_cast<const exprseq &>(*($3.bp)), i->second.serial);
182                         } else {
183                                 $$ = (i->second.p)(static_cast<const exprseq &>(*($3.bp)));
184                         }
185                 }
186         | T_DIGITS '=' T_NUMBER
187                 {$$ = $3; Digits = ex_to_numeric($3).to_int();}
188         | T_SYMBOL '=' exp
189                 {$$ = $3; const_cast<symbol *>(&ex_to_symbol($1))->assign($3);}
190         | exp T_EQUAL exp       {$$ = $1 == $3;}
191         | exp T_NOTEQ exp       {$$ = $1 != $3;}
192         | exp '<' exp           {$$ = $1 < $3;}
193         | exp T_LESSEQ exp      {$$ = $1 <= $3;}
194         | exp '>' exp           {$$ = $1 > $3;}
195         | exp T_GREATEREQ exp   {$$ = $1 >= $3;}
196         | exp '+' exp           {$$ = $1 + $3;}
197         | exp '-' exp           {$$ = $1 - $3;}
198         | exp '*' exp           {$$ = $1 * $3;}
199         | exp '/' exp           {$$ = $1 / $3;}
200         | exp '%' exp           {$$ = $1 % $3;}
201         | '-' exp %prec NEG     {$$ = -$2;}
202         | '+' exp %prec NEG     {$$ = $2;}
203         | exp '^' exp           {$$ = power($1, $3);}
204         | exp '!'               {$$ = factorial($1);}
205         | '(' exp ')'           {$$ = $2;}
206         | '[' list_or_empty ']' {$$ = $2;}
207         | T_MATRIX_BEGIN matrix T_MATRIX_END    {$$ = lst2matrix($2);}
208         ;
209
210 exprseq : exp                   {$$ = exprseq($1);}
211         | exprseq ',' exp       {exprseq es(static_cast<exprseq &>(*($1.bp))); $$ = es.append($3);}
212         ;
213
214 list_or_empty: /* empty */      {$$ = *new lst;}
215         | list                  {$$ = $1;}
216         ;
217
218 list    : exp                   {$$ = lst($1);}
219         | list ',' exp          {lst l(static_cast<lst &>(*($1.bp))); $$ = l.append($3);}
220         ;
221
222 matrix  : T_MATRIX_BEGIN row T_MATRIX_END               {$$ = lst($2);}
223         | matrix ',' T_MATRIX_BEGIN row T_MATRIX_END    {lst l(static_cast<lst &>(*($1.bp))); $$ = l.append($4);}
224         ;
225
226 row     : exp                   {$$ = lst($1);}
227         | row ',' exp           {lst l(static_cast<lst &>(*($1.bp))); $$ = l.append($3);}
228         ;
229
230
231 /*
232  *  Routines
233  */
234
235 %%
236 // Error print routine
237 int yyerror(char *s)
238 {
239         cerr << s << " at " << yytext << endl;
240         return 0;
241 }
242
243 // Push expression "e" onto the expression stack (for ", "" and """)
244 static void push(const ex &e)
245 {
246         exstack[2] = exstack[1];
247         exstack[1] = exstack[0];
248         exstack[0] = e;
249 }
250
251
252 /*
253  *  Built-in functions
254  */
255
256 static ex f_beta(const exprseq &e) {return gamma(e[0])*gamma(e[1])/gamma(e[0]+e[1]);}
257 static ex f_denom(const exprseq &e) {return e[0].denom();}
258 static ex f_eval1(const exprseq &e) {return e[0].eval();}
259 static ex f_evalf1(const exprseq &e) {return e[0].evalf();}
260 static ex f_expand(const exprseq &e) {return e[0].expand();}
261 static ex f_gcd(const exprseq &e) {return gcd(e[0], e[1]);}
262 static ex f_lcm(const exprseq &e) {return lcm(e[0], e[1]);}
263 static ex f_lsolve(const exprseq &e) {return lsolve(e[0], e[1]);}
264 static ex f_nops(const exprseq &e) {return e[0].nops();}
265 static ex f_normal1(const exprseq &e) {return e[0].normal();}
266 static ex f_numer(const exprseq &e) {return e[0].numer();}
267 static ex f_power(const exprseq &e) {return power(e[0], e[1]);}
268 static ex f_sqrt(const exprseq &e) {return sqrt(e[0]);}
269 static ex f_subs2(const exprseq &e) {return e[0].subs(e[1]);}
270
271 #define CHECK_ARG(num, type, fcn) if (!is_ex_of_type(e[num], type)) throw(std::invalid_argument("argument " #num " to " #fcn " must be a " #type))
272
273 static ex f_charpoly(const exprseq &e)
274 {
275         CHECK_ARG(0, matrix, charpoly);
276         CHECK_ARG(1, symbol, charpoly);
277         return ex_to_matrix(e[0]).charpoly(ex_to_symbol(e[1]));
278 }
279
280 static ex f_coeff(const exprseq &e)
281 {
282         CHECK_ARG(1, symbol, coeff);
283         CHECK_ARG(2, numeric, coeff);
284         return e[0].coeff(ex_to_symbol(e[1]), ex_to_numeric(e[2]).to_int());
285 }
286
287 static ex f_collect(const exprseq &e)
288 {
289         CHECK_ARG(1, symbol, collect);
290         return e[0].collect(ex_to_symbol(e[1]));
291 }
292
293 static ex f_content(const exprseq &e)
294 {
295         CHECK_ARG(1, symbol, content);
296         return e[0].content(ex_to_symbol(e[1]));
297 }
298
299 static ex f_degree(const exprseq &e)
300 {
301         CHECK_ARG(1, symbol, degree);
302         return e[0].degree(ex_to_symbol(e[1]));
303 }
304
305 static ex f_determinant(const exprseq &e)
306 {
307         CHECK_ARG(0, matrix, determinant);
308         return ex_to_matrix(e[0]).determinant();
309 }
310
311 static ex f_diag(const exprseq &e)
312 {
313         int dim = e.nops();
314         matrix &m = *new matrix(dim, dim);
315         for (int i=0; i<dim; i++)
316                 m.set(i, i, e.op(i));
317         return m;
318 }
319
320 static ex f_diff2(const exprseq &e)
321 {
322         CHECK_ARG(1, symbol, diff);
323         return e[0].diff(ex_to_symbol(e[1]));
324 }
325
326 static ex f_diff3(const exprseq &e)
327 {
328         CHECK_ARG(1, symbol, diff);
329         CHECK_ARG(2, numeric, diff);
330         return e[0].diff(ex_to_symbol(e[1]), ex_to_numeric(e[2]).to_int());
331 }
332
333 static ex f_divide(const exprseq &e)
334 {
335         ex q;
336         if (divide(e[0], e[1], q))
337                 return q;
338         else
339                 return *new fail();
340 }
341
342 static ex f_eval2(const exprseq &e)
343 {
344         CHECK_ARG(1, numeric, eval);
345         return e[0].eval(ex_to_numeric(e[1]).to_int());
346 }
347
348 static ex f_evalf2(const exprseq &e)
349 {
350         CHECK_ARG(1, numeric, evalf);
351         return e[0].evalf(ex_to_numeric(e[1]).to_int());
352 }
353
354 static ex f_has(const exprseq &e)
355 {
356         return e[0].has(e[1]) ? exONE() : exZERO();
357 }
358
359 static ex f_inverse(const exprseq &e)
360 {
361         CHECK_ARG(0, matrix, inverse);
362         return ex_to_matrix(e[0]).inverse();
363 }
364
365 static ex f_is(const exprseq &e)
366 {
367         CHECK_ARG(0, relational, is);
368         return (bool)ex_to_relational(e[0]) ? exONE() : exZERO();
369 }
370
371 static ex f_lcoeff(const exprseq &e)
372 {
373         CHECK_ARG(1, symbol, lcoeff);
374         return e[0].lcoeff(ex_to_symbol(e[1]));
375 }
376
377 static ex f_ldegree(const exprseq &e)
378 {
379         CHECK_ARG(1, symbol, ldegree);
380         return e[0].ldegree(ex_to_symbol(e[1]));
381 }
382
383 static ex f_normal2(const exprseq &e)
384 {
385         CHECK_ARG(1, numeric, normal);
386         return e[0].normal(ex_to_numeric(e[1]).to_int());
387 }
388
389 static ex f_op(const exprseq &e)
390 {
391         CHECK_ARG(1, numeric, op);
392         int n = ex_to_numeric(e[1]).to_int();
393         if (n < 0 || n >= e[0].nops())
394                 throw(std::out_of_range("second argument to op() is out of range"));
395         return e[0].op(n);
396 }
397
398 static ex f_prem(const exprseq &e)
399 {
400         CHECK_ARG(2, symbol, prem);
401         return prem(e[0], e[1], ex_to_symbol(e[2]));
402 }
403
404 static ex f_primpart(const exprseq &e)
405 {
406         CHECK_ARG(1, symbol, primpart);
407         return e[0].primpart(ex_to_symbol(e[1]));
408 }
409
410 static ex f_quo(const exprseq &e)
411 {
412         CHECK_ARG(2, symbol, quo);
413         return quo(e[0], e[1], ex_to_symbol(e[2]));
414 }
415
416 static ex f_rem(const exprseq &e)
417 {
418         CHECK_ARG(2, symbol, rem);
419         return rem(e[0], e[1], ex_to_symbol(e[2]));
420 }
421
422 static ex f_series2(const exprseq &e)
423 {
424         CHECK_ARG(1, symbol, series);
425         return e[0].series(ex_to_symbol(e[1]), exZERO());
426 }
427
428 static ex f_series3(const exprseq &e)
429 {
430         CHECK_ARG(1, symbol, series);
431         return e[0].series(ex_to_symbol(e[1]), e[2]);
432 }
433
434 static ex f_series4(const exprseq &e)
435 {
436         CHECK_ARG(1, symbol, series);
437         CHECK_ARG(3, numeric, series);
438         return e[0].series(ex_to_symbol(e[1]), e[2], ex_to_numeric(e[3]).to_int());
439 }
440
441 static ex f_sqrfree(const exprseq &e)
442 {
443         CHECK_ARG(1, symbol, sqrfree);
444         return sqrfree(e[0], ex_to_symbol(e[1]));
445 }
446
447 static ex f_subs3(const exprseq &e)
448 {
449         CHECK_ARG(1, lst, subs);
450         CHECK_ARG(2, lst, subs);
451         return e[0].subs(ex_to_lst(e[1]), ex_to_lst(e[2]));
452 }
453
454 static ex f_tcoeff(const exprseq &e)
455 {
456         CHECK_ARG(1, symbol, tcoeff);
457         return e[0].tcoeff(ex_to_symbol(e[1]));
458 }
459
460 static ex f_trace(const exprseq &e)
461 {
462         CHECK_ARG(0, matrix, trace);
463         return ex_to_matrix(e[0]).trace();
464 }
465
466 static ex f_transpose(const exprseq &e)
467 {
468         CHECK_ARG(0, matrix, transpose);
469         return ex_to_matrix(e[0]).transpose();
470 }
471
472 static ex f_unassign(const exprseq &e)
473 {
474         CHECK_ARG(0, symbol, unassign);
475         (const_cast<symbol *>(&ex_to_symbol(e[0])))->unassign();
476         return e[0];
477 }
478
479 static ex f_unit(const exprseq &e)
480 {
481         CHECK_ARG(1, symbol, unit);
482         return e[0].unit(ex_to_symbol(e[1]));
483 }
484
485 static ex f_dummy(const exprseq &e)
486 {
487         throw(std::logic_error("dummy function called (shouldn't happen)"));
488 }
489
490
491 /*
492  *  Add all registered GiNaC functions to ginsh
493  */
494
495 static ex f_ginac_function(const exprseq &es, int serial)
496 {
497         return function(serial, es).eval(1);
498 }
499
500 void ginsh_get_ginac_functions(void)
501 {
502         vector<registered_function_info>::const_iterator i = function::registered_functions().begin(), end = function::registered_functions().end();
503         unsigned serial = 0;
504         while (i != end) {
505                 fcns.insert(make_pair(i->name, fcn_desc(f_ginac_function, i->nparams, serial)));
506                 i++;
507                 serial++;
508         }
509 }
510
511
512 /*
513  *  Find a function given a name and number of parameters. Throw exceptions on error.
514  */
515
516 static fcn_tab::const_iterator find_function(const ex &sym, int req_params)
517 {
518         const string &name = ex_to_symbol(sym).getname();
519         typedef fcn_tab::const_iterator I;
520         pair<I, I> b = fcns.equal_range(name);
521         if (b.first == b.second)
522                 throw(std::logic_error("unknown function '" + name + "'"));
523         else {
524                 for (I i=b.first; i!=b.second; i++)
525                         if ((i->second.num_params == 0) || (i->second.num_params == req_params))
526                                 return i;
527         }
528         throw(std::logic_error("invalid number of arguments to " + name + "()"));
529 }
530
531
532 /*
533  *  Convert list of lists to matrix
534  */
535
536 static ex lst2matrix(const ex &l)
537 {
538         if (!is_ex_of_type(l, lst))
539                 throw(std::logic_error("internal error: argument to lst2matrix() is not a list"));
540
541         // Find number of rows and columns
542         int rows = l.nops(), cols = 0, i, j;
543         for (i=0; i<rows; i++)
544                 if (l.op(i).nops() > cols)
545                         cols = l.op(i).nops();
546
547         // Allocate and fill matrix
548         matrix &m = *new matrix(rows, cols);
549         for (i=0; i<rows; i++)
550                 for (j=0; j<cols; j++)
551                         if (l.op(i).nops() > j)
552                                 m.set(i, j, l.op(i).op(j));
553                         else
554                                 m.set(i, j, exZERO());
555         return m;
556 }
557
558
559 /*
560  *  Function name completion functions for readline
561  */
562
563 static char *fcn_generator(char *text, int state)
564 {
565         static int len;                         // Length of word to complete
566         static fcn_tab::const_iterator index;   // Iterator to function being currently considered
567
568         // If this is a new word to complete, initialize now
569         if (state == 0) {
570                 index = fcns.begin();
571                 len = strlen(text);
572         }
573
574         // Return the next function which partially matches
575         while (index != fcns.end()) {
576                 const char *fcn_name = index->first.c_str();
577                 index++;
578                 if (strncmp(fcn_name, text, len) == 0)
579                         return strdup(fcn_name);
580         }
581         return NULL;
582 }
583
584 static char **fcn_completion(char *text, int start, int end)
585 {
586         if (rl_line_buffer[0] == '!') {
587                 // For shell commands, revert back to filename completion
588                 rl_completion_append_character = orig_completion_append_character;
589                 rl_basic_word_break_characters = orig_basic_word_break_characters;
590                 return completion_matches(text, filename_completion_function);
591         } else {
592                 // Otherwise, complete function names
593                 rl_completion_append_character = '(';