3

I'm implementing a stack-based VM and I've been trying to read up on literature that explains or outlines algorithms for dealing with stacks no no avail. Here's an example:

int i = 3
int j = 4
int k = 5

Lets assume i, j, and k are local variables so they would be traditionally stored on the stack. The assembly/bytecode translation would look something like:

pushi 3
pushi 4
pushi 5

And the stack would be: 5 4 3

I have an integer stack and a string stack, hence the pushi, however my question is without storing these on the heap (with some ptr* or literal identifier), how would a compiler or interpreter know that if I want to do something like int x = i + j after the definition, I have to pop two and three times, respectively, as well as do my best not to lose k (save it in a register or something, then push it back)?

I hope my question made some sense and there's probably a much smarter approach :P Thank you for any insight!

3
  • You need to stack the operators too, and the intermediate results. Which book about expression evaluation and/or compiler design are you reading? Take a look at stackoverflow.com/questions/1669/learning-to-write-a-compiler
    – anon
    May 13, 2010 at 20:32
  • Not reading any book at the moment. Just Google and peer reviewed articles through JSTOR at my school. Thanks for the reference though, if only most of those books wouldn't be so expensive =P May 13, 2010 at 20:37
  • You are not going to get far without reading books. But this is a good online resource on how to write a compiler - compilers.iecc.com/crenshaw.
    – anon
    May 13, 2010 at 20:50

2 Answers 2

2

This is usually done with something called a stack frame. You allocate space for all local variables at once (modulo variables allocated/optimized into registers), store base address of that block, and operate on offsets from there. Then pop everything off the stack on scope exit.

3
  • 2
    Bah - you win the speed type battle here :) May 13, 2010 at 20:35
  • Awesome, so during scope resolution, the compiler says something like variable i is at memaddress, variable n is at memaddress, so later on in that particular stack frame, you can access i or n and it the pointer just "goes there" without the need to pop or push anything May 13, 2010 at 21:32
  • Yep, that's also how debuggers find your stuff on the stack. May 13, 2010 at 21:45
2

What the compiler does it this case is grab a bunch of stack space at once by directly adding to the stack pointer, then index into the stack values without using push and pop with normal memory read functions. Then subtract the stack back to its original value when complete.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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