NPU Compiler developer를 위한 Compiler 개발 6~7일차, 허허 참 힘드네요

의미 분석은 언어 규칙에 맞게 의미적으로 타당한지 확인하는 과정이다.

우리는 렉서, 파서 그다음에 의미분석으로 들어왔다.

렉서단계는 토큰을 만드는 작업이고, 파서는 Ast로 만들기 위한 과정이고, 마지막으로 의미 분석은 이 과정이 올바른지 검사하는 것이다. 이런 규칙들을 예로 들어보자.

1. 선언 / 사용 규칙

x = 20;
int x;

분명한 오류이다. 왜냐하면, x는 선언이 되어있지도 않은데, 사용하는 x = 20에서 오류가 발생한다.

2. 타입 검사

int x;
x = "hello"

이것 또한 문제다. hello는 문자열 타입이지만, x안에 들어갈 수 있는 것은 int형의 정수의 특정 범위이다.

3. 스코프 검사

int x = 3;
{
	int x = 5;
}

이번에는, 변수 x의 범위에 대한 문제이다. 지역 변수로 쓰이는 x와, (의미상) 전역으로 쓰이는 x로, 같은 일므을 가지도록 2번 호출되었기 대문에, 문제가 발생하는 코드이다.

4. 제어문 규칙

break;

이런식으로 나오게 된다면, 당연히 문제가 많다. 왜냐하면, break는 for문을 탈출하기 위한 예약어인데, 그냥 생으로 나왓으면 당연히 문제가 있는 코드이다.

그러면 이런 문제를 발생시키지 않기위해선, 의미 분석단계가 필요한데, 어떻게 구현해야 할까?

일단 여러가지 역할을 먼저 보자.

1. 심볼 관리 (Symbol Table) → 선언 / 사용 규칙을 제한

• 변수/함수 이름과 속성을 저장
• 선언 이전에, 중복체크를 하는지 여부 확인

2. 타입 검사 (Type Checking) → 올바른 변수에 올바른 값이 들어갔는지 확인

• 연산자 / 피연산자 타입 체크
• 함수 인자 타입 체크

3. 스코프 규칙 적용

• 블록 단위 { . . . } 별로 심볼 테이블 갱신

4. 의미적 제약 확인

• return문 검사, break/continue 위치 검사

이제 하나하나 위의 과제들을 해결해나가보자.

기본적으로 SymbolInfo 구조체를 이용해서 관리할 것이다.

struct SymbolInfo {
  std::string stype;
}

type은 int형인지, float인지의 정보를 담아놓을 것이다.

이제 동작들을 보자.

class SymbolTable {
private:
  // 스코프, Vector에 map으로 선언되고, 스택처럼 사용된다.( 프로시져 호출시 생성되는 메모리 구조와 유사 )
  std::vector<std::unordered_map<std::string, SymbolInfo>> scopes;  

public:
  SymbolTable();

  void enterScope(); //진입점, {  <=
  void exitScope();  //탈출    }  <=
  //선언 되어져 있는지
  // bool SymbolTable::isDeclared(const std::string& name, const SymbolInfo& info);
  // 선언
  bool declare(const std::string& name, const SymbolInfo& info);
  // 성공시 true, 중복선언 및 규칙 허용x -> false;

  // 조회 관련
  std::optional<SymbolInfo> lookup(const std::string& name) const;
};

1. scopes를 관리하는데, map으로 관리할 거다. string, 즉 선언된 symbolInfo에 맞는 맵 형태로 저장하는 것이다.
2. 새로운 스코프에 접근하게 되면, vector를 빈 값을 push하여 새로운 map을 선언해준다.
3. 스코프가 닫히게 되면 ,외부에서 더이상 사용하지 않기 때문에, Pop을 통해 map을 갱신시켜준다.
4. 선언이 된다면, 삽입이 가능한지 여부를 확인하고, 가능하다면 성공 여부를 반환해준다.
5. 상위 스코프에서도 확인을 해줘야 하기 때문에 상위 스코프도 봐줘야 한다.

// 새로운 스코프가 생긴다면, {가 생긴다면, push로 엔트리를 새로 생성해준다.
void SymbolTable::enterScope() {
  scopes.push_back({});
}

// 스코프가 닺혀서 더이상 사용하지 않는다면, pop으로 스코프 엔트리를 빼준다.
void SymbolTable::exitScope() {
  if(!scopes.empty()){
    scopes.pop_back();
  }
}

// 새로우 변수가 선언되었다면, 현재 스코프에 있는지 검사하고, 검사할때는 find()를 통해서 하는데, find()는 iterator를 반환하니까, 주소를 기준으로 값을 비교
// curScope.end()는 최종 요소, 즉 마지막 요소의 다음값인 빈 주소를 가리키기에 선언이 find()해서 값이 안나온다면, 그건 end()를 return 하는 것이다.

bool SymbolTable::declare(const std::string& name, const SymbolInfo& info) {
  auto& curScope = scopes.back();
  if (curScope.find(name) != curScope.end()) {
    return false; // 이미 존재
  }
  curScope[name] = info; // 새로운 심볼 등록
  return true;
}

// scopes의 vector안에 push된 최상위 엔트리부터 차례대로 확인하는데, 스코프별 맵을 하나하나씩 확인하는 절차
std::optional<SymbolInfo> SymbolTable::lookup(const std::string& name) const {
  for (auto it = scopes.rbegin(); it != scopes.rend(); ++it) {
    auto found = it->find(name);
    if (found != it->end())
      return found->second;
  }
  return std::nullopt; // 못 찾음  
}

이렇게 한다면, 심볼관리의 기본적인 틀은 완성되었다. 이제 코드에 새로운 기능을 하나하나씩 추가해나가자.

다음으로 할 일은, Visitor 패턴을 조금 익혀볼 필요가 있다.

Visitor패턴은 쓰임새가 다양하다. 위키백과에서의 방문자 패턴의 정의는 다음과 같다.

객체 구조의 요소에 대해 수행되는 연산을 나타냅니다. Visitor를 사용하면 연산 대상 요소의 클래스를 변경하지 않고도 새 연산을 정의할 수 있습니다.

객체지향의 GoF 23가지 패턴중 한가지로 객체와 알고리즘을 분리하는 과정을 적용시킨 방법이다.

객체 구조의 요소에 대해 작업을 구현하는 방문자 객체를 새로 정의하는 방식으로, 우리는 Visitor 객체를 사용할 것이다.

먼저 Visitor패턴학습을 해보자. ( 이해 하고싶으시면 먼저 읽고오세요~)

---

이거 보고오십셔~ visitor 간단하게 구현한겁니다요

---

이제 각 토큰 타입별로 AstNode를 만들어보자.

struct AstNode {
    virtual ~AstNode() = default;
    virtual void accept(class Visitor& v) = 0;
};

AstNode를 통해서 Visitor패턴을 구현할 것이기 때문에, Node를 Element라고 생각하자.

그다음에, 이제 실제 객체들을 전부 받아와야 한다.

우리가 기준으로 나눌 것들은 선언부, 식별자, 할당, EOF만을 기준으로 잡을 것이다.

int x = 10
// VarDecl: ("x", "int")  ->  VarDecl("x", "int")
// Identifier: x  ->  Identifier("x")
// Assign ("x", 10)  ->  Assign("x", Number(10))
// Block  ->  {...}

결과:
Block
	VarDecl(x:int)
	Assign(=)
		Identifier(x), lhs
		Number(10), rhs

그러면, 하나를 기준으로 만들어보자. 위에것을 기준으로 생성해내면 된다.

struct VarDecl : AstNode {
    std::string name, type;
    VarDecl(std::string n, std::string t) {
        name = n;
        type = t;
    }
    void accept(Visitor& v) override; 
};

VarDecl안에 int x 데이터를 집어 넣는다.

두개의 문자열을 받아주는 필드가 필요하다. 이 기준으로 나머지도 작성해나가보자.

struct Identifier : AstNode {
    std::string name;
    VarDecl(std::string n) {
        name = n;
    }
    void accept(Visitor& v) override; 
};
struct Assig : AstNode {
    std::string name;
	  AstNode* expr
    VarDecl(std::string n, AstNode* e) {
        name = n;
        expr = e;
    }
    void accept(Visitor& v) override; 
};
struct Block : AstNode {
    std::Vector<AstNode> stmts;
    VarDecl(std::Vector<AstNode*> s) {
			stmts = s;
    }
    void accept(Visitor& v) override; 
};

이렇게 하면, AstNode를 Element로 하는 Visitor패턴을 적용시키기 위한 기본 틀은 완성했다. 이제 다음으로 넘어가서 알고리즘 부분을 Visitor에 적용시켜보자.

class Visitor {
public:
    virtual void visit(VarDecl& node) = 0;
    virtual void visit(Identifier& node) = 0;
    virtual void visit(Assign& node) = 0;
    virtual void visit(Block& node) = 0;
};

방문자 객체가 방문할때의 처리를 각각 수행할 수 있도록, 인터페이스를 정의해준다. 우리는 Visitor의 구현체에 따라 다르게 처리해주도록 구현해주면 되는것이다.

class SemanticAnalyzer : public Visitor {
    SymbolTable symbols;

public:
    void visit(VarDecl& node) override;      // 선언 → SymbolTable 등록
    void visit(Identifier& node) override;   // 사용 → lookup 검사
    void visit(Assign& node) override;       // 대입 → 좌변 선언 체크, RHS 순회
    void visit(Block& node) override;        // enterScope/exitScope
};

방문자의 클래스를 상속받은SemanticAnalyzer클래스를 사용하는데, Visitor인터페이스에서 정의한 것을 적절히 분리하여 처리하도록 한다. 이제 나머지 구현부로 다시 들어가보자.

void VarDecl::accept(Visitor& v) { 
  v.visit(*this); 
}
void Identifier::accept(Visitor& v) { 
  v.visit(*this); 
}
void Assign::accept(Visitor& v) {
   v.visit(*this); 
}
void Block::accept(Visitor& v) {
  v.visit(*this);
}

각 element들의 처리를 할때, visit에 대한 구현을 오버라이드를 해준다. 단순히 각 accept에 대한 클래스별로 처리할 수 있게 해주는 부분이다. (Visitor패턴에서, 어떤 element이든지, visit을 수행하도록)

void SemanticAnalyzer::visit(VarDecl& node){
  SymbolInfo info{node.type};
  if (!symbols.declare(node.name, info)) {
    std::cerr << "Error: 중복 선언된 변수 '" << node.name << "'\n";
  }
}

void SemanticAnalyzer::visit(Identifier& node) {
  auto result = symbols.lookup(node.name);
  if(!result) {
    std::cerr << "Error: 선언되지 않은 변수 '" << node.name << "' 사용\n";
  }
}

void SemanticAnalyzer::visit(Assign& node) {
  auto lhs = symbols.lookup(node.name);
  if(!lhs) {
    std::cerr << "Error: 선언되지 않은 변수 '" << node.name << "'에 대입\n";
  }
  if(node.expr) {
   node.expr->accept(*this); 
  }
}

void SemanticAnalyzer::visit(Block& node) {
  symbols.enterScope();
  for (auto* stmt : node.stmts) {
    stmt->accept(*this);
  }
  symbols.exitScope();
}

이제 마지막으로, Visitor패턴에서, 함수별 처리하는 로직이다. Visitor를 상속받은 SemanticAnalyer클래스는 Element객체 안에 들어가게 되면,

VarDecl (int x)의 경우, 트리를 생성할때, symbol_table을 생성하는 동작을 한다.

Identifier (x) 의 경우, 상위 스코프에서 선언되어져있는지 확인한다.

Assigna의 경우, 만약, name인 Identifier가 있고, 다른 표현식이 나와서 Node로 새로 생성해야 한다면, 표현식을 expr를 또 AstNode에 맞춰서 실행시켜 준다.

마지막으로 Block의 경우, 의미 분석용으로 만들어놓은 배열, stmts안에 push 후 visitor패턴을 시작하고, pop해줌으로써 마무리한다.

이걸 하면서, 왜 visitor패턴을 쓰는지는 조금 더 알아봐야 할 것 같다. (추후 if문으로 처리하는 것과, visitor패턴으로 하는것의 차이를 느끼려면 코드를 직접 가져오는것까지, 즉 IR까지 구현하고 나서 추가로 진행할것이다.)