Hardware Reference
In-Depth Information
reverse Polish notation in the order they will actually be executed during the evalu-
ation of the expression. Figure 5-22 gives several examples of infix formulas and
their reverse Polish notation equivalents.
Evaluation of Reverse Polish Notation Formulas
Reverse Polish notation is the ideal notation for evaluating formulas on a com-
puter with a stack. The formula consists of
n
symbols, each one either an operand
or an operator. The algorithm for evaluating a reverse Polish notation formula
using a stack is simple. Scan the reverse Polish notation string from left to right.
When an operand is encountered, push it onto the stack. When an operator is
encountered, execute the corresponding instruction.
Figure 5-23 shows the evaluation of
×
×
(8+2
5)/(1+3
2
−
4)
in IJVM. The corresponding reverse Polish notation formula is
×
×
825
+132
+4
−
/
In the figure, we have introduced
IMUL
and
IDIV
as the multiplication and division
instructions, respectively. The number on top of the stack is the right operand, not
the left operand. This point is important for division (and subtraction) since the
order of the operands is significant (unlike addition and multiplication). In other
words,
IDIV
has been carefully defined so that first pushing the numerator, then
pushing the denominator, and then doing the operation gives the correct result.
Notice how easy code generation is from reverse Polish notation to IJVM: just scan
the reverse Polish notation formula and output one instruction per symbol. If the
symbol is a constant or variable, output an instruction to push it onto the stack. If
the symbol is an operator, output an instruction to perform the operation.
So far we have been looking only at instructions that operate on data. Branch
instructions (and procedure calls) also need addressing modes for specifying the
target address. The modes we have examined so far also work for branches for the
most part. Direct addressing is certainly a possibility, with the target address sim-
ply being included in the instruction in full.
However, other addressing modes also make sense. Register indirect ad-
dressing allows the program to compute the target address, put it in a register, and
then go there. This mode gives the most flexibility since the target address is com-
puted at run time. It also presents the greatest opportunity for creating bugs that
are nearly impossible to find.
Another reasonable mode is indexed mode, which offsets a known distance
from a register. It has the same properties as register indirect mode.
