Kaleidoscope #1: 언어 소개, 그리고 Lexer

eunjo·2022년 9월 4일

compiler

LLVM-Kaleidoscope 튜토리얼 따라하기

목록 보기

2/3

1.1. The Kaleidoscope Language

LLVM 튜토리얼에서 구현할 Kaleidoscope는 다음과 같은 특징을 지닌 매우 간소한 프로그래밍 언어입니다.

절차지향적 언어
데이터 타입이 단 1개 (8바이트 실수 타입)

Kaleidoscope 소스코드 예시 #1

# 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)

위는 피보나치 수열을 Kaleidoscope로 작성한 예시에요. 소스코드를 통해 추측할 수 있는 언어의 기능은 다음과 같습니다.

# : 주석
def : 사용자 함수 정의
if-then-else : 조건문
줄의 마지막에 세미콜론을 입력하지 않아도 됨
블록 단위를 들여쓰기로 구분함

Kaleidoscope 소스코드 예시 #2

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

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

또한, Kaleidoscope는 표준 라이브러리 함수를 호출할 수 있다고 하네요. extern 키워드를 보니 아마도 LLVM 프레임워크에서 코드를 가져와 정적 링킹을 하는게 아닐까 생각합니다.

1.2. The Lexer

Lexer는 텍스트 파일 형태의 소스코드를 읽어 token stream으로 변환해주는 역할을 수행합니다.

토큰 정의

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

토큰은 각각의 소스코드를 예약어 또는 리터럴 값에 따라 분류한 정보 단위입니다. 토큰의 유형에 따라 추가적인 정보가 필요한 경우도 있는데요. tok_identifier의 경우, 특정 토큰으로 분류되기 전까지의 임시 토큰이므로 IdentifierStr에 읽어들인 식별자가 저장되어 추가 정보로 쓰이고, tok_number의 경우, 숫자값이 NumVal에 저장되어 추가 정보로 쓰입니다.

또한, 토큰 목록에 정의되지 않은 유형들을 분류할 unknown과 같은 토큰도 필요합니다. 예를 들어, +와 같은 문자는 어떤 토큰 유형에도 속하지 못합니다.

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

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

예시에서 Lexer가 소스코드를 읽는 방법은 간단합니다. 공백을 필터링하고, 나머지 문자는 모두 읽어들입니다.

예약어 분류

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

isalpha() : 알파벳 대소문자([a-zA-Z])일 경우에만 non-zero 반환
isalnum() : 알파벳 대소문자 또는 정수([a-zA-Z0-9])일 경우에만 non-zero 반환

식별자는 알파벳 대소문자 및 숫자로 구성되지만, 첫 글자로 숫자는 허용하지 않습니다. 읽어들인 식별자가 예약어와 일치하면 그에 대응되는 토큰으로 분류되지만, 그 이전까지는 임시로 tok_identifier로 분류되고, 식별자는 IdentifierStr에 저장됩니다.

숫자 분류

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

isdigit() : 정수([0-9])일 경우에만 non-zero 반환
strtod() : 문자열을 실수 타입으로 변환

Kaleidoscope는 8바이트 실수 타입이 유일한 데이터 타입입니다. 따라서, 다른 경우의 수를 고려할 필요 없이 소수점을 포함한 숫자를 읽으면 tok_number로 분류합니다.

주석 분류

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

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

주석은 토큰으로 변환하지 않고 버립니다. 주석은 컴파일 단계에서 제거되는 정보임을 알 수 있습니다.

파일의 끝

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