[밑바닥부터 만드는 컴퓨팅 시스템] 6. 어셈블러 - 구현

지난 포스트에선 기호 없는 버전의 어셈블러를 만들어보았다.

이번엔 A-명령어에서 기호가 포함되어 있을 때 기호 테이블을 활용해 기호를 처리할 수 있는 어셈블러를 만들어볼 것이다.

최종적인 어셈블러는 다음과 같이 기호가 있는 명령어를 번역할 수 있다.

1. 선언 기호
   @SCREEN -> @16384
   기호 테이블을 생성할 때 선언 기호를 초기화 해두어 선언 기호는 항상 기호 테이블에 있게 한다.

2. 레이블 기호
   3 @LOOP -> @18
   ...
   17 (LOOP)
   18 M=M+1
   레이블 기호를 발견하면 기호 테이블에 값과 함께 입력해둔다.

3. 변수
   @sum -> @16
   @i -> @17
   기호 테이블에 존재하지 않는 기호는 변수로 인식하여 16부터 값을 매핑한다.

이를 위해 Parser, Code 모듈 이외에 새로 'SymbolTable' 모듈을 만들었다.

---

SymbolTable

SymbolTable 모듈은 Map 타입의 'table' 필드를 갖고, 다음과 같은 서브루틴을 지원한다.

• SymbolTable()
  생성자. 생성되면서 선언 기호들을 table에 추가한다.
• void addEntry(String symbol, int address)
  (symbol, address) 쌍을 table에 추가한다.
• boolean contains(String symbol)
  symbol이 table에 있는지 여부를 반환한다.
• int getAddress(String symbol)
  key값인 symbol에 대응하는 value인 address를 반환한다.

java 코드 구현은 다음과 같다.

SymbolTable.java

import java.util.HashMap;
import java.util.Map;

public class SymbolTable {
    private final Map<String, Integer> table;

    public SymbolTable() {
        table = new HashMap<>();
        initializePredefinedSymbols();
    }

    private void initializePredefinedSymbols() {
        for (int i = 0; i < 16; i++) {
            table.put("R" + i, i);
        }

        table.put("SP", 0);
        table.put("LCL", 1);
        table.put("ARG", 2);
        table.put("THIS", 3);
        table.put("THAT", 4);
        table.put("SCREEN", 16384);
        table.put("KBD", 24576);
    }

    public void addEntry(String symbol, int address) {
        table.put(symbol, address);
    }

    public boolean contains(String symbol) {
        return table.containsKey(symbol);
    }

    public int getAddress(String symbol) {
        return table.get(symbol);
    }
}

SymbolTable 클래스의 필드인 table은 실제로 초기화될 땐 HashMap으로 초기화되지만, 코드의 범용성을 위해 Map 타입으로 선언했다.
추후에 HashMap을 다른 TreeMap등으로 변경하여도 필드의 Map 타입은 변하지 않는다.

생성자의 간결함을 위해 initializePredefinedSymbols를 따로 메소드로 구현하였다.

---

이제 기호를 처리하는 어셈블러를 만들 차례다.

다음 예시처럼 레이블 변수는 선언되기 이전에도 사용할 수 있다.

Max.asm

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/6/max/Max.asm

// Computes R2 = max(R0, R1)  (R0,R1,R2 refer to RAM[0],RAM[1],RAM[2])
// Usage: Before executing, put two values in R0 and R1.

  // D = R0 - R1
  @R0
  D=M
  @R1
  D=D-M
  // If (D > 0) goto ITSR0
  @ITSR0
  D;JGT
  // Its R1
  @R1
  D=M
  @OUTPUT_D
  0;JMP
(ITSR0)
  @R0
  D=M
(OUTPUT_D)
  @R2
  M=D
(END)
  @END
  0;JMP

@ITSR0 기호가 (ITSR0)보다 먼저 나왔다.

처음 보는 기호를 변수로 저장한다 했다면 ITSR0는 변수로써 16값으로 기호 테이블에 추가되는 버그가 생긴다.

이를 해결하기 위해 전체를 두 번 훑어보는 2-pass 어셈블러로 만든다.

first pass에선 L 명령어만을 감지해서 레이블 기호를 기호 테이블에 추가한다.

second pass에선 기호를 마주쳤을 때 기호 테이블에 있다면 그 symbol에 해당하는 address를 받아 쓰고, 기호 테이블에 없다면 변수로써 처리하면 된다.

---

이제 SymbolTable 모듈을 사용해 어셈블러에 기호를 처리하는 기능을 추가해보자.

다음은 기능이 추가된 Assemlber.java의 main 메소드이다.

main

	public static void main(String[] args) {
        String inputFileName = args[0];
        String outputFileName = inputFileName.split("\\.")[0] + ".hack";

        try {
            File inputFile = new File(inputFileName);
            Parser parser = new Parser(inputFile);
            Code code = new Code();
            // symbolTable 객체 생성
            SymbolTable symbolTable = new SymbolTable();
            FileWriter writer = new FileWriter(outputFileName);

            // L_COMMAND 를 처리하는 firstPass
            firstPass(parser, symbolTable);
            // parser 가 다시 처음부터 보도록 초기화
            parser.reset(inputFile);

            // 변수가 할당되기 시작하는 값
            int variableAddress = 16;

            while (parser.hasMoreLines()) {
                parser.advance();

                if (parser.commandType().equals("A_COMMAND")) {
                    // symbol 이 기존 symbolTable 에 존재하지 않는 경우 writeAInstruction 의 return 값이 variableAddress + 1
                    variableAddress = writeAInstruction(parser, writer, symbolTable, variableAddress);
                } else if (parser.commandType().equals("C_COMMAND")) {
                    writeCInstruction(parser, code, writer);
                }
            }

            writer.close();
            System.out.println("Assembly completed.");
        } catch (IOException e) {
            System.err.println("Error: " + e.getMessage());
        }
    }

변경 사항이 있는 부분에 주석을 추가했다.

먼저 SymbolTable 객체를 symbolTable로 생성하였다.

그리고 L-명령어를 처리해 symbolTable에 추가하는 작업만을 하는 firstPass 를 수행하였다.

firstPass

    private static void firstPass(Parser parser, SymbolTable symbolTable) {
        int countInstruction = 0;

        while (parser.hasMoreLines()) {
            parser.advance();
            String commandType = parser.commandType();

            if (commandType.equals("A_COMMAND") || commandType.equals("C_COMMAND")) {
                countInstruction++;
            } else if (commandType.equals("L_COMMAND")) {
                symbolTable.addEntry(parser.symbol(), countInstruction);
            }
        }
    }

A 명령어와 C 명령어를 만나면 countInstruction 값만 증가시키고, L 명령어를 만나면 countInstruction 값과 symbol의 쌍을 symbolTable에 추가해준다.

두 번째 pass 를 하기 위해선 parser가 다시 inputFile의 첫 부분을 가리켜야 한다. 이를 위해 Parser 모듈에 reset 메소드를 추가하였다.

Parser.reset()

public void reset(File inputFile) throws FileNotFoundException {
        scanner.close();
        this.scanner = new Scanner(inputFile);
    }

두 번째 pass 를 진행하기 전에, parser.reset(inputFile); 명령을 통해 parser를 초기화 시켜둔다.

variableAddress 변수를 사용하여 변수를 마주쳤을 때 바인딩할 주소를 기록한다. 한 번 기록이 마쳐질 때마다 +1이 된다.

두 번째 pass는 기능 추가 전의 로직과 유사하다. 여기서 writeAInstruction 메소드만 수정해주었다.

writeAInstruction

private static int writeAInstruction(Parser parser, FileWriter writer, SymbolTable symbolTable, int variableAddress) throws IOException {
        String symbol = parser.symbol();
        // 첫 글자가 숫자 -> 상수
        if (Character.isDigit(symbol.charAt(0))) {
            writer.write(decimalStringTo16BitBinaryString(symbol));
            writer.write('\n');
            return variableAddress;
        } else {
        	// symbolTable에 존재 -> 레이블 기호, 선언 기호
            if (symbolTable.contains(symbol)) {
                writer.write(decimalStringTo16BitBinaryString(String.valueOf(symbolTable.getAddress(symbol))));
                writer.write('\n');
                return variableAddress;
            }
            // symbolTable에 존재하지 않음 -> 변수
            else {
                symbolTable.addEntry(symbol, variableAddress);
                writer.write(decimalStringTo16BitBinaryString(String.valueOf(variableAddress)));
                writer.write('\n');
                return variableAddress + 1;
            }
        }
    }

A 명령어는 세 가지 경우의 수가 있다.

• 상수인 경우
• 기호 테이블에 있는 경우
• 기호 테이블에 없는 경우

변수와 레이블 기호는 숫자로 시작할 수 없다는 규칙이 있기 때문에, A 명령어에서 symbol의 첫 글자가 숫자라면 상수가 된다.

상수가 아니라면 레이블 기호이거나, 선언 기호이거나, 변수가 된다.
레이블 기호와 선언 기호는 symbolTable상에 존재하므로, 지금 A 명령어의 symbol이 symbolTable상에 존재하는지로 분기가 가능하다.

symbolTable에 존재하는 경우, symbol에 해당하는 address를 받아 binary 코드로 만들어 outputFile에 작성해주면 된다.

변수의 경우, 변수와 현재 저장 가능한 주소를 쌍으로 symbolTable에 추가한다. 그 다음 variableAddress의 값을 binary 코드로 변환한 후 outputFile에 작성해준다. 이 경우, variableAddress의 값이 하나 증가해야하기 때문에 return 값으로 variableAddress + 1을 해준다.

---

이제 어셈블러가 완성되었다. 어셈블러로 기호가 포함된 max.asm 프로그램을 어셈블해보겠다.

먼저 javac Assembler.java로 Assembler.java를 컴파일 해준다.

이제 Max.asm 파일을 어셈블러 실행의 인자로 넘겨주면 된다.

Assemly completed. 라는 메시지와 함께 Max.hack 파일이 생성되었다.

Max.asm

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/6/max/Max.asm

// Computes R2 = max(R0, R1)  (R0,R1,R2 refer to RAM[0],RAM[1],RAM[2])
// Usage: Before executing, put two values in R0 and R1.

  // D = R0 - R1
  @R0
  D=M
  @R1
  D=D-M
  // If (D > 0) goto ITSR0
  @ITSR0
  D;JGT
  // Its R1
  @R1
  D=M
  @OUTPUT_D
  0;JMP
(ITSR0)
  @R0
  D=M
(OUTPUT_D)
  @R2
  M=D
(END)
  @END
  0;JMP

Max.hack

0000000000000000
1111110000010000
0000000000000001
1111010011010000
0000000000001010
1110001100000001
0000000000000001
1111110000010000
0000000000001100
1110101010000111
0000000000000000
1111110000010000
0000000000000010
1110001100001000
0000000000001110
1110101010000111

---

6장에선 어셈블러를 직접 개발해보았다. 어셈블러를 개발해보면서 하나의 프로그램이 어떻게 개발되는지, 그 과정을 알 수 있었다.

그동안 알고리즘 문제를 풀기 위해 java를 사용할 때는 그저 하나의 코드 단락만을 작성했다면, 이번 어셈블러 프로그램을 제작할 때는 여러 모듈을 사용하고, 명령줄에서 인자를 넘겨받는 등 하나의 프로그램을 만들어서 더 의미있었다.

프로그램을 단순하게 만들어 놓고 추후에 기능을 업데이트 해보는 경험도 좋았다. 처음부터 기호 처리를 포함한 어셈블러를 제작하는 것은 어려울 것이지만, 간단한 버전의 어셈블러를 제작하고 기능을 확장하는 것은 수월했다. 이 과정을 통해 코드를 왜 메소드 단위로 끊는 것이 유지 보수에 용이한지 직접 느낄 수 있었다.

---

이로써 [밑바닥부터 만드는 컴퓨팅 시스템]의 1부 - 하드웨어 파트가 마무리 되었다.

하드웨어 파트에서 다룬 내용을 간단히 정리해보자.

1. 불 논리

• 여러가지 논리 게이트 제작 (Nand, Mux, DMux 등등)

2. 불 연산

• 가산기와 ALU 제작

3. 메모리

• 플립플롭, RAM 등 제작

4. 기계어

• 핵 어셈블리어

5. 컴퓨터 아키텍처

• CPU, Memory, ROM32K 칩을 활용해 Computer 칩 제작

6. 어셈블러

• 핵 어셈블리어를 핵 기계어로 변환하는 프로그램 제작

이로써 범용 컴퓨터의 기반을 만들었다.

2부에선 이러한 기반 위에 가상 머신, 컴파일러, 운영체제등을 올려 정말 tetris와 같은 프로그램을 수행할 수 있는 컴퓨터를 만들어볼 것이다.