Assembler

Building a Modern Computer From First Principles

www.nand2tetris.org

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 1
Where we are at:

Human Abstract design Software

abstract interface
Thought hierarchy
Chapters 9, 12
H.L. Language Compiler
& abstract interface
Chapters 10 - 11
Operating Sys.
Virtual VM Translator
abstract interface
Machine Chapters 7 - 8

Assembly
Language

Assembler

Chapter 6

abstract interface
Computer
Machine Architecture
abstract interface
Language
Chapters 4 - 5
Hardware Gate Logic
abstract interface
Platform Chapters 1 - 3 Electrical
Chips & Engineering
Hardware Physics
Logic Gates
hierarchy

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 2
Why care about assemblers?
 Assemblers employ nifty programming tricks

 Assemblers are the first rung up the software hierarchy ladder

 An assembler is a translator of a simple language

 Writing an assembler = low-impact practice for writing compilers.

cross-platform
compiling
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 3
Assembly example
Target code (a text file of binary Hack
code)
Source code (example)
// 0000000000010000
// Computes
Computes 1+...+RAM[0]
1+...+RAM[0] 0000000000010000
// 1110111111001000
// And stored
And stored the
the sum
sum in
in RAM[1]
RAM[1] 1110111111001000
@i 0000000000010001
0000000000010001
@i
M=1 // 1110101010001000
M=1 // ii == 11 1110101010001000
0000000000010000
0000000000010000
@sum
@sum
assemble 1111110000010000
1111110000010000
execute
M=0 // 0000000000000000
M=0 // sum
sum == 00 0000000000000000
(LOOP) 1111010011010000
1111010011010000
(LOOP)
@i // 0000000000010010
@i // if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE 0000000000010010
D=M 1110001100000001
1110001100000001
D=M
@R0 0000000000010000
0000000000010000
@R0
D=D-M 1111110000010000
1111110000010000
D=D-M
@WRITE 0000000000010001
0000000000010001
@WRITE
D;JGT ...
...
D;JGT
...
... //
// Etc.
Etc.
The program translation challenge
 Extract the program’s semantics from the source program,
using the syntax rules of the source language
 Re-express the program’s semantics in the target language,
using the syntax rules of the target language
Assembler = simple translator
 Translates each assembly command into one or more binary machine instructions
 Handles symbols (e.g. i, sum, LOOP, …).
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 4
Revisiting Hack low-level programming: an example
Assembly program (sum.asm) CPU emulator screen shot
after running this program
//
// Computes
Computes 1+...+RAM[0]
1+...+RAM[0]
//
// And stores
And stores the
the sum
sum in
in RAM[1].
RAM[1].
@i
@i
M=1
M=1 //// ii == 11
@sum
@sum
M=0 user
M=0 // // sum
sum == 00 supplied
(LOOP)
(LOOP) input
@i
@i //
// if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE
D=M
D=M
@R0 program
@R0 generated
D=D-M
D=D-M output
@WRITE
@WRITE
D;JGT
D;JGT
@i
@i //
// sum
sum +=
+= ii
D=M
D=M
@sum
@sum
M=D+M
M=D+M
@i
@i //
// i++
i++
M=M+1
M=M+1
@LOOP
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP
(WRITE)
(WRITE)
@sum
@sum
D=M
D=M
@R1
@R1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
(END)
sum The CPU emulator allows loading and executing
(END) symbolic Hack code. It resolves all the symbolic
@END
@END
0;JMP
0;JMP
symbols to memory locations, and executes the code.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 5
The assembler’s view of an assembly program
Assembly program
//
// Computes
Computes 1+...+RAM[0]
//
// And stores
And
1+...+RAM[0]
stores the
the sum
sum in
in RAM[1].
RAM[1].
Assembly program =
@i
@i a stream of text lines, each being
M=1
M=1 //// ii == 11 one of the following:
@sum
@sum
M=0
M=0 // // sum
sum == 00
(LOOP)
(LOOP)
@i
@i //
// if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE
D=M
D=M
@R0
@R0
D=D-M
D=D-M
@WRITE
@WRITE
D;JGT
D;JGT
@i
@i //
// sum
sum +=
+= ii
D=M
D=M
@sum
@sum
M=D+M
M=D+M
@i
@i //
// i++
i++
M=M+1
M=M+1
@LOOP
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP
(WRITE)
(WRITE)
@sum
@sum
D=M
D=M
@R1
@R1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
sum
(END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 6
The assembler’s view of an assembly program
Assembly program
//
// Computes
Computes 1+...+RAM[0]
//
// And stores
And
1+...+RAM[0]
stores the
the sum
sum in
in RAM[1].
RAM[1].
Assembly program =
@i
@i a stream of text lines, each being
M=1
M=1 //// ii == 11 one of the following:
@sum
@sum
M=0
 White space
M=0 // // sum
sum == 00
(LOOP)
(LOOP)  Empty lines/indentation
@i
@i //
// if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE
D=M  Line comments
D=M
@R0
@R0  In-line comments
D=D-M
D=D-M
@WRITE
@WRITE
D;JGT
D;JGT
@i
@i //
// sum
sum +=
+= ii
D=M
D=M
@sum
@sum
M=D+M
M=D+M
@i
@i //
// i++
i++
M=M+1
M=M+1
@LOOP
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP
(WRITE)
(WRITE)
@sum
@sum
D=M
D=M
@R1
@R1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
sum
(END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 7
The assembler’s view of an assembly program
Assembly program
//
// Computes
Computes 1+...+RAM[0]
//
// And stores
And
1+...+RAM[0]
stores the
the sum
sum in
in RAM[1].
RAM[1].
Assembly program =
@i
@i a stream of text lines, each being
M=1
M=1 //// ii == 11 one of the following:
@sum
@sum
M=0
 White space
M=0 // // sum
sum == 00
(LOOP)
(LOOP)  Empty lines/indentation
@i
@i //
// if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE
D=M  Line comments
D=M
@R0
@R0  In-line comments
D=D-M
D=D-M
@WRITE
@WRITE
D;JGT
 Instructions
D;JGT
@i
@i //
// sum
sum +=
+= ii  A-instruction
D=M
D=M
@sum  C-instruction
@sum
M=D+M
M=D+M
@i
@i //
// i++
i++
M=M+1
M=M+1
@LOOP
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP
(WRITE)
(WRITE)
@sum
@sum
D=M
D=M
@R1
@R1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
sum
(END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 8
The assembler’s view of an assembly program
Assembly program
//
// Computes
Computes 1+...+RAM[0]
//
// And stores
And
1+...+RAM[0]
stores the
the sum
sum in
in RAM[1].
RAM[1].
Assembly program =
@i
@i a stream of text lines, each being
M=1
M=1 //// ii == 11 one of the following:
@sum
@sum
M=0
 White space
M=0 // // sum
sum == 00
(LOOP)
(LOOP)  Empty lines/indentation
@i
@i //
// if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE
D=M  Line comments
D=M
@R0
@R0  In-line comments
D=D-M
D=D-M
@WRITE
@WRITE
D;JGT
 Instructions
D;JGT
@i
@i //
// sum
sum +=
+= ii  A-instruction
D=M
D=M
@sum  C-instruction
@sum
M=D+M
M=D+M
@i
@i //
// i++
i++
 Symbols
M=M+1
M=M+1  references
@LOOP
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP  Label declaration (XXX)
(WRITE)
(WRITE)
@sum
@sum
D=M
D=M
@R1
@R1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
sum
(END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 9
The assembler’s view of an assembly program
Assembly program
//
// Computes
Computes 1+...+RAM[0]
//
// And stores
And
1+...+RAM[0]
stores the
the sum
sum in
in RAM[1].
RAM[1].
Assembly program =
@16
@16 a stream of text lines, each being
M=1
M=1 //// ii == 11 one of the following:
@17
@17
M=0 //
 White space
M=0 // sum
sum == 00
 Empty lines/indentation
@16
@16 //
// if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE
D=M  Line comments
D=M
@0
@0  In-line comments
D=D-M
D=D-M
@18
@18
D;JGT
 Instructions
D;JGT
@16
@16 //
// sum
sum +=
+= ii  A-instruction
D=M
D=M
@17  C-instruction
@17
M=D+M
M=D+M
@16
@16 //
// i++
i++
 Symbols
M=M+1
M=M+1  references
@4
@4 //
// goto
goto LOOP
LOOP
0;JMP
0;JMP  Label declaration (XXX)

@17
@17
D=M
Assume that there is
D=M
@1
@1
no symbol for now!
M=D
M=D //
// RAM[1]
RAM[1] == the
the sum
sum
@22
@22
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 10
White space
Assembly program
//
// Computes
Computes 1+...+RAM[0]
//
// And stores
And
1+...+RAM[0]
stores the
the sum
sum in
in RAM[1].
RAM[1].
Assembly program =
@16
@16 a stream of text lines, each being
M=1
M=1 //// ii == 11 one of the following:
@17
@17
M=0 //
 White space
M=0 // sum
sum == 00
 Empty lines/indentation
@16
@16 //
// if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE
D=M  Line comments
D=M
@0
@0  In-line comments
D=D-M
D=D-M
@18
@18
D;JGT
 Instructions
D;JGT
@16
@16 //
// sum
sum +=
+= ii  A-instruction
D=M
D=M
@17  C-instruction
@17
M=D+M
M=D+M
@16
@16 //
// i++
i++
 Symbols
M=M+1
M=M+1  references
@4
@4 //
// goto
goto LOOP
LOOP
0;JMP
0;JMP  Label declaration (XXX)

@17
@17
D=M
D=M
@1
@1
M=D
M=D //
// RAM[1]
RAM[1] == the
the sum
sum
@22
@22
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 11
White space → ignore/remove them
Assembly program
@16
@16
M=1
M=1
Assembly program =
a stream of text lines, each being
@17
@17
M=0
one of the following:
M=0
@16
@16
D=M
 White space
D=M
@0
@0  Empty lines/indentation
D=D-M
D=D-M
@18  Line comments
@18
D;JGT
D;JGT  In-line comments
@16
@16
D=M
D=M
@17
 Instructions
@17
M=D+M
M=D+M  A-instruction
@16
@16
M=M+1  C-instruction
M=M+1
@4
@4
0;JMP
0;JMP
 Symbols
@17
@17  references
D=M
D=M
@1
@1  Label declaration (XXX)
M=D
M=D
@22
@22
0;JMP
0;JMP

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 12
Instructions → binary encoding
Assembly program
@16
@16
M=1
M=1
Assembly program =
a stream of text lines, each being
@17
@17
M=0
one of the following:
M=0
@16
@16
D=M
 White space
D=M
@0
@0  Empty lines/indentation
D=D-M
D=D-M
@18  Line comments
@18
D;JGT
D;JGT  In-line comments
@16
@16
D=M
D=M
@17
 Instructions
@17
M=D+M
M=D+M  A-instruction
@16
@16
M=M+1  C-instruction
M=M+1
@4
@4
0;JMP
0;JMP
 Symbols
@17
@17  references
D=M
D=M
@1
@1  Label declaration (XXX)
M=D
M=D
@22
@22
0;JMP
0;JMP

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 13
Translating / assembling A-instructions

Translation to binary:

 If value is a non-negative decimal number, simple, e.g. @16

 If value is a symbol, later.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 14
Translating / assembling C-instructions

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 15
Translating / assembling C-instructions

Example: MD=D+1

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 16
Translating / assembling C-instructions

Example: D; JGT

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 17
The overall assembly logic
Assembly program
//
For each (real) command
// Computes
Computes 1+...+RAM[0]
1+...+RAM[0]
//
// And stores
And stores the
the sum
sum in
in RAM[1].
@i
RAM[1].  Parse the command,
@i
M=1
M=1 //// ii == 11 i.e. break it into its underlying fields
@sum
@sum  A-instruction: replace the symbolic
M=0
M=0 // // sum
sum == 00
(LOOP) reference (if any) with the
(LOOP)
@i
@i //
// if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE corresponding memory address,
D=M
D=M which is a number
@0
@0
D=D-M
D=D-M  (how to do it, later)
@WRITE
@WRITE
D;JGT
D;JGT
@i //
 C-instruction: for each field in the
@i // sum
sum +=
+= ii
D=M
D=M
instruction, generate the
@sum
@sum corresponding binary code
M=D+M
M=D+M
@i
@i //
// i++
i++  Assemble the translated binary codes
M=M+1
M=M+1
@LOOP into a complete 16-bit machine
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP instruction
(WRITE)
(WRITE)
@sum
@sum  Write the 16-bit instruction to the
D=M
D=M
@1
output file.
@1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
sum
(END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 18
 Typical symbolic Hack
assembly code:
Handling symbols (aka symbol resolution)
@R0
@R0
D=M
Assembly programs typically have many symbols: D=M
@END
@END
 Labels that mark destinations of goto commands D;JLE
D;JLE
@counter
@counter
 Labels that mark special memory locations M=D
M=D
@SCREEN
@SCREEN
 Variables D=A
D=A
@x
@x
M=D
M=D
These symbols fall into two categories: (LOOP)
(LOOP)
@x
@x
 User–defined symbols (created by programmers) A=M
A=M
 Variables M=-1
M=-1
@x
@x
 Labels (forward reference could be a problem) D=M
D=M
@32
@32
 Pre-defined symbols (used by the Hack platform). D=D+A
D=D+A
@x
@x
M=D
M=D
@counter
@counter
MD=M-1
MD=M-1
@LOOP
@LOOP
D;JGT
D;JGT
(END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 19
 Typical symbolic Hack
assembly code:
Handling symbols: user-defined symbols
@R0
@R0
Label symbols: Used to label destinations of goto D=M
D=M
commands. Declared by the pseudo-command @END
@END
D;JLE
D;JLE
(XXX). This directive defines the symbol XXX to @counter
@counter
refer to the instruction memory location holding M=D
M=D
@SCREEN
the next command in the program. (the assembler @SCREEN
D=A
D=A
needs to maintain instrCtr) @x
@x
M=D
M=D
Variable symbols: Any user-defined symbol xxx (LOOP)
(LOOP)
@x
appearing in an assembly program that is not @x
A=M
A=M
defined elsewhere using the (xxx) directive is M=-1
M=-1
@x
treated as a variable, and is automatically assigned @x
D=M
D=M
a unique RAM address, starting at RAM address @32
@32
16 (the assembler needs to maintain nextAddr) D=D+A
D=D+A
@x
@x
M=D
(why start at 16? Later.) M=D
@counter
@counter
MD=M-1
MD=M-1
By convention, Hack programmers use lower-case @LOOP
@LOOP
and upper-case to represent variable and label D;JGT
(END)
D;JGT
(END)
names, respectively @END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 20
 Typical symbolic Hack
assembly code:
Handling symbols: pre-defined symbols
@R0
@R0
Virtual registers: D=M
D=M
The symbols R0,…, R15 are automatically @END
@END
D;JLE
D;JLE
predefined to refer to RAM addresses 0,…,15 @counter
@counter
M=D
M=D
I/O pointers: The symbols SCREEN and KBD are @SCREEN
@SCREEN
automatically predefined to refer to RAM D=A
D=A
@x
addresses 16384 and 24576, respectively (base @x
M=D
M=D
addresses of the screen and keyboard memory (LOOP)
(LOOP)
@x
maps) @x
A=M
A=M
M=-1
VM control pointers: the symbols SP, LCL, ARG, M=-1
@x
@x
THIS, and THAT (that don’t appear in the code D=M
D=M
example on the right) are automatically @32
@32
D=D+A
D=D+A
predefined to refer to RAM addresses 0 to 4, @x
@x
respectively M=D
M=D
@counter
@counter
(The VM control pointers, which overlap R0,…, R4 MD=M-1
MD=M-1
@LOOP
will come to play in the virtual machine @LOOP
D;JGT
D;JGT
implementation, covered in the next lecture) (END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 21
Handling symbols: symbol table
Source code (example) Symbol table
// R0 00
// Computes
Computes 1+...+RAM[0]
1+...+RAM[0] R0
//
// And stored
And stored the
the sum
sum in
in RAM[1]
RAM[1] R1
R1 11
@i
@i R2
R2 22
M=1
M=1 //// ii == 11 ... ...
... ...
R15
R15 15
15
@sum
@sum SCREEN 16384
M=0 SCREEN 16384
M=0 // // sum
sum == 00 KBD
KBD 24576
24576
(LOOP)
(LOOP) SP 00
@i // SP
@i // if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE LCL 11
D=M LCL
D=M ARG 22
@R0 ARG
@R0 THIS 33
D=D-M THIS
D=D-M THAT 44
@WRITE
@WRITE THAT
D;JGT LOOP
LOOP 44
D;JGT WRITE 18
@i
@i //
// sum
sum +=
+= ii WRITE 18
D=M END
END 22
22
D=M
@sum ii 16
16
@sum
M=D+M sum
sum 17
17
M=D+M
@i
@i //
// i++
i++
M=M+1
M=M+1
@LOOP
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP
(WRITE)
(WRITE) This symbol table is generated by the
@sum
@sum assembler, and used to translate the
D=M
D=M
@R1 symbolic code into binary code.
@R1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
sum
(END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 22
Handling symbols: constructing the symbol table
Source code (example) Symbol table
// R0 00
// Computes
Computes 1+...+RAM[0]
1+...+RAM[0] R0
//
// And stored
And stored the
the sum
sum in
in RAM[1]
RAM[1] R1
R1 11
@i
@i R2
R2 22
M=1
M=1 //// ii == 11 ...
...
R15
R15 15
15
@sum
@sum SCREEN 16384
M=0 SCREEN 16384
M=0 // // sum
sum == 00 KBD
KBD 24576
24576
(LOOP)
(LOOP) SP 00
@i // SP
@i // if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE LCL 11
D=M LCL
D=M ARG 22
@R0 ARG
@R0 THIS 33
D=D-M THIS
D=D-M THAT 44
@WRITE
@WRITE THAT
D;JGT
D;JGT
@i
@i //
// sum
sum +=
+= ii
D=M
D=M
@sum
@sum
M=D+M
M=D+M
@i
@i //
// i++
i++ Initialization: create an empty symbol table and
M=M+1
M=M+1 populate it with all the pre-defined symbols
@LOOP
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP
(WRITE)
(WRITE)
@sum
@sum
D=M
D=M
@R1
@R1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
sum
(END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 23
Handling symbols: constructing the symbol table
Source code (example) Symbol table
// R0 00
// Computes
Computes 1+...+RAM[0]
1+...+RAM[0] R0
//
// And stored
And stored the
the sum
sum in
in RAM[1]
RAM[1] R1
R1 11
@i
@i R2
R2 22
M=1
M=1 //// ii == 11 ...
...
R15
R15 15
15
@sum
@sum SCREEN 16384
M=0 SCREEN 16384
M=0 // // sum
sum == 00 KBD
KBD 24576
24576
(LOOP)
(LOOP) SP 00
@i // SP
@i // if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE LCL 11
D=M LCL
D=M ARG 22
@R0 ARG
@R0 THIS 33
D=D-M THIS
D=D-M THAT 44
@WRITE
@WRITE THAT
D;JGT LOOP
LOOP 44
D;JGT WRITE 18
@i
@i //
// sum
sum +=
+= ii WRITE 18
D=M END
END 22
22
D=M
@sum
@sum
M=D+M
M=D+M
@i
@i //
// i++
i++ Initialization: create an empty symbol table and
M=M+1
M=M+1 populate it with all the pre-defined symbols
@LOOP
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP First pass: go through the entire source code,
(WRITE)
(WRITE)
@sum
and add all the user-defined label symbols to
@sum
D=M the symbol table (without generating any code)
D=M
@R1
@R1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
sum
(END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 24
Handling symbols: constructing the symbol table
Source code (example) Symbol table
// R0 00
// Computes
Computes 1+...+RAM[0]
1+...+RAM[0] R0
//
// And stored
And stored the
the sum
sum in
in RAM[1]
RAM[1] R1
R1 11
@i
@i R2
R2 22
M=1
M=1 //// ii == 11 ...
...
R15
R15 15
15
@sum
@sum SCREEN 16384
M=0 SCREEN 16384
M=0 // // sum
sum == 00 KBD
KBD 24576
24576
(LOOP)
(LOOP) SP 00
@i // SP
@i // if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE LCL 11
D=M LCL
D=M ARG 22
@R0 ARG
@R0 THIS 33
D=D-M THIS
D=D-M THAT 44
@WRITE
@WRITE THAT
D;JGT LOOP
LOOP 44
D;JGT WRITE 18
@i
@i //
// sum
sum +=
+= ii WRITE 18
D=M END
END 22
22
D=M
@sum ii 16
16
@sum
M=D+M sum
sum 17
17
M=D+M
@i
@i //
// i++
i++ Initialization: create an empty symbol table and
M=M+1
M=M+1 populate it with all the pre-defined symbols
@LOOP
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP First pass: go through the entire source code,
(WRITE)
(WRITE)
@sum
and add all the user-defined label symbols to
@sum
D=M the symbol table (without generating any code)
D=M
@R1
@R1
M=D Second pass: go again through the source code,
M=D //// RAM[1]
RAM[1] == the
the sum
sum
(END)
(END)
and use the symbol table to translate all the
@END
@END commands. In the process, handle all the user-
0;JMP
0;JMP defined variable symbols.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 25
Handling symbols: constructing the symbol table (one-pass solution?)
Source code (example) Symbol table
// R0 00
// Computes
Computes 1+...+RAM[0]
1+...+RAM[0] R0
//
// And stored
And stored the
the sum
sum in
in RAM[1]
RAM[1] R1
R1 11
@i
@i R2
R2 22
M=1
M=1 //// ii == 11 ...
...
R15
R15 15
15
@sum
@sum SCREEN 16384
M=0 SCREEN 16384
M=0 // // sum
sum == 00 KBD
KBD 24576
24576
(LOOP)
(LOOP) SP 00
@i // SP
@i // if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE LCL 11
D=M LCL
D=M ARG 22
@R0 ARG
@R0 THIS 33
D=D-M THIS
D=D-M THAT 44
@WRITE
@WRITE THAT
D;JGT
D;JGT
@i
@i //
// sum
sum +=
+= ii
D=M
D=M
@sum
@sum
M=D+M
M=D+M
@i
@i //
// i++
i++
M=M+1
M=M+1
@LOOP
@LOOP //
// goto
goto LOOP
LOOP
0;JMP
0;JMP
(WRITE)
(WRITE)
@sum
@sum
D=M
D=M
@R1
@R1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
sum
(END)
(END)
@END
@END
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 26
The assembly process (detailed)
 Initialization: create the symbol table and initialize it with the pre-
defined symbols

 First pass: march through the source code without generating any
code.
For each label declaration (LABEL) that appears in the source code,
add the pair <LABEL , n > to the symbol table

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 27
The assembly process (detailed)
 Second pass: march again through the source, and process each line:

 If the line is a C-instruction, simple

 If the line is @xxx where xxx is a number, simple

 If the line is @xxx and xxx is a symbol, look it up in the symbol

table and proceed as follows:

 If the symbol is found, replace it with its numeric value and

complete the command’s translation

 If the symbol is not found, then it must represent a new

variable:
add the pair <xxx , n > to the symbol table, where n is the next
available RAM address, and complete the command’s
translation.

 (Platform design decision: the allocated RAM addresses are

running, starting at address 16).
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 28
The result ...
Source code (example) Target code
//
// Computes
Computes 1+...+RAM[0]
1+...+RAM[0] 0000000000010000
0000000000010000
//
// And stored
And stored the
the sum
sum in
in RAM[1]
RAM[1] 1110111111001000
1110111111001000
@i
@i 0000000000010001
0000000000010001
M=1
M=1 //// ii == 11 1110101010001000
1110101010001000
0000000000010000
0000000000010000
@sum
@sum 1111110000010000
M=0 1111110000010000
M=0 // // sum
sum == 00 0000000000000000
0000000000000000
(LOOP)
(LOOP) 1111010011010000
@i // 1111010011010000
@i // if
if i>RAM[0]
i>RAM[0] goto
goto WRITE
WRITE 0000000000010010
0000000000010010
D=M
D=M 1110001100000001
@R0 1110001100000001
@R0 0000000000010000
0000000000010000
D=D-M
D=D-M
@WRITE
@WRITE
assemble 1111110000010000
1111110000010000
0000000000010001
D;JGT 0000000000010001
D;JGT 1111000010001000
1111000010001000
@i
@i //
// sum
sum +=
+= ii 0000000000010000
D=M 0000000000010000
D=M 1111110111001000
1111110111001000
@sum
@sum 0000000000000100
M=D+M 0000000000000100
M=D+M 1110101010000111
1110101010000111
@i
@i //
// i++
i++ 0000000000010001
M=M+1 0000000000010001
M=M+1 1111110000010000
1111110000010000
@LOOP
@LOOP //
// goto
goto LOOP
LOOP 0000000000000001
0;JMP 0000000000000001
0;JMP 1110001100001000
1110001100001000
(WRITE)
(WRITE) 0000000000010110
@sum 0000000000010110
@sum 1110101010000111
1110101010000111
D=M
D=M
@R1
@R1
M=D
M=D //// RAM[1]
RAM[1] == the
the sum
(END)
sum Note that comment lines and pseudo-commands
(END)
@END
@END (label declarations) generate no code.
0;JMP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 29
Proposed assembler implementation
An assembler program can be written in any high-level language. (and could be run in the
other platforms, cross-platform compiling)

The book proposes a language-independent design, as follows.

Software modules:

 Parser: Unpacks each command into its underlying fields

 Code: Translates each field into its corresponding binary value,

and assembles the resulting values

 SymbolTable: Manages the symbol table

 Main: Initializes I/O files and drives the show.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 30
Perspective

 Simple machine language, simple assembler

 Most assemblers are not stand-alone, but rather encapsulated in a
translator of a higher order
 C programmers that understand the code generated by a C compiler
can improve their code considerably
 C programming (e.g. for real-time systems) may involve re-writing
critical segments in assembly, for optimization
 Writing an assembler is an excellent practice for writing more
challenging translators, e.g. a VM Translator and a compiler, as we
will do in the next lectures.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 6: Assembler slide 31