Search code examples
assemblycompiler-constructionstackexpression-evaluation

What does expression stack mean in assembly language?


I have been using a textbook to study assembly language. I am not in a class, I just want to learn assembly language. At the end of the chapter, one of the terms is "expression stack". This book tends to be very poor at clearly defining the key terms, and I just cant figure what this term means exactly. Can somebody give me a fairly concise, direct explanation of what it means? Thank you.

To clarify, here is more information: The chapter is called "Floating-Point Processing and Instruction Coding" and the section is on the FPU register stack. It mentions this: "A stack holds intermediate values during the evaluation of postfix expressions." and i wonder if it means "THE EXPRESSION stack holds intermediate values during the evaluation of postfix expressions"


Solution

  • In the general case, with a complex expression, it is necessary to evaluate piece parts of the expression, and then switch to something else, and then use those piece part results later in other parts of the expression.  These piece parts are sometimes called intermediates or temporaries.

    For example, the following expression involves 2 multiplies and one division: (a*b)/(c*d)

    Three address code is a good first start in understanding the process of decomposing an expression into these piece parts.  In three address code, we create a new variable to hold the result of each individual (line of) computation.  Three address code works similar to assembly language on a machine that has registers, in that the order of certain operations is flexible.

    t1 = a*b
    t2 = c*d
    t3 = t1/t2
    

    With three address code we could change the order:

    t2 = c*d
    t1 = a*b
    t3 = t1/t2
    

    and the code will still work to compute the proper answer, because the line t3= has explicitly named variables for the operands of the division.

    If you evaluate an expression in a systematic manner, such as left to right (or something repeatable), you can observe that the intermediate results of the partial expression evaluation can be stored in a stack rather than in random storage (where three address code uses random storage by introducing new variables and explicitly naming them at their use).

    A stack machine evaluation of the above expression would be:

                      before                   after
        push a     stack empty           stack has "a"
        push b     stack has "a"         stack has on top "b" then "a" behind
        multiply   stack has "b", "a"    stack has one item: the value of a*b
        push c     stack has a*b         stack has c, then value of a*b
        push d     stack has c, a*b      stack has d, c, a*b
        multiply   stack has d, c, a*b   stack has value of c*d, then value of a*b
        divide     stack has c*d, a*b    stack has value of (a*b)/(c*d)
    

    Using a stack, we are more restricted, depending on the operations available in the stack machine.  If we reverse the order of computation of a*b and c*d, then when we get to the divide if we didn't do something special, it would compute (c*d)/(a*b), which is not desired.  If the hardware instructions provide a reverse divide, we would use that instead; otherwise we'd have to exchange the top two elements on the stack so as to use the regular divide instruction.

    The intel x87 floating point unit is a stack machine, and it provides for something like a stack of 8 floating point values.  These values are quickly accessible like the regular CPU registers, though unlike the regular CPU instructions, these instructions that do floating point computation in this unit do not specify operands — they assume the top of stack is where they are working (that the stack has source operands, and target operands will return to the stack).

    Since this small hardware stack is often used to compute complex expressions that involve intermediate results, it is sometimes referred to as an expression stack.