🔒 Locked

Parsing expression into a binary tree

Started by MutteringGoblin May 10, 2003 at 8:15 PM 4 replies 3.2k views

Original Post

May 10, 2003 at 8:15 PM

Hello all, Okay say I have this line of source code... a = b + c * d; I can convert the expression into a list of tokens like this: IDENTIFIER "a" OPERATOR_ASSIGN IDENTIFIER "b" OPERATOR_ADD IDENTIFIER "c" OPERATOR_MULTIPY IDENTIFIER "d" But here's the confusing bit. Jack Crenshaw's tutorial says it's possible to parse arithmetic expressions without looking ahead by more than one token. I can't figure out how to do it. And I don't understand his code. It's the operator precedence that's causing problems. I want to translate the above expression (or any other) into a tree like this:

      

        ASSIGN
       /            a       ADD
             /               b    MULTIPLY
                /                       c          d

Also I have another question. Would it be possible to write a generalised routine to parse grammar (like control structures) and arithmetic expressions, based on a set of rules provided at runtime? If so how would you approach it? I already have the blueprint for a generic lexical scanner, so I've negated the need to use lex.

Obviously I'd like to do the same for yacc. Thanks for reading. EDIT: Okay I just noticed I said 'binary tree' in the subject line. Obviously I'll need to include one or two unary operators as well. Oh shit the tree's buggered up now. Hang on.... [edited by - MutteringGoblin on May 10, 2003 9:17:58 PM] [edited by - MutteringGoblin on May 10, 2003 9:19:39 PM]

MutteringGoblin

May 10, 2003 at 8:29 PM

  

        ASSIGN
       /      \
      a       ADD
             /   \
            b    MULTIPLY
                /        \
               c          d

Ishan

May 11, 2003 at 6:35 PM

It''s just a recursive function. Think about your example tree.

a = b + c * d;

So you find the ''='' operator first. Now interpret the operator to OPERATOR_ASSIGN and assign its two children to be recursive calls on the strings a and (b + c * d).

Now we have:

  
       ____ a
      /       
ASSIGN 
      \_____ b + c * d

The only trick is to be aware of operators that have differing precedences. If the first operator you encountered was *, and you hit a +, you just assign the multiplication tree to be an argument of the + tree. Basically, if you hit something of higher precedence, it becomes an child of the lower-precedence node (e.g. c * d is a child to b +) while the relationship is reversed if a lower-precedence operator is encountered (e.g. in c * d + b, c * d becomes a child of b +)

Now we enter the recursive call on b + c * d. Now we find the addition operator. Remember, when scanning to the right, you have to check for operators of lesser precedence.

so you get

  
          ______ a 
         /
ADDITION
         \______ c * d

And so on.

MutteringGoblin

May 12, 2003 at 12:53 AM

Thanks Ishan, I think I kind of get it now. Well it will take some fiddling but I get the idea.

LowCalorieSoftDrink

May 12, 2003 at 8:29 AM

Another possiblity you may want to explore is converting the infix form of the experssion to the postfix, eg.

a + b * c

becomes

abc*+

The main advantage of this is you avoid the need for operator precedence. If you are interested i can go into greater detail.

CWizard

May 12, 2003 at 8:57 AM

I did a similar thing a while back, and had some help from here:

http://www.gamedev.net/community/forums/topic.asp?topic_id=142825

In the end, I posted my solution (code). You may find it helpful.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.