[LLVM tutorial] 01 ~ 02

LLVM tutorial

이 글은 LLVM tutorial의 아래 두 챕터를 바탕으로 정리한 글이다.

 

https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl01.html

1. Kaleidoscope: Kaleidoscope Introduction and the Lexer — LLVM 21.0.0git documentation

 

https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl02.html

2. Kaleidoscope: Implementing a Parser and AST — LLVM 21.0.0git documentation

 

1.1. The Kaleidoscope Language

Kaleidoscope 언어는 LLVM tutorial을 설명하기 위한 toy language로, 조건문, 반복문, 사용자 정의 연산자 및 간단한 명령줄 인터페이스를 통한 JIT 컴파일, 디버그 정보 등까지 확장한다.

 

Kaleidoscope는 매우 단순한 체계의 언어이다.

 

- 64bit 부동 소수점(double)의 유일한 data type을 사용하며, 단일 타입을 가지는만큼 타입 선언도 없다.

# Compute the x'th fibonacci number.
def fib(x)
  if x < 3 then
    1
  else
    fib(x-1)+fib(x-2)

# This expression will compute the 40th number.
fib(40)

 

 

- 표준 라이브러리 함수를 호출할 수 있으며, 'extern' 키워드를 사용하여 함수를 사용하기 전에 정의할 수 있다.

- LLVM JIT이 외부 함수들을 연결, 호출하는 작업을 쉽게해주어 외부 표준 라이브러리 함수들을 불러오는게 간편해졌다.

extern sin(arg);
extern cos(arg);
extern atan2(arg1 arg2);

atan2(sin(.4), cos(42))

 

 

1.2. Lexer

Lexer는 텍스트 파일의 입력을 받아서, 그것을 해석할 수 있도록 토큰 단위로 잘라주는 역할을 한다.

구현은 C 언어를 기반으로 한다.

 

- input : text file

- output : tokens (Token enum values OR unknown character)

- token : token code + metadata

- token code : token의 종류 (ex) tok_number)

- metadata : token의 실제 값 (ex) 42.0)

 

// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
// of these for known things.
enum Token {
  tok_eof = -1,

  // commands
  tok_def = -2,
  tok_extern = -3,

  // primary
  tok_identifier = -4,
  tok_number = -5,
};

static std::string IdentifierStr; // Filled in if tok_identifier
static double NumVal;             // Filled in if tok_number

 

Lexer로부터 반환되는 Token enum 값들에 포함되지 않은 unknown character들은 (ex) '+') ASCII value로 반환된다.

 

 

Lexer의 실제구현은 다음 gettok() 한 개의 함수에 구현되어 있다.

- gettok() 함수는 입력을 읽고 다음 토큰을 만들어서 반환하는 역할을 하며, static 변수로 선언되는 LastChar 변수는 문자 및 EOF 값을 저장하며, 읽고 처리하지 않은 문자가 저장되어 있다.

 

gettok()의 절차

1. token 사이의 whitespace는 무시 

/// gettok - Return the next token from standard input.
static int gettok() {
  static int LastChar = ' ';

  // Skip any whitespace.
  while (isspace(LastChar))
    LastChar = getchar();

 

2. identifier의 처리 : 문자로 시작하는 모든 token이 여기에 해당하며, def와 extern의 키워드들을 개별적인 토큰으로 반환

if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
  IdentifierStr = LastChar;
  while (isalnum((LastChar = getchar())))
    IdentifierStr += LastChar;

  if (IdentifierStr == "def")
    return tok_def;
  if (IdentifierStr == "extern")
    return tok_extern;
  return tok_identifier;
}

 

3. numeric value의 처리 : 숫자로 시작하는 double 값을 저장한 뒤 tok_number 반환

    (strtod에 의해 유효하지 않은 값을 제거됨, 1.23.45.67 -> 1.23)

if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
  std::string NumStr;
  do {
    NumStr += LastChar;
    LastChar = getchar();
  } while (isdigit(LastChar) || LastChar == '.');

  NumVal = strtod(NumStr.c_str(), 0);
  return tok_number;
}

 

4. comment는 문장의 끝을 찾아 EOF 토큰 혹은 다음 문장의 첫 토큰을 반환

if (LastChar == '#') {
  // Comment until end of line.
  do
    LastChar = getchar();
  while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');

  if (LastChar != EOF)
    return gettok();
}

 

5. EOF이면 tok_eof를 반환하고 어디에도 해당되지 않은 문자열은 ASCII 값 그대로 반환

  // Check for end of file.  Don't eat the EOF.
  if (LastChar == EOF)
    return tok_eof;

  // Otherwise, just return the character as its ascii value.
  int ThisChar = LastChar;
  LastChar = getchar();
  return ThisChar;
}

 

 

---

2.1. Chapter 2 Introduction

Chapter 2 에서 다루는 것 : AST의 정의, Kaleidoscope language의 paser의 build

여기에서의 parser는 Recursive Descent Parsing(이항 표현식 외 전체 구현)과 Operater-Precedence Parsing(이 표현식을 구현)으로 구현된다.

 

 

2.2. The Abstract Syntax Tree (AST)

Kaleidoscope의 문법은 표현식(expression), 프로토타입(prototype), 함수 정의(function)로 크게 세 가지로 나뉘며, 이에 대응하는 AST 노드를 각각 구현한다.

 

Expression

- ExprAST : 모든 expression node 들에 대한 기본이 되는 interface 역할을 하는 class

- NumberExprAST : 숫자 리터럴을 표현하기 위한 class, 해당 리터럴의 실제 값을 저장

- VariableExprAST : 변수 참조를 표현하는 class, 변수의 이름을 저장하여 참조할 수 있게 함
- BinaryExprAST : binary operator을 표현하는 class, 연산자와 좌우 피연산자의 expression을 저장

- CallExprAST : function call을 표현하는 class, 호출할 함수의 이름과 전달할 인자 목록을 저장

 

/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
  virtual ~ExprAST() = default;
};

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

public:
  NumberExprAST(double Val) : Val(Val) {}
};
/// VariableExprAST - Expression class for referencing a variable, like "a".
class VariableExprAST : public ExprAST {
  std::string Name;

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

/// 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)) {}
};

/// 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)) {}
};

 

 

Conditional control flow 구현되지 않음

 

 

Prototype & Function

- PrototypeAST : 함수의 시그니처 부분 (ex) def func1 (arg1, arg2))
- FunctionAST : 함수의 시그니처 + body

 

Kaleidoscope에서는 데이터 타입이 한 개 이므로 함수의 타입은 파라미터 개수만으로 결정된다. 

/// 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)) {}
};

 

 

2.3. Parser Basics

Parser 파트에서는 lexer 파트에서 구현한 gettok()을 사용하여 토큰을 바탕으로 AST를 생성하는 코드를 설명한다.

 

Parser 구현을 위한 basic helper routines

- CurTok : 현재 파싱해야하는 토큰

- getNextToken() : gettok() 함수를 호출하여 CurTok에 다음으로 파싱할 토큰을 저장

- LogError() : 파싱 과정 중 오류 발생 시에 호출되는 에러 처리 함수. 다양한 반환 타입을 갖는 파싱 함수 내에서 일관된 방식으로 오류를 처리할 수 있도록 도와줌

 

/// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
/// token the parser is looking at.  getNextToken reads another token from the
/// lexer and updates CurTok with its results.
static int CurTok;
static int getNextToken() {
  return CurTok = gettok();
}

/// LogError* - These are little helper functions for error handling.
std::unique_ptr<ExprAST> LogError(const char *Str) {
  fprintf(stderr, "Error: %s\n", Str);
  return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
  LogError(Str);
  return nullptr;
}

 

 

2.4. Basic Expression Parsing

이 파트에서는 가장 간단하게 구현되는 리터럴 수를 파싱하는 것을 구현하는 것부터 파싱 과정에서 사용되는 방법들을 소개한다.

 

아래 ParseNumberExpr에서는 tok_number 토큰에서 NumVal 값을 가져와 NumberExprAST 노드를 생성하고 현 토큰은 소비한 후 노드를 반환한다.

여기서 parser는 node 생성에 필요한 모든 토큰을 처리한 후 다음 토큰을 lexer buffer에 반환(getNextToken())하고 있으며, 이는 Recursive Descent Parser의 표준 방식이다.

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

 

 

ParseParenExpr은 '(' expression ')' 의 괄호를 처리하는 함수로, expression과 ')'이 오류가 났을 시 각각에 대한 대응을 nullptr 반환과 LogError를 반환하는 것으로 보여주고 있다.

모든 토큰이 오류 없이 parsing되면 각 토큰을 소모하고 노드를 반환한다. 이 때 AST에서는 괄호를 제거하고 expression만 노드에 저장하게 되는데 이는 괄호가 표현식의 우선순위와 그룹핑을 위한 도구로만 사용될 뿐 어떠한 의미를 담고 있지 않기 때문에 제거되어도 영향을 끼치지 않기 때문이다.

/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
  getNextToken(); // eat (.
  auto V = ParseExpression();
  if (!V)
    return nullptr;

  if (CurTok != ')')
    return LogError("expected ')'");
  getNextToken(); // eat ).
  return V;
}

 

또한 위의 코드에서 ParseExpression을 호출하여 expression에 대한 처리를 다른 함수에 맡기는 것을 볼 수 있다. 이는 호출을 통해 재귀를 사용하는 Recursive Decent Parser의 특징을 보여주며, 이러한 특징을 바탕으로 괄호가 중첩되는 구조도 쉽게 처리할 수 있다.

 

 

다음은 Identifier에 대한 처리를 담당하는 함수이다. identifier에는 변수 참조와 함수 호출의 두가지 패턴이 있으며 이를 한 함수에서 조건문 분기를 통해 각각 적절한 노드를 반환하는 것을 확인할 수 있다.

조건문 분기 과정에서 look-ahead를 사용하며 다음 토큰을 미리 보고 '('와의 일치 여부에 따라 생성되는 노드가 갈린다.

/// 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 (true) {
      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));
}

 

 

ParsePrimary는 expression-parsing에서 가장 상위의 primary를 파싱하는 함수이다.

현재 토큰을 확인하여 token 종류에 따라 함수를 호출한다. 여기서 CurTok은 처리되지 않은 토큰을 가리키고 있기 때문에 다음 토큰을 가져올 필요 없이 바로 확인 후 분기할 수 있다.

/// 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 (true) {
      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));
}

 

 

2.5. Binary Expression Parsing

이 파트에서는 이항 연산자가 포함된 표현식에 대해 parsing하는 과정을 다루며 Operator-Precedence Parsing 방법을 사용한다.

Kaleidoscope language의 기본 형태에서는 4개의 이 연산자 (<, +, -, *)만을 지원하며, 각 연산자에 맞는 우선순위를 반환하는 함수인 GetTokPrecedence를 사용할 수 있다. 4개의 연산자 외에는 -1이 반환되도록 설계되어있다.

/// 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;
}

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

 

 

이항 연산자가 포함된 표현식에 대한 처리는 그 표현식을 [binop, primaryexpr] 쌍의 여러 조각으로 나눠 시퀀스를 만들어 낸다.

 

예시 : “a+b+(c+d)*e*f+g”

[binop, primaryexpr] sequence :  [+, b] [+, (c+d)] [*, e] [*, f], [+, g]

 

위의 예에서 'a'는 먼저 구문 분석된 상태이며, 시퀀스에서 각 연산자의 우선순위를 비교하며 primaryexpr 간의 node를 구성하고 연결한다.

'(c+d)'의 경우 expression으로서 내부적으로 처리되기 때문에 해당 단계에서 고려할 필요가 없다.

 

아래 코드는 a + b ... 에서 a의 구문 분석을 마친 후 우선순위 0을 준 뒤 오른쪽에 따라오는 연산들을 처리한다.

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

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

 

나머지 '+b+(c+d)*e*f+g'를 [0, a] 인자를 갖고 처리하는 과정이다.

/// binoprhs
///   ::= ('+' primary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                              std::unique_ptr<ExprAST> LHS) {
  // If this is a binop, find its precedence.
  while (true) {
    int TokPrec = GetTokPrecedence(); // 현재 토큰이 연산자일 시 우선순위를 가져옴

    // If this is a binop that binds at least as tightly as the current binop,
    // consume it, otherwise we are done.
    // 현재 연산자가 ExprPrec보다 낮으면 반환
    // ex) a * b + c
    // * 보다 +의 우선 순위가 낮음 > * 까지만 계산하고 반환 
    if (TokPrec < ExprPrec) 
      return LHS;

    // Okay, we know this is a binop.
    int BinOp = CurTok; // 현재 이항 연산자 저장
    getNextToken(); // eat binop

    // Parse the primary expression after the binary operator.
    auto RHS = ParsePrimary(); // 피연산자 파싱
    if (!RHS)
      return nullptr;

    // If BinOp binds less tightly with RHS than the operator after RHS, let
    // the pending operator take RHS as its LHS.
    // a + b * c
    int NextPrec = GetTokPrecedence(); 
    if (TokPrec < NextPrec) {	
      // 다음 연산자의 우선순위가 더 높으면 b * c 를 먼저 완성 해야하므로 함수 호출
      // 피연산자에 있는 연산자의 우선순위가 더 높은 상태 a + b * c * d
      // (TokPrec + 1, => 함수를 재귀적으로 호출하여 우선순위를 높임으로써 
      // b * c * d 가 한 묶음으로 묶이도록 함
      RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
      if (!RHS)
        return nullptr;
    }

    // Merge LHS/RHS.
    LHS =
        std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
  }
}

 

 

2.6. Parsing the Rest

마지막으로 함수 prototype 처리 부분으로 이는 함수의 시그니처를 표현하는 부분이다. 

prototype은 함수 본문 정의에도 사용되지만 'extern'을 사용한 함수 선언에도 사용된다.

 

prototype의 정의는 다음과 같다.

/// prototype
///   ::= id '(' id* ')'
static std::unique_ptr<PrototypeAST> ParsePrototype() {
  if (CurTok != tok_identifier)
    return LogErrorP("Expected function name in prototype");

  std::string FnName = IdentifierStr;
  getNextToken();

  if (CurTok != '(')
    return LogErrorP("Expected '(' in prototype");

  // Read the list of argument names.
  std::vector<std::string> ArgNames;
  while (getNextToken() == tok_identifier)
    ArgNames.push_back(IdentifierStr);
  if (CurTok != ')')
    return LogErrorP("Expected ')' in prototype");

  // success.
  getNextToken();  // eat ')'.

  return std::make_unique<PrototypeAST>(FnName, std::move(ArgNames));
}

 

위에 구현한 prototype에 더불어 함수의 본문을 정의하는 경우를 대비해 함수 본문을 구현하는 것을 덧붙이는 것으로 완성한다.

각 'def'와 'extern' 키워드에 대한 처리이다.

/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDefinition() {
  getNextToken();  // eat def.
  auto Proto = ParsePrototype();
  if (!Proto) return nullptr;

  if (auto E = ParseExpression())
    return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
  return nullptr;
}
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
  getNextToken();  // eat extern.
  return ParsePrototype();
}

 

마지막으로 익명 함수 트릭을 써서 호출 없이 결과를 내도록 하는 방법을 사용한 parsing 이다.

사용자가 1 + 2  * 3 을 입력했을 때 함수 호출 없이 바로 실행하여 출력하게 하고자 할 때 사용할 수 있다.

static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
  if (auto E = ParseExpression()) {
    // Make an anonymous proto.
    auto Proto = std::make_unique<PrototypeAST>("", std::vector<std::string>());
    return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
  }
  return nullptr;
}

 

 

2.7. The Driver

아래는 모든 파싱을 호출할 수 있는 최상위 루프 함수이다.

주목할만한 점은 최상위 세미콜론을 무시하는것으로, 이는 파서에게 입력이 끝났음을 알려주는 역할을 한다. 

/// top ::= definition | external | expression | ';'
static void MainLoop() {
  while (true) {
    fprintf(stderr, "ready> ");
    switch (CurTok) {
    case tok_eof:
      return;
    case ';': // ignore top-level semicolons.
      getNextToken();
      break;
    case tok_def:
      HandleDefinition();
      break;
    case tok_extern:
      HandleExtern();
      break;
    default:
      HandleTopLevelExpression();
      break;
    }
  }
}

 

전체 코드 

LLVM tutorial 2.9. 참고