Faster, better (recursive descent) expression parser.
[ginac.git] / ginac / parser / parse_binop_rhs.cpp
1 #include "ex.h"
2 #include "symbol.h"
3 #include "mul.h"
4 #include "add.h"
5 #include "power.h"
6 #include "operators.h"
7 #include <stdexcept>
8 #include <sstream>
9 #include "parser.hpp"
10 #include "lexer.hpp"
11 #include "debug.hpp"
12
13 namespace GiNaC
14 {
15
16 /// Make a sum or a product.
17 static ex make_binop_expr(const int binop, const exvector& args);
18 /// Check if the token is a binary operator. 
19 static inline bool is_binop(const int c);
20 /// Get the precedence of the pending binary operator.
21 static int get_tok_prec(const int c);
22
23 /// binoprhs: ([+*/^-] primary)*
24 ex parser::parse_binop_rhs(int expr_prec, ex& lhs)
25 {
26         exvector args;
27         args.push_back(lhs);
28         int binop = -1, orig_binop = -1;
29         bool need_sign_flip = false;
30         while (1) {
31                 // check if this is a binop
32                 if (!is_binop(token)) {
33                         if (args.size() > 1)
34                                 return make_binop_expr(orig_binop, args);
35                         else
36                                 return lhs;
37                 }
38                 
39                 // Okay, we know this is a binop.
40                 if (args.size() == 1)
41                         orig_binop = token;
42
43                 binop = token;
44
45                 // If this is a binop that binds at least as tightly as
46                 // the current binop, consume it, otherwise we are done.
47                 int tok_prec = get_tok_prec(token);
48                 if (tok_prec < expr_prec) {
49                         if (args.size() > 1)
50                                 return make_binop_expr(orig_binop, args);
51                         else 
52                                 return lhs;
53                 }
54
55                 get_next_tok();  // eat binop
56
57                 // Parse the primary expression after the binary operator.
58                 ex rhs = parse_primary();
59
60                 // If binop binds less tightly with rhs than the operator after
61                 // rhs, let the pending operator take rhs as its lhs.
62                 int next_prec = get_tok_prec(token);
63                 if (tok_prec < next_prec)
64                         rhs = parse_binop_rhs(tok_prec + 1, rhs);
65
66                 // previous operator was '+', and current one is '-'
67                 // (or vice a versa).
68                 if (need_sign_flip)
69                         rhs = - rhs;
70
71                 args.push_back(rhs);
72
73                 // Minimize the number of eval() and ctor calls. This is
74                 // crucial for a reasonable performance. If the next operator
75                 // is compatible with the pending one (or the same) don't create
76                 // the expression and continue collecting operands instead.
77                 if (binop == token)
78                         continue;
79                 else if (binop == '+' && token == '-') {
80                         need_sign_flip = token != orig_binop;
81                         continue;
82                 } else if (binop == '-' && token == '+') {
83                         need_sign_flip = token != orig_binop;
84                         continue;
85                 } else { 
86                         if (args.size() <= 1)
87                                 bug("binop has " << args.size() << " arguments, expected >= 2");
88                         lhs = make_binop_expr(orig_binop, args);
89                         args.clear();
90                         args.push_back(lhs);
91                 }
92         }
93 }
94
95 extern numeric* _num_1_p;
96
97 static ex make_minus_expr(const exvector& args)
98 {
99         exvector rest_args;
100         rest_args.reserve(args.size() - 1);
101         std::copy(args.begin() + 1, args.end(), std::back_inserter(rest_args));
102         ex rest_base = (new add(rest_args))->setflag(status_flags::dynallocated);
103         ex rest = (new mul(rest_base, *_num_1_p))->setflag(status_flags::dynallocated);
104         ex ret = (new add(args[0], rest))->setflag(status_flags::dynallocated);
105         return ret;
106 }
107
108 static ex make_divide_expr(const exvector& args)
109 {
110         exvector rest_args;
111         rest_args.reserve(args.size() - 1);
112         std::copy(args.begin() + 1, args.end(), std::back_inserter(rest_args));
113         ex rest_base = (new mul(rest_args))->setflag(status_flags::dynallocated);
114         ex rest = pow(rest_base, *_num_1_p);
115         return (new mul(args[0], rest))->setflag(status_flags::dynallocated);
116 }
117
118 static ex make_binop_expr(const int binop, const exvector& args)
119 {
120         switch (binop) {
121                 case '+':
122                         return (new add(args))->setflag(status_flags::dynallocated);
123                 case '-':
124                         return make_minus_expr(args);
125                 case '*':
126                         return (new mul(args))->setflag(status_flags::dynallocated);
127                 case '/':
128                         return make_divide_expr(args);
129                 case '^':
130                         if (args.size() != 2)
131                                 throw std::invalid_argument(
132                                                 std::string(__func__) 
133                                                 + ": power should have exactly 2 operands");
134                         return pow(args[0], args[1]);
135                 default:
136                         throw std::invalid_argument(
137                                         std::string(__func__) 
138                                         + ": invalid binary operation: " 
139                                         + char(binop));
140         }
141 }
142
143 static inline bool is_binop(const int c)
144 {
145         switch (c) {
146                 case '+':
147                 case '-':
148                 case '*':
149                 case '/':
150                 case '^':
151                         return true;
152                 default:
153                         return false;
154         }
155 }
156
157 /// Get the precedence of the pending binary operator.
158 static int get_tok_prec(const int c)
159 {
160         switch (c) {
161                 case '+':
162                 case '-':
163                         return 20;
164                 case '*':
165                 case '/':
166                         return 40;
167                 case '^':
168                         return 60;
169                 default:
170                         return -1;
171                         // means 'this is not a binary operator'
172         }
173 }
174
175 } // namespace GiNaC
176