   Parsing expression into a binary tree
  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_ASSIGNIDENTIFIER "b"OPERATOR_ADDIDENTIFIER "c"OPERATOR_MULTIPYIDENTIFIER "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 /   cd 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]
ASSIGN  / \ a  ADD   /   \  b    MULTIPLY /   \cd  ;  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.  ;  Thanks Ishan, I think I kind of get it now. Well it will take some fiddling but I get the idea. ;  Another possiblity you may want to explore is converting the infix form of the experssion to the postfix, eg.a + b * cbecomesabc*+The main advantage of this is you avoid the need for operator precedence. If you are interested i can go into greater detail.  ;  I did a similar thing a while back, and had some help from here:http://www.gamedev.net/community/forums/topic.asp?topic_id=142825In the end, I posted my solution (code). You may find it helpful.  