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
2
3
@p
A = M
D = M
  • 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
2
p--
D = *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:

  1. The stack pointer will be stored in RAM[0].
  2. 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.