Kaleidoscope #2: AST를 생성하기 위한 Parser 작성

2.1. Chapter 2 소개

지난 챕터에서는 Lexer를 작성했습니다. 그 덕에 텍스트 형태의 Kaleidoscope 소스코드를 파싱하여 사용자 정의 함수, 변수, 외부 함수 등 유형에 따라 분류했습니다. 그 과정에서 소스코드의 빈 칸, 개행 문자, 그리고 주석 등 컴파일에 불필요한 정보들이 제거되면서 데이터의 크기가 감소하였습니다. 이번 챕터에서는 AST(Abstract Syntax Tree)가 무엇인지 알아보고, 또 만드는 방법에 대해 배웁니다.

2.2. The Abstract Syntax Tree (AST)

AST는 뒤의 컴파일 과정에서 코드 생성이 쉽도록 소스코드를 표현하는 트리 형태의 자료 구조입니다. Kaleidoscope에서 AST를 생성하기 위해 필요한 구성 요소들은 어떤 것들이 있는지 살펴보겠습니다.

Number Expression

/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
  double Val;

public:
  NumberExprAST(double Val) : Val(Val) {}
};

Number는 Kaleidoscope의 유일한 자료형입니다. 챕터 1에서 Number에는 8바이트 크기의 실수값을 넣기로 약속했기에 double 형으로 정의합니다.

Variable Expression

/// VariableExprAST - Expression class for referencing a variable, like "a".
class VariableExprAST : public ExprAST {
  std::string Name;

public:
  VariableExprAST(const std::string &Name) : Name(Name) {}
};

변수를 정의합니다. 변수명을 가리키는 Name을 멤버로 가져 서로 다른 변수를 식별합니다.

Binary Expression

/// BinaryExprAST - Expression class for a binary operator.
class BinaryExprAST : public ExprAST {
  char Op;
  std::unique_ptr<ExprAST> LHS, RHS;

public:
  BinaryExprAST(char op, std::unique_ptr<ExprAST> LHS,
                std::unique_ptr<ExprAST> RHS)
    : Op(op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
};

사칙연산을 표현합니다. Op(Operator)에는 +, -, *, /와 같은 1바이트 크기의 연산자가 저장됩니다. 또한, 왼쪽 자식 노드는 좌측 피연산자를 가지고, 오른쪽 자식 노드는 우측 피연산자를 가집니다. 피연산자는 ExprAST 클래스를 상속받은 클래스 타입이라면 무엇이든 위치할 수 있습니다. 즉, 피연산자에는 실수, 변수, 함수의 반환 값이 위치하거나 혹은 또다른 사칙연산이 위치할 수도 있습니다.

Call Expression

/// CallExprAST - Expression class for function calls.
class CallExprAST : public ExprAST {
  std::string Callee;
  std::vector<std::unique_ptr<ExprAST>> Args;

public:
  CallExprAST(const std::string &Callee,
              std::vector<std::unique_ptr<ExprAST>> Args)
    : Callee(Callee), Args(std::move(Args)) {}
};

함수 호출을 표현합니다. Callee에는 호출할 함수의 이름이 저장되고, Args에는 인자값들이 저장됩니다. Args가 std::vector 클래스 타입이므로 Kaleidoscope는 함수 호출 시 인자 개수를 제한 없이 전달 가능한 것으로 보입니다(올바른 호출인지는 이후에 Prototype과 비교할 것으로 예상됩니다). 인자는 ExprAST 클래스를 상속받은 타입이라면 무엇이든 위치할 수 있습니다.

Function

/// PrototypeAST - This class represents the "prototype" for a function,
/// which captures its name, and its argument names (thus implicitly the number
/// of arguments the function takes).
class PrototypeAST {
  std::string Name;
  std::vector<std::string> Args;

public:
  PrototypeAST(const std::string &name, std::vector<std::string> Args)
    : Name(name), Args(std::move(Args)) {}

  const std::string &getName() const { return Name; }
};

/// FunctionAST - This class represents a function definition itself.
class FunctionAST {
  std::unique_ptr<PrototypeAST> Proto;
  std::unique_ptr<ExprAST> Body;

public:
  FunctionAST(std::unique_ptr<PrototypeAST> Proto,
              std::unique_ptr<ExprAST> Body)
    : Proto(std::move(Proto)), Body(std::move(Body)) {}
};

함수 호출 시 인자는 Prototype에 정의된 인자의 타입과 개수를 따라야 합니다. 그러나 Kaleidoscope가 지원하는 자료형은 Number가 유일하므로 인자의 타입이 일치하는지 검사할 필요가 없습니다. 오직 인자의 개수가 일치하는지만 검사하면 됩니다. 여기서 Name은 CallExprAST::Callee와 연결되겠죠. Callee와 일치하는 Name이 없다면 정의되지 않은 함수를 호출한 것일테고, 일치하는 Name이 있다면 올바른 함수 호출인지 검사할 것입니다(PrototypeAST::Args와 CallExprAST::Args의 개수 비교).

자료형을 여러 개 지원하는 프로그래밍 언어의 경우, Prototype에 인자의 자료형을 저장하는 필드가 추가될 수도 있다고 합니다.

FunctionAST는 함수의 Prototype(Proto)과 구현체(Body)를 멤버로 가지는 클래스입니다. Kaleidoscope에서 함수는 def 키워드를 사용해서 사용자가 직접 정의한 함수와 extern 키워드를 사용하는 외부 함수(다른 오브젝트 파일에 정의된 함수) 두 가지로 구분되는데요. FunctionAST는 사용자가 직접 정의한 함수만이 가지는 클래스 타입입니다. 외부 함수는 이미 컴파일을 마친 다른 오브젝트 파일에 정의되어 있으며 링킹 시 사용되므로 외부 함수의 구현체를 이루는 소스코드는 컴파일러가 알 수 없습니다. 하지만 외부 함수의 Prototype은 헤더 파일에 정의되어 있어요. 따라서 외부 함수는 PrototypeAST만을 사용합니다.

2.3. Parser

AST를 구성하는 노드의 정의가 끝났으므로 이제 AST를 생성하기 위해 Parser를 작성해야 합니다. 챕터 1에서 작성했던 Lexer가 반환해주는 토큰 유형에 따라 어떤 AST 노드를 생성할지 분기합니다. 각 표현식에 따른 파싱 방식은 다음과 같습니다.

Number Expression

/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
  auto Result = std::make_unique<NumberExprAST>(NumVal);
  getNextToken(); // consume the number
  return std::move(Result);
}

ParseNumberExpr 함수는 tok_number 유형의 토큰을 파싱합니다.

Variable & Call Expression

/// identifierexpr
///   ::= identifier
///   ::= identifier '(' expression* ')'
static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
  std::string IdName = IdentifierStr;

  getNextToken();  // eat identifier.

  if (CurTok != '(') // Simple variable ref.
    return std::make_unique<VariableExprAST>(IdName);

  // Call.
  getNextToken();  // eat (
  std::vector<std::unique_ptr<ExprAST>> Args;
  if (CurTok != ')') {
    while (1) {
      if (auto Arg = ParseExpression())
        Args.push_back(std::move(Arg));
      else
        return nullptr;

      if (CurTok == ')')
        break;

      if (CurTok != ',')
        return LogError("Expected ')' or ',' in argument list");
      getNextToken();
    }
  }

  // Eat the ')'.
  getNextToken();

  return std::make_unique<CallExprAST>(IdName, std::move(Args));
}

ParseIdentifierExpr 함수는 tok_identifier 유형의 토큰을 파싱합니다. 이 토큰의 쓰임새는 함수 호출과 변수 참조 두 가지로 구분되는데요. 식별자 다음에 소괄호가 이어서 따라온다면 함수 호출 표현식으로 간주하고, 소괄호가 없다면 변수 참조 표현식으로 간주합니다. 함수 호출 시 인자를 여러 개 전달할 경우, 쉼표로 구분합니다.

Binary Expression

/// BinopPrecedence - This holds the precedence for each binary operator that is
/// defined.
static std::map<char, int> BinopPrecedence;

/// GetTokPrecedence - Get the precedence of the pending binary operator token.
static int GetTokPrecedence() {
  if (!isascii(CurTok))
    return -1;

  // Make sure it's a declared binop.
  int TokPrec = BinopPrecedence[CurTok];
  if (TokPrec <= 0) return -1;
  return TokPrec;
}

// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['<'] = 10;
BinopPrecedence['+'] = 20;
BinopPrecedence['-'] = 20;
BinopPrecedence['*'] = 40;  // highest.

사칙연산 표현식은 어떤 연산자를 우선적으로 처리할지 결정해야 합니다. Kaleidoscope에서는 Operator-Precedence Parsing 방식을 사용합니다. 이 방식은 각각의 연산자에 대해 우선순위를 결정하는 값을 매기고 그에 따라 처리하는 방식입니다. 연산자 우선순위는 컴파일러 개발자가 정의하기 나름이지만, 일반적으로 수학에서 통용되는 우선순위를 따릅니다. 예제 코드에서는 <, +, -, * 총 네 가지 연산자에 대해서만 정의되어 있지만, 임의로 추가할 수 있습니다. 값이 높을수록 더 높은 우선순위를 가집니다.

/// expression
///   ::= primary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
  auto LHS = ParsePrimary();
  if (!LHS)
    return nullptr;

  return ParseBinOpRHS(0, std::move(LHS));
}

/// primary
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
  switch (CurTok) {
  default:
    return LogError("unknown token when expecting an expression");
  case tok_identifier:
    return ParseIdentifierExpr();
  case tok_number:
    return ParseNumberExpr();
  case '(':
    return ParseParenExpr();
  }
}

ParseExpression 함수는 tok_identifier, tok_number 유형의 토큰을 파싱합니다. 사칙연산 표현식에는 변수, 함수 호출 반환값, 숫자 리터럴 모두 사용될 수 있으므로 파싱하는 토큰 유형이 다른 파싱 함수보다 상대적으로 많습니다. AST에서 사칙연산 표현식은 연산자를 기준으로 왼쪽 자식 노드(LHS)와 오른쪽 자식 노드(RHS)로 나뉩니다.