I'm building a compiler. I already have a parse tree which I built using Bison for a grammar similar to the ANSI C grammar in this link. I see that for multiplicative expression in my parse tree, there can be 3 children e.g.

child 1: multiplicative_expression 
child 2: '*'
child 3: cast_expression

I expect to implement a new class for interpreting the parse tree. However, I have no idea how to even traverse the parse tree in order to evaluate the statements. How do I traverse the tree properly in order to interpret all the types of statements? I want to interpret not only multiplicative statements but also if-else statements etc.

  • $\begingroup$ Which tree traversals do you know? Are you familiar with recursion? What do you mean by "interprete"; translate? (A note of concern: compilers are complex, intricate beasts. Are you sure you are ready to build on yourself, given you have such elementary (read: first or second year in a CS course) issues?) $\endgroup$ – Raphael Nov 18 '14 at 7:48
  • $\begingroup$ @Raphael I'm familiar with traversal for binary trees, but my "parse tree" is not a binary tree. Yes, I'm familiar with recursion and I have tried recursing expression statements until I see a postfix expression but I'm concerned about which values to save during parsing. I'm ready to build one myself but I'm in need of finding the logic for statements. It seems like there's a way to recognize statements (including expression statements) and I have yet to find it. Please help, Sir. $\endgroup$ – Tamad Lang Nov 18 '14 at 8:01
  • $\begingroup$ With interpret, I meant that I want to have a runtime environment that executes the code. $\endgroup$ – Tamad Lang Nov 18 '14 at 8:04
  • 1
    $\begingroup$ @b16db0 3 remarks: a compiler is different from an interpreter. When given an expression, a compiler translates it into another language, while an interpreter computes its value from the values of the variables it is using. Which are you doing? Then you should fist start with a very simple language ... far far less complicated than the link you give. I would suggest a language without types (use only integer), and only expressions, assignment and if statement ... just for training. And you should read books on this topic (interpreters and compilers). $\endgroup$ – babou Nov 18 '14 at 11:02
  • 1
    $\begingroup$ In this case, much depends on the nature of the intermediate code. Most likely expressions no longer appear as such in intermediate code, so that my answer is moot. What the compiler does, most likely, is translate an expression into a succession of intermediate commands that do what is needed to compute the evaluation of the expression. But the execution of this intermediate code for actual evaluation can occur only at run-time, when all variables used have a value. $\endgroup$ – babou Nov 20 '14 at 11:37

An expression is composed usually of an operator (or function) applied to some arguments, or in the simplest case, just a constant (aka literal) or a variable.

For evaluation:
The value of a constant is that constant, The value for a variable is the current value stored in that variable, as each variable corresponds to a memory location where values can be stored. The value of an operator or function applied to arguments is obtained by evaluating arguments (recursively) and then applying the operator or function to the values thus obtained.

Actually, things can be more complex for a function (and some operator), depending on parameter passing mechanisms or evaluation modes (lazy or not), but that is to complex to explain at this level of discourse.

In your example the operator is child 2, and the two other children are arguments.

In general the algorithm does pretty much what you would do if you had to interpret the program by hand. That should be a good guide.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.