[컴파일러 만들기] 3. Generator 만들기

• Generator는 목적 코드를 생성한다.
  • 목적코드는 기계가 읽을 수 있는 바이너리 형태의 코드이다. 
• Parser에서 syntax tree를 만들었었다.
  • 트리 구조는 비선형이라 순회가 비교적 느리다.
  • 트리를 선형 구조로 만들어서 속도를 높인다. 
• Generator는 비선형 구조인 syntax tree를 선형 구조로 표현하는 과정이다. 
• 우리는 가상머신을 만들고 그 위에서 동작할 수 있는 목적코드를 생성할 것이다. 

 

명령어 만들기

---

Code.h

 

#include <any>
using std::any;

enum class Instruction
{
	Exit,
	Call, Alloca, Return,
	Jump, ConditionJump,
	Print,

	LogicalOr, LogicalAnd,
	Add, Subtract,
	Multiply, Divide, Modulo,
	Equal, NotEqual,

	LessThan, GreaterThan,
	LessOrEqual, GreaterOrEqual,
	Absolute, ReverseSign,

	GetElement, SetElement,
	GetGlobal, SetGlobal,
	GetLocal, SetLocal,

	PushNull, PushBoolean,
	PushNumber, PushString,
	PushArray, PushMap,
	PopOperand,
};

struct Code
{
	Instruction instruction;
	any operand;
};

Node.h

struct Statement {
    virtual auto generate() -> void = 0;
};
struct Expression {
    virtual auto generate() -> void = 0;
};

typedef struct Function : Statement {
    wstring name;
    vector<wstring> parameters;
    vector<Statement*> blocks;
    auto generate() -> void;
} Function;

struct Or : Expression {
    Expression* lhs;
    Expression* rhs;
    auto generate() -> void;
};

• Statement와 Expression에 generate() 가상함수를 만든다.
• Generator.cpp에 구현체 스켈레톤을 만들어준다.

 

Main.cpp

tuple<vector<Code>, map<string, size_t>> generate(Program* syntaxTree);
auto printObjectCode(tuple<vector<Code>, map<string, size_t>>) -> void;

int main() {
    string sourceCode = R"(
        함수 시작() {
            출력("안녕");
            출력("\n");
            출력(1 + 2 * 3);
            출력("\n");
        }
    )";

    vector<Token> tokenList = scan(sourceCode);
	Program* syntaxTree = parse(tokenList);
	auto objectCode = generate(syntaxTree);
    printObjectCode(objectCode);

    return 0;
}

• generate 함수를 작성해주었다.

 

Generator.cpp

• korlang에서는 시작() 이라는 함수가 시작점이다.
• 함수를 호출하려면, 함수의 주소가 필요하다.

auto generate(Program* program) -> tuple<vector<Code>, map<wstring, size_t>>
{
    wstring main = L"시작";
    writeCode(Instruction::GetGlobal, main);
	//...
}

• generate함수는 "시작()"함수의 주소를 가져오는 GetGlobal 코드를 생성함으로써 시작한다.
  • 지금의 과정은 프로그램을 해석하고 실행하는 것이 아니다.
  • 목적코드를 작성하는 것. 트리 형태의 프로그램을 선형으로 나타내는 것이다.

static vector<Code> codeList;

auto writeCode(Instruction instruction) -> size_t {

    codeList.push_back({ instruction });
    return codeList.size() - 1;

}

auto writeCode(Instruction instruction, any operand) -> size_t {

    codeList.push_back({ instruction, operand });
    return codeList.size() - 1;

}

• writeCode()에서는 명령어를 만들어서 codeList에 삽입한다.
• 반환하는 것은 목적 코드의 상대주소이다. 

auto generate(Program* program) -> tuple<vector<Code>, map<wstring, size_t>>
{
    wstring main = L"시작";
    writeCode(Instruction::GetGlobal, main);
    writeCode(Instruction::Call, static_cast<size_t>(0));
    writeCode(Instruction::Exit);

    for (auto& node : program->functions)
    {
        node->generate();
    }

    return {codeList, functionTable};
}

• 그 다음으로는 함수를 호출하는 Call 명령을 작성한다.
  • GetGlobal로 가져온 "시작()" 함수를 호출한다는 뜻이다. 
  • 2번째 인자는 매개변수가 0개라는 의미이다. 
• 그 다음으로 프로그램의 종료, 즉 "시작()" 함수의 종료를 뜻하는 Exit 명령을 작성한다. 
• 그리고 코드 리스트와 함수 테이블을 반환한다.

"시작()"함수의 바디를 쓰기도 전에 EXIT을 먼저 쓰는 이유가 무엇일까?

• 앞에서 말했듯이 Generator의 과정은 목적 코드를 생성하는 과정이다.
• 선형으로 코드를 만든다.
• 실행할 때는, 순차적으로 실행하는 것이 아닌, Goto(jump)을 통해서 주소를 이동하여 실행할 수 있다.
• 그래서 "시작()" 함수 안에 모든 코드를 목적코드로 바꾼 다음에 Exit을 호출하는 것이 아닌 미리 적어놓을 수 있는 것이다. 
  • 종료할 때는 Exit 주소로 jump 하면 되기 때문이다. 

 

• Exit까지 작성한 다음. functions의 노드들을 생성한다.
• functions는 Program 구조체의 멤버로, Parser에서 생성한 syntax tree이다.

struct Program {
    vector<Function*> functions;
};

 

• korlang은 최상위에 function만 올 수 있다. 

static map<wstring, size_t> functionTable;

auto Function::generate() -> void {
    functionTable[name] = codeList.size();

    for (auto& node : blocks)
    {
        node->generate();
    }
    writeCode(Instruction::Return);

}

• generate에서 program의 functions를 생성했을 때는 Function::generate() 로 들어온다.
• 이제 함수의 바디를 목적 코드로 생성한다.
• 이 함수에서 첫번째로 생성하는 코드가 함수의 주소가 된다.
  • functionTable에 함수의 주소를 등록해준다.
    • 나중에 프로그램을 시작할 때, functionTable의 함수명과 매핑된 주소를 보고 codeList에서 주소를 찾아간다.
• 그 다음 함수의 바디를 생성한다.

 

// Print
auto Print::generate() -> void {
    for (int i = arguments.size(); i >= 0; i--)
    {
        arguments[i - 1]->generate();
    }
    writeCode(Instruction::Print, arguments.size());
}

• "출력()"함수는 이렇게 작성한다.
• 인자들을 먼저 생성하고, 그 다음 Print 를 작성한다.
  • 2번째 인자로 Print 문 인지의 개수를 전달한다.
    • 이것의 크기만큼 피연산자 스택에서 꺼내서 콘솔에 출력한다.

// NumberLiteral
auto NumberLiteral::generate() -> void {
    writeCode(Instruction::PushNumber, value);
}

// StringLiteral
auto StringLiteral::generate() -> void {
    writeCode(Instruction::PushString, value);
}

// Arithmetic
auto Arithmetic::generate() -> void {
    map<Kind, Instruction> instructions = {
            {Kind::Add, Instruction::Add},
            {Kind::Subtract, Instruction::Subtract},
            {Kind::Multiply, Instruction::Multiply},
            {Kind::Divide, Instruction::Divide},
            {Kind::Modulo, Instruction::Modulo}
    };

    lhs->generate();
    rhs->generate();
    writeCode(instructions[kind]);
}

• 이렇게 Instruction의 generate()함수도 작성해준다.

 

auto ExpressionStatement::generate() -> void {
    expression->generate();
}

• ExpressionStatement는 이런 코드가 있을 때 생성된다.

함수 시작()
{
	1 + 2;
}

• 계산식이지만, 그 자체로 하나의 문이다.

• 위의 코드로 generate를 수행하면 목적코드가 이렇게 나온다. 
• 이 상태에서 1+2의 결과인 3은 피연산자 스택에 남아있게 된다.
• 피연산자 스택에서 같은 가져와 버리는 코드를 작성해야한다.

auto ExpressionStatement::generate() -> void {
    expression->generate();
    writeCode(Instruction::PopOperand);
}

 

변수 선언

• 변수를 어떻게 관리할 수 있을까?
  • 변수의 이름과 값을 key와 value로 해서 map에 관리 할 수 있다.
  • 변수의 값이 위치한 주소를 사용할 수 있다.
    • 재귀 호출 등을 생각했을 때, 상대주소로 사용해야한다.

static list<map<wstring, size_t>> symbolStack;
static vector<size_t> offsetStack;
static size_t localSize = 0;

• symbolStack에서 map은 변수이름이 key이고, 상대주소 offset이 value이다.
  • 맵을 리스트로 갖고 있는 이유는, 변수의 유효범위를 관리하기 위함이다.
• offsetStack은 유효범위 별로 오프셋을 관리한다. 해당 유효범위에서 사용할 수 있는 가장 큰 오프셋 값을 저장해둔다.
• offsetStack에 담고있는 최대 오프셋 값은 메모리 공간의 크기와 같다.
  • 함수의 실행이 끝나면 지역 변수들 값을 버린다.
  • 지역 변수를 버리기 위해 오프셋 크기를 갖고 있는 변수가 localSize이다.

 

auto patchOperand(size_t codeIndex, size_t operand) -> void
{
	codeList[codeIndex].operand = operand;
}

auto initBlock() -> void
{
    localSize = 0;
	offsetStack.push_back(0);
    symbolStack.emplace_front();
}

auto popBlock() -> void
{
	offsetStack.pop_back();
	symbolStack.pop_front();
}

// Function
auto Function::generate() -> void {
    functionTable[name] = codeList.size();

    auto temp = writeCode(Instruction::Alloca);
    initBlock();
    for (auto& node : blocks)
    {
        node->generate();
    }
    popBlock();
    patchOperand(temp, localSize);

    writeCode(Instruction::Return);
}

• Function::generate()함수에 이렇게 추가해준다.
  1. Instruction::Alloca 코드를 추가해서 함수 실행 전에 지역변수 용 공간을 확보한다.
  2. initBlock에서는 symbolStack, offsetStack, localSize를 초기화 한다.
  3. 함수 바디를 생성하고 난 후에, popBlock()으로 스택을 정리한다.
  4. 그리고 이제 지역변수의 크기를 알았으므로, Instruction::Alloca 명령의 인자를 업데이트 해준다.

auto setLocal(wstring name) -> void
{
    symbolStack.front()[name] = offsetStack.back();
    offsetStack.back() += 1;
	localSize = max(localSize, offsetStack.back());
}

auto getLocal(wstring name) -> size_t
{
	for (auto& symbolTable : symbolStack)
	{
        if (symbolTable.count(name))
        {
            return symbolTable[name];
        }
	}
	return SIZE_MAX;
}

// Variable
auto Variable::generate() -> void {
    setLocal(name);
    expression->generate();
	writeCode(Instruction::SetLocal, getLocal(name));
    writeCode(Instruction::PopOperand);
}

• Variable::generate()는 이렇게 작성한다.
• setLocal에서는 symbolstack에 변수명으로 공간을 만들고, offset을 1 증가시킨다.
• 값을 생성한 다음, SetLocal 명령어를 작성한다. getLocal함수로 변수의 값을 받아와서 인자로 사용한다.
• 그리고 피연산자 스택을 비운다.

변수 참조

이 언어에서는 선언이 없는 변수의 참조는 전역변수로 간주한다.

getLocal 함수가 SIZE_MAX를 반환하면 로컬 참조가 없는 것이다.

// GetVariable
auto GetVariable::generate() -> void {
	if (getLocal(name) != SIZE_MAX)
	{
		writeCode(Instruction::GetLocal, getLocal(name));
	}
	else
	{
		writeCode(Instruction::GetGlobal, name);
	}
}

// SetVariable
auto SetVariable::generate() -> void {
    value->generate();
    if (getLocal(name) != SIZE_MAX)
    {
		writeCode(Instruction::SetLocal, getLocal(name));
    }
    else
    {
        writeCode(Instruction::SetGlobal, name);
    }
}

'반복' 문

반복문의 제어변수는 반복문 스코프 안에서만 유효하다.

// For
auto For::generate() -> void {
    pushBlock();
    variable->generate();
    auto jumpAddress = codeList.size();
	condition->generate();

    auto conditionJump = writeCode(Instruction::ConditionJump);

    // 참인 경우에 실행할 코드
    for (auto& node : blocks)
    {
		node->generate();
    }

	expression->generate();
	writeCode(Instruction::PopOperand);
	writeCode(Instruction::Jump, jumpAddress);
	patchAddress(conditionJump);
	popBlock();
}

1. 유효 범위를 정해주기 위해, 시작과 끝에 pushBlock(), popBlock()을 해주었다.
2. 제어 변수를 생성하고,
3. 점프 주소를 기록한다.
   1. jumpAddress는 반복문 순회를 위해 기록한다.
4. 조건문을 생성하고, 
5. 거짓일 때 점프하는 명령어를 작성한다.
6. 다음으로 참일 때, 실행할 코드를 생성한다.
7. i++ 증감식을 생성한다.
8. 지역 변수를 제거하고,
9. 다시 jumpAddress 주소로 가서 조건식을 평가 할 수 있게, jump 코드를 작성한다.
10. 그리고 조건식이 거짓일 때, jump할 주소를 업데이트 해준다.

 

'만약' 문

• 만약문은 여러 개의 조건문 (if, elif)과 블럭을 가진다.
• 하나의 본문을 실행한 뒤 끝으로 점프해야한다.

auto If::generate() -> void {
    vector<size_t> jumpList;
    for (int i = 0; i < conditions.size(); i++)
    {
        conditions[i]->generate();
		auto conditionJump = writeCode(Instruction::ConditionJump);
        pushBlock();
		for (auto& node : blocks[i])
		{
			node->generate();
		}
        popBlock();
        jumpList.push_back(writeCode(Instruction::Jump));
		patchAddress(conditionJump);

    }
    if (!elseBlock.empty())
    {
        pushBlock();
        for (auto& node : elseBlock)
        {
            node->generate();
        }
        popBlock();
    }

	for (auto& jump : jumpList)
	{
		patchAddress(jump);
	}
}

1. 조건문마다 실행 후, 만약 문의 마지막으로 이동해야 한다. Jump 문을 작성하기 위해 list를 생성한다.
   1. 코드 작성 전에는 마지막 주소가 어딘지 모르기 때문에 jump 코드 주소를 다 저장해둔다.
2. conditions부터 작성하고, conditionaljump를 작성한다.
   1. jump하는 주소는 body를 다 적고, patch 해준다.
3. body를 작성한다. 
   1. 바디의 스코프 설정을 해줘야한다. pushblock()/popblock()
4. 조건문을 다 적었으면, else 문 케이스에 대해 적어준다.
5. 그리고 if 문에 대한 목적코드를 모두 작성했으므로, jumplist를 patch해준다.

 

계속하기 문

• 계속하기(continue)문은 for문의 증감식 주소로 점프하는 명령이다.

static vector<vector<size_t>> continueStack;

// Continue
auto Continue::generate() -> void {
    if (continueStack.empty())
    {
        return;
    }

    auto jumpCode = writeCode(Instruction::Jump);
	continueStack.back().push_back(jumpCode);
}

• continueStack은 jump 코드의 주소를 담는 리스트이다. 
  • 2중 리스트인 이유는
    • for문 안에 continue가 여러개 올 수 있고,
    • for문이 여러개 나올 수 있기 때문이다. 
• Continue::generate에서는 코드 작성하고 리스트에만 넣어주고 끝이다.

// For
auto For::generate() -> void {
    continueStack.emplace_back();
    pushBlock();
    variable->generate();
    auto jumpAddress = codeList.size();
	condition->generate();

    auto conditionJump = writeCode(Instruction::ConditionJump);

    // 참인 경우에 실행할 코드
    for (auto& node : blocks)
    {
		node->generate();
    }

    auto continueAddress = codeList.size(); // 증감식 주소
	expression->generate();
	writeCode(Instruction::PopOperand);
	writeCode(Instruction::Jump, jumpAddress);
	patchAddress(conditionJump);
	popBlock();

    for (auto& jump : continueStack.back())
    {
		patchOperand(jump, continueAddress);
    }
    continueStack.pop_back();
}

• for문도 업데이트 해주었다.
• break문도 같은 논리 이므로 비슷하게 구현된다. 다만 증감식 위치로 가는 것이 아니라, for문 종료 위치로 patch 해줘야한다.

 

함수 호출

// Call
auto Call::generate() -> void {
	for (auto i = parameters.size(); i > 0; i--)
	{
		parameters[i - 1]->generate();
	}
	sub->generate();
	writeCode(Instruction::Call, parameters.size());

}

// Function
auto Function::generate() -> void {
    functionTable[name] = codeList.size();

    auto temp = writeCode(Instruction::Alloca);
    initBlock();
    for (auto& name : parameters)
    {
		setLocal(name);
    }

    for (auto& node : blocks)
    {
        node->generate();
    }
    popBlock();
    patchOperand(temp, localSize);

    writeCode(Instruction::Return);
}

// Return
auto Return::generate() -> void {
    expression->generate();
	writeCode(Instruction::Return);
}

• Call
  1. 파라미터를 역순으로 생성한다 -> 스택구조이기 때문
  2. 피연산자식 코드를 생성한다.
     1. 피연산자는 함수를 뜻한다. 
  3. Call 명령을 작성한다.
• Function
  • 함수 Call에서 파라미터를 참조할 수 있게, Function::generate에서 local 변수로 등록해준다.
• Return
  1. 반환식을 생성하고
  2. Return 코드를 작성한다.

 

배열

// ArrayLiteral
auto ArrayLiteral::generate() -> void {
    for (int i = values.size(); i > 0; i--)
    {
		values[i - 1]->generate();
    }
	writeCode(Instruction::PushArray, values.size());
}

• 피연산자 스택에 배열을 넣는 코드를 생성한다.
• 스택을 사용하기 때문에 역순으로 생성한다.

 

원소값 참조

• 배열이나 맵의 원소를 참조하는 목적 코드이다.
• arr[1] 이런거

auto GetElement::generate() -> void {
	sub->generate();
	index->generate();
	writeCode(Instruction::GetElement);
}

1. 피연산자 식(배열 명)을 먼저 생성하고
2. 인덱스를 작성한다.
3. 그리고 명령어를 작성한다.

 

원소값 수정

auto SetElement::generate() -> void {
    value->generate();
    sub->generate();
	index->generate();
	writeCode(Instruction::SetElement);
}

• GetElement에서 대입식 생성하는 코드만 추가되었다.

 

나머지 코드들도 작성해준다.