How to check if the stack is empty on 8086

I am working on a study in Assembler 8086 that checks the balance of the parenthesis in a mathematical expression. The algorithm is as follows:

Make an empty stack
Read characters until end of string
If the character is an opening symbol, push it onto stack
If it is a closing symbol, then if the stack is empty report an error, otherwise, pop the stack
If the symbol popped is not the corresponding opening symbol, then report an error
At end of file, if the stack is not empty report an error

I have figured out all the parts except the part that I need to check if the stack is empty. How can I check if the stack is empty or how can I create an empty stack in the code? When there is nothing left to pop in the stack, I try to pop it and some value comes out. What does that value mean?

Solution

So you want to use the call-stack to implement your stack data structure. This is normal and often a good idea in asm.

You don't want to "empty" the call stack, you just want to set up a way to tell when you've popped all the data you pushed in this function. i.e. that your stack data structure is empty.

Either push a sentinel value that your code doesn't otherwise generate, or use a register (or memory location) to save the current value of SP. Especially in 16-bit code, it's very common to use mov bp,sp to make a stack frame, so you are already dedicating a register to remembering an old value of SP. You can use cmp sp,bp in later code to see if you've emptied your stack data structure.

If you need any space for locals on the stack, you could set up your stack frame with space for locals above BP, and your variable sized stack data below BP.

 my_func:
    ; push  si   ; save whatever other register you want
    sub   sp, 28      ; reserve 28 bytes for locals
    push  bp
    mov   bp, sp

  .my_loop:
    ...                ; use locals from [bp+2] to [bp+26]
    cmp  bp, sp
    jne   .my_loop
    ; else fall through: stack empty

    leave
    add   sp, 28
    ret

If you don't need to spill any local variables to memory at all, then you don't need to make a stack frame and can use bp as an extra scratch register. But if you do, then you can use bp as the top of your stack data structure for free.

Note that it's not quite a traditional stack frame: normally [bp+2] is the return address, so debugger stack backtraces might show bogus results. But [bp+0] is still pointing at the caller's saved bp value, so only that entry will be wrong, and it won't break backtracing through this function.

What would it mean for the call stack to be empty?

There's always memory above ss:sp unless sp = 0xFFFE (2 byte aligned at the top of a segment). pop doesn't even fault if sp wraps around from 0xFFFE to 0x0000. pop [mem] can #GP if popping into memory outside the segment limit of CS, DS, ES, FS, or GS, according to the manual, but I think that's only possible in unreal mode.

push in real-mode does fault with #SS if the new value of sp or esp is outside the stack segment limit (impossible in pure x86-16 without using unreal mode cached segment descriptors loaded in protected mode). Actually I think you could maybe get a #SS in pure real-mode with SP=1 / push ax. The store address would be ss:0xFFFF, and thus the 2-byte store would include memory 1 byte outside the 64k segment starting at ss<<4