이 문서는 C++ 언어와 Koopa IR(Intermediate Representation)을 활용하여 컴파일러를 구축하는 과정에서 발생할 수 있는 주요 문제점들과 그 해결 방안을 다룹니다. 특히 Lex/Yacc(Flex/Bison) 기반의 컴파일러 프레임워크를 사용하는 개발자들이 참고할 수 있도록 실제 경험을 바탕으로 한 유용한 팁을 제공합니다.
환경 설정 및 기본 개념
Windows 환경에서 개발할 경우, 가상화 기반 보안(VBS) 기능이 특정 시나리오에서 그래픽 카드 성능에 영향을 줄 수 있습니다. Hyper-V와 같은 가상화 플랫폼과 VBS 간의 충돌을 피하기 위해, 개발자는 Hyper-V를 비활성화하는 방안을 고려할 수 있습니다. 이 경우 Docker와 같은 컨테이너 환경은 Linux 가상 머신에 설치하고 SSH를 통해 원격으로 접근하는 것이 일반적입니다.
Koopa IR에서는 함수, 기본 블록(BasicBlock), 값(Value)과 같은 요소들의 이름에 특정 접두사를 사용합니다. @는 주로 사용자 정의 함수나 전역 변수와 같이 "이름을 가진 심볼"을 나타내며, %는 컴파일러가 생성하는 임시 레지스터나 로컬 변수와 같은 "임시 심볼"을 의미합니다. 예를 들어, 소스 코드에 정의된 main 함수는 @main으로 표현될 수 있습니다.
어휘 분석 단계의 도전 과제
어휘 분석기(Lexer)를 위한 .lex 파일 작성 시, 주석 처리와 같은 특정 토큰 정의에서 예상치 못한 문제가 발생할 수 있습니다. 특히 C 스타일의 블록 주석(/* ... */)을 올바르게 인식하는 정규 표현식은 까다로울 수 있습니다. 초기에는 /\*[\s\S]*?\*\/와 같은 표현식을 시도했으나, 이는 특정 Lex/Flex 구현에서 제대로 작동하지 않는 경우가 있습니다. 대신 /\*.*?\*\/와 같이 더 단순한 형태가 의외로 효과적일 수 있습니다. 정규 표현식의 동작은 Lexer 도구의 구현에 따라 미묘한 차이를 보일 수 있으므로, 항상 테스트를 통해 검증해야 합니다.
AST 생성 및 IR 코드 생성
추상 구문 트리(AST)를 구성하고 이를 순회하여 Koopa IR 코드를 생성하는 과정에서는 다양한 고려 사항이 있습니다. DFS(깊이 우선 탐색) 방식은 AST를 순회하며 IR을 생성하는 데 효과적입니다. 이때, 각 노드의 Dump(또는 GenerateIR) 함수는 std::cout 대신 std::ostringstream을 사용하여 생성된 IR을 문자열 버퍼에 축적하는 방식으로 구현하여 유연성을 확보할 수 있습니다.
표현식 처리 시 유의점
산술/논리 시프트 연산
비트 시프트 연산에는 두 가지 주요 유형이 있습니다:
- 논리 오른쪽 시프트 (Logical Right Shift, shr): 모든 비트를 오른쪽으로 이동시키고, 가장 왼쪽(최상위) 비트는 항상 0으로 채워집니다. 이는 부호 비트를 고려하지 않으며, 양수나 부호 없는 정수에 대해 동일하게 작동합니다. 예: 이진수 1101을 논리 오른쪽으로 1비트 시프트하면 0110이 됩니다.
- 산술 오른쪽 시프트 (Arithmetic Right Shift, sar): 부호 있는 정수에 적용되며, 부호 비트(최상위 비트)를 유지하면서 비트를 오른쪽으로 이동시킵니다. 즉, 원래 수가 양수이면 0으로, 음수이면 1로 최상위 비트가 채워집니다. 예: 이진수 1101(음수로 간주)을 산술 오른쪽으로 1비트 시프트하면 1110이 됩니다.
AST 노드 구조 및 연산자 처리
단항 연산자(예: !, -)는 일반적으로 오른쪽에서 왼쪽으로 결합하므로, AST 노드의 GenerateIR 함수에서는 먼저 피연산자에 대한 IR을 생성한 후 단항 연산자 자체에 대한 IR을 생성해야 합니다.
Bison과 같은 파서 생성기를 사용할 때, 문자열 리터럴("abc")과 단일 문자 리터럴('a')을 엄격하게 구분해야 합니다. 잘못 사용하면 구문 오류(syntax error)가 발생할 수 있습니다.
다음은 단항 표현식을 처리하는 AST 노드의 예시입니다. 이 예시는 Koopa IR의 템포러리 레지스터(%temp_idx)를 생성하고 사용하며, IR 코드 스트림에 직접 추가하는 방식을 보여줍니다.
#include <memory>
#include <string>
#include <sstream>
// 가상의 BaseAST와 IRGenerationContext 정의
// 실제 구현에서는 이들이 더 복잡한 상태를 가질 수 있습니다.
class BaseAST {
public:
virtual ~BaseAST() = default;
virtual void GenerateIR(std::ostringstream &ir_stream, class IRGenerationContext& context) const = 0;
};
struct IRGenerationContext {
mutable int next_temp_reg_idx = 0; // 다음 사용 가능한 임시 레지스터 인덱스
mutable int last_literal_value = 0; // 마지막으로 생성된 리터럴 값
mutable bool last_result_is_literal = false; // 마지막 결과가 리터럴인지 여부
std::string get_last_result_representation() const {
if (last_result_is_literal) {
return std::to_string(last_literal_value);
} else {
// 마지막으로 사용된 임시 레지스터는 항상 next_temp_reg_idx - 1 입니다.
return "%" + std::to_string(next_temp_reg_idx - 1);
}
}
int get_and_increment_temp_reg_idx() const {
last_result_is_literal = false; // 새 임시 레지스터가 생성될 것이므로, 리터럴 아님
return next_temp_reg_idx++;
}
void set_last_result_literal(int val) const {
last_literal_value = val;
last_result_is_literal = true;
}
};
class UnaryExpressionNode : public BaseAST {
public:
std::unique_ptr<BaseAST> operand_expression; // 피연산자 표현식
char unary_operator_char; // 단항 연산자 문자 (예: '!', '-')
UnaryExpressionNode(char op, std::unique_ptr<BaseAST> expr)
: operand_expression(std::move(expr)), unary_operator_char(op) {}
void GenerateIR(std::ostringstream &ir_stream, IRGenerationContext& context) const override {
// 단항 연산자는 오른쪽에서 왼쪽으로 결합하므로, 피연산자 먼저 처리
operand_expression->GenerateIR(ir_stream, context);
// 피연산자의 IR 생성 결과 가져오기
std::string operand_repr = context.get_last_result_representation();
// 새 임시 레지스터 인덱스 할당
int current_temp_reg_idx = context.get_and_increment_temp_reg_idx();
std::string result_register = "%" + std::to_string(current_temp_reg_idx);
// 연산자에 따른 Koopa IR 생성
if (unary_operator_char == '!') {
ir_stream << result_register << " = eq " << operand_repr << ", 0\n";
} else if (unary_operator_char == '-') {
ir_stream << result_register << " = sub 0, " << operand_repr << "\n";
}
// context는 자동으로 마지막 결과가 현재 result_register임을 알게 됩니다.
}
};
IR 코드 생성 시 상태 관리
Koopa IR의 다양한 원시(raw) 요소를 레지스터(또는 메모리 위치)에 매핑하는 데 std::map이나 std::unordered_map을 사용할 때, 사용자 정의 타입이나 포인터를 키로 사용하면 문제가 발생할 수 있습니다. 대신, 모든 명령어가 궁극적으로 Koopa IR의 koopa_raw_value_t 타입으로 귀결되므로, 이를 맵의 키로 통일하여 사용하면 유연하고 일관된 상태 관리가 가능합니다.
특정 구현 방식에서는 연산 결과가 항상 새로운 임시 레지스터에 저장되지 않고, 기존의 레지스터를 덮어쓸 수 있습니다. 이러한 "레지스터 재사용" 전략을 따른다면, 각 연산 후 레지스터 카운터를 증가시키지 않을 수 있습니다. 그러나 일반적인 SSA(Static Single Assignment) 기반 IR 생성에서는 각 중간 결과마다 새로운 임시 레지스터를 할당하고 카운터를 증가시키는 것이 표준적입니다. 다음 예시는 표준적인 SSA 방식에 따라 이항 연산 후 새로운 임시 레지스터를 할당하는 방식을 보여줍니다.
void GenerateBinarySubtractIR(std::ostringstream& ir_stream, IRGenerationContext& context,
const BaseAST* left_operand_node, const BaseAST* right_operand_node) {
// 왼쪽 피연산자 IR 생성
left_operand_node->GenerateIR(ir_stream, context);
std::string left_operand_repr = context.get_last_result_representation();
// 오른쪽 피연산자 IR 생성
right_operand_node->GenerateIR(ir_stream, context);
std::string right_operand_repr = context.get_last_result_representation();
// 결과 저장을 위한 새 임시 레지스터 할당
int result_reg_idx = context.get_and_increment_temp_reg_idx();
ir_stream << "\t%" << result_reg_idx << " = sub " << left_operand_repr << ", " << right_operand_repr << "\n";
// context는 자동으로 마지막 결과가 현재 result_reg_idx임을 알게 됩니다.
}
복잡한 표현식(예: 2*3+4*5)을 IR로 변환할 때, 각 부분 표현식의 결과가 리터럴인지 아니면 임시 레지스터에 저장되었는지에 따라 출력 형식이 달라질 수 있습니다. 이러한 상황을 처리하기 위해 mul_done, add_done과 같은 플래그를 사용하여 각 부분 표현식의 처리 완료 여부를 추적하고, 그 결과에 따라 적절한 IR을 생성해야 합니다.
스마트 포인터 사용
C++에서 std::make_unique<T>()는 T 타입 객체를 힙에 할당하고 이를 관리하는 std::unique_ptr<T>를 생성합니다. 반면, std::unique_ptr<T>(raw_pointer)는 이미 존재하는 원시 포인터(raw pointer)의 소유권을 std::unique_ptr로 이전합니다. 예를 들어, auto comp_unit = std::make_unique<CompUnitAST>();는 새로운 CompUnitAST 객체를 생성하고 스마트 포인터로 관리하며, comp_unit->func_def = std::unique_ptr<BaseAST>(static_cast<BaseAST*>($1));는 Bison 액션에서 반환된 원시 포인터($1)의 소유권을 unique_ptr로 이전하는 방식입니다.
const 멤버 함수와 참조
C++ 클래스에서 const 멤버 함수는 객체의 상태를 변경할 수 없습니다. 따라서 const 멤버 함수 내에서는 오직 다른 const 멤버 함수만 호출할 수 있습니다. 또한, const 멤버 함수가 클래스 멤버 변수에 대한 참조를 반환할 때는 반드시 const 참조(예: const std::string&)를 반환해야 합니다. 비-const 참조를 반환하려고 하면 컴파일러 오류가 발생합니다. 다음 예시를 참고하십시오:
class DataStore {
private:
std::string name_data;
public:
DataStore(const std::string& name) : name_data(name) {}
// 올바른 사용: const 멤버 함수는 const 참조를 반환해야 합니다.
const std::string& GetNameConst() const {
return name_data;
}
// 잘못된 사용: const 멤버 함수가 비-const 참조를 반환하려고 시도 (컴파일 오류)
// std::string& GetNameMutableIncorrect() const {
// return name_data;
// }
// 올바른 사용: 비-const 멤버 함수는 비-const 참조를 반환할 수 있습니다.
std::string& GetNameMutable() {
return name_data;
}
};
Bison의 Shift/Reduce 충돌과 연산자 토큰화
Bison 문법을 작성할 때, ||, && 와 같은 두 글자 연산자들을 DoubleCharOp와 같은 단일 토큰으로 묶으면 Shift/Reduce 충돌이 발생할 수 있습니다. 이는 파서가 x op y 형태의 표현식을 처리할 때, op가 단일 문자인지 두 문자인지, 그리고 어떤 연산자에 해당하는지 모호해지기 때문입니다. 각 연산자(예: LOR_OP for ||, LAND_OP for &&)에 대해 고유한 토큰을 정의하여 문법의 모호성을 제거해야 합니다.
Koopa IR은 일반적으로 논리 연산(&&, ||)을 위한 특정 명령어를 제공합니다. 연산의 피연산자들이 항상 0 또는 1이라는 것을 알고 있다면, 비트 연산(andi, ori) 대신 명시적인 논리 연산 명령어(and, or)를 사용하는 것이 좋습니다. Koopa IR에서 and, or 명령어는 이진 논리 연산을 수행하며, 결과는 0 또는 1이 됩니다. 모든 피연산자가 0일 때 레지스터 할당 카운터가 이동하지 않아 레지스터 덮어쓰기 문제가 발생할 수 있으므로, 이러한 특수한 경우를 처리하기 위한 명시적인 카운터 증가 로직을 추가해야 할 수도 있습니다.
선언 및 스코프 관리
ENBF 반복 구문 구현
EBNF(Extended Backus-Naur Form)에서 {...}는 0회 이상의 반복을 나타냅니다. Bison 문법은 이를 직접 지원하지 않으므로, 재귀적인 규칙을 사용하여 이러한 반복을 구현해야 합니다. 예를 들어, ConstDecl ::= "const" BType ConstDef {"," ConstDef} ";";와 같은 반복되는 ConstDef 목록은 다음과 같이 재귀적으로 정의될 수 있습니다.
BlockItemList
: BlockItem {
auto stmt_list = std::make_unique<std::vector<std::unique_ptr<StatementNode>>>();
stmt_list->push_back(std::unique_ptr<StatementNode>(static_cast<StatementNode*>($1)));
$$ = stmt_list.release(); // $$에 원시 포인터 할당
}
| BlockItemList BlockItem {
auto stmt_list = std::unique_ptr<std::vector<std::unique_ptr<StatementNode>>>(static_cast<std::vector<std::unique_ptr<StatementNode>>*>($1));
stmt_list->push_back(std::unique_ptr<StatementNode>(static_cast<StatementNode*>($2)));
$$ = stmt_list.release();
}
;
이 패턴은 BlockItemList가 하나 이상의 BlockItem으로 구성된 벡터를 반환하도록 합니다. `$$`에 할당할 때 std::unique_ptr의 release() 메서드를 사용하여 소유권을 전달하는 것이 중요합니다.
스마트 포인터 벡터 순회
std::vector<std::unique_ptr<T>>와 같은 스마트 포인터 컬렉션을 범위 기반 for 루프(range-based for loop)로 순회할 때, for(auto i : my_vector) 형태는 unique_ptr를 복사하려고 시도하여 오류를 발생시킵니다. unique_ptr는 복사할 수 없으므로, for(const auto& i : my_vector)와 같이 참조를 사용하여 순회해야 합니다.
LVal (좌변 값)의 의미론적 검사
컴파일러는 좌변 값(LVal)을 처리할 때 중요한 의미론적 검사를 수행해야 합니다. 예를 들어:
- 상수 평가 시, 심볼 테이블에서 상수가 아닌 변수를 참조하면 의미론적 오류입니다. (예: 상수 표현식에서 변수 사용)
- 할당문(assignment statement)에서 좌변의
LVal이 변수가 아닌 상수에 해당하면 의미론적 오류입니다. (예:const_var = value;) - 이 외에도 심볼의 중복 정의나 미정의와 같은 상황은 의미론적 오류로 처리되어야 합니다.
전역 변수와 extern 키워드
여러 소스 파일에서 동일한 전역 변수를 사용해야 할 때, 단 하나의 파일에서 전역 변수를 정의하고, 다른 파일의 헤더에서는 extern 키워드를 사용하여 해당 변수를 선언해야 합니다. 이는 메모리 중복 할당을 방지하고 링커 오류를 피하기 위함입니다. 그러나 struct 정의는 메모리 할당을 수반하지 않고 단순히 타입을 정의하는 것이므로, 여러 헤더 파일에 포함되어도 문제되지 않습니다.
심볼 테이블 구현
심볼 테이블은 변수 및 함수의 정보를 저장하는 핵심 컴포넌트입니다. Koopa IR에서 다양한 원시 요소들을 매핑할 때, koopa_raw_value_t를 심볼 테이블의 키로 사용하면 유연성이 향상됩니다. 모든 Koopa IR 명령어가 궁극적으로 koopa_raw_value_t 타입의 값으로 귀결되기 때문에, 이를 통해 균일한 방식으로 정보를 관리할 수 있습니다. 자체 참조 구조체(self-referential struct)를 정의할 때, 다음과 같은 패턴을 활용할 수 있습니다.
#include <string>
#include <map> // 또는 <unordered_map>
// SymbolTable의 전방 선언
struct SymbolTable;
// SymbolTable 포인터의 타입 정의 (편의용)
typedef SymbolTable* SymbolTable_ptr;
// 실제 SymbolTable 정의
struct SymbolTable {
std::map<std::string, koopa_raw_value_t> identifiers; // 심볼 이름과 Koopa IR 값 매핑
SymbolTable_ptr parent_scope; // 부모 스코프 포인터
int depth = 0; // 스코프 깊이
SymbolTable() : parent_scope(nullptr), depth(1) {} // 기본 생성자
// 심볼을 현재 스코프 또는 상위 스코프에서 검색
SymbolTable_ptr find_identifier_scope(const std::string& ident_name) {
if (identifiers.count(ident_name)) {
return this; // 현재 스코프에 존재
}
if (parent_scope == nullptr) {
return nullptr; // 더 이상 상위 스코프가 없음
}
return parent_scope->find_identifier_scope(ident_name); // 부모 스코프에서 재귀 검색
}
void set_parent_scope(SymbolTable_ptr parent) {
parent_scope = parent;
if (parent) {
depth = parent->depth + 1;
} else {
depth = 1;
}
}
int get_depth() const {
return depth;
}
};
제어 흐름 및 스코프 관리
컴파일러에서 블록 스코프(block scope)를 처리하는 것은 스택처럼 동작하는 심볼 테이블 관리와 밀접하게 관련됩니다. 새로운 블록에 진입할 때마다 새로운 심볼 테이블을 생성하고 현재 스코프에 연결하며, 블록을 벗어날 때 이를 해제하는 과정이 필요합니다. 이러한 스코프 스택 관리는 std::unique_ptr나 std::shared_ptr 같은 스마트 포인터의 복잡한 소유권 규칙보다는 원시 포인터와 명시적인 new/delete를 사용하는 것이 더 직관적일 수 있습니다. 특히 순환 참조나 특정 생명주기 관리 요구사항 때문에 스마트 포인터가 부적절한 경우가 있을 수 있습니다.
// 가상의 SymbolTable 및 StatementBlockNode 정의
class StatementBlockNode : public BaseAST {
public:
// 이 블록에 포함된 StatementNode 리스트
std::vector<std::unique_ptr<BaseAST>> statements;
void GenerateIR(std::ostringstream &ir_stream, IRGenerationContext& ir_context, SymbolTable_ptr& current_symbol_table) const override {
// 현재 스코프를 저장
SymbolTable_ptr outer_scope = current_symbol_table;
// 새로운 스코프 생성 및 연결
current_symbol_table = new SymbolTable();
current_symbol_table->set_parent_scope(outer_scope);
// 블록 내의 모든 문장 IR 생성
for (const auto& stmt_node : statements) {
stmt_node->GenerateIR(ir_stream, ir_context, current_symbol_table);
}
// 블록 종료: 현재 스코프 해제 및 이전 스코프로 복원
delete current_symbol_table;
current_symbol_table = outer_scope;
}
};
Dangling Else 문제 해결
프로그래밍 언어의 if-else 문법에서 흔히 발생하는 "Dangling Else" 문제는 else가 어떤 if에 속하는지 모호할 때 발생합니다. 이를 해결하기 위해 Bison 문법에서는 문장(Statement)을 '완전한(Matched)' 문장과 '미완성(Unmatched)' 문장으로 구분합니다. '완전한' 문장은 항상 if와 else 쌍을 가지거나, else가 필요 없는 단순 문장입니다. '미완성' 문장은 else를 가질 수 있는 if 문이지만, 아직 else가 붙지 않은 형태입니다.
Statement
: MatchedStatement
| UnmatchedStatement
;
MatchedStatement
: AssignmentStatement ';'
| ExpressionStatement ';'
| BlockStatement
| IF_TOKEN LPAREN Expression RPAREN MatchedStatement ELSE_TOKEN MatchedStatement
| RETURN_TOKEN Expression_opt ';'
;
UnmatchedStatement
: IF_TOKEN LPAREN Expression RPAREN Statement // 'if' 다음에 어떤 문장이 와도 가능 (else 없는 경우)
| IF_TOKEN LPAREN Expression RPAREN MatchedStatement ELSE_TOKEN UnmatchedStatement // 'if-else'에서 'else'가 다시 UnmatchedStatement를 가질 수 있도록 허용
;
이 문법은 파서가 항상 가장 가까운 if에 else를 연결하도록 강제함으로써 모호성을 제거합니다.