xref: /haiku/src/kits/shared/ExpressionParser.cpp (revision cbe0a0c436162d78cc3f92a305b64918c839d079)
1 /*
2  * Copyright 2006-2012 Haiku, Inc. All Rights Reserved.
3  * Distributed under the terms of the MIT License.
4  *
5  * Authors:
6  *		Stephan Aßmus <superstippi@gmx.de>
7  *		John Scipione <jscipione@gmail.com>
8  *		Ingo Weinhold <bonefish@cs.tu-berlin.de>
9  */
10 
11 #include <ExpressionParser.h>
12 
13 #include <ctype.h>
14 #include <math.h>
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <strings.h>
18 
19 #include <m_apm.h>
20 
21 
22 static const int32 kMaxDecimalPlaces = 32;
23 
24 
25 enum {
26 	TOKEN_NONE					= 0,
27 	TOKEN_IDENTIFIER,
28 	TOKEN_CONSTANT,
29 
30 	TOKEN_END_OF_LINE			= '\n',
31 
32 	TOKEN_PLUS					= '+',
33 	TOKEN_MINUS					= '-',
34 
35 	TOKEN_STAR					= '*',
36 	TOKEN_SLASH					= '/',
37 	TOKEN_MODULO				= '%',
38 
39 	TOKEN_POWER					= '^',
40 	TOKEN_FACTORIAL				= '!',
41 
42 	TOKEN_OPENING_BRACKET		= '(',
43 	TOKEN_CLOSING_BRACKET		= ')',
44 
45 	TOKEN_AND					= '&',
46 	TOKEN_OR					= '|',
47 	TOKEN_NOT					= '~'
48 };
49 
50 
51 struct ExpressionParser::Token {
52 	Token()
53 		: string(""),
54 		  type(TOKEN_NONE),
55 		  value(0),
56 		  position(0)
57 	{
58 	}
59 
60 	Token(const Token& other)
61 		: string(other.string),
62 		  type(other.type),
63 		  value(other.value),
64 		  position(other.position)
65 	{
66 	}
67 
68 	Token(const char* string, int32 length, int32 position, int32 type)
69 		: string(string, length),
70 		  type(type),
71 		  value(0),
72 		  position(position)
73 	{
74 	}
75 
76 	Token& operator=(const Token& other)
77 	{
78 		string = other.string;
79 		type = other.type;
80 		value = other.value;
81 		position = other.position;
82 		return *this;
83 	}
84 
85 	BString		string;
86 	int32		type;
87 	MAPM		value;
88 
89 	int32		position;
90 };
91 
92 
93 class ExpressionParser::Tokenizer {
94  public:
95 	Tokenizer()
96 		: fString(""),
97 		  fCurrentChar(NULL),
98 		  fCurrentToken(),
99 		  fReuseToken(false),
100 		  fHexSupport(false)
101 	{
102 	}
103 
104 	void SetSupportHexInput(bool enabled)
105 	{
106 		fHexSupport = enabled;
107 	}
108 
109 	void SetTo(const char* string)
110 	{
111 		fString = string;
112 		fCurrentChar = fString.String();
113 		fCurrentToken = Token();
114 		fReuseToken = false;
115 	}
116 
117 	const Token& NextToken()
118 	{
119 		if (fCurrentToken.type == TOKEN_END_OF_LINE)
120 			return fCurrentToken;
121 
122 		if (fReuseToken) {
123 			fReuseToken = false;
124 //printf("next token (recycled): '%s'\n", fCurrentToken.string.String());
125 			return fCurrentToken;
126 		}
127 
128 		while (*fCurrentChar != 0 && isspace(*fCurrentChar))
129 			fCurrentChar++;
130 
131 		if (*fCurrentChar == 0)
132 			return fCurrentToken = Token("", 0, _CurrentPos(), TOKEN_END_OF_LINE);
133 
134 		bool decimal = *fCurrentChar == '.' || *fCurrentChar == ',';
135 
136 		if (decimal || isdigit(*fCurrentChar)) {
137 			if (fHexSupport && *fCurrentChar == '0' && fCurrentChar[1] == 'x')
138 				return _ParseHexNumber();
139 
140 			BString temp;
141 
142 			const char* begin = fCurrentChar;
143 
144 			// optional digits before the comma
145 			while (isdigit(*fCurrentChar)) {
146 				temp << *fCurrentChar;
147 				fCurrentChar++;
148 			}
149 
150 			// optional post comma part
151 			// (required if there are no digits before the comma)
152 			if (*fCurrentChar == '.' || *fCurrentChar == ',') {
153 				temp << '.';
154 				fCurrentChar++;
155 
156 				// optional post comma digits
157 				while (isdigit(*fCurrentChar)) {
158 					temp << *fCurrentChar;
159 					fCurrentChar++;
160 				}
161 			}
162 
163 			// optional exponent part
164 			if (*fCurrentChar == 'E') {
165 				temp << *fCurrentChar;
166 				fCurrentChar++;
167 
168 				// optional exponent sign
169 				if (*fCurrentChar == '+' || *fCurrentChar == '-') {
170 					temp << *fCurrentChar;
171 					fCurrentChar++;
172 				}
173 
174 				// required exponent digits
175 				if (!isdigit(*fCurrentChar)) {
176 					throw ParseException("missing exponent in constant",
177 						fCurrentChar - begin);
178 				}
179 
180 				while (isdigit(*fCurrentChar)) {
181 					temp << *fCurrentChar;
182 					fCurrentChar++;
183 				}
184 			}
185 
186 			int32 length = fCurrentChar - begin;
187 			BString test = temp;
188 			test << "&_";
189 			double value;
190 			char t[2];
191 			int32 matches = sscanf(test.String(), "%lf&%s", &value, t);
192 			if (matches != 2) {
193 				throw ParseException("error in constant",
194 					_CurrentPos() - length);
195 			}
196 
197 			fCurrentToken = Token(begin, length, _CurrentPos() - length,
198 				TOKEN_CONSTANT);
199 			fCurrentToken.value = temp.String();
200 		} else if (isalpha(*fCurrentChar) && *fCurrentChar != 'x') {
201 			const char* begin = fCurrentChar;
202 			while (*fCurrentChar != 0 && (isalpha(*fCurrentChar)
203 				|| isdigit(*fCurrentChar))) {
204 				fCurrentChar++;
205 			}
206 			int32 length = fCurrentChar - begin;
207 			fCurrentToken = Token(begin, length, _CurrentPos() - length,
208 				TOKEN_IDENTIFIER);
209 		} else if (strncmp(fCurrentChar, "π", 2) == 0) {
210 			fCurrentToken = Token(fCurrentChar, 2, _CurrentPos() - 1,
211 				TOKEN_IDENTIFIER);
212 			fCurrentChar += 2;
213 		} else {
214 			int32 type = TOKEN_NONE;
215 
216 			switch (*fCurrentChar) {
217 				case TOKEN_PLUS:
218 				case TOKEN_MINUS:
219 				case TOKEN_STAR:
220 				case TOKEN_SLASH:
221 				case TOKEN_MODULO:
222 				case TOKEN_POWER:
223 				case TOKEN_FACTORIAL:
224 				case TOKEN_OPENING_BRACKET:
225 				case TOKEN_CLOSING_BRACKET:
226 				case TOKEN_AND:
227 				case TOKEN_OR:
228 				case TOKEN_NOT:
229 				case TOKEN_END_OF_LINE:
230 					type = *fCurrentChar;
231 					break;
232 
233 				case '\\':
234 				case ':':
235 				type = TOKEN_SLASH;
236 					break;
237 
238 				case 'x':
239 					if (!fHexSupport) {
240 						type = TOKEN_STAR;
241 						break;
242 					}
243 					// fall through
244 
245 				default:
246 					throw ParseException("unexpected character", _CurrentPos());
247 			}
248 			fCurrentToken = Token(fCurrentChar, 1, _CurrentPos(), type);
249 			fCurrentChar++;
250 		}
251 
252 //printf("next token: '%s'\n", fCurrentToken.string.String());
253 		return fCurrentToken;
254 	}
255 
256 	void RewindToken()
257 	{
258 		fReuseToken = true;
259 	}
260 
261  private:
262 	static bool _IsHexDigit(char c)
263 	{
264 		return isdigit(c) || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F');
265 	}
266 
267 	Token& _ParseHexNumber()
268 	{
269 		const char* begin = fCurrentChar;
270 		fCurrentChar += 2;
271 			// skip "0x"
272 
273 		if (!_IsHexDigit(*fCurrentChar))
274 			throw ParseException("expected hex digit", _CurrentPos());
275 
276 		fCurrentChar++;
277 		while (_IsHexDigit(*fCurrentChar))
278 			fCurrentChar++;
279 
280 		int32 length = fCurrentChar - begin;
281 		fCurrentToken = Token(begin, length, _CurrentPos() - length,
282 			TOKEN_CONSTANT);
283 
284 		// MAPM has no conversion from long long, so we need to improvise.
285 		uint64 value = strtoll(fCurrentToken.string.String(), NULL, 0);
286 		if (value <= 0x7fffffff) {
287 			fCurrentToken.value = (long)value;
288 		} else {
289 			fCurrentToken.value = (int)(value >> 60);
290 			fCurrentToken.value *= 1 << 30;
291 			fCurrentToken.value += (int)((value >> 30) & 0x3fffffff);
292 			fCurrentToken.value *= 1 << 30;
293 			fCurrentToken.value += (int)(value& 0x3fffffff);
294 		}
295 
296 		return fCurrentToken;
297 	}
298 
299 	int32 _CurrentPos() const
300 	{
301 		return fCurrentChar - fString.String();
302 	}
303 
304 	BString		fString;
305 	const char*	fCurrentChar;
306 	Token		fCurrentToken;
307 	bool		fReuseToken;
308 	bool		fHexSupport;
309 };
310 
311 
312 ExpressionParser::ExpressionParser()
313 	:	fTokenizer(new Tokenizer()),
314 		fDegreeMode(false)
315 {
316 }
317 
318 
319 ExpressionParser::~ExpressionParser()
320 {
321 	delete fTokenizer;
322 }
323 
324 
325 bool
326 ExpressionParser::DegreeMode()
327 {
328 	return fDegreeMode;
329 }
330 
331 
332 void
333 ExpressionParser::SetDegreeMode(bool degrees)
334 {
335 	fDegreeMode = degrees;
336 }
337 
338 
339 void
340 ExpressionParser::SetSupportHexInput(bool enabled)
341 {
342 	fTokenizer->SetSupportHexInput(enabled);
343 }
344 
345 
346 BString
347 ExpressionParser::Evaluate(const char* expressionString)
348 {
349 	fTokenizer->SetTo(expressionString);
350 
351 	MAPM value = _ParseBinary();
352 	Token token = fTokenizer->NextToken();
353 	if (token.type != TOKEN_END_OF_LINE)
354 		throw ParseException("parse error", token.position);
355 
356 	if (value == 0)
357 		return BString("0");
358 
359 	char* buffer = value.toFixPtStringExp(kMaxDecimalPlaces, '.', 0, 0);
360 	if (buffer == NULL)
361 		throw ParseException("out of memory", 0);
362 
363 	// remove surplus zeros
364 	int32 lastChar = strlen(buffer) - 1;
365 	if (strchr(buffer, '.')) {
366 		while (buffer[lastChar] == '0')
367 			lastChar--;
368 		if (buffer[lastChar] == '.')
369 			lastChar--;
370 	}
371 
372 	BString result(buffer, lastChar + 1);
373 	free(buffer);
374 	return result;
375 }
376 
377 
378 int64
379 ExpressionParser::EvaluateToInt64(const char* expressionString)
380 {
381 	fTokenizer->SetTo(expressionString);
382 
383 	MAPM value = _ParseBinary();
384 	Token token = fTokenizer->NextToken();
385 	if (token.type != TOKEN_END_OF_LINE)
386 		throw ParseException("parse error", token.position);
387 
388 	char buffer[128];
389 	value.toIntegerString(buffer);
390 
391 	return strtoll(buffer, NULL, 0);
392 }
393 
394 
395 double
396 ExpressionParser::EvaluateToDouble(const char* expressionString)
397 {
398 	fTokenizer->SetTo(expressionString);
399 
400 	MAPM value = _ParseBinary();
401 	Token token = fTokenizer->NextToken();
402 	if (token.type != TOKEN_END_OF_LINE)
403 		throw ParseException("parse error", token.position);
404 
405 	char buffer[1024];
406 	value.toString(buffer, sizeof(buffer) - 4);
407 
408 	return strtod(buffer, NULL);
409 }
410 
411 
412 MAPM
413 ExpressionParser::_ParseBinary()
414 {
415 	return _ParseSum();
416 	// binary operation appearantly not supported by m_apm library,
417 	// should not be too hard to implement though....
418 
419 //	double value = _ParseSum();
420 //
421 //	while (true) {
422 //		Token token = fTokenizer->NextToken();
423 //		switch (token.type) {
424 //			case TOKEN_AND:
425 //				value = (uint64)value & (uint64)_ParseSum();
426 //				break;
427 //			case TOKEN_OR:
428 //				value = (uint64)value | (uint64)_ParseSum();
429 //				break;
430 //
431 //			default:
432 //				fTokenizer->RewindToken();
433 //				return value;
434 //		}
435 //	}
436 }
437 
438 
439 MAPM
440 ExpressionParser::_ParseSum()
441 {
442 	// TODO: check isnan()...
443 	MAPM value = _ParseProduct();
444 
445 	while (true) {
446 		Token token = fTokenizer->NextToken();
447 		switch (token.type) {
448 			case TOKEN_PLUS:
449 				value = value + _ParseProduct();
450 				break;
451 			case TOKEN_MINUS:
452 				value = value - _ParseProduct();
453 				break;
454 
455 			default:
456 				fTokenizer->RewindToken();
457 				return _ParseFactorial(value);
458 		}
459 	}
460 }
461 
462 
463 MAPM
464 ExpressionParser::_ParseProduct()
465 {
466 	// TODO: check isnan()...
467 	MAPM value = _ParsePower();
468 
469 	while (true) {
470 		Token token = fTokenizer->NextToken();
471 		switch (token.type) {
472 			case TOKEN_STAR:
473 				value = value * _ParsePower();
474 				break;
475 			case TOKEN_SLASH: {
476 				MAPM rhs = _ParsePower();
477 				if (rhs == MAPM(0))
478 					throw ParseException("division by zero", token.position);
479 				value = value / rhs;
480 				break;
481 			}
482 			case TOKEN_MODULO: {
483 				MAPM rhs = _ParsePower();
484 				if (rhs == MAPM(0))
485 					throw ParseException("modulo by zero", token.position);
486 				value = value % rhs;
487 				break;
488 			}
489 
490 			default:
491 				fTokenizer->RewindToken();
492 				return _ParseFactorial(value);
493 		}
494 	}
495 }
496 
497 
498 MAPM
499 ExpressionParser::_ParsePower()
500 {
501 	MAPM value = _ParseUnary();
502 
503 	while (true) {
504 		Token token = fTokenizer->NextToken();
505 		if (token.type != TOKEN_POWER) {
506 			fTokenizer->RewindToken();
507 			return _ParseFactorial(value);
508 		}
509 		value = value.pow(_ParseUnary());
510 	}
511 }
512 
513 
514 MAPM
515 ExpressionParser::_ParseUnary()
516 {
517 	Token token = fTokenizer->NextToken();
518 	if (token.type == TOKEN_END_OF_LINE)
519 		throw ParseException("unexpected end of expression", token.position);
520 
521 	switch (token.type) {
522 		case TOKEN_PLUS:
523 			return _ParseUnary();
524 		case TOKEN_MINUS:
525 			return -_ParseUnary();
526 // TODO: Implement !
527 //		case TOKEN_NOT:
528 //			return ~(uint64)_ParseUnary();
529 
530 		case TOKEN_IDENTIFIER:
531 			return _ParseFunction(token);
532 
533 		default:
534 			fTokenizer->RewindToken();
535 			return _ParseAtom();
536 	}
537 
538 	return MAPM(0);
539 }
540 
541 
542 struct Function {
543 	const char*	name;
544 	int			argumentCount;
545 	void*		function;
546 	MAPM		value;
547 };
548 
549 
550 void
551 ExpressionParser::_InitArguments(MAPM values[], int32 argumentCount)
552 {
553 	_EatToken(TOKEN_OPENING_BRACKET);
554 
555 	for (int32 i = 0; i < argumentCount; i++)
556 		values[i] = _ParseBinary();
557 
558 	_EatToken(TOKEN_CLOSING_BRACKET);
559 }
560 
561 
562 MAPM
563 ExpressionParser::_ParseFunction(const Token& token)
564 {
565 	if (token.string == "e")
566 		return _ParseFactorial(MAPM(MM_E));
567 	else if (token.string.ICompare("pi") == 0 || token.string == "π")
568 		return _ParseFactorial(MAPM(MM_PI));
569 
570 	// hard coded cases for different count of arguments
571 	// supports functions with 3 arguments at most
572 
573 	MAPM values[3];
574 
575 	if (strcasecmp("abs", token.string.String()) == 0) {
576 		_InitArguments(values, 1);
577 		return _ParseFactorial(values[0].abs());
578 	} else if (strcasecmp("acos", token.string.String()) == 0) {
579 		_InitArguments(values, 1);
580 		if (fDegreeMode)
581 			values[0] = values[0] * MM_PI / 180;
582 
583 		if (values[0] < -1 || values[0] > 1)
584 			throw ParseException("out of domain", token.position);
585 
586 		return _ParseFactorial(values[0].acos());
587 	} else if (strcasecmp("asin", token.string.String()) == 0) {
588 		_InitArguments(values, 1);
589 		if (fDegreeMode)
590 			values[0] = values[0] * MM_PI / 180;
591 
592 		if (values[0] < -1 || values[0] > 1)
593 			throw ParseException("out of domain", token.position);
594 
595 		return _ParseFactorial(values[0].asin());
596 	} else if (strcasecmp("atan", token.string.String()) == 0) {
597 		_InitArguments(values, 1);
598 		if (fDegreeMode)
599 			values[0] = values[0] * MM_PI / 180;
600 
601 		return _ParseFactorial(values[0].atan());
602 	} else if (strcasecmp("atan2", token.string.String()) == 0) {
603 		_InitArguments(values, 2);
604 
605 		if (fDegreeMode) {
606 			values[0] = values[0] * MM_PI / 180;
607 			values[1] = values[1] * MM_PI / 180;
608 		}
609 
610 		return _ParseFactorial(values[0].atan2(values[1]));
611 	} else if (strcasecmp("cbrt", token.string.String()) == 0) {
612 		_InitArguments(values, 1);
613 		return _ParseFactorial(values[0].cbrt());
614 	} else if (strcasecmp("ceil", token.string.String()) == 0) {
615 		_InitArguments(values, 1);
616 		return _ParseFactorial(values[0].ceil());
617 	} else if (strcasecmp("cos", token.string.String()) == 0) {
618 		_InitArguments(values, 1);
619 		if (fDegreeMode)
620 			values[0] = values[0] * MM_PI / 180;
621 
622 		return _ParseFactorial(values[0].cos());
623 	} else if (strcasecmp("cosh", token.string.String()) == 0) {
624 		_InitArguments(values, 1);
625 		// This function always uses radians
626 		return _ParseFactorial(values[0].cosh());
627 	} else if (strcasecmp("exp", token.string.String()) == 0) {
628 		_InitArguments(values, 1);
629 		return _ParseFactorial(values[0].exp());
630 	} else if (strcasecmp("floor", token.string.String()) == 0) {
631 		_InitArguments(values, 1);
632 		return _ParseFactorial(values[0].floor());
633 	} else if (strcasecmp("ln", token.string.String()) == 0) {
634 		_InitArguments(values, 1);
635 		if (values[0] <= 0)
636 			throw ParseException("out of domain", token.position);
637 
638 		return _ParseFactorial(values[0].log());
639 	} else if (strcasecmp("log", token.string.String()) == 0) {
640 		_InitArguments(values, 1);
641 		if (values[0] <= 0)
642 			throw ParseException("out of domain", token.position);
643 
644 		return _ParseFactorial(values[0].log10());
645 	} else if (strcasecmp("pow", token.string.String()) == 0) {
646 		_InitArguments(values, 2);
647 		return _ParseFactorial(values[0].pow(values[1]));
648 	} else if (strcasecmp("sin", token.string.String()) == 0) {
649 		_InitArguments(values, 1);
650 		if (fDegreeMode)
651 			values[0] = values[0] * MM_PI / 180;
652 
653 		return _ParseFactorial(values[0].sin());
654 	} else if (strcasecmp("sinh", token.string.String()) == 0) {
655 		_InitArguments(values, 1);
656 		// This function always uses radians
657 		return _ParseFactorial(values[0].sinh());
658 	} else if (strcasecmp("sqrt", token.string.String()) == 0) {
659 		_InitArguments(values, 1);
660 		if (values[0] < 0)
661 			throw ParseException("out of domain", token.position);
662 
663 		return _ParseFactorial(values[0].sqrt());
664 	} else if (strcasecmp("tan", token.string.String()) == 0) {
665 		_InitArguments(values, 1);
666 		if (fDegreeMode)
667 			values[0] = values[0] * MM_PI / 180;
668 
669 		MAPM divided_by_half_pi = values[0] / MM_HALF_PI;
670 		if (divided_by_half_pi.is_integer() && divided_by_half_pi.is_odd())
671 			throw ParseException("out of domain", token.position);
672 
673 		return _ParseFactorial(values[0].tan());
674 	} else if (strcasecmp("tanh", token.string.String()) == 0) {
675 		_InitArguments(values, 1);
676 		// This function always uses radians
677 		return _ParseFactorial(values[0].tanh());
678 	}
679 
680 	throw ParseException("unknown identifier", token.position);
681 }
682 
683 
684 MAPM
685 ExpressionParser::_ParseAtom()
686 {
687 	Token token = fTokenizer->NextToken();
688 	if (token.type == TOKEN_END_OF_LINE)
689 		throw ParseException("unexpected end of expression", token.position);
690 
691 	if (token.type == TOKEN_CONSTANT)
692 		return _ParseFactorial(token.value);
693 
694 	fTokenizer->RewindToken();
695 
696 	_EatToken(TOKEN_OPENING_BRACKET);
697 
698 	MAPM value = _ParseBinary();
699 
700 	_EatToken(TOKEN_CLOSING_BRACKET);
701 
702 	return _ParseFactorial(value);
703 }
704 
705 
706 MAPM
707 ExpressionParser::_ParseFactorial(MAPM value)
708 {
709 	if (fTokenizer->NextToken().type == TOKEN_FACTORIAL) {
710 		fTokenizer->RewindToken();
711 		_EatToken(TOKEN_FACTORIAL);
712 		if (value < 1000)
713 			return value.factorial();
714 		else {
715 			// Use Stirling's approximation (9 term expansion)
716 			// http://en.wikipedia.org/wiki/Stirling%27s_approximation
717 			// http://www.wolframalpha.com/input/?i=stirling%27s+series
718 			// all constants must fit in a signed long for MAPM
719 			// (LONG_MAX = 2147483647)
720 			return value.pow(value) / value.exp()
721 				* (MAPM(2) * MAPM(MM_PI) * value).sqrt()
722 				* (MAPM(1) + (MAPM(1) / (MAPM(12) * value))
723 					+ (MAPM(1) / (MAPM(288) * value.pow(2)))
724 					- (MAPM(139) / (MAPM(51840) * value.pow(3)))
725 					- (MAPM(571) / (MAPM(2488320) * value.pow(4)))
726 					+ (MAPM(163879) / (MAPM(209018880) * value.pow(5)))
727 						// 2147483647 * 35 + 84869155 = 75246796800
728 					+ (MAPM(5246819) / ((MAPM(2147483647) * MAPM(35)
729 						+ MAPM(84869155)) * value.pow(6)))
730 						// 2147483647 * 420 + 1018429860 = 902961561600
731 					- (MAPM(534703531) / ((MAPM(2147483647) * MAPM(420)
732 						+ MAPM(1018429860)) * value.pow(7)))
733 						// 2147483647 * 2 + 188163965 = 4483131259
734 						// 2147483647 * 40366 + 985018798 = 86686309913600
735 					- ((MAPM(2147483647) * MAPM(2) + MAPM(188163965))
736 						/ ((MAPM(2147483647) * MAPM(40366) + MAPM(985018798))
737 							* value.pow(8)))
738 						// 2147483647 * 201287 + 1380758682 = 432261921612371
739 						// 2147483647 * 239771232 + 1145740896
740 						// = 514904800886784000
741 					+ ((MAPM(2147483647) * MAPM(201287) + MAPM(1380758682))
742 						/ ((MAPM(2147483647) * MAPM(239771232)
743 								+ MAPM(1145740896))
744 							* value.pow(9))));
745 		}
746 	}
747 
748 	fTokenizer->RewindToken();
749 	return value;
750 }
751 
752 
753 void
754 ExpressionParser::_EatToken(int32 type)
755 {
756 	Token token = fTokenizer->NextToken();
757 	if (token.type != type) {
758 		BString expected;
759 		switch (type) {
760 			case TOKEN_IDENTIFIER:
761 				expected = "an identifier";
762 				break;
763 
764 			case TOKEN_CONSTANT:
765 				expected = "a constant";
766 				break;
767 
768 			case TOKEN_PLUS:
769 			case TOKEN_MINUS:
770 			case TOKEN_STAR:
771 			case TOKEN_MODULO:
772 			case TOKEN_POWER:
773 			case TOKEN_FACTORIAL:
774 			case TOKEN_OPENING_BRACKET:
775 			case TOKEN_CLOSING_BRACKET:
776 			case TOKEN_AND:
777 			case TOKEN_OR:
778 			case TOKEN_NOT:
779 				expected << "'" << (char)type << "'";
780 				break;
781 
782 			case TOKEN_SLASH:
783 				expected = "'/', '\\', or ':'";
784 				break;
785 
786 			case TOKEN_END_OF_LINE:
787 				expected = "'\\n'";
788 				break;
789 		}
790 		BString temp;
791 		temp << "Expected " << expected.String() << " got '" << token.string << "'";
792 		throw ParseException(temp.String(), token.position);
793 	}
794 }
795