源码:https://github.com/felicityin/nand2tetris-rs
原始门电路:Nand (if a=b=1 then out=0 else out=1)
。
基本门电路:Not、And、Or、Xor、Mux、DMux
是组合芯片,即输出结果仅依赖输入变量的组合。
有符号数在计算机中存储为补码,因为补码可以利用加法器来计算减法。
ALU 通过 6 个控制位得到 f(x, y) 的输出值。f(x, y) 可表示 x、y 的所有运算。
是时序芯片,不仅可以计算值,还可以存取数据。
时钟:提供连续的交变信号。
触发器:是最基本的时序单元。DFF 简单将前一个时间周期的输入值作为当前周期的输出 out(t) = in(t-1)
。
寄存器:可以存储某个时刻的值,比如在时刻 t 重现时刻 t-1 的值,out(t) = out(t-1)。if load(t-1) then out(t) = in(t-1) else out(t) = out(t-1)
,前者是写操作,后者是读操作。
RAM:可直接访问的记忆单元,由 n 个 w 位寄存器组成的阵列。典型的 RAM 接收三种输入:数据输入、地址输入和加载位。地址指定了当前时钟周期内哪个 RAM 寄存器被访问。
PC:可执行 out(t) = out(t-1) + 1。相对于寄存器,有两个额外的控制位控制位:reset 和 inc。
if reset(t-1) then out(t) = 0
else if load(t-1) then out(t) = in(t-1)
else if inc(t-1) then out(t) = out(t-1) + 1
else out(t) = out(t-1)
CPU 由 ALU、数据寄存器(D,data register)、地址寄存器(A,address register)、程序计数器(PC,program counter)组成。
每个时钟周期内整个计算机的操作:
总结:
ROM,可以直接访问的只读内存设备。
Hack 平台的 Memory 芯片主要由三个底层芯片构成:RAM16K、Screen、Keyboard。这 3 个底层芯片应该实现一个统一的逻辑地址空间。
计算机与 I/O 设备交互的最简单的实现技巧之一就是 I/O 映像。创建 I/O 设备的二进制仿真,使其对于 CPU 而言,看上去就像是普通的内存。每个 I/O 设备在内存都分配了独立的区域,作为它的”内存映像“。
Hack 计算机是最小的系统。
机器语言一般分为两类:符号型和二进制型。
比如,二进制码 110000101000000110000000000000111,最左边的 8 位代表操作码 LOAD,接着的 8 位代表寄存器 R3,剩下的 16 位表示地址 7。该条指令等价的汇编是 LOAD R3, 7
,将 Memory[7] 的内容加载到寄存器 R3 中。
汇编编译器:将汇编翻译成二进制码的程序。
汇编程序中的符号:
符号解析:将变量或标签映射到内存地址。解决方式是读两遍代码:
汇编编译器实现:语法分析器、编码(提供所有汇编命令对应的二进制码)、符号表。
例如 @1
翻译成二进制:
0000000000000001
例如预定义标签 @R1
翻译成二进制:
0000000000000001 // R1 在 RAM 中的地址
例如标签 @label1
翻译成二进制:
0000000000001010 // label1 所指代的命令的 ROM 地址
例如变量 @var1
翻译成二进制:
0000000000010000 // var1 在 RAM 中的地址
dest=comp;jump
,其中,dest
或 jump
可以省略。
例如 D=A
翻译成二进制:
// 111 表示是计算指令
// 0110000 表示寄存器 A
// 010 表示将结果存到寄存器 D
// 000 表示不跳转
1110110000010000
例如 D=M
翻译成二进制:
// 111 表示是计算指令
// 1110000 表示 M
// 010 表示将结果存到寄存器 D
// 000 表示不跳转
1111110000010000
例如 D=D-M
翻译成二进制:
// 111 表示是计算指令
// 101001 表示 D-M
// 010 表示将结果存到寄存器 D
// 000 表示不跳转
1111010011010000
例如 D;JGT // if D>0 (first is greater) goto output_first
翻译成二进制:
// 111 表示是计算指令
// 0001100 表示寄存器 D
// 000 表示不存储结果
// 001 表示大于 0 时跳转
1110001100000001
虚拟机指令是高级命令分解而成的中间处理步骤。
在 VM 操作中的操作数和结果应该驻留到哪里,“最干净利落”的解决方式是放在堆栈里。
VM 语言包括 4 种类型的命令:
VM 语言有 9 个面向堆栈的算术命令和逻辑命令。7 个面向二元的:add, sub, and, or, eq, gt, lt;2 个面向一元的:not,neg。
例如 add 翻译成汇编:
@SP
AM=M-1 // SP -= 1,指向 y
D=M // 加载 y
A=A-1 // SP -= 1,指向 x
M=M+D // x = x + y
例如 eq 翻译成汇编:
@SP
AM=M-1 // SP -= 1,指向 y
D=M // 加载 y
A=A-1 // SP -= 1,指向 x
D=M-D // x - y
M=0 // 记录:发生了跳转
@eq_0
D;JNE // 如果 x - y == 0,则跳转到 eq_0
@SP
A=M-1 // 否则,没有跳转,继续出栈,SP-=1
M=-1 // 记录:没有发生跳转
(eq_0)
例如 neg 翻译成汇编:
@SP
A=M-1 // SP -= 1,指向 y
M=-M // y = -y
push argument 2
和 pop local 1
会把函数的第三个参数的值存储在函数的第二个局部变量中。
操作数组:
操作对象:
例如 push constant 1
翻译成汇编:
@1
D=A // D = 1
// 将 D 中的值存到 *SP,SP++
@SP
A=M // A = SP
M=D // M[A] = D
@SP
M=M+1 // SP = SP + 1
例如 push argument 1
翻译成汇编:
// 将 ARG[1] 的值存到 D
@1
D=A // D = 1
@ARG
A=M+D // A = ARG + 1
D=M // D = M[A]
// 将 D 中的值存到 *SP,SP++
@SP
A=M // A = SP
M=D // M[A] = D
@SP
M=M+1 // SP = SP + 1
例如 push pointer 1
翻译成汇编:
@1
D=A // D = 1
@3
A=A+D // A = 3 + 1
D=M // D = M[4]
// 将 D 中的值存到 *SP,SP++
@SP
A=M // A = SP
M=D // M[A] = D
@SP
M=M+1 // SP = SP + 1
例如 push static 1
翻译成汇编:
@filename.1
D=M
// 将 D 中的值存到 *SP,SP++
@SP
A=M // A = SP
M=D // M[A] = D
@SP
M=M+1 // SP = SP + 1
例如 pop local 1
翻译成汇编:
@1
D=A // D = 1
@LCL
D=M+D // D = LCL + 1
@R15
M=D // R15 = D,记录第 1 个变量的地址
// SP--,将 SP 指向的值存到 M[address]
@SP
AM=M-1 // A = SP = SP - 1
D=M // D = M[A],SP 指向的值
@R15
A=M // A = R15
M=D // M[A] = D,将 SP 指向的值存到 M[A],即第 1 个变量中
例如 pop pointer 1
翻译成汇编:
@1
D=A // D = 1
@3
D=A+D // D = 3 + 1
@R15
M=D // R15 = D,记录了地址 4
// SP--,将 SP 指向的值存到 M[address]
@SP
AM=M-1 // A = SP = SP - 1
D=M // D = M[A],SP 指向的值
@R15
A=M // A = R15
M=D // M[A] = D,将 SP 指向的值存到 M[A],即地址 4 指向的内存中
例如 pop static 1
翻译成汇编:
@filename.1
D=M
@R15
M=D // R15 = D
// SP--,将 SP 指向的值存到 M[address]
@SP
AM=M-1 // A = SP = SP - 1
D=M // D = M[A],SP 指向的值
@R15
A=M // A = R15
M=D // M[A] = D,将 SP 指向的值存到 M[A]
VM 语言有三种形式的程序控制流命令:
例如 label label1
翻译成汇编:
(cur_funcname$label1)
例如 goto label
翻译成汇编:
@cur_funcname$label1
0;JMP
例如 if-goto label1
翻译成汇编:
@SP
AM=M-1 // A = SP = SP - 1
D=M // D = M[A],SP 指向的值
@cur_funcname$label1
D;JNE // D 非 0 则跳转到 (cur_funcname$label1)
对于运行期的每个子程序调用,底层必须处理如下细节:
VM 语言有三种函数相关的命令:
例如 function f 2
翻译成汇编:
(f) // 为函数入口声明一个标签
// push 0,压栈第 1 个参数,并将其初始化为 0
@SP
A=M
M=0
@SP
M=M+1
// push 0,压栈第 2 个参数,并将其初始化为 0
@SP
A=M
M=0
@SP
M=M+1
例如 call f 2
翻译成汇编:
// push return-address
@End$f$0
D=A
@SP
A=M
M-D
@SP
M=M+1
// push LCL
@LCL
D=M
@SP
A=M
M-D
@SP
M=M+1
// push ARG
// push THIS
// push THAT
...
// ARG = SP - n - 5,重置 ARG(n = 参数数量)
@7
D=A
@SP
D=M-D
@ARG
M=D
// LCL = SP,重置 LCL
@SP
D=M
@LCL
M=D
// goto f
@f
0;JMP
// 为返回地址声明一个标签
(f)
例如 return
翻译成汇编:
// FRAME = LCL,FRAME 是临时变量
@LCL
D=M
@R15
M=D
// RET = *(FRAME - 5),将返回地址放入临时变量中
@5
D=A
@R15
A=M-D
D=M
@R14
M=D
// *ARG = pop(),重置为调用者的返回值
@SP
AM=M-1
D=M
@ARG
A=M
M=D
// SP = ARG + 1,恢复调用者的 SP
@ARG
D=M+1
@SP
M=D
// THAT = *(FRAME - 1),恢复调用者的 THAT 段指针
@R15
A=M-1
D=M
@THAT
M=D
// THIS = *(FRAME - 2),恢复调用者的 THIS 段指针
@2
D=A
@R15
A=M-D
D=M
@THIS
M=D
// ARG = *(FRAME - 3),恢复调用者的 ARG 段指针
// LCL = *(FRAME - 4),恢复调用者的 LCL 段指针
...
// goto RET,跳转到返回地址(在调用者代码中)
@R14
A=M
0;JMP
编译器:将高级语言翻译成目标语言。
编译器一般组成:
递归下降分析,是应用由语法规则描述的嵌套结构来尝试递归地分析 token stream,可用来构建语法分析树。如果非终结符仅由终结符构成,直接处理;否则,对于规则的右边的每个非终结符块递归调用“分析该非终结符”的程序。整个处理过程递归进行,直到所有终结符全部被处理完毕。
每当一个非终结符有多种可选的导出规则时,其第一个 token 足以确定该非终结符所属的表达式类型,而不会出现不确定的情况。具有这种属性的语法称为 LL(0)。递归下降算法可简洁明了地处理这类语法。
将高级语言编译成低级语言主要涉及两个主要的问题:数据的翻译和命令的翻译。
数据翻译涉及变量类型、变量的生命周期和作用域。
符号表:记录每个标识符的类型(int、bool 等)、种类(局部变量、静态变量等),记录标识符的作用域。
变量处理:将各种变量类型映射到目标平台内存。不同变量类型有不同大小的内存块,不同的生命周期。不过,VM 层已通过通过使用全局堆栈和虚拟内存段,处理了变量的分配和释放细节。编译器唯一需要做的事情就是将源程序中的变量映射到虚拟内存段上,然后用 VM 命令来表达操控这些变量的高级命令。
数组处理和对象处理:见本文的 3.2 节。但对于类中的方法,在目标代码层只存在唯一副本。因此,编译 b.mult(5) 就好像被写成 mult(b, 5)。
命令翻译设设计表达式求值和程序流程控制。对于表达式求值,可遍历语法分析树,生成对应的 VM 代码。对于程序流程控制,只使用 goto 和 if-goto 来表达 if、while 语句,另外,控制结构也可能是嵌套的。
表达式求值:
程序流程控制:
操作系统通常由高级语言编写,并被编译成二进制形式。不过,操作系统代码必须了解它所运行的硬件平台。
Hack 操作系统比较初级,其服务包括数学函数、字符串操作、内存管理、文本和图形输出到屏幕的处理,会涉及一系列优秀的算法。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。