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

SeungHeon Kim·2022년 4월 28일

The Elements of Computing System

목록 보기

6/8

우리는 1장부터 5장까지 공부하며 nand게이트부터 CPU까지 만들었다. 6장부터는 소프트웨어 계층에 초점을 맞추어서 컴파일러, 객체 기반 프로그래밍 언어, 운영체제까지 개발할 것이다. 먼저 가장 기본이 되는 어셈블러를 먼저 만들어 볼텐데, 이번 장에서는 어셈블러가 어떻게 2진코드로 변환하는지와 더 나아가서 핵 어셈블러를 직접 만들어볼 예정이다.

6.1 배경

기계어는 직관적이지 않다. 다양한 연산 코드, 메모리 주소 지정 방식, 명령어 형식으로 인해서 110000101000000110000000000000111 같은 2진코드 보다는 LOAD R3 7처럼 약속된 문법으로 표기하는 것이 더 직관적이다. 그리고 기호를 2진 코드로 옮기기는 쉽기 때문에 어셈블리 코드를 거쳐서 최종 실행 바이너리 코드로 빌드하는 것이 효율적이다.

기호
- 변수
  
  번역기가 기호로 표기된 변수명을 발견하면 '자동적으로'그 기호를 주소에 할당한다.
- 레이블
  
  프로그래머는 프로그램 내 다양한 위치를 기호로 표시해놓을 수 있다.
  2진 명령어들은 실제 숫자를 이용해서 해당 변수의 메모리 주소를 표기하지만, 하지만 어셈블리는 그 대신에 변수명을 직접 표기해서 사용할 수 있다.
  ex) LOAD R3, 7 -> LOAD R3, weight
  
  하지만 사용자 정의 변수명과 기호 레이블을 실제 메모리 주소에 매핑하는 것은 그리 간단하지 않다. 실제로 하드웨어에서 소프트웨어로 전환되는 과정 중에 가장 먼저 접하는 난관이 바로 이 기호 변환 작업이다.
기호 변환

위의 그림은 기호가 포함된 코드를 기호가 해석된 코드로 바꾸는 과정을 그린 것이다.
먼저 사용자 정의 변수인 i와 sum은 차례대로 메모리 주소 1024, 1025를 할당받는다. 그리고 레이블 loop와 end는 그 선언된 위치에 따라서 명령어 주소 2와 6을 각각 할당 받는다. 이에 대한 내용을 가운데의 기호 테이블에 표시하고, 기호 테이블을 토대로 최종 코드를 만들 수 있다.
어셈블러
어셈블러는 기본적으로 번역 기능이 있는 텍스트 처리 프로그램이다. 따라서 어셈블리 문법에 대한 전체 문서가 있어야 한다. 보통 기계어 명세라 불리는 이 규칙을 따르면 기호 명령마다 다음과 같은 작업을 수행하는 프로그램을 만드는 일은 그리 어렵지 않다.
- 구문 분석을 통해 기호 명령 내 필드들 식별
- 각 필드에 대응하는 기계어 비트 생성
- 모든 기호 참조를 메모리 주소를 가리키는 숫자로 변환
- 2진 코드들을 조립하여 완전한 기게 명령어로 변환

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

6.2.1 문법 관례와 파일 형식

파일명

관례적으로 어셈블리로 작성된 파일은 .asm, 2진 기계어 코드로 작성된 파일은 .hack 확장자를 가진다.
2진 코드(.hack) 파일

16비트 기계어 명령어를 0과 1형태의 ASCII 문자열로 작성되어 있다. 프로그램의 라인 번호와 명령어 메모리(ROM)의 주소는 둘 다 0에서 시작한다.
어셈블리어(.asm) 파일
명령어나 기호 선언이 어셈블리어로 작성되어 있다.
- 명령어 : A-명령어 또는 C-명령어
- (Label) : 실제 기계어 코드로 번역되지 않지만, Symbol table에 (Label, address)를 추가한다. 여기서 address는 (Label) 다음에 쓰인 명령어의 주소이다.
상수와 기호

상수는 10진법으로 표기된 음수가 아닌 숫자이다. 기호는 문자, 숫자, 밑줄(_), 마침표(.), 달러 기호($), 콜론(:)들로 이루어진 문자열로 맨 앞 글자는 숫자가 아니어야 한다.
주석

두개의 빗금(//)에서 라인 끝까지의 텍스트는 주석으로 간주되어 무시된다.
공백

공백 문자와 빈 라인은 무시된다.
대소문자 규칙

어셈블리 연상기호는 전부 대문자로 써야 한다. 사용자 정의 레이블과 변수명은 대소문자 구분을 한다.

6.2.2 명령어

핵 기계어는 주소 명령어(A-명령어)와 계산 명령어(C-명령어) 두 종류로 구성된다. 이에 대한 자세한 설명은 Chapter 4 : 기계어 파트에서 자세히 설명했다.

6.2.3 기호

핵 어셈블리는 상수나 기호로 메모리 위치(주소)를 참조할 수 있는데, 다음은 어셈블리에서 기호를 쓰는 방법 세가지다.

선언 기호

핵 시스템이 기본적으로 제공하는 기호라고 생각하면 될 것이다.
레이블 기호

실제 수행할 명령어는 아닌 의사명령 (Xxx)는 Xxx가 프로그램의 다음 명령이 있는 명령어 메모리 주소를 참조하도록 정의한다.
변수 기호

프로그램 내에서 (Xxx)로 정의되지 않는 Xxx는 변수로 취급된다. 변수는 등장한 순서대로 RAM주소 16부터 차례대로 매핑된다.

6.2.4 예제

주의 : 핵 어셈블러는 2진 코드를 생성하고 이 파일이 직접적으로 CPU에서 실행되지만, 일반적인 컴퓨터에서는 어셈블러가 16진수 objct파일을 만들고 만들어진 object 파일들을 linker가 조합하여 최종 실행파일을 만든다. 이를 Hex Fiend로 열어보면 첫 부분에 라이브러리를 불러오는 헤더가 있고 중간 부분에 오브젝트 파일의 내용이 들어있는 것을 확인 할 수 있다.

6.3 구현

핵 어셈블러는 기본적으로 위와 같이 Parser, SymbolTabel, Code 세 가지 모듈로 구성되어 있다. 지금부터 각 모듈이 어떤 역할을 하는지 알아보자

6.3.1 Parser 모듈

어셈블리 명령을 읽어 구문분석을 하고, 필드와 기호에 편리하게 접근하도록 한다. 추가로 모든 공백과 주석을 제거한다. 다음은 Parser class의 기본 메소드다.

6.3.2 Code 모듈

핵 어셈블리의 연상기호 ex) D=A, D;JMP 를 2진 코드로 번역한다.
다음은 Code class의 기본 메소드다.

6.3.3 SymbolTable 모듈

핵 명령어의 번역 과정에서 기호들을 실제 주소로 바꾸어야 하는데, 기호와 그 의미의 대응관계를 관리하는 기호 테이블(Symbol table)을 만들었다. 이를 자연스럽게 구현할 수 있는 해시 테이블이라는 데이터 구조가 있다. 다음은 SymbolTable class의 기본 메소드다.

6.3.4 어셈블러 구현

위의 그림은 내가 C++로 구현한 어셈블러의 실행 흐름을 표현한다.
1. Code 객체를 생성하는데, Code class는 Parser에게 상속 받는다.
2. 객체 생성후에 Parser의 생성자고 호출되는데, 인자로 받은 어셈블리 파일을 읽는다.
3. 1st pass와 2nd pass를 거치는데 이는 단계를 보기 쉽게 나눈것 뿐이므로 pass 자체가 가진 의미는 없다.
4. 1st pass : .asm 파일의 문자열을 읽어 vector로 저장하는데, 이때 주석과, 공백을 제거하고, (Xxx)를 만날 시에 (Xxx, address)를 symbol table에 저장하고 (Xxx) 문자열은 제거한다.
5. 2nd pass : 다시 처음부터 vector를 읽기 시작하는데, 변수를 만날 시에 (변수, address)를 symbol table에 저장하고, @Xxx에서 Xxx를 해당하는 주소로 대체한다.
6. 이로서 모든 기호가 주소값으로 대체된 명령어가 완성되었다. 이를 Code 모듈에서 2진 코드를 생성해 .hack 파일에 쓴다.

6.3.5 C++ Code

main.cpp

#include "Code.hpp"
#include "Parser.hpp"

int main(int argc, char **argv){
    Code *assembler = new Code(argv[1]);

    assembler->write_binary();
    
    return 0;
}

Parser.hpp

#ifndef Parser_hpp
#define Parser_hpp

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <unistd.h>
#include <sys/types.h>

#include "Instruction.hpp"
#include "SymbolTable.hpp"

using namespace std;

class Parser {
private:
    int cur_index = 0;
    int numOfLine = 0;
    string write_file_name;
    ifstream readFile;
    vector<string> _assembly;
    SymbolTable symbols;
    // vector<string>::iterator _assembly_iterator;
public:
    Parser(){};
    Parser(string read_file_name) {
        this->readFile.open(read_file_name); 
        for(int i=0; i<3; i++)
            read_file_name.pop_back();
        this->write_file_name = read_file_name;
        write_file_name.push_back('h');
        write_file_name.push_back('a');
        write_file_name.push_back('c');
        write_file_name.push_back('k');
        // this->_assembly_iterator = this->_assembly.begin();
        this->first_pass();
        this->second_pass();
        // this->symbols.print_map();
        // this->_print_assembly();
    };
    ~Parser() {
    };
    void first_pass();
    void second_pass();

    int get_numOfLine();
    int get_cur_index();
    string get_cur_instruction(int index);
    string get_write_file_name();
    
    void reset();
    void _print_assembly();
    bool is_digit(string str);

    bool hasMoreCommands();
    void advance();
    COMMAND_TYPE commandType();
    string symbol();
    string dest();
    string jump();
    string comp();
    string to_binary(int num);
};

#endif

Parser.cpp

#include "Parser.hpp"

using namespace std;


void Parser::first_pass(){
    string instruction;
    if (this->readFile.is_open()){
        while(getline(this->readFile, instruction)){
            if(instruction.front()!='/' && instruction.size()!=1){
                while(instruction.front()==' '){
                    instruction.erase(instruction.begin());
                }
                if(instruction.find(" ")!=string::npos)
                    instruction.resize(instruction.find(" ")+1);
                this->_assembly.push_back(instruction);
                this->numOfLine++;
            }
        }
        this->cur_index = 0;
        while(this->hasMoreCommands()==1){
            if(this->commandType()==L_COMMAND) {
                this->numOfLine--;
                instruction = this->get_cur_instruction(this->get_cur_index());
                instruction = instruction.substr(1, instruction.size()-3);
                this->symbols.addEntry(instruction, this->get_cur_index());
                this->_assembly.erase(this->_assembly.begin()+cur_index);
            }
            this->advance();
        }
    }
}

void Parser::second_pass(){
    string label;
    this->cur_index=0;
    while(this->hasMoreCommands()==1){
        if(this->commandType()==A_COMMAND && !this->is_digit(this->_assembly[cur_index].substr(1, this->_assembly[cur_index].size()-1))){
            label = this->_assembly[cur_index].substr(1, this->_assembly[cur_index].size()-1);
            if(this->symbols.contains(label)){
                this->_assembly[cur_index].replace(1, -1, to_string(this->symbols.getAddress(label)));
            }
            else {
                this->symbols.addEntry(label, this->symbols.get_extra_address());
                this->_assembly[cur_index].replace(1, -1, to_string(this->symbols.getAddress(label)));
            }
        }
        this->cur_index++;
    }
    this->cur_index = 0;
}

int Parser::get_numOfLine(){
    return this->numOfLine;
};

string Parser::get_write_file_name(){
    return this->write_file_name;
}

int Parser::get_cur_index(){
    return this->cur_index;
}

string Parser::get_cur_instruction(int index){
    return this->_assembly[index];
}

void Parser::_print_assembly(){
    for(int i=0;i<this->_assembly.size();i++){
        cout << this->_assembly[i] << endl;
    }
}

bool Parser::hasMoreCommands(){
    if(this->cur_index==this->_assembly.size()-1)
        return 0;
    else
        return 1;
}

void Parser::advance(){
    if(this->hasMoreCommands()==1){
        this->cur_index++;
    }
}

void Parser::reset(){
    this->cur_index = 0;
}

COMMAND_TYPE Parser::commandType(){
    if(this->_assembly[this->cur_index].front()=='@')
        return A_COMMAND;
    else if(this->_assembly[this->cur_index].front()=='(')
        return L_COMMAND;
    else
        return C_COMMAND;
}

string Parser::symbol(){
    if(this->commandType()==A_COMMAND){
        return this->_assembly[this->cur_index].substr(1);
    }
    else if(this->commandType()==L_COMMAND){
        return this->_assembly[this->cur_index].substr(1,this->_assembly[this->cur_index].size()-2);
    }
    return "";
}

string Parser::dest(){
    int equal_index = this->_assembly[this->cur_index].find('=');
    if(equal_index==string::npos)
        return "null0";
    else
        return this->_assembly[this->cur_index].substr(0, equal_index);
        
}

string Parser::jump(){
    int semiColone_index = this->_assembly[this->cur_index].find(';');
    if(semiColone_index==string::npos)
        return "null";
    else
        return this->_assembly[this->cur_index].substr(semiColone_index+1, 3);
}

string Parser::comp(){
    int equal_index = this->_assembly[this->cur_index].find('=');
    int semiColone_index = this->_assembly[this->cur_index].find(';');
    size_t len;
    len = this->_assembly[cur_index].size()-equal_index-2;
    if(equal_index!=string::npos){
        return this->_assembly[this->cur_index].substr(equal_index+1, len);
    }
    else if(semiColone_index!=string::npos){
        return this->_assembly[this->cur_index].substr(0, semiColone_index);
    }
    else
        return "";
}

string Parser::to_binary(int num) {
    string binary15 = "000000000000000";
    string binary = "";
    while (num > 0) {
        if (num % 2 == 1) binary = "1" + binary;
        else binary = "0" + binary;
        num >>= 1;
    }
    binary15.replace(15-binary.size(), binary.size(), binary);
    return binary15;
}

bool Parser::is_digit(string str) {
    return atoi(str.c_str()) != 0;
}

SymbolTable.hpp

#ifndef SymbolTable_hpp
#define SymbolTable_hpp

#include <map>
#include <string>
#include <iostream>

using namespace std;

class SymbolTable
{
private:
    int extra_address = 16;
    map<string, int> _symbol_table;
    map<string, int>::iterator iter;
public:
    SymbolTable(){
        this->iter = _symbol_table.begin();

        this->_symbol_table["R0"] = 0;
        this->_symbol_table["R1"] = 1;
        this->_symbol_table["R2"] = 2;
        this->_symbol_table["R3"] = 3;
        this->_symbol_table["R4"] = 4;
        this->_symbol_table["R5"] = 5;
        this->_symbol_table["R6"] = 6;
        this->_symbol_table["R7"] = 7;
        this->_symbol_table["R8"] = 8;
        this->_symbol_table["R9"] = 9;
        this->_symbol_table["R10"] = 10;
        this->_symbol_table["R11"] = 11;
        this->_symbol_table["R12"] = 12;
        this->_symbol_table["R13"] = 13;
        this->_symbol_table["R14"] = 14;
        this->_symbol_table["R15"] = 15;

        this->_symbol_table["SCREEN"] = 16384;
        this->_symbol_table["KBD"] = 24576;
        this->_symbol_table["SP"] = 0;
        this->_symbol_table["LCL"] = 1;
        this->_symbol_table["ARG"] = 2;
        this->_symbol_table["THIS"] = 3;
        this->_symbol_table["THAT"] = 4;
    };

    ~SymbolTable(){

    }

    int get_extra_address();
    void addEntry(string symbol, int address);
    bool contains(string symbol);
    int getAddress(string Symbol);
    void print_map();
};

#endif

SymbolTable.cpp

#include "SymbolTable.hpp"

void SymbolTable::addEntry(string symbol, int address){
    this->_symbol_table[symbol] = address;
}

bool SymbolTable::contains(string symbol){
    this->iter = this->_symbol_table.find(symbol);
    return (iter!=this->_symbol_table.end());
}

int SymbolTable::getAddress(string symbol){
    return this->_symbol_table[symbol];
}

int SymbolTable::get_extra_address(){
    return this->extra_address++;
}

void SymbolTable::print_map() {
    for (map<string, int>::iterator itr = this->_symbol_table.begin(); itr != this->_symbol_table.end(); ++itr) {
        cout << itr->first << " " << itr->second << endl;
    }
}

Code.hpp

#ifndef Code_hpp
#define Code_hpp

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <unistd.h>
#include <sys/types.h>
#include "Parser.hpp"


using namespace std;

class Code : Parser {
private:
    ofstream writeFile;
public:
    Code(string read_file_name) : Parser(read_file_name){
        this->writeFile.open(this->get_write_file_name());
    }
    
    string incode_dest();
    string incode_jump();
    string incode_comp();
    
    void write_binary();
};

#endif

Code.cpp

#include "Code.hpp"

string Code::incode_dest(){
    string symbol = this->dest();
    
    if(symbol.compare("null0")==0)
        return "000";
    else if(symbol.compare("M")==0)
        return "001";
    else if(symbol.compare("D")==0)
        return "010";
    else if(symbol.compare("MD")==0)
        return "011";
    else if(symbol.compare("A")==0)
        return "100";
    else if(symbol.compare("AM")==0)
        return "101";
    else if(symbol.compare("AD")==0)
        return "110";
    else if(symbol.compare("AMD")==0)
        return "111";
    else
        return "";
}

string Code::incode_jump(){
    string symbol = this->jump();

    if(symbol.compare("null")==0)
        return "000";
    else if(symbol.compare("JGT")==0)
        return "001";
    else if(symbol.compare("JEQ")==0)
        return "010";
    else if(symbol.compare("JGE")==0)
        return "011";
    else if(symbol.compare("JLT")==0)
        return "100";
    else if(symbol.compare("JNE")==0)
        return "101";
    else if(symbol.compare("JLE")==0)
        return "110";
    else if(symbol.compare("JMP")==0)
        return "111";
    else
        return "";
}

string Code::incode_comp(){
    string symbol = this->comp();

    if(symbol.compare("0")==0)
        return "0101010";
    else if(symbol.compare("1")==0)
        return "0111111";
    else if(symbol.compare("-1")==0)
        return "0111010";
    else if(symbol.compare("D")==0)
        return "0001100";
    else if(symbol.compare("A")==0)
        return "0110000";
    else if(symbol.compare("!D")==0)
        return "0001101";
    else if(symbol.compare("!A")==0)
        return "0110001";
    else if(symbol.compare("-D")==0)
        return "0001111";
    else if(symbol.compare("-A")==0)
        return "0110011";
    else if(symbol.compare("D+1")==0)
        return "0011111";
    else if(symbol.compare("A+1")==0)
        return "0110111";
    else if(symbol.compare("D-1")==0)
        return "0001110";
    else if(symbol.compare("A-1")==0)
        return "0110010";
    else if(symbol.compare("D+A")==0)
        return "0000010";
    else if(symbol.compare("D-A")==0)
        return "0010011";
    else if(symbol.compare("A-D")==0)
        return "0000111";
    else if(symbol.compare("D&A")==0)
        return "0000000";
    else if(symbol.compare("D|A")==0)
        return "0010101";
    else if(symbol.compare("M")==0)
        return "1110000";
    else if(symbol.compare("!M")==0)
        return "1110001";
    else if(symbol.compare("-M")==0)
        return "1110011";
    else if(symbol.compare("M+1")==0)
        return "1110111";
    else if(symbol.compare("M-1")==0)
        return "1110010";
    else if(symbol.compare("D+M")==0)
        return "1000010";
    else if(symbol.compare("D-M")==0)
        return "1010011";
    else if(symbol.compare("M-D")==0)
        return "1000111";
    else if(symbol.compare("D&M")==0)
        return "1000000";
    else if(symbol.compare("D|M")==0)
        return "1010101";
    else 
        return "";
}

void Code::write_binary(){
    string str;
    int num;
    int i = 0;
    for(i=0; i<get_numOfLine(); i++){
        if(this->commandType()==C_COMMAND)
            str = "111"+this->incode_comp()+this->incode_dest()+this->incode_jump();
        if(this->commandType()==A_COMMAND){
            num = stoi(this->symbol());
            str = "0"+this->to_binary(num);
        }
        this->writeFile << str << endl;
        advance();
    }
}

Instruction.hpp

#ifndef Instruction_hpp
#define Instruction_hpp

enum COMMAND_TYPE {
    A_COMMAND = 0,
    C_COMMAND,
    L_COMMAND
};

#endif

SeungHeon Kim

성장

이전 포스트

Chapter 5 컴퓨터 아키텍처- [밑바닥부터 만드는 컴퓨팅 시스템]

다음 포스트