Sign in to follow this  

Parsing mathematical expressions

This topic is 4817 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.


// 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 subtraction
parse_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 division
parse_term()
{
parse_factor();
while(peek() == '*' || peek() == '/')
{
token op = get();
parse_term();
add_op(op == '*' ? MUL : DIV);
}
}

// parse negation, parentheses, numbers
parse_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

Share this post


Link to post
Share on other sites

This topic is 4817 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this