Parsing Expressions from Token Stream

Question

I'm trying to parse expressions for a simple scripting language, but I'm confused. Right now, only numbers and string literals can be parsed as an expression:

int x = 5; double y = 3.4; str t = "this is a string"; 

However, I am confused in the analysis of more complex expressions:

 int a = 5 + 9; int x = (5 + a) - (a ^ 2); 

I think I would execute it like this:

 do { // no clue what I would do here? if (current token is a semi colon) break; } while (true); 

Any help would be great, I don't know where to start. Thanks.

EDIT: My parser is a recursive descent parser.

My expression "class" is as follows:

 typedef struct s_Expression { char type; Token *value; struct s_Expression *leftHand; char operand; struct s_Expression *rightHand; } ExpressionNode; 

Someone mentioned that a recursive descent parser is able to parse expressions without making infix, postfix. Preferably, I would like the expression to be as follows:

For instance:

 int x = (5 + 5) - (a / b); 

The following will be analyzed: Note: this is not valid C, this is just some pseudo code, to get my point is simple :)

 ExpressionNode lh; lh.leftHand = new ExpressionNode(5); lh.operand = '+' lh.rightHand = new ExpressionNode(5); ExpressionNode rh; rh.leftHand = new ExpressionNode(a); rh.operand = '/'; rh.rightHand = new ExpressionNode(b); ExpressionNode res; res.leftHand = lh; res.operand = '-'; res.rightHand = rh; 

I asked the question quite late, so I'm sorry if I did not understand and that I completely forgot what my original goal was.

Answer 1

The method I used is parsing operator priority .

 parse_expression_1 (lhs, min_precedence) lookahead := peek next token while lookahead is a binary operator whose precedence is >= min_precedence op := lookahead advance to next token rhs := parse_primary () lookahead := peek next token while lookahead is a binary operator whose precedence is greater than op's, or a right-associative operator whose precedence is equal to op's rhs := parse_expression_1 (rhs, lookahead precedence) lookahead := peek next token lhs := the result of applying op with operands lhs and rhs return lhs 

Answer 2

There are several ways to do this. One of them, which I used in the past, is to read the input line (i.e. the code of the programming language) and convert the expressions from the infix to the backtick. Here's a really good post on how to do this:

http://andreinc.net/2010/10/05/converting-infix-to-rpn-shunting-yard-algorithm/

Note that = also an operator, so your parsing should really include the entire code file, not just specific expressions.

After back polishing, expressions are very easy to evaluate. You simply put the stack, storing the operands until you click on the operator. Execute as many operands from the stack as the operator needs and perform your operation.

Answer 3

If you create a recursive descent parser, implementing a shunt yard is a lot of unnecessary work, because a recursive descent is great at evaluating expressions or outputting RPNs by itself.

You did not tell us anything about your programming language, your Token structures, or even what you are trying to achieve, so it is very difficult to give you sample code. Take a look at Eric White's implementation of the recursive descent parser in C #. If you provide more information, we can help more.