| 1 | """ |
| 2 | This module provides a parser for symbolic equations and expressions. |
| 3 | |
| 4 | It is both safer and more powerful than using Python's eval, as one has |
| 5 | complete control over what names are used (including dynamically creating |
| 6 | variables) and how integer and floating point literals are created. |
| 7 | |
| 8 | AUTHOR: |
| 9 | -- Robert Bradshaw 2008-04 (initial version) |
| 10 | """ |
| 11 | |
| 12 | #***************************************************************************** |
| 13 | # Copyright (C) 2008 Robert Bradshaw <robertwb@math.washington.edu> |
| 14 | # |
| 15 | # Distributed under the terms of the GNU General Public License (GPL) |
| 16 | # |
| 17 | # This code is distributed in the hope that it will be useful, |
| 18 | # but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 19 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 20 | # General Public License for more details. |
| 21 | # |
| 22 | # The full text of the GPL is available at: |
| 23 | # |
| 24 | # http://www.gnu.org/licenses/ |
| 25 | #***************************************************************************** |
| 26 | |
| 27 | cdef extern from "string.h": |
| 28 | char *strchr(char *str, int ch) |
| 29 | |
| 30 | cdef extern from "Python.h": |
| 31 | object PyString_FromStringAndSize(char *v, Py_ssize_t len) |
| 32 | |
| 33 | import math |
| 34 | |
| 35 | def foo(*args, **kwds): |
| 36 | """ |
| 37 | This is a function for testing that simply returns the arguments and |
| 38 | keywords passed into it. |
| 39 | |
| 40 | EXAMPLES: |
| 41 | sage: from sage.calculus.parser import foo |
| 42 | sage: foo(1, 2, a=3) |
| 43 | ((1, 2), {'a': 3}) |
| 44 | """ |
| 45 | return args, kwds |
| 46 | |
| 47 | fuction_map = { |
| 48 | 'foo': foo, |
| 49 | 'sqrt': math.sqrt, |
| 50 | 'sin': math.sin, |
| 51 | 'cos': math.cos, |
| 52 | 'tan': math.tan, |
| 53 | } |
| 54 | |
| 55 | cdef enum token_types: |
| 56 | # leave room for ASCII character tokens such as '+' |
| 57 | INT = 128 |
| 58 | FLOAT |
| 59 | NAME |
| 60 | EOS |
| 61 | ERROR |
| 62 | |
| 63 | LESS_EQ |
| 64 | GREATER_EQ |
| 65 | NOT_EQ |
| 66 | |
| 67 | enum_map = { |
| 68 | INT: 'INT', |
| 69 | FLOAT: 'FLOAT', |
| 70 | NAME: 'NAME', |
| 71 | EOS: 'EOS', |
| 72 | ERROR: 'ERROR', |
| 73 | LESS_EQ: 'LESS_EQ', |
| 74 | GREATER_EQ: 'GREATER_EQ', |
| 75 | NOT_EQ: 'NOT_EQ', |
| 76 | } |
| 77 | |
| 78 | def token_to_str(int token): |
| 79 | """ |
| 80 | For speed reasons, tokens are integers. This function returns a string |
| 81 | representation of a given token. |
| 82 | |
| 83 | EXAMPLES: |
| 84 | sage: from sage.calculus.parser import Tokenizer, token_to_str |
| 85 | sage: t = Tokenizer("+ 2") |
| 86 | sage: token_to_str(t.next()) |
| 87 | '+' |
| 88 | sage: token_to_str(t.next()) |
| 89 | 'INT' |
| 90 | """ |
| 91 | try: |
| 92 | return enum_map[token] |
| 93 | except KeyError: |
| 94 | return chr(token) |
| 95 | |
| 96 | |
| 97 | cdef inline bint is_alphanumeric(char c): |
| 98 | return 'a' <= c < 'z' or 'A' <= c <= 'Z' or '0' <= c <= '9' or c == '_' |
| 99 | |
| 100 | cdef inline bint is_whitespace(char c): |
| 101 | return (c != 0) & (strchr(" \t\n\r", c) != NULL) |
| 102 | |
| 103 | |
| 104 | cdef class Tokenizer: |
| 105 | cdef char *s |
| 106 | cdef string_obj |
| 107 | cdef int token |
| 108 | cdef int pos |
| 109 | cdef int last_pos |
| 110 | |
| 111 | def __init__(self, s): |
| 112 | """ |
| 113 | This class takes a string and turns it into a list of tokens for use |
| 114 | by the parser. |
| 115 | |
| 116 | The tokenizer wraps a string object, to tokenize a different string |
| 117 | create a new tokenizer. |
| 118 | |
| 119 | EXAMPLES: |
| 120 | sage: from sage.calculus.parser import Tokenizer |
| 121 | sage: Tokenizer("1.5+2*3^4-sin(x)").test() |
| 122 | ['FLOAT(1.5)', '+', 'INT(2)', '*', 'INT(3)', '^', 'INT(4)', '-', 'NAME(sin)', '(', 'NAME(x)', ')'] |
| 123 | |
| 124 | The single character tokens are given by: |
| 125 | sage: Tokenizer("+-*/^(),=<>").test() |
| 126 | ['+', '-', '*', '/', '^', '(', ')', ',', '=', '<', '>'] |
| 127 | |
| 128 | Two-character comparisons accepted are: |
| 129 | sage: Tokenizer("<= >= != == **").test() |
| 130 | ['LESS_EQ', 'GREATER_EQ', 'NOT_EQ', '=', '^'] |
| 131 | |
| 132 | Integers are strings of 0-9: |
| 133 | sage: Tokenizer("1 123 9879834759873452908375013").test() |
| 134 | ['INT(1)', 'INT(123)', 'INT(9879834759873452908375013)'] |
| 135 | |
| 136 | Floating point numbers can contain a single decimal point and possibly exponential notation: |
| 137 | sage: Tokenizer("1. .01 1e3 1.e-3").test() |
| 138 | ['FLOAT(1.)', 'FLOAT(.01)', 'FLOAT(1e3)', 'FLOAT(1.e-3)'] |
| 139 | |
| 140 | Note that negative signes are not attached to the token: |
| 141 | sage: Tokenizer("-1 -1.2").test() |
| 142 | ['-', 'INT(1)', '-', 'FLOAT(1.2)'] |
| 143 | |
| 144 | Names are alphanumeric sequences not starting with a digit: |
| 145 | sage: Tokenizer("a a1 _a_24").test() |
| 146 | ['NAME(a)', 'NAME(a1)', 'NAME(_a_24)'] |
| 147 | |
| 148 | Anything else is an error: |
| 149 | sage: Tokenizer("&@!~").test() |
| 150 | ['ERROR', 'ERROR', 'ERROR', 'ERROR'] |
| 151 | |
| 152 | No attempt for correctness is made at this stage: |
| 153 | sage: Tokenizer(") )( 5e5e5").test() |
| 154 | [')', ')', '(', 'FLOAT(5e5)', 'NAME(e5)'] |
| 155 | sage: Tokenizer("[$%").test() |
| 156 | ['ERROR', 'ERROR', 'ERROR'] |
| 157 | """ |
| 158 | self.pos = 0 |
| 159 | self.last_pos = 0 |
| 160 | self.s = s |
| 161 | self.string_obj = s # so it doesn't get deallocated before self |
| 162 | |
| 163 | def test(self): |
| 164 | """ |
| 165 | This is a utility function for easy testing of the tokenizer. |
| 166 | |
| 167 | Distructively read off the tokens in self, returning a list of string |
| 168 | representations of the tokens. |
| 169 | |
| 170 | EXAMPLES: |
| 171 | sage: from sage.calculus.parser import Tokenizer |
| 172 | sage: t = Tokenizer("a b 3") |
| 173 | sage: t.test() |
| 174 | ['NAME(a)', 'NAME(b)', 'INT(3)'] |
| 175 | sage: t.test() |
| 176 | [] |
| 177 | """ |
| 178 | all = [] |
| 179 | cdef int token = self.next() |
| 180 | while token != EOS: |
| 181 | if token in [INT, FLOAT, NAME]: |
| 182 | all.append("%s(%s)" % (token_to_str(token), self.last_token_string())) |
| 183 | else: |
| 184 | all.append(token_to_str(token)) |
| 185 | token = self.next() |
| 186 | return all |
| 187 | |
| 188 | def reset(self, int pos = 0): |
| 189 | """ |
| 190 | Reset the tokenizer to a given position. |
| 191 | |
| 192 | EXAMPLES: |
| 193 | sage: from sage.calculus.parser import Tokenizer |
| 194 | sage: t = Tokenizer("a+b*c") |
| 195 | sage: t.test() |
| 196 | ['NAME(a)', '+', 'NAME(b)', '*', 'NAME(c)'] |
| 197 | sage: t.test() |
| 198 | [] |
| 199 | sage: t.reset() |
| 200 | sage: t.test() |
| 201 | ['NAME(a)', '+', 'NAME(b)', '*', 'NAME(c)'] |
| 202 | sage: t.reset(3) |
| 203 | sage: t.test() |
| 204 | ['*', 'NAME(c)'] |
| 205 | |
| 206 | No care is taken to make sure we don't jump in the middle of a token: |
| 207 | sage: t = Tokenizer("12345+a") |
| 208 | sage: t.test() |
| 209 | ['INT(12345)', '+', 'NAME(a)'] |
| 210 | sage: t.reset(2) |
| 211 | sage: t.test() |
| 212 | ['INT(345)', '+', 'NAME(a)'] |
| 213 | """ |
| 214 | self.pos = self.last_pos = pos |
| 215 | |
| 216 | cdef int find(self) except -1: |
| 217 | """ |
| 218 | This function actually does all the work, and extensively is tested above. |
| 219 | """ |
| 220 | cdef bint seen_exp, seen_decimal |
| 221 | cdef int type |
| 222 | cdef char* s = self.s |
| 223 | cdef int pos = self.pos |
| 224 | |
| 225 | # skip whitespace |
| 226 | if is_whitespace(s[pos]): |
| 227 | while is_whitespace(s[pos]): |
| 228 | pos += 1 |
| 229 | self.pos = pos |
| 230 | |
| 231 | # end of string |
| 232 | if s[pos] == 0: |
| 233 | return EOS |
| 234 | |
| 235 | # dipthongs |
| 236 | if s[pos+1] == '=': |
| 237 | if s[pos] == '<': |
| 238 | self.pos += 2 |
| 239 | return LESS_EQ |
| 240 | elif s[pos] == '>': |
| 241 | self.pos += 2 |
| 242 | return GREATER_EQ |
| 243 | elif s[pos] == '!': |
| 244 | self.pos += 2 |
| 245 | return NOT_EQ |
| 246 | elif s[pos] == '=': |
| 247 | self.pos += 2 |
| 248 | return '=' |
| 249 | |
| 250 | elif s[pos] == '*' and s[pos+1] == '*': |
| 251 | self.pos += 2 |
| 252 | return '^' |
| 253 | |
| 254 | # simple tokens |
| 255 | if strchr("+-*/^()=<>,", s[pos]): |
| 256 | type = s[pos] |
| 257 | self.pos += 1 |
| 258 | return type |
| 259 | |
| 260 | # numeric literals |
| 261 | if '0' <= s[pos] <= '9' or s[pos] == '.': |
| 262 | type = INT |
| 263 | seen_exp = False |
| 264 | seen_decimal = False |
| 265 | while True: |
| 266 | if '0' <= s[pos] <= '9': |
| 267 | pass |
| 268 | elif s[pos] == '.': |
| 269 | if seen_decimal or seen_exp: |
| 270 | self.pos = pos |
| 271 | return type |
| 272 | else: |
| 273 | type = FLOAT |
| 274 | seen_decimal = True |
| 275 | elif s[pos] == 'e' or s[pos] == 'E': |
| 276 | if seen_exp: |
| 277 | self.pos = pos |
| 278 | return type |
| 279 | else: |
| 280 | type = FLOAT |
| 281 | seen_exp = True |
| 282 | elif s[pos] == '+' or s[pos] == '-': |
| 283 | if not (seen_exp and (s[pos-1] == 'e' or s[pos-1] == 'E')): |
| 284 | self.pos = pos |
| 285 | return type |
| 286 | else: |
| 287 | self.pos = pos |
| 288 | return type |
| 289 | pos += 1 |
| 290 | |
| 291 | # name literals |
| 292 | if is_alphanumeric(s[pos]): |
| 293 | while is_alphanumeric(s[pos]): |
| 294 | pos += 1 |
| 295 | self.pos = pos |
| 296 | return NAME |
| 297 | |
| 298 | pos += 1 |
| 299 | self.pos = pos |
| 300 | return ERROR |
| 301 | |
| 302 | cpdef int next(self): |
| 303 | """ |
| 304 | Returns the next token in the string. |
| 305 | |
| 306 | EXAMPLES: |
| 307 | sage: from sage.calculus.parser import Tokenizer, token_to_str |
| 308 | sage: t = Tokenizer("a+3") |
| 309 | sage: token_to_str(t.next()) |
| 310 | 'NAME' |
| 311 | sage: token_to_str(t.next()) |
| 312 | '+' |
| 313 | sage: token_to_str(t.next()) |
| 314 | 'INT' |
| 315 | sage: token_to_str(t.next()) |
| 316 | 'EOS' |
| 317 | """ |
| 318 | while is_whitespace(self.s[self.pos]): |
| 319 | self.pos += 1 |
| 320 | self.last_pos = self.pos |
| 321 | self.token = self.find() |
| 322 | return self.token |
| 323 | |
| 324 | cpdef int last(self): |
| 325 | """ |
| 326 | Returns the last token seen. |
| 327 | |
| 328 | EXAMPLES: |
| 329 | sage: from sage.calculus.parser import Tokenizer, token_to_str |
| 330 | sage: t = Tokenizer("3a") |
| 331 | sage: token_to_str(t.next()) |
| 332 | 'INT' |
| 333 | sage: token_to_str(t.last()) |
| 334 | 'INT' |
| 335 | sage: token_to_str(t.next()) |
| 336 | 'NAME' |
| 337 | sage: token_to_str(t.last()) |
| 338 | 'NAME' |
| 339 | """ |
| 340 | return self.token |
| 341 | |
| 342 | cpdef int peek(self): |
| 343 | """ |
| 344 | Returns the next token that will be encountered, without changing |
| 345 | the state of self. |
| 346 | |
| 347 | EXAMPLES: |
| 348 | sage: from sage.calculus.parser import Tokenizer, token_to_str |
| 349 | sage: t = Tokenizer("a+b") |
| 350 | sage: token_to_str(t.peek()) |
| 351 | 'NAME' |
| 352 | sage: token_to_str(t.next()) |
| 353 | 'NAME' |
| 354 | sage: token_to_str(t.peek()) |
| 355 | '+' |
| 356 | sage: token_to_str(t.peek()) |
| 357 | '+' |
| 358 | sage: token_to_str(t.next()) |
| 359 | '+' |
| 360 | """ |
| 361 | cdef int save_pos = self.pos |
| 362 | cdef int token = self.find() |
| 363 | self.pos = save_pos |
| 364 | return token |
| 365 | |
| 366 | cpdef bint backtrack(self) except -2: |
| 367 | """ |
| 368 | Put self in such a state that the subsequent call to next() will |
| 369 | return the same as if next() had not been called. |
| 370 | |
| 371 | Currently, one can only backtrack once. |
| 372 | |
| 373 | EXAMPLES: |
| 374 | sage: from sage.calculus.parser import Tokenizer, token_to_str |
| 375 | sage: t = Tokenizer("a+b") |
| 376 | sage: token_to_str(t.next()) |
| 377 | 'NAME' |
| 378 | sage: token_to_str(t.next()) |
| 379 | '+' |
| 380 | sage: t.backtrack() # the return type is bint for performance reasons |
| 381 | False |
| 382 | sage: token_to_str(t.next()) |
| 383 | '+' |
| 384 | """ |
| 385 | if self.pos == self.last_pos and self.token != EOS: |
| 386 | raise NotImplementedError, "Can only backtrack once." |
| 387 | else: |
| 388 | self.pos = self.last_pos |
| 389 | self.token = 0 |
| 390 | |
| 391 | cpdef last_token_string(self): |
| 392 | """ |
| 393 | Return the actual contents of the last token. |
| 394 | |
| 395 | EXAMPLES: |
| 396 | sage: from sage.calculus.parser import Tokenizer, token_to_str |
| 397 | sage: t = Tokenizer("a - 1e5") |
| 398 | sage: token_to_str(t.next()) |
| 399 | 'NAME' |
| 400 | sage: t.last_token_string() |
| 401 | 'a' |
| 402 | sage: token_to_str(t.next()) |
| 403 | '-' |
| 404 | sage: token_to_str(t.next()) |
| 405 | 'FLOAT' |
| 406 | sage: t.last_token_string() |
| 407 | '1e5' |
| 408 | """ |
| 409 | return PyString_FromStringAndSize(&self.s[self.last_pos], self.pos-self.last_pos) |
| 410 | |
| 411 | |
| 412 | cdef class Parser: |
| 413 | |
| 414 | cdef integer_constructor |
| 415 | cdef float_constructor |
| 416 | cdef variable_constructor |
| 417 | cdef callable_constructor |
| 418 | cdef bint implicit_multiplication |
| 419 | |
| 420 | def __init__(self, make_int=int, make_float=float, make_var=str, make_function={}, bint implicit_multiplication=True): |
| 421 | """ |
| 422 | Create a symbolic expression parser. |
| 423 | |
| 424 | INPUT: |
| 425 | make_int -- callable object to construct integers from strings (default int) |
| 426 | make_float -- callable object to construct real numbers from strings (default float) |
| 427 | make_var -- callable object to construct variables from strings (default str) |
| 428 | this may also be a dictionary of variable names |
| 429 | make_function -- callable object to construct callable functions from strings |
| 430 | this may also be a dictionary |
| 431 | implicit_multiplication -- whether or not to accept implicit multiplication |
| 432 | |
| 433 | OUTPUT: |
| 434 | The evaluated expression tree given by the string, where the above |
| 435 | functions are used to create the leaves of this tree. |
| 436 | |
| 437 | EXAMPLES: |
| 438 | sage: from sage.calculus.parser import Parser |
| 439 | sage: p = Parser() |
| 440 | sage: p.parse("1+2") |
| 441 | 3 |
| 442 | sage: p.parse("1+2 == 3") |
| 443 | True |
| 444 | |
| 445 | sage: p = Parser(make_var=var) |
| 446 | sage: p.parse("a*b^c - 3a") |
| 447 | a*b^c - 3*a |
| 448 | |
| 449 | sage: R.<x> = QQ[] |
| 450 | sage: p = Parser(make_var = {'x': x }) |
| 451 | sage: p.parse("(x+1)^5-x") |
| 452 | x^5 + 5*x^4 + 10*x^3 + 10*x^2 + 4*x + 1 |
| 453 | sage: p.parse("(x+1)^5-x").parent() is R |
| 454 | True |
| 455 | |
| 456 | sage: p = Parser(make_float=RR, make_var=var, make_function={'foo': (lambda x: x*x+x)}) |
| 457 | sage: p.parse("1.5 + foo(b)") |
| 458 | b^2 + b + 1.50000000000000 |
| 459 | sage: p.parse("1.9").parent() |
| 460 | Real Field with 53 bits of precision |
| 461 | """ |
| 462 | self.integer_constructor = make_int |
| 463 | self.float_constructor = make_float |
| 464 | if not callable(make_var): |
| 465 | make_var = LookupNameMaker(make_var) |
| 466 | if not callable(make_function): |
| 467 | make_function = LookupNameMaker(make_function) |
| 468 | self.variable_constructor = make_var |
| 469 | self.callable_constructor = make_function |
| 470 | self.implicit_multiplication = implicit_multiplication |
| 471 | |
| 472 | cpdef parse(self, s, bint accept_eqn=True): |
| 473 | """ |
| 474 | Parse the given string. |
| 475 | |
| 476 | EXAMPLES: |
| 477 | sage: from sage.calculus.parser import Parser |
| 478 | sage: p = Parser(make_var=var) |
| 479 | sage: p.parse("E = m c^2") |
| 480 | E == c^2*m |
| 481 | """ |
| 482 | cdef Tokenizer tokens = Tokenizer(s) |
| 483 | expr = self.p_eqn(tokens) if accept_eqn else self.p_expr(tokens) |
| 484 | if tokens.next() != EOS: |
| 485 | self.parse_error(tokens) |
| 486 | return expr |
| 487 | |
| 488 | # eqn ::= expr op expr | expr |
| 489 | cpdef p_eqn(self, Tokenizer tokens): |
| 490 | """ |
| 491 | Parse an equation or expression. |
| 492 | |
| 493 | This is the top-level node called by the \code{parse} function. |
| 494 | |
| 495 | EXAMPLES: |
| 496 | sage: from sage.calculus.parser import Parser, Tokenizer |
| 497 | sage: p = Parser(make_var=var) |
| 498 | sage: p.p_eqn(Tokenizer("1+a")) |
| 499 | a + 1 |
| 500 | |
| 501 | sage: p.p_eqn(Tokenizer("a == b")) |
| 502 | a == b |
| 503 | sage: p.p_eqn(Tokenizer("a < b")) |
| 504 | a < b |
| 505 | sage: p.p_eqn(Tokenizer("a > b")) |
| 506 | a > b |
| 507 | sage: p.p_eqn(Tokenizer("a <= b")) |
| 508 | a <= b |
| 509 | sage: p.p_eqn(Tokenizer("a >= b")) |
| 510 | a >= b |
| 511 | sage: p.p_eqn(Tokenizer("a != b")) |
| 512 | a != b |
| 513 | """ |
| 514 | lhs = self.p_expr(tokens) |
| 515 | cdef int op = tokens.next() |
| 516 | if op == EOS: |
| 517 | return lhs |
| 518 | elif op == '=': |
| 519 | return lhs == self.p_expr(tokens) |
| 520 | elif op == NOT_EQ: |
| 521 | return lhs != self.p_expr(tokens) |
| 522 | elif op == '<': |
| 523 | return lhs < self.p_expr(tokens) |
| 524 | elif op == LESS_EQ: |
| 525 | return lhs <= self.p_expr(tokens) |
| 526 | elif op == '>': |
| 527 | return lhs > self.p_expr(tokens) |
| 528 | elif op == GREATER_EQ: |
| 529 | return lhs >= self.p_expr(tokens) |
| 530 | else: |
| 531 | self.parse_error(tokens, "Malformed equation") |
| 532 | |
| 533 | # expr ::= term | expr '+' term | expr '-' term |
| 534 | cpdef p_expr(self, Tokenizer tokens): |
| 535 | """ |
| 536 | Parse a list of one or more terms. |
| 537 | |
| 538 | EXAMPLES: |
| 539 | sage: from sage.calculus.parser import Parser, Tokenizer |
| 540 | sage: p = Parser(make_var=var) |
| 541 | sage: p.p_expr(Tokenizer("a+b")) |
| 542 | b + a |
| 543 | sage: p.p_expr(Tokenizer("a")) |
| 544 | a |
| 545 | sage: p.p_expr(Tokenizer("a - b + 4*c - d^2")) |
| 546 | -d^2 + 4*c - b + a |
| 547 | sage: p.p_expr(Tokenizer("a - -3")) |
| 548 | a + 3 |
| 549 | sage: p.p_expr(Tokenizer("a + 1 == b")) |
| 550 | a + 1 |
| 551 | """ |
| 552 | # Note: this is left-recursive, so we can't just recurse |
| 553 | cdef int op |
| 554 | operand1 = self.p_term(tokens) |
| 555 | op = tokens.next() |
| 556 | while op == '+' or op == '-': |
| 557 | operand2 = self.p_term(tokens) |
| 558 | if op == '+': |
| 559 | operand1 = operand1 + operand2 |
| 560 | else: |
| 561 | operand1 = operand1 - operand2 |
| 562 | op = tokens.next() |
| 563 | tokens.backtrack() |
| 564 | return operand1 |
| 565 | |
| 566 | # term ::= factor | term '*' factor | term '/' factor |
| 567 | cpdef p_term(self, Tokenizer tokens): |
| 568 | """ |
| 569 | Parse a single term (consisting of one or more factors). |
| 570 | |
| 571 | EXAMPLES: |
| 572 | sage: from sage.calculus.parser import Parser, Tokenizer |
| 573 | sage: p = Parser(make_var=var) |
| 574 | sage: p.p_term(Tokenizer("a*b")) |
| 575 | a*b |
| 576 | sage: p.p_term(Tokenizer("a * b / c * d")) |
| 577 | a*b*d/c |
| 578 | sage: p.p_term(Tokenizer("-a * b + c")) |
| 579 | -a*b |
| 580 | sage: p.p_term(Tokenizer("a*(b-c)^2")) |
| 581 | a*(b - c)^2 |
| 582 | sage: p.p_term(Tokenizer("-3a")) |
| 583 | -3*a |
| 584 | """ |
| 585 | # Note: this is left-recursive, so we can't just recurse |
| 586 | cdef int op |
| 587 | operand1 = self.p_factor(tokens) |
| 588 | op = tokens.next() |
| 589 | if op == NAME and self.implicit_multiplication: |
| 590 | op = '*' |
| 591 | tokens.backtrack() |
| 592 | while op == '*' or op == '/': |
| 593 | operand2 = self.p_factor(tokens) |
| 594 | if op == '*': |
| 595 | operand1 = operand1 * operand2 |
| 596 | else: |
| 597 | operand1 = operand1 / operand2 |
| 598 | op = tokens.next() |
| 599 | if op == NAME and self.implicit_multiplication: |
| 600 | op = '*' |
| 601 | tokens.backtrack() |
| 602 | tokens.backtrack() |
| 603 | return operand1 |
| 604 | |
| 605 | # factor ::= '+' factor | '-' factor | power |
| 606 | cpdef p_factor(self, Tokenizer tokens): |
| 607 | """ |
| 608 | Parse a single factor, which consists of any number of unary +/- |
| 609 | and a power. |
| 610 | |
| 611 | EXAMPLES: |
| 612 | sage: from sage.calculus.parser import Parser, Tokenizer |
| 613 | sage: R.<t> = ZZ[['t']] |
| 614 | sage: p = Parser(make_var={'t': t}) |
| 615 | sage: p.p_factor(Tokenizer("- -t")) |
| 616 | t |
| 617 | sage: p.p_factor(Tokenizer("- + - -t^2")) |
| 618 | -t^2 |
| 619 | sage: p.p_factor(Tokenizer("t^11 * x")) |
| 620 | t^11 |
| 621 | """ |
| 622 | cdef int token = tokens.next() |
| 623 | if token == '+': |
| 624 | return self.p_factor(tokens) |
| 625 | elif token == '-': |
| 626 | return -self.p_factor(tokens) |
| 627 | else: |
| 628 | tokens.backtrack() |
| 629 | return self.p_power(tokens) |
| 630 | |
| 631 | # power ::= atom ^ factor | atom |
| 632 | cpdef p_power(self, Tokenizer tokens): |
| 633 | """ |
| 634 | Parses a power. Note that exponentiation groups right to left. |
| 635 | |
| 636 | EXAMPLES: |
| 637 | sage: from sage.calculus.parser import Parser, Tokenizer |
| 638 | sage: R.<t> = ZZ[['t']] |
| 639 | sage: p = Parser(make_var={'t': t}) |
| 640 | sage: p.p_factor(Tokenizer("-(1+t)^-1")) |
| 641 | -1 + t - t^2 + t^3 - t^4 + t^5 - t^6 + t^7 - t^8 + t^9 - t^10 + t^11 - t^12 + t^13 - t^14 + t^15 - t^16 + t^17 - t^18 + t^19 + O(t^20) |
| 642 | sage: p.p_factor(Tokenizer("t**2")) |
| 643 | t^2 |
| 644 | sage: p.p_power(Tokenizer("2^3^2")) == 2^9 |
| 645 | True |
| 646 | """ |
| 647 | operand1 = self.p_atom(tokens) |
| 648 | cdef int token = tokens.next() |
| 649 | if token == '^': |
| 650 | operand2 = self.p_factor(tokens) |
| 651 | return operand1 ** operand2 |
| 652 | else: |
| 653 | tokens.backtrack() |
| 654 | return operand1 |
| 655 | |
| 656 | # atom ::= int | float | name | '(' expr ')' | name '(' args ')' |
| 657 | cpdef p_atom(self, Tokenizer tokens): |
| 658 | """ |
| 659 | Parse an atom. This is either a parenthesized expression, a function call, or a literal name/int/float. |
| 660 | |
| 661 | EXAMPLES: |
| 662 | sage: from sage.calculus.parser import Parser, Tokenizer |
| 663 | sage: p = Parser(make_var=var, make_function={'sin': sin}) |
| 664 | sage: p.p_atom(Tokenizer("1")) |
| 665 | 1 |
| 666 | sage: p.p_atom(Tokenizer("12")) |
| 667 | 12 |
| 668 | sage: p.p_atom(Tokenizer("12.5")) |
| 669 | 12.5 |
| 670 | sage: p.p_atom(Tokenizer("(1+a)")) |
| 671 | a + 1 |
| 672 | sage: p.p_atom(Tokenizer("(1+a)^2")) |
| 673 | a + 1 |
| 674 | sage: p.p_atom(Tokenizer("sin(1+a)")) |
| 675 | sin(a + 1) |
| 676 | sage: p = Parser(make_var=var, make_function={'foo': sage.calculus.parser.foo}) |
| 677 | sage: p.p_atom(Tokenizer("foo(a, b, key=value)")) |
| 678 | ((a, b), {'key': value}) |
| 679 | sage: p.p_atom(Tokenizer("foo()")) |
| 680 | ((), {}) |
| 681 | """ |
| 682 | cdef int token = tokens.next() |
| 683 | if token == INT: |
| 684 | return self.integer_constructor(tokens.last_token_string()) |
| 685 | elif token == FLOAT: |
| 686 | return self.float_constructor(tokens.last_token_string()) |
| 687 | elif token == NAME: |
| 688 | name = tokens.last_token_string() |
| 689 | token = tokens.next() |
| 690 | if token == '(': |
| 691 | func = self.callable_constructor(name) |
| 692 | args, kwds = self.p_args(tokens) |
| 693 | token = tokens.next() |
| 694 | if token != ')': |
| 695 | self.parse_error(tokens, "Bad function call") |
| 696 | return func(*args, **kwds) |
| 697 | else: |
| 698 | tokens.backtrack() |
| 699 | return self.variable_constructor(name) |
| 700 | elif token == '(': |
| 701 | expr = self.p_expr(tokens) |
| 702 | token = tokens.next() |
| 703 | if token != ')': |
| 704 | self.parse_error(tokens, "Mismatched parentheses") |
| 705 | return expr |
| 706 | else: |
| 707 | self.parse_error(tokens) |
| 708 | |
| 709 | # args = arg (',' arg)* | EMPTY |
| 710 | cpdef p_args(self, Tokenizer tokens): |
| 711 | """ |
| 712 | Returns a list, dict pair. |
| 713 | |
| 714 | EXAMPLES: |
| 715 | sage: from sage.calculus.parser import Parser, Tokenizer |
| 716 | sage: p = Parser() |
| 717 | sage: p.p_args(Tokenizer("1,2,a=3")) |
| 718 | ([1, 2], {'a': 3}) |
| 719 | sage: p.p_args(Tokenizer("1, 2, a = 1+5^2")) |
| 720 | ([1, 2], {'a': 26}) |
| 721 | """ |
| 722 | args = [] |
| 723 | kwds = {} |
| 724 | if tokens.peek() == ')': |
| 725 | return args, kwds |
| 726 | cdef int token = ',' |
| 727 | while token == ',': |
| 728 | arg = self.p_arg(tokens) |
| 729 | if isinstance(arg, tuple): |
| 730 | name, value = arg |
| 731 | kwds[name] = value |
| 732 | else: |
| 733 | args.append(arg) |
| 734 | token = tokens.next() |
| 735 | tokens.backtrack() |
| 736 | return args, kwds |
| 737 | |
| 738 | # arg = expr | name '=' expr |
| 739 | cpdef p_arg(self, Tokenizer tokens): |
| 740 | """ |
| 741 | Returns an expr, or a (name, expr) tuple corresponding to a single |
| 742 | function call argument. |
| 743 | |
| 744 | EXAMPLES: |
| 745 | sage: from sage.calculus.parser import Parser, Tokenizer |
| 746 | sage: p = Parser(make_var=var) |
| 747 | sage: p.p_arg(Tokenizer("a+b")) |
| 748 | b + a |
| 749 | sage: p.p_arg(Tokenizer("val=a+b")) |
| 750 | ('val', b + a) |
| 751 | """ |
| 752 | cdef int token = tokens.next() |
| 753 | if token == NAME and tokens.peek() == '=': |
| 754 | name = tokens.last_token_string() |
| 755 | tokens.next() |
| 756 | return name, self.p_expr(tokens) |
| 757 | else: |
| 758 | tokens.backtrack() |
| 759 | return self.p_expr(tokens) |
| 760 | |
| 761 | cdef parse_error(self, Tokenizer tokens, msg="Malformed expression"): |
| 762 | raise ValueError, (msg, tokens.s, tokens.pos) |
| 763 | |
| 764 | |
| 765 | cdef class LookupNameMaker: |
| 766 | cdef object names |
| 767 | cdef object fallback |
| 768 | def __init__(self, names, fallback=None): |
| 769 | """ |
| 770 | This class wraps a dictionary as a callable for use in creating names. |
| 771 | It takes a dictionary of names, and an (optional) callable to use |
| 772 | when the given name is not found in the dictionary. |
| 773 | |
| 774 | EXAMPLES: |
| 775 | sage: from sage.calculus.parser import LookupNameMaker |
| 776 | sage: maker = LookupNameMaker({'pi': pi}, var) |
| 777 | sage: maker('pi') |
| 778 | pi |
| 779 | sage: maker('pi') is pi |
| 780 | True |
| 781 | sage: maker('a') |
| 782 | a |
| 783 | """ |
| 784 | self.names = names |
| 785 | self.fallback = fallback |
| 786 | def __call__(self, name): |
| 787 | """ |
| 788 | TESTS: |
| 789 | sage: from sage.calculus.parser import LookupNameMaker |
| 790 | sage: maker = LookupNameMaker({'a': x}, str) |
| 791 | sage: maker('a') |
| 792 | x |
| 793 | sage: maker('a') is x |
| 794 | True |
| 795 | sage: maker('b') |
| 796 | 'b' |
| 797 | """ |
| 798 | try: |
| 799 | return self.names[name] |
| 800 | except KeyError: |
| 801 | if self.fallback is not None: |
| 802 | return self.fallback(name) |
| 803 | raise NameError, "Unknown variable: '%s'" % name |
| 804 | |
| 805 | |