6-2. Assembler - [밑바닥부터 만드는 컴퓨팅 시스템]

이 글은 insight 출판사의 [밑바닥부터 만드는 컴퓨팅 시스템 / The Elements of Computing System]이라는 책에 있는 프로젝트(과제)를 수행하는 글입니다.

해외에서는 nand2tetris라는 이름의 프로젝트로 알려져 있습니다! 동일한 내용으로 구성되어 있으니, nand2tetris를 공부할 때 참고바랍니다

프로젝트 수행을 위한 언어로 C#을 사용하였습니다.

Chapter 6의 프로젝트에 대한 글 보러가기

The Elements of Computing System - Ch.6 PJ (1)

---

HACK 어셈블리 - 2진 번역 명세서

4장에서 정리한 내용을 되새기기 위해 다시 정식으로 기술해보자.

분법적 관례와 파일 형식

파일명

어셈블리 코드로 작성한 파일의 확장자는 .asm, 2진 기계어 코드는 .hack으로 하자. ABC.asm을 어셈블러로 번역하면 ABC.hack파일이 생성된다.

어셈블리어 파일 FILE.asm

어셈블리어 파일은 명령어 + 기호선언으로 이루어져있다.

• 명령어 : A 명령어 / C 명령어
• 기호선언 : Symbol을 다음 명령어가 전달되는 메모리위치에 연결하는 의사코드_pseudo code. 대응되는 명령어를 생성하지 않는다. ex) (LOOP)2진코드 파일 FILE.hack0또는 1로 구성된 16자리 텍스트라인으로 이루어져있다. 각 행은 하나의 명령어를 의미한다. 프로그램 명령어 번호와 ROM주소가 모두 0부터 시작한다면, n번째 명령어는 n번 주소의 ROM에 저장된다.

이 아래의 RULE들은 어셈블리 프로그램에만 해당한다.

상수&기호

상수_constant는 10진법의 음이 아닌 수여야 한다. 기호는 문자 숫자 _ . $ : 들로 이루어진 문자열이다. 제일 앞자리에 숫자가 올 수는 없다.

주석

// 부터 뒤의 txt는 행이 끝날때까지 주석으로 처리되어 무시된다.

공백

공백문자위 빈 라인은 무시된다.

대소문자

어셈블리 명령어(연상기호_mnemocid)은 모두 대문자를 사용한다. 나머지는 대소문자를 구분할 수 있으나, 레이블은 대문자로 사용하고 변수명은 소문자로 사용하는 것이 관례이다.

명령어

Hack 명령어는 주소명령어_addressing instruction (A 명령어)와 계산명령어_compute instruction (C 명령어)로 구성된다.
A 명령어의 형태 : @VALUE // VALUE는 10진수인 음이 아닌 수 또는 그런 수를 참조하는 기호.
-> 2진코드로 0VVV VVVV VVVV VVVV (첫 Bit는 0, 나머지는 Value가 된다)

C명령어의 형태 : dest=comp;jump // dest= 또는 ;jump 필드는 공란이 될 수 있다.
-> 2진코드로 111A CCCC CCDD DJJJ (첫 Bit는 1, A와 C는 comp, D는 dest, J는 jump Bit이 된다.)

기호

hack의 어셈블리 명령에서는 상수나 기호를 통해 메모리위치를 참조할 수 있다. 3가지 기호 사용 방법이 있다.

선언기호 Predefined Symbol

Hack에서는 다음과 같은 선언된 기호를 제공한다.
위부터 5개의 RAM주소에는 선언기호가 2개씩 할당된다. (기호와 Rx)

Label	RAM 주소	in Hexa
SP	0	0x0000
LCL	1	0x0001
ARG	2	0x0002
THIS	3	0x0003
THAT	4	0x0004
R0-R15	0-15	0x0000-F
SCREEN	16384	0x4000
KBD	24579	0x6000

레이블 기호 Label Symbol

Pseudo code인 (XXX)는 기호 XXX가 프로그램의 다음 명령어의 주소를 참조하도록 정의한다. 같은 기호의 레이블은 한 번만 정의가 가능하다. 정의된 레이블은 프로그램 어디서든 (정의된 부분의 앞에서도!) 호출이 가능하다.

변수 기호

선언기호 X나 (XXX)로 정의되지 않은 기호는 변수로 취급된다. 등장한 순서대로 RAM주소 16 (0x0010) 부터 메모리에 차례대로 매핑된다.

예제

//Adds 1+2+...+100 
//Program.asm
    @i
    M = 1
    @sum
    M=0
(LOOP)
    ...
    @END
    D;JGT
    ...
    0;JMP
(END)
    @END
    0;JMP // 무한루프

위 프로그램을 어셈블러로 번역하면

//Program.hack
0000 0000 0001 0000
1110 1111 1100 1000
0000 0000 0001 0001
1110 1010 1000 1000
(생략)
...
0000 0000 0001 0010
1110 0011 0000 0001
...
1110 1010 1000 0111
(생략)
0000 0000 0001 0010
1110 1010 1000 0111

구현

Program.asm 파일을 txt 파일 입력으로 읽어들여서 Program.hack이라는 txt 파일로 출력한다. 입력은 cmd를 통해 수행된다.
어셈블리를 2진코드로 번역하는 작업은 1대1 변환작업이다. 연상기호들은 대응되는 Bit로, 기호는 명시된 숫자주소로 변환한다. 어셈블러를 다음의 4가지 모듈로 나누어 구현을 하고자 한다.

• Parser 모듈 : 입력구문 분석
• Code 모듈 : 모든 어셈블리 연상기호의 2진 코드를 제공
• Symbol Table 모듈 : 기호를 처리
• 메인 프로그램 : 전체 번역과정을 실행

API 표기법에 대한 설명

앞으로 구현할 번역기 (어셈블러, 가상머신, 컴파일러)를 계층으로 구현할 소프트웨어 프로젝트의 첫번째이다! 루틴은 메서드 또는 함수, 서브루틴, 프로시저에 대엉되고, 모듈은 클래스 또는 데이터를 처리하는 루틴의 집합에 대응된다. 자기가 자신있는 언어로 구현하면 된다! 언어에 상관이 없는 API를 제공하겠다.

Parser 모듈

Parser 모듈은 어셈블리 명령어를 부분들(필드 + 기호) 로 분리한다.
입력코드에 대한 접근을 캡슐화하고, 어셈블리 명령을 읽어들여 구문 분석을 하고, 필드나 기호같은 명령 세부요소에 편히 접근할 수 있게 해준다. 모든 공백과 주석을 제공한다.

루틴	인수	반환	함수
생성자 초기자	입력파일/스트림	-	입력 파일/스트림을 열고 분석을 준비한다.
hasMoreCommands	-	Boolean	입력에 명령이 더 있는가?
advance	-	-	입력에서 다음 명령을 읽고, 현재 명령으로 만든다.  hasMoreCommands()의 값이 참일때 호출이 가능하다.  초기에 현재 명령은 정해져있지 않다.
commandType	-	A_COMMAND,  C_COMMAND,  D_COMMAND	현재명령의 타입을 반환한다.  A:@xxx ... xxx는 기호나 10진수 C:dest=comp;jump L:실제로는 pseudo code. (Label)
symbol	-	String	@xxx나 (xxx)의 현재명령에서 기호나 10진수 xxx를 반환.  commandType()의 값이 A나 L일때만 호출가능하다.
dest	-	String	현재 C명령의 dest 연상기호를 반환. (8종류)  이는 CommandType()의 값이 C일때만 호출가능하다.
comp	-	String	현재 C명령의 comp 연상기호를 반환. (28종류) 이는 CommandType()의 값이 C일때만 호출가능하다.
jump	-	String	현재 C명령의 jump 연상기호를 반횐. (8종류)  이는 CommandType()의 값이 C일때만 호출가능하다.

 

Code 모듈

Code는 Hack 어셈블리 언어의 연상기호를 2진 코드로 번역한다.

루틴	인수	반환	함수
dest	연상기호 String	3 Bit	dest 연상기호의 2진코드를 반환한다.
comp	연상기호 String	7 Bit	comp 연상기호의 2진코드를 반환한다.
jump	연상기호 String	3 Bit	jump 연상기호의 2진코드를 반환한다.

기호를 처리하지 않은 어셈블리

Parser 모듈과 Code 모듈만을 이용해 기호가 없는 어셈블리 프로그램을 번역하는 어셈블러를 먼저 만들어본 뒤에 기호처리 기능이 있는 어셈블러로 확장시켜보다. 기호가 없는 프로그램 파일이란 @xxx 형식의 명령어에 기호가 사용되어서는 안되며, (LOOP)와 같은 레이블 기호가 없는 것을 말한다.
이 Program.asm 파일을 입력으로 받으면 한 줄씩 C 명령어를 명령코드 16Bit 2진수로 바꾸고 Program.hack에 기록한다. A 명령어에 대해서는 Parser가 반환하는 10진수 상수를 2진수로 옮기고 그 결과를 16Bit 2진수로 Program.hack에 기록한다.

Symbol Table 모듈

Hack의 명령어에 포함된 기호들은 번역과정에서 실제 메모리주소로 대치해주어야 한다. 어셈블러는 기호와 그 의미끼리의 대응관계를 기호테이블_symbol table을 통해 관리하고, 작업을 처리한다. 대부분의 프로그래밍 언어가 제공하는 데이터구조인 해시 테이블_hash table을 이용하면 자연스러운 구현이 가능하다.
Symbol Table : 기호, 레이블과 숫자 주소간의 대응관계를 기억하는 도구.

루틴	인수	반환	함수
Constructur	-	-	새로운 빈 기호테이블을 생성한다.
addEntry	symbol(String), address(Int)	-	(Symbol, Address) 쌍을 테이블에 추가한다.
contains	symbol(String)	Boolean	테이블이 주어진 Symbol을 가지고 있는가?
getAddress	symbol(String)	Int	Symbol과 연결된 주소를 반환한다.

기호 처리 어셈블러

어셈블리에서는 기호 레이블을 정의한 행 앞에서도 사용할 수 있다. 이는 프로그래머에게는 유용하나 어셈블러 디자이너에게는 까다롭게 작용하는 부분이다. 보통 처음부터 끝까지 코드를 2차례 읽는 2 Pass 어셈블러 방식으로 해결한다.

1. 코드를 읽으면서 기호테이블만 구성하고 다른 코드를 만들지 않는다.
2. 프로그램 내의 모든 기호와 레이블이 기호테이블에 기록된 상태 (메모리 매핑 끝) 이므로 기호를 주소로 대치하고 2진코드를 생성하면 된다.

초기화

기호테이블을 선언기호와 그 기호에 할당된 RAM주소들로 초기화한다.

1 Pass

어셈블리 프로그램을 행 단위로 처음부터 끝까지 훑으면서 기호테이블만 구성한다. 현재 명령어 주소를 기억할 숫자를 두고(PC처럼), A나 C 명령어 행마다 +1을 하지만, 레이블 의사코드가 나오면 값을 증가시키지 않고 해당 레이블과 명령어주소를 기호테이블에 등록한다. 이를 통해 모든 레이블과 명령주소가 테이블에 저장된다. 변수는 2 Pass에서 처리된다.

2 Pass

다시 처음부터 프로그램을 읽는다. A 명령어를 만나면 기호를 기호테이블에서 찾아보고 (@기호 로 되어있는 명령어의 경우에) 테이블에 기호가 있으면 기호를 해당 숫자값과 대치하고, 기호가 없으면 새로운 변수를 찾은 것이므로 기호테이블에 새로운 쌍을 추가한다. 이때 숫자값은 RAM주소 16번부터 연속적으로 매겨진다.

위 내용을 모두 구현하면 어셈블리 구현이 마무리된다.

정리

Hack 어셈블러는 매우 단순하다. 주로 TXT 처리를 담당한다. 물론 다른 더 복잡한 어셈블러의 경우, 데이터 주소자리에 기호+숫자 처럼 연산을 넣을 수도 있다. 또 매크로 명령을 지원하는 어셈블러의 경우 여러 줄의 명령어를 한 줄의 입력으로 압축할 수도 있다.
일반적으로 어셈블러는 단독으로 쓰이지 않고, 컴파일러가 코드를 2진 코드를 생성할 때 자동으로 사용된다. 특정한 고수준 언어의 경우, 개발자가 어셈블리를 직접 제어하여 HW에 최적화할 수 있는 기능도 제공한다.

---

코드를 짤만한 환경이 아니다보니 (이제 PC를 써서 코드는 작성할 수 있다고 해도 컴파일이 어려워서) 제가 그린 어셈블러의 인터페이스를 다음 글에서 올리겠슴당! 나중에 코드를 짤 환경이 갖춰진다면 새로 업데이트해서 어셈블러에 대한 스크립트를 올리는 걸로 하죠!