LIFO stack algorithm design

Question

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!

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 http://stackoverflow.com/questions/1669/learning-to-write-a-compiler — , May 13 '10 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 — David Titarenco, May 13 '10 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 - http://compilers.iecc.com/crenshaw. — , May 13 '10 at 20:50

score 2 · Accepted Answer · answered May 13 '10 at 20:33

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.

answered May 13 '10 at 20:33

Nikolai Fetissov

82,306
11
110
171

2

Bah - you win the speed type battle here :) – Michael Dorgan May 13 '10 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 – David Titarenco May 13 '10 at 21:32
Yep, that's also how debuggers find your stuff on the stack. – Nikolai Fetissov May 13 '10 at 21:45

score 2 · Answer 2 · answered May 13 '10 at 20:33

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.

LIFO stack algorithm design

2 Answers2