7.4.堆栈结构实现
\(7.4.\)Implementation of Stack
1.Pointer manipulation
We first introduce pointer notation: *p
represents the value stores in the address that p
points to.
In Hack, the pointer statement:
1 | D = *p // D becomes 23 |
can be translated into:
1 | @p |
A = M
points the pointer to the address of register M.D = M
gets the value of the RAM.
The calculation of pointer, such as:
1 | p-- |
When p--
, *p
refers to
RAM[256]
. After than when we invoke D = *p
, it
will get the value stored in RAM[256]
, namely 19.
When we assign a number to pointer, such as: 1
2*q = 9
q++
The *q
refers to RAM[1024]
, which stores
value 5. After the assignment, RAM[1024]
stores 9
instead.
2.Stack machine operation
Before implementation, we make two assumption:
- The stack pointer will be stored in
RAM[0]
. - Stack base address will be
addr = 256
.
Let's push
two value first:
After the push
, the stack pointer will point to 258,
and our RAM looks like this:
And we push 12 + 5
into the stack, then 17 will be in
the previous available space, and stack pointer moves forward:
So we can write the VM code: 1
2
3//push x
*sp = x
sp++
This can be translated into this Hack assembly: 1
2
3
4
5
6
7
8//push x
@x
D = A // D = x
@SP
A = M // *sp = D
M = D
@SP //increase the location
M = M + 1
In this program, the A register plays two roles: Data register which stores x Address register as usual
3.VM translator perspective
VM translator is:
- A program that translates VM code into machine language.
- Each VM command generates several assembly commands.