7.12.翻译器实现笔记

\(7.12.\)翻译器实现笔记

1. local,argument,this,that,temp的实现

  这几个内存段的push实现都遵循*sp=*addr的过程。我们可以将该过程拆分为下面的子过程:

  • D=*addr.
  • *sp=D.
  • sp++

  同时,根据先前的讨论,push操作中的addr可以通过baseAddr+index来计算。index的值很容易获取,假设我们的操作为push local x, 则:

1
2
3
//get index
@x
D=A

  但接下来,如果要获取baseAddr,因为此时的D寄存器已经存储了x的序号, 我们会想通过A寄存器获得baseAddr, 然后将baseAddr+index的地址存入A寄存器中:

1
2
3
4
//get base addr
@LCL
A=M
A=A+D

  顺利完成LCL内存段的地址读入后,我们接着用D寄存器读入baseAddr+index对应的数据。

1
D=A+D
  但是,此时的A储存的已不是原先的baseAddr了,通过这种方式更新D的值是不行的。这时,我们可以考虑同时更新AD的值,这样就可以利用未改变的A成功更新AD:
1
2
3
4
5
@x
D=A
@LCL
A=M //pointer
AD=A+D

  然后,我们需要D=*addr,由前面讲解的指针的表示,只需补上D=M语句即可。

  接下来就是较为简单的*sp=D操作了:

1
2
3
4
5
@SP
A=M
M=D
@SP
M=M+1

2.Loop实现

  对于if-goto语句,我们只需根据栈顶元素是否为0来判断是否需要跳转到所需分支。因为在栈中,我们用0表示false

1
2
3
4
5
6
7
@SP
M=M-1
@SP
A=M
D=M
@LABEL
D;JNE

  而对于无条件的goto语句,利用0,JMP即可实现:

1
2
@LABEL
0;JMP

3.function实现

  在Hack中,我们只需为function创建对应标签即可:

1
(LABEL)

4.Call实现

  我们按照\(8.6.\)节所讲逐步实现call功能:

  1. 在栈中放入returnAddress的标签,这标志着我们在调用函数后将返回的地址:

    1
    @return_address1
      该地址亦是栈指针的初始位置所在之处:
    1
    2
    3
    4
    D=A
    @SP
    A=M
    M=D

  2. 然后,我们依次放入LCL, ARG, THIS, THAT,以保存调用者(caller)的内存段。

  对于每一个内存段,我们像普通的push操作一样,将其放入栈指针所指位置,然后移动栈指针:

1
2
SP = memorySegment
SP = SP + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
@LCL
D=M
@SP
A=M
M=D
@SP
M=M+1

@SRG
D=M
@SP
A=M
M=D
@SP
M=M+1

@THIS
D=M
@SP
A=M
M=D
@SP
M=M+1

@THAT
D=M
@SP
A=M
M=D
@SP
M=M+1
  1. 接下来我们要重定向ARG的位置,我们需要把它定向至ARG[0]的位置,而该位置可以通过计算得出:

  假设我们调用的函数为call func x,则在ARG内存段前有4(前四个内存段)+x(LCL需要的位置个数),对应代码为:

1
2
@5+x
D=A

  然后我们需要将栈指针移到对应位置,并将ARG的初始位置设置在这里:

1
2
3
4
5
@SP
A=M
AD=A-D
@ARG
M=D

  1. 为了能够正确访问LCL的位置,我们将LCL push到栈指针所在位置:

    1
    2
    3
    4
    @SP
    D=M
    @LCL
    M=D

  2. 然后,我们goto需要执行的函数以执行函数:

    1
    2
    @func
    0;JMP

  3. 最后我们插入returnAddress的标签,这样当函数被执行完,我们可以回到最初调用它的地方:

    1
    (return_address1)

5.return实现

  我们按照\(8.6.\)节所讲逐步实现call功能:

  1. 创建一个临时变量frame,并把LCL的值赋给它。

    1
    2
    3
    4
    @LCL
    D=M
    @frame
    M=D

  2. 我们将return的值放在栈顶。由于有四个占据主内存的内存段,因此我们需要上移4+1=5个,frame-5即为return的地址:

    1
    2
    3
    4
    5
    @5
    A=D-A
    D=M
    @ret
    M=D

为什么此时不考虑每个内存段中的原有元素了呢?因为return的过程中,我们需要覆盖所有的已有元素,这要求我们将这些元素当作不存在。而如果我们考虑这些元素并将ret上移,在之后的步骤中就无法覆盖一些原有的旧数据和清空调用函数的栈了

  1. 由于我们需要将待return的值复制到ARG[0]的位置,而该值就在栈顶,我们可以轻易地通过操纵栈指针读取该值:

    1
    2
    3
    4
    5
    6
    7
    @SP
    M=M-1
    A=M
    D=M
    @ARG
    A=M
    M=D

  2. 调用者需要能够获取该值,因此栈指针应与ARG相邻:

    1
    2
    3
    4
    @ARG
    D=M
    @SP
    M=D+1

  3. 然后,我们就可以着手覆盖原有的内存段了。我们从先前设置的frame地址往下,依次设置新的内存段地址:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    @frame
    M=M-1
    A=M
    D=M
    @THAT
    M=D

    @frame
    M=M-1
    A=M
    D=M
    @THIS
    M=D

    @frame
    M=M-1
    A=M
    D=M
    @ARG
    M=D

    @frame
    M=M-1
    A=M
    D=M
    @LCL
    M=D

  4. 最后,我们回到最初设置的ret位置。由于ret并非标签,要跳转到其地址,我们需要指针操作:

    1
    2
    3
    @ret
    A=M
    0;JMP

6.Initial实现

  当我们需要翻译的VM代码是有效的时,我们就需要对我们的硬件系统进行初始化:

1
2
3
4
5
6
@256
D=A
@SP
M=D

call Sys.init// same as other call statements before.