Jump to content
  • Advertisement
Sign in to follow this  
Chocoboko

Parsing mathematical expressions

This topic is 5118 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!