Implementing a stack based virtual machine for a subset of C

Question

Hello everyone I'm currently implementing a simple programming language for learning experience but I'm in need of some advice. Currently I'm designing my Interpreter and I've come into a problem.

My language is a subset of C and I'm having a problem regarding the stack interpreter implementation. In the language the following will compile:

somefunc ()
{
    1 + 2;
}

main ()
{
    somefunc ();
}

Now this is alright but when "1+2" is computed the result is pushed onto a stack and then the function returns but there's still a number on the stack, and there shouldn't be. How can I get around this problem?

I've thought about saving a "state" of the stack before a function call and restoring the "state" after the function call. For example saving the number of elements on the stack, then execute the function code, return, and then pop from the stack until we have the same number of elements as before (or maybe +1 if the function returned something).

Any ideas? Thanks for any tips!

Answer 1

Great question! One of my hobbies is writing compilers for toy languages, so kudos for your excellent programming taste.

An expression statement is one where the code in the statement is simply an expression. This means anything of the form <expression> ;, which includes things like assignments and function calls, but not ifs, whiles, or returns. Any expression statement will have a left over value on the stack at the end, which you should discard.

1 + 2 is an expression statement, but so are these:

• x = 5;
  The assignment expression leaves the value 5 on the stack since the result of an assignment is the value of the left-hand operand. After the statement is finished you pop off the unused value 5.

• printf("hello world!\n");
  printf() returns the number of characters output. You will have this value left over on the stack, so pop it when the statement finishes.

Effectively every expression statement will leave a value on the stack unless the expression's type is void. In that case you either special-case void statements and don't pop anything afterwards, or push a pretend "void" value onto the stack so you can always pop a value.

Answer 2

You'll need a smarter parser. When you see an expression whose value isn't being used then you need to emit a POP.