NPU Compiler developer를 위한 Compiler 개발 5일차, 진도가 안나가네, 땅끝마을이라 그런가

이젠 실제 컴파일러에서 파싱하는결과를 조금 봐보자

// 입력
x = 1+2;
y = x*3;
y;

// 출력
== PROGRAM ==
  Assign 'x'
    Binary(+)
      Number(1)
      Number(2)
  Assign 'y'
    Binary(*)
      Variable(x)
      Number(3)
  ExprStmt
    Variable(y)

그냥 숫자, 연산자만 있는게 아니라 추가로 많은것들이 존재한다.

Indet, Assign, Semi등이 있다.

그러니, 이걸 토큰화 스키기 위해 새로운 토큰의 타입들을 만들어줘야 한다.

실제 문장을 보면, x = 1+2; 를 기준으로, x라는 변수, =라는 할당문, 1+2라는 표현식 ;라는 문장의 끝맺음으로 구성되어져 있으니, 우리는 아직 추가하지 않은 변수, 할당문, 끝맺음을 추가하자.

위 세게는 IDENT, ASSIGN, SEMI라는 TokenType으로 추가하자.

enum class TokenType { NUMBER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, 
  IDENT, ASSIGN, SEMI, // 변수, 할당(=), ;
  END };

이제, 토큰으로 여러 예약어에 맞춰서 데이터를 저장할 것인데, 토큰 타입으로 추가해준다.

// 문자 처리 헬퍼 함수
static bool is_alpha(char c){
  return ('A' <= c && 'Z' <= c) || ('a' <= c && 'z' <= c) || c == '_';
}

// 숫자 + 문자 처리 헬퍼 함수
Static bool is_alnum(char c) {
  return is_digit(c) || is_alpha(c);
}

추가로, 알파벳과 문자열을 처리해줘야 하기 떄문에, 두 경우를 케이스로 나눠서 처리해준다.

 if(c == '='){
   pos++;
   return {TokenType::ASSIGN, "=", startLine, startCol};
 }
 if(c == ';'){
   pos++;
   return {TokenType::SEMI, ";", startLine, startCol};
 }
 if(is_alpha(c)) {
   std::string id;
   while(pos < text.size() && (is_alnum(text.at(pos)))) {
     id.push_back(advance());
   }
   return {TokenType::IDENT, id, L, C};
 }

할당문과 문장의 끝맺음인 콜론 값을 넣고, 추가로 alpha 처리를 하는데, 예약어는 문자열이기 때문에, 한단어로 처리하지 않고 ,계속 처리해준다.

이제 이 단계까지만 하면, 렉서에 하나의 문장을 처리할 수 있는 단계에 도달했다. 이제 이 값들을 파싱해주는 단계가 필요한데, 그 파싱은 AST로 계속 구현해나가자.

struct VariableAst : Ast {
  std::string name;
  VariableAst(std::string n, int L, int C){
    name = std::move(n);
    kind = AstKind::Variable;
    line = L;
    col = C;
  }
};

할당문의 구성을 추가했다. 이제, 변수 = 할당문 의 구조를 만들기 위해선, 할당문 또한 정의를 해줘야 하는데, 추가로 구조체를 하나 더 만들자.

우리가 지금까지 한것은 표현식 이전의 것들을 Ast로 만들어낸 것 뿐이다. 위의 구조처럼 Assign을 하기 위해선 변수와 표현식을 구분해야 하고, 이 할당문과 변수를 전부다 쓰게 된다면, Statement가 된다. 우리는 사실 Statement를 만드는 작업을 하는 것이다.

다시 말해, 우리는 명령만 내리고, 주체는 따로 정하지 않았다. 그냥 단순히 친구에게 말하는데, 혼자 허공에 대고 얘기하는 상황이었던 것이다. 이게 Expression이다. Expression 은, 컴퓨터 공학적으로 다시 얘기하자면 할 일이라고 생각하면 된다. 하지만 Statement는 실제 의미는 문장이다. 그러면, 문장이라면 누군가와 대화할때 주체가 꼭 필요하게 된다. 그 주체를 포함한 표현식이 바로 Statement 가 되는것이다.
나는 왜 이걸 nhn과정에서 약 2주동안 이해하는데 힘을 들였을까, 결국 직접 구현해보면서 어떤게 무엇인지 바로 알 수 있었을텐데 말이다.

계속해 나가보자.

이제 Statement 의 구성은 Variable = Expression이 된다. 그러면, 또 이것들을 이용해 트리로 만들어야 하는데, 이미 우리는 Expression할당문을 생성해낼 줄 안다. 그러면 이제 남은 과제는? 다음과 같다.

1. variable을 assign의 left node로 놓기
2. assign(=)을 parent node로 놓기
3. expression을 right node로 놓기

아니면, 이렇게 놔도 된다.

1. variable을 그냥 assign으로 구분시키기
2. 단항연산처럼 하나의 자식노드만 가지기

구현해나가보자.

struct Stmt {
  StmtKind kind;
  int line = 0;
  int col = 0;
  virtual ~Stmt() noexcept = default;
};

struct ExprStmt : Stmt {
  std::unique_ptr<Ast> expr;
  ExprStmt(std::unique_ptr<Ast> e, int L, int C){
    expr = std::move(e);
    kind = StmtKind::ExprStmt;
    line = L;
    col = C;
  }
};

struct AssignStmt : Stmt {
  std::string name;
  std::unique_ptr<Ast> expr;
  AssignStmt(std::string n, std::unique_ptr<Ast> e, int L, int C) {
    name = std::move(n);
    expr = std::move(e);
    kind = StmtKind::AssignStmt;
    line = L;
    col = C;
  }
};

stmt는 Assignment인지, 아니면 일반 Expr인지만 구분해주면 된다. 다시 보자

assign = expr 이 구조만 떠올리면 별로 어렵지 않다.

Expr의 경우에는 자식이 필요가 없다. 결국은 =라는 연산에 의해 결정되는 것이다. 그러기에, 따로 자식노드를 만들 필드를 생성하지 않아도 되고, assign의 경우에는 expression이 없으면, 단지 declare에 지나지 않는다. 그렇기 때문에, assign을 하기 위해선 Expression이 필요하기 때문에 자식노드로 가지는 방식으로 구조체를 작성해주면 된다.

이제, 많은 문장들을 배열로 관리해주면 된다.

struct Program {
  std::vector<std::unique_ptr<Stmt>> stmts;
}

이제 기본적인 틀은 전부 다 작성했다. 로직을 추가해보자. 이젠 어떤것을 어떻게 추가해줘야 할까?

첫번째 작업은, 기존작업을 건드리지 않고, 하나의 코드를 하나의 프로그램이라 생각하고, 프로그램을 실행시킬 코드를 추가하자.

if (cur.type == TokenType::IDENT) {
    auto n = std::make_unique<VariableAst>(cur.value, cur.line, cur.col);
    advance();
    return n;
  }

일단 첫번째로, parseFactor안에 코드를 추가한다. 만약, 우리가 지금 보려고하는 cur값이 Ident인지 확인하는데, 만약 Ident인 경우라면 다음 노드에 대해서 처리만 해주면 된다. 그리고, 가장 최초의 우선순위가 높은 것이기 때문에, 할당문을 기준으로 나누면 된다. 이제 파서 로직에 한에서는 variable은 나눠졌다. 그러면, 다음으로 할 일은 전체를 불러와서 stmts라는 필드 안에 값을 statement단위로 넣어주면 된다. stmt 단위는 나누는 기준이 위에서 얘기한것처럼 SEMI (;)를 기준으로 하니까 이부분을 코드로 작성해보자.

Program Parser::parseProgram() {
  Program p;
  while(cur.type != TokenType::END){
    cout << "cur value = " << cur.value << "\n";
    p.stmts.push_back(parseStmt());
  }
  return p;
}

파일 전체를 호출내해는 코드이다.

std::unique_ptr<Stmt> Parser::parseStmt(){
  // 현재 토큰이 변수라면
  if(cur.type == TokenType::IDENT) {
    // 루트 토큰을 생성하고
    Token identTok = cur;
    // 다음으로 넘어가서, factor요소를 완성시키는데, 그전에 assign(=) 인지확인함
    advance();
    if(cur.type == TokenType::ASSIGN){
      advance();
      auto rhs = parseExpr();
      cout << "last is" << cur.value;
      expect(TokenType::SEMI, "expected ';' after assignment");
      return std::make_unique<AssignStmt>(identTok.value, std::move(rhs), identTok.line, identTok.col);
    } else {
      // 변수를 선언만 했을 경우, 그냥 넘어감
      // cur = identTok;
      auto var = std::make_unique<VariableAst>(identTok.value, identTok.line, identTok.col);
      expect(TokenType::SEMI, "expected ';' after variable statement");
      return std::make_unique<ExprStmt>(std::move(var), identTok.line, identTok.col);
    }
  }

  int L = cur.line;
  int C = cur.col;
  auto e = parseExpr();
  expect(TokenType::SEMI, "expected ';' after expression");
  return std::make_unique<ExprStmt>(std::move(e), L, C);
}

호출을 하고 나서부턴 이제 또 프로그램 단위로 파싱을 해줘야 한다.

statement의 맨 첫번째 토큰이 IDENT 인 경우, AssignStmt 로 추가해주고, 그게 아닐경우 ExpressionStmt 로 파싱하여 결과를 stmts안에 넣어주면 된다.