Parsing mathematical expressions
Author
Hi. I am just wondering how I might parse mathematical expression in a scripting language. My method is to have a compiler to translate my language into "virtual opcodes" For example, consider this expression:
variable=2*2+4;
That expression would translate to the following virtual opcodes.
PUSH 2 // Pushes 2 onto the stack
PUSH 2 // Pushes 2 onto the stack
MULTIPLY // Multiplies next two items in stack and pushes result
PUSH 4 // Pushes 4 onto stack
ADD // adds next two items on stack
SETVAR variable // sets variable to value on top of stack
However, I am having a bit of difficulty. I am wondering how I might implement order of operations in parsing an expression. For example, how might I parse the following expression into virtual opcodes (following the order of operations where multiplication and division are done first)
variable=4+2*5+8/2;
Thank you for your time.
If you don't want to bother yourself with operator precedence and what not, use Lisp-like syntax, it should be much easier to parse:
(+ 4 (* 2 5) (/ 8 2))
[Edited by - Diodor on October 10, 2004 2:41:17 AM]
(+ 4 (* 2 5) (/ 8 2))
[Edited by - Diodor on October 10, 2004 2:41:17 AM]
The easiest parsing algorithm to implement manually (without using automatic parser generators such as yacc/bison) is called recursive descent. The idea is rather simple; it is basically translating a grammar written in BNF (Backus-Naur Form) directly into programming language.
Here's an example in pseudo that parses arbitrary arithmetic operations consisting of additions, subtractions, multiplications, divisions and negations. Parentheses are supported.
HTH, Johannes
Here's an example in pseudo that parses arbitrary arithmetic operations consisting of additions, subtractions, multiplications, divisions and negations. Parentheses are supported.
// peek() returns the next token from stream// get() returns and consumes the next token// require() gets the next token and throws an error if it doesn't match the token given as parameter// add_op() pushes an opcode into the list of opcodes// parse addition and subtractionparse_arithmetic(){ // parse the left hand side parse_term(); while(peek() == '+' || peek() == '-') { token op = get(); // parse the right hand side parse_term(); add_op(op == '+' ? ADD : SUB); }}// parse multiplication and divisionparse_term(){ parse_factor(); while(peek() == '*' || peek() == '/') { token op = get(); parse_term(); add_op(op == '*' ? MUL : DIV); }}// parse negation, parentheses, numbersparse_factor(){ if(peek() == '(') { get(); parse_arithmetic(); require(')'); } else if(peek() == '-') { get(); parse_factor(); add_op(NEG); } else if(peek() == number) { add_op(PUSH, get().value); }}HTH, Johannes
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
