반응형
- 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에서 주소를 찾아간다.
- functionTable에 함수의 주소를 등록해준다.
- 그 다음 함수의 바디를 생성한다.
// 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 문 인지의 개수를 전달한다.
- 이것의 크기만큼 피연산자 스택에서 꺼내서 콘솔에 출력한다.
- 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()함수에 이렇게 추가해준다.
- Instruction::Alloca 코드를 추가해서 함수 실행 전에 지역변수 용 공간을 확보한다.
- initBlock에서는 symbolStack, offsetStack, localSize를 초기화 한다.
- 함수 바디를 생성하고 난 후에, popBlock()으로 스택을 정리한다.
- 그리고 이제 지역변수의 크기를 알았으므로, 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();
}- 유효 범위를 정해주기 위해, 시작과 끝에 pushBlock(), popBlock()을 해주었다.
- 제어 변수를 생성하고,
- 점프 주소를 기록한다.
- jumpAddress는 반복문 순회를 위해 기록한다.
- 조건문을 생성하고,
- 거짓일 때 점프하는 명령어를 작성한다.
- 다음으로 참일 때, 실행할 코드를 생성한다.
- i++ 증감식을 생성한다.
- 지역 변수를 제거하고,
- 다시 jumpAddress 주소로 가서 조건식을 평가 할 수 있게, jump 코드를 작성한다.
- 그리고 조건식이 거짓일 때, 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);
}
}- 조건문마다 실행 후, 만약 문의 마지막으로 이동해야 한다. Jump 문을 작성하기 위해 list를 생성한다.
- 코드 작성 전에는 마지막 주소가 어딘지 모르기 때문에 jump 코드 주소를 다 저장해둔다.
- conditions부터 작성하고, conditionaljump를 작성한다.
- jump하는 주소는 body를 다 적고, patch 해준다.
- body를 작성한다.
- 바디의 스코프 설정을 해줘야한다. pushblock()/popblock()
- 조건문을 다 적었으면, else 문 케이스에 대해 적어준다.
- 그리고 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문이 여러개 나올 수 있기 때문이다.
- 2중 리스트인 이유는
- 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
- 파라미터를 역순으로 생성한다 -> 스택구조이기 때문
- 피연산자식 코드를 생성한다.
- 피연산자는 함수를 뜻한다.
- Call 명령을 작성한다.
- Function
- 함수 Call에서 파라미터를 참조할 수 있게, Function::generate에서 local 변수로 등록해준다.
- Return
- 반환식을 생성하고
- 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);
}- 피연산자 식(배열 명)을 먼저 생성하고
- 인덱스를 작성한다.
- 그리고 명령어를 작성한다.
원소값 수정
auto SetElement::generate() -> void {
value->generate();
sub->generate();
index->generate();
writeCode(Instruction::SetElement);
}- GetElement에서 대입식 생성하는 코드만 추가되었다.
나머지 코드들도 작성해준다.
728x90
'CS > 컴파일러' 카테고리의 다른 글
| [컴파일러 만들기] 2. Parser 만들기 (0) | 2025.03.18 |
|---|---|
| [컴파일러 만들기] 1. Scanner 만들기 (0) | 2025.03.16 |
| [컴파일러 만들기] C++로 컴파일러 만들어보기 (0) | 2025.03.11 |
