3. Kaleidoscope: Code generation to LLVM IR 한글 번역

분류없음 2017.07.24 16:47
크리에이티브 커먼즈 라이선스
Creative Commons License

3.1. Chapter 3 Introduction

3장에서는 2장에서 만든 AST를 LLVM IR로 변환하는 법과, LLVM 프레임워크가 얼마나 사용하기 편한지 설명합니다. 이번장에서 하는게 Lexer나 Parser를 구현하는 것보다 할게 많이 없습니다


주의: 이번장부터는 LLVM API를 사용합니다. 반드시 튜토리얼과 같은 LLVM버젼을 사용해주세요. 저는 LLVM 4.0.0버젼을 사용하고 있습니다



3.2. Code Generation Setup

먼저 Parser.h를 열어 모든 AST클래스에 codegen() 메소드를 추가해줍니다


#ifndef __PARSER_H__
#define __PARSER_H__
#include <memory>
#include <string>
#include <vector>

class ExprAST {
public:
    virtual ~ExprAST() {}
    virtual Value *codegen() = 0;
};

class NumberExprAST : public ExprAST {
    double Val;

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

    Value *codegen() override;
};

class VariableExprAST : public ExprAST {
    std::string Name;

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

    Value *codegen() override;
};

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

    Value *codegen() override;
};

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

  Value *codegen() override;
};

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

    Function *codegen() override;
};

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

    Function *codegen();
};

int getNextToken();
int getNextToken(FILE *);
std::unique_ptr<FunctionAST> ParseDefinition();
std::unique_ptr<PrototypeAST> ParseExtern();
std::unique_ptr<FunctionAST> ParseTopLevelExpr();
#endif

codegen() 함수는 각 AST노드에 해당하는 LLVM IR을 생성해줍니다

LLVM IR이 익숙치 않으신 분들은 LLVM IR자체에 대해서 한번 공부해오시면 이해하는데 훨씬 수월합니다


사실 이렇게 함수들을 다 선언해서 해주는것말고 Visitor를 작성해 처리하는것도 좋겠지만, 이 튜토리얼은 좋은 알고리즘 구조를 갖추는것에 초점을 맞추는것이 아니고, 우리 언어에 있어서는 단순히 codegen함수를 모든 클래스에 추가해주는게 가장 간단합니다


두번쨰로, Parser에서도 만들었던것처럼 Code generator에서 사용할 함수를 정의합니다

CodeGen.cpp 를 엽니다


#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Verifier.h"
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <vector>
#include "Parser.h"

LLVMContext TheContext;
IRBuilder<> Builder(TheContext);
std::unique_ptr<Module> TheModule;
std::map<std::string, Value *> NamedValues;

Value *LogErrorV(const char *Str) {
    LogError(Str);
    return nullptr;
}

헤더파일은 이 파일 내에서 사용할 모든 헤더파일을 인클루드 했습니다.

우선 LogErrorV를 그냥 LogError의 래퍼로 구현했고


TheContext, Builder, TheModule, NamedValues 이 변수들은 코드제네레이션에서 계속 사용될 변수들입니다


TheContext: LLVM프레임워크에서 사용할 여러 타입이나 데이터들을 저장하고 있습니다. 정확하게 이해할 필요는 없고 그냥 LLVMContext를 인자로 받는 함수들에 전달해주면 됩니다

Builder: LLVM IR을 생성할때 사용할 인스턴스입니다. 일종의 엔진이라고 생각하면 됩니다

TheModule: 함수, 전역변수등을 저장하는 구조입니다. 코드제네레이션을 할 때 이 모듈에 LLVM IR을 저장합니다. 모든 IR에 대한 실질적 소유권을 갖고 있고, 이것때문에 codegen함수를 선언할 때 unique_ptr<Value *>가 아닌 Value *로 선언한것입니다

NamedValues: 컴파일러가 사용할 일종의 심볼테이블입니다. Kaleidoscope에서는 함수 코드를 생성할 때 그 함수의 인자들을 여기에 저장해둡니다



신고

설정

트랙백

댓글

2. Kaleidoscope: Implementing a Parser and AST 한글 번역

컴퓨터공부/엘엘비엠 2017.07.20 17:27
크리에이티브 커먼즈 라이선스
Creative Commons License

2.1. Chapter 2 Introduction

이번장에서는, 저번장에서 구현한 Lexer를 이용해 Parser를 만들고, Parser를 이용해 소스코드의 AST를 만듭니다.


우리가 구현할 파서는 Recursive Descent Parsing과 Operator-Precedence Parsing을 같이 사용합니다.

수 연산식을 파싱할때는 Operator-Precedence Parsing을 이용하고, 그 외 모든 다른 구문들은 Recursive Descent Parsing방식으로 파싱합니다


파싱을 바로 구현하기전에 소스코드 파싱을 해서 만들고자 하는 AST에 대해 먼저 설명합니다




2.2. The Abstract Syntax Tree

컴파일러에서 소스코드에 대한 AST를 만드는 것은 AST를 구성함으로써 다른 컴파일 과정들이 더 수월해지기 때문입니다(code -> LLVM IR generation같은 작업들)

AST를 만들기 위해서 우선 AST의 노드로 들어갈 각 언어 요소들에 대한 클래스를 정의하는것부터 시작합니다.

다시말해, NumberExprAST, FunctionAST, BinaryExprAST등 각 요소별 클래스를 정의합니다.


Parser.h

#ifndef __PARSER_H__
#define __PARSER_H__
#include <memory>
#include <string>
#include <vector>

class ExprAST {
public:
    virtual ~ExprAST() {}
};

class NumberExprAST : public ExprAST {
    double Val;

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

ExprAST는 모든 표현식을 나타내는 베이스 클래스입니다. 다른 클래스들이 모두 ExprAST를 상속받습니다.

NumberExprAST는 1.0과 같은 숫자데이터를 처리하기 위한 클래스입니다


이렇게 클래스를 정의할땐, 각 노드의 타입뿐 아니라, 각 노드가 갖고 있는 실제 값을 저장해야 합니다. 따라서 NumberExprAST도 인스턴스 변수를 둬서 그 숫자노드의 실제 값이 뭔지 저장해둡니다.


약간은 지루하겠지만, 먼저 모든 AST클래스를 정의한 뒤에 그걸 처리하는 파서 메소드를 작성하겠습니다


class VariableExprAST : public ExprAST {
    std::string Name;

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

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

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


NumberExprAST 선언부와 #endif 사이에 쓰시면 됩니다.

여기까지 하고 테스트 해보시려면 그냥 Parser.h -> Parser.cpp 로 바꾸고 clang++으로 컴파일 하면되는데, 그냥 컴파일하면 에러가 하나 납니다.

맨 마지막줄의 std::move(Args) 에서 나는데, clang++ -c Parser.cpp -std=c++11 로 컴파일하시면 해결됩니다.


여기까지해서, 우리 언어가 갖는 모든 표현식 종류를 정의했습니다. 예를들어 VariableExprAST는 변수명을 저장할거고, BinaryExprAST는 '+', '*' 등의 연산자를, CallExprAST는 함수 호출문을 정의해줍니다.

하지만 이 노드들로 언어 전체를 설명하기엔 부족함이 많죠, 지금 우리 언어에는 아직 조건분기가 없고, 따라서 튜링완전하지 않습니다. 이런 여러 언어의 요소들을 앞으로 더 추가해나가겠지만, 이번 글에서는 간단한 파서를 작성하는게 최종 목표이기 때문에 최대한 언어의 요소를 간단하게 한정합니다


그다음 클래스는 두개입니다.

지금 우리는 함수 호출하는거는 분석하지만 함수 자체는 관리하지 못합니다.

함수 자체를 관리하기 위한 클래스를 추가해줍니다

CallExprAST와 #endif사이에 쓰면 됩니다


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

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

여기까지, AST를 구성하는 모든 클래스의 정의를 마쳤습니다.

이제 이걸 바탕으로 파서를 구현할 수 있습니다



2.3. Parser Basics

소스코드를 파싱해 AST를 만든다는 것은, 예를들면 이런것입니다

x + y 라는 코드를 파싱해서, 여기에는 두개의 VariableExprAST가 있고, 이 두개가 BinaryExprAST에 의해 서로 연결되어 있다는 것을 분석하는 작업입니다.

auto LHS = llvm::make_unique<VariableExprAST>("x");
auto RHS = llvm::make_unique<VariableExprAST>("y");
auto Result = std::make_unique<BinaryExprAST>('+', std::move(LHS),
                                              std::move(RHS));

이러한 코드로 x+y라는 텍스트를 분석하겠다는 것입니다.


이 작업을 자동으로 하기 위해, Lexer에서 구현했던 gettok함수를 이용해 텍스트에서 토큰을 파싱합니다


Parser.cpp

#include "Parser.h"
#include "Lexer.h"

int CurTok;
int getNextToken(FILE *fp) {
    return CurTok = gettok(fp);
}

CurTok이라는 임시변수를 선언했습니다. 파서에서 구현할 모든 함수들에서 CurTok이 '현재' 파싱되고 있는 토큰이라는 것을 모두 전제한 상태에서 작동합니다.


std::unique_ptr<ExprAST> LogError(const char *Str) {
    fprintf(stderr, "LogError: %s\n", Str);
    return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
    LogError(Str);
    return nullptr;
}


파서에서는 AST를 구성하면서, 소스코드 문법에 대한 검사도 함께 진행합니다. 따라서 문법오류가 발생했을 때 에러를 띄워줄 함수를 정의해줍니다


이제 실제로 토큰을 파싱하는 코드들을 작성해봅시다



2.4. Basic Expression Parsing

먼저, 가장 처리하기 쉬운 숫자부터 처리해보겠습니다


std::unique_ptr<ExprAST> ParseNumberExpr() {
    auto Result = llvm::make_unique<NumberExprAST>(NumVal);
    getNextToken();
    return std::move(Result);
}

갑자기 NumVal이 나왔는데, 이건 Lexer에서 선언한 전역변수 입니다. 


#include "Parser.h"
#include "Lexer.h"

extern double NumVal;
extern std::string IdentifierStr;

int CurTok;


Parser.cpp의 위에 extern으로 선언해줍니다.


ParseNumberExpr함수는 현재 토큰이 tok_number일때 호출될것이기 때문에, Lexer에서 NumVal에 값이 설정된단것도 알고 있어서 바로 NumberExprAST 클래스를 생성합니다


여기서 파서의 한가지 특징이 나오는데, 각 타입에 대한 파서는 현재 타입에 대해 처리하고(eat한다고 표현합니다), 다음 파서 함수가 잘 작동할 수 있게 다음 토큰을 읽어들여줍니다.

예를들어 identifier를 처리한다면 identifier의 문자열 길이만큼 token을 처리하고 그 다음 문자를 가르키게 설정하고 종료하겠죠

이런 파싱 방식은 재귀하향파싱 방식에서 표준처럼 사용되는 방식입니다.

한가지 더 보죠


std::unique_ptr<ExprAST> ParseParenExpr() {
    getNextToken();
    auto V = ParseExpression();
    if (!V)
        return nullptr;

    if (CurTok != ')')
        return LogError("expected ')'");
    getNextToken();
    return v;
}

괄호식을 파싱하는 코드입니다. 현재 토큰이 '(' 일때 출력될것이고, 괄호 안의 표현식을 ParseExpression함수를 호출해 분석합니다.

func(arg1, arg2)

for(haha = 1; haha < 10; haha++) 이런 괄호는 이걸로 분석 안되는거 아니냐는 의문을 가지실 수 있는데 함수호출이나 for문등의 괄호는 따로 처리되고, 이건 연산식에서 사용되는 괄호를 처리합니다.


3가지를 짚고 넘어가겠습니다.

1. 이 함수에서는 LogError를 이용해 에러를 출력하고, 그 에러메세지는 원래 문법상 현재 와야하는 문자가 뭔지를 알려줍니다. 이런식으로 각각 파서에서는 잘못된 문법을 잡아 출력해줍니다.

2. 모든걸 한번에 분석하는 것이 아닌, ParseExpression함수를 이용해 작업을 분담합니다. 하나 재밌는것은 ParseExpression함수에서도 ParseParanExpr을 호출할수 있다는 겁니다.

예를들어

(haha == 1 && (hoho == 2 || hehe == 3)) 등과 같은 코드를 처리하기 위해서죠

3. 괄호는 단순 텍스트로 처리되고, AST에는 추가되지 않습니다. 괄호는 단순히 표현식들의 그룹핑을 위해 존재하는것이고 그 자체로 큰 의미가 있지 않기 떄문입니다. 그래서 파서가 AST를 구성하고 나면 괄호는 필요하지 않습니다



다음으로 변수 참조와 함수 호출을 처리합니다


std::unique_ptr<ExprAST> ParseIdentifierExpr() {
    std::string IdName = IdentifierStr;

    getNextToken();

    if (CurTok != '(')
        return std::make_unique<VariableExprAST>(IdName);

    getNextToken();
    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();
        }
    }

    getNextToken();

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

지금까지 작성한 함수들과 전체적인 스타일이 비슷한 루틴입니다. 재귀호출을 하고, 예외처리를 하고, 토큰 하나를 더 읽어들여 현재 식별자가 변수참조인지 함수호출인지 알아냅니다

지금까지 처리한 토큰들은 IdentifierExpr, NumberExpr, ParenExpr이고, 이 세가지를 primary expression이라고 부르겠습니다.이렇게 나누는 이유는 나중에 user defined operator들을 처리하기 수월해지기 때문입니다.


이제 수식을 파싱해보겠습니다. 수식파싱은 조금더 복잡합니다



2.5. Binary Expression Parsing

수식을 파싱하려면 수식 안에 있는 연산자들과 표현식들의 우선순위를 판별해야 합니다.

연산자가 한두개는 아니기 때문에 범용적으로 여러 우선순위의 연산자들을 잘 처리해줘야 합니다

우선순위를 처리하기 위한 방법들은 많지만 깔끔하고 효율적인 방식인 Operator-Precedence Parsing을 사용하겠습니다

Operator-Precedence Parsing은 각 연산자 우선순위에 맞게 재귀적으로 수식을 처리합니다

먼저, 연산자들과 각각의 우선순위의 맵을 생성합니다

std::map<char, int> BinOpPrecedence; int GetTokPrecedence(){ if (!isascii(CurTok)) return -1; int TokPrec = BinOpPrecedence[CurTok]; if (TokPrec <= 0) return -1; return TokPrec; }

BinOpPrecedence라는 맵을 전역변수로 선언했고, 현재 토큰을 BinOpPrecedence의 키로 써서 우선순위를 가져오는 함수를 작성했습니다.

이 BinOpPrecedence는 main함수에서 후에 초기화 됩니다.


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

Kaleidoscope는 기본적으로 연산자가 4개입니다. 직접 있으면 좋겠다 싶은 연산자들도 구현해보세요

이렇게 맵을 만들어서 우선순위를 관리하면, 새로운 연산자를 추가하기도 쉽고 파싱 알고리즘이 특정 연산자들에 의존하지 않는, 즉 범용적인 파싱이 가능합니다.


Operator-Precedence Parsing은 우선 수식 전체를 일정 단위로 잘라냅니다

예를들어

a+b+(c+d)*e*f+g 라는 식이 있다면

(binary operator, primary expression) 의 단위로 잘라냅니다

a 는 첫 시작이니 그대로 냅두고

a (+, b) (+, (c+d)) (*, e) (*, f) (+, g) 이런식으로 나눕니다

괄호식은 그 자체로 primary expression이기 때문에 그 안에 있는것은 ParsePrimary함수에 의해 재귀적으로 파싱됩니다


전체 표현식은 우선 처음에 primary expression하나가 있고, 그다음에 (binop, primaryexpr)가 올수도 있고 안올수도 있습니다

x 도 expression이고

x+y+z 도 expression입니다

이걸 코드로 분석해봅시다


std::unique_ptr<ExprAST> ParseExpression() {
    auto LHS = ParsePrimary();
    if (!LHS)
        return nullptr;

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

ParseBinOpRHS는 parse binop, rhs 입니다

(binop, primaryexpr) 에서 primaryexpr이 RHS라고 보시면 됩니다(Right Hand Side, 우항)

ParseBinOpRHS는 수식을 모두 파싱할때까지 재귀적으로 호출됩니다


std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                       std::unique_ptr<ExprAST> LHS) {
    while (1) {
        int TokPrec = GetTokPrecedence();
        if (TokPrec < ExprPrec)
            return LHS;

ParseBinOpRHS함수의 첫 번째 인자는 현재 파싱된 식 중에 제일 높은 우선순위를 갖고 있습니다

GetTokPrecedence함수가 현재 토큰이 연산자가 아니면 -1을 리턴하기 때문에 if (TokPrec < ExprPrec)에서 파싱은 종료됩니다


그리고 우선순위가 높은것부터 먼저 처리해야 하기 때문에, ExprPrec보다 우선순위가 낮은것은 일단 스킵하고 높거나 같은것부터 먼저 처리합니다


        int BinOp = CurTok;
        getNextToken();

        auto RHS = ParsePrimary();
        if (!RHS)
            return nullptr;

위의 조건문에 의해서 현재 CurTok은 무조건 연산자입니다.

연산자를 BinOp에 저장하고 그다음 토큰을 읽어들이고, primary expression을 파싱합니다.

이 때 RHS에 nullptr이 리턴될경우 expression이 없다는 것이고, 이는 문법오류기 때문에 nullptr를 리턴해줍니다.


여기까지 딱 한번 도달했다고 치면, 아까 예로 든 식 a+b+(c+d)*e*f+g 에서

a + b 까지 분석했고 BinOp='+' RHS='b' 가 된 상태입니다

여기서 이걸 바로 처리하느냐 아니면 나중에 처리하느냐는 RHS의 다음 operator 우선순위와 현재 BinOp의 우선순위를 비교해야 알 수 있습니다

즉, a + b * 처럼 RHS다음 operator가 *라면 +보다 우선순위가 높은것이기 때문에 현재 식은 처리하지 않고 다음 식부터 처리합니다.(재귀적으로 그다음 항에 대해 ParseBinOpRHS를 호출하면 함수가 끝나고 돌아와서 다시 a+b 와 그 식을 처리해줄 수 있겠죠.)


설명이 조금 어려울 수도 있지만 그렇게 어려운 내용은 아닙니다. 그럼 코드로 보죠


        int NextPrec = GetTokPrecedence();
        if (TokPrec < NextPrec) {

ParsePrimary함수는 현재 토큰들을 모두 처리한뒤 getNextToken함수를 호출해 다음토큰까지 읽어들입니다.

따라서 이 위의 코드까지 실행된 뒤에는 CurTok은 RHS다음 연산자를 갖게 됩니다

그래서 바로 GetTokPrecedence를 하면 RHS다음 연산자 우선순위를 가져오게 됩니다

이걸 현재 Precedence와 비교합니다


if (TokPrec < NextPrec) { RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS)); if (!RHS) return nullptr; } LHS = std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));

우선 if문 안에는 현재 처리하고 있는 식보다 다음식이 우선순위가 더 높은경우이고,

if문 밖에는 항상 LHS가 RHS보다 우선순위가 더 높습니다(우선순위가 더 높으면 if문안에서 모두 처리되기 때문에)

그런데 한가지 재밌는것은 TokPrec + 1 을 Precedence로 설정해서 함수를 호출한다는 것입니다

RHS들을 쭉 돌면서, 현재 TokPrec과 같거나 작은 Precedence가 발견되면 거기서 멈추겠다는 겁니다

a+b+(c+d)*e*f+g

a+를 빼고 b + (c+d) * e *f + g 여기부터 봅시다

b + (c+d) * e * f + g 가 있을 때

b 가 LHS라고 한다면

RHS는 (c+d) * e * f 까지만 이어야 합니다

즉 TokPrec과 같은 우선순위를 갖는 연산자까지 RHS로 묶어버릴 필요는 없다는 겁니다

이를 위해서 TokPrec + 1 을 인자로 넣어줍니다


이렇게까지 처리가 끝나면, 그 다음 루프에서 + g 까지 모두 처리가 됩니다

어렵긴 했지만, 재귀호출만 잘 이해한다면 이해할 수 있는 처리입니다

여기까지해서 모든 expression에 대한 파싱이 끝났습니다


여기까지 한걸 컴파일해보려면 우선 map헤더파일을 추가해주고

#include <map>


 std::unique_ptr<ExprAST> ParseExpression();
 std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                        std::unique_ptr<ExprAST> LHS);

이렇게 함수 선언부를 코드 맨위쪽에 추가합니다


cd80@Sungui-MacBook-Pro ~/study/Kaleidoscope » clang -c Parser.cpp -std=c++14

cd80@Sungui-MacBook-Pro ~/study/Kaleidoscope »

오류 없이 잘 컴파일됩니다.




2.6. Parsing the Rest

마지막으로 함수 프로토타입과 구현부를 파싱해봅시다

표현식 파싱을 제대로 이해하셨다면 딱히 다를게 없습니다. 수식 파싱보다도 훨씬 쉽습니다


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");

    std::vector<std::string> ArgNames;
    while (getNextToken() == tok_identifier)
        ArgNames.push_back(IdentifierStr);
    if (CurTok != ')')
        return LogErrorP("Expected ')' in prototype");

    getNextToken();

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

참고로 Kaleidoscope에서의 함수는 

def f(a, b) <Expression> 의 형태입니다.

그래서 함수 구현체를 파싱하려면 먼저 Prototype을 파싱하고, ParseExpression을 한번만 호출해주면됩니다


std::unique_ptr<FunctionAST> ParseDefinition() {
    getNextToken();
    auto Proto = ParsePrototype();
    if (!Proto) return nullptr;

    if (auto E = ParseExpression())
        return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
    return nullptr;
}


추가로, 외부함수나 c언어에서와 같은 forward declaration을 지원하기 위한 extern을 처리합니다

extern은 프로토타입만 있는 함수 선언입니다

std::unique_ptr<PrototypeAST> ParseExtern() {
    getNextToken();
    return ParsePrototype();
}


마지막으로, 파이썬이나 자바스크립트에서처럼 함수 없이 그냥 있는 코드들을 처리해줍니다

이 코드들을 인자가 없는 익명함수 안에 있는 코드로 만들어 처리합니다


std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
    if (auto E = ParseExpression()) {
        auto Proto = std::make_unique<PrototypeAST>("", std::vector<std::string>());
        return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
    }
    return nullptr;
}


이제 다 완성됐습니다. 고생하셨습니다

저번장에서 만든 메인함수를 수정해서 이번 글에서 작성한 코드를 테스트해봅시다.


main.cpp

#include "Parser.h"
#include <stdio.h>
#include <map>
void HandleDefinition();
void HandleExtern();
void HandleTopLevelExpression();


extern std::map<char, int> BinOpPrecedence;
extern char CurTok;
int main(int argc, char *argv[]){
    BinOpPrecedence['<'] = 10;
    BinOpPrecedence['+'] = 20;
    BinOpPrecedence['-'] = 20;
    BinOpPrecedence['*'] = 40;
    fprintf(stderr, "ready> ");
    getNextToken();
    while(1){
        fprintf(stderr, "ready> ");
        switch (CurTok) {
            case tok_eof:
                return 0;
            case ';':
                getNextToken();
                break;
            case tok_def:
                HandleDefinition();
                break;
            case tok_extern:
                HandleExtern();
                break;
            default:
                HandleTopLevelExpression();
                break;
        }
    }
}

void HandleDefinition() {
    if (ParseDefinition()) {
        fprintf(stderr, "Parsed a function definition.\n");
   } else {
        getNextToken();
    }
}

void HandleExtern() {
    if (ParseExtern()) {
        fprintf(stderr, "Parsed an extern\n");
    } else {
        getNextToken();
    }
}

void HandleTopLevelExpression() {
    if (ParseTopLevelExpr()) {
        fprintf(stderr, "Parsed a top-level expr\n");
    } else {
        getNextToken();
    }
}    } else {
        getNextToken();
    }
}

void HandleExtern() {
    if (ParseExtern()) {
        fprintf(stderr, "Parsed an extern\n");
    } else {
        getNextToken();
    }
}

void HandleTopLevelExpression() {
    if (ParseTopLevelExpr()) {
        fprintf(stderr, "Parsed a top-level expr\n");
    } else {
        getNextToken();
    }
}


Parser.h

#ifndef __PARSER_H__
#define __PARSER_H__
#include <memory>
#include <string>
#include <vector>

class ExprAST {
    public:
        virtual ~ExprAST() {}
};

class NumberExprAST : public ExprAST {
        double Val;

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

class VariableExprAST : public ExprAST {
        std::string Name;

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

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

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

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

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

int getNextToken();
int getNextToken(FILE *);
std::unique_ptr<FunctionAST> ParseDefinition();
std::unique_ptr<PrototypeAST> ParseExtern();
std::unique_ptr<FunctionAST> ParseTopLevelExpr();
#endif


Parser.cpp

#include "Parser.h"
#include "Lexer.h"
#include <memory>
#include <map>

extern double NumVal;
extern std::string IdentifierStr;
std::unique_ptr<ExprAST> ParseExpression();
std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                       std::unique_ptr<ExprAST> LHS);

int CurTok;
int getNextToken() {
    return CurTok = gettok(stdin);
}
int getNextToken(FILE *fp) {
    return CurTok = gettok(fp);
}

std::unique_ptr<ExprAST> LogError(const char *Str) {
    fprintf(stderr, "LogError: %s\n", Str);
    return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
    LogError(Str);
    return nullptr;
}

std::unique_ptr<ExprAST> ParseNumberExpr() {
    auto Result = std::make_unique<NumberExprAST>(NumVal);
    getNextToken();
    return std::move(Result);
}

std::unique_ptr<ExprAST> ParseParenExpr() {
    getNextToken();
    auto V = ParseExpression();
    if (!V)
        return nullptr;

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

std::unique_ptr<ExprAST> ParseIdentifierExpr() {
    std::string IdName = IdentifierStr;

    getNextToken();

    if (CurTok != '(')
        return std::make_unique<VariableExprAST>(IdName);

    getNextToken();
    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();
        }
    }

    getNextToken();

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

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

std::map<char, int> BinOpPrecedence;
int GetTokPrecedence(){
    if (!isascii(CurTok))
        return -1;

    int TokPrec = BinOpPrecedence[CurTok];
    if (TokPrec <= 0) return -1;
    return TokPrec;
}

std::unique_ptr<ExprAST> ParseExpression() {
    auto LHS = ParsePrimary();
    if (!LHS)
        return nullptr;

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

std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                       std::unique_ptr<ExprAST> LHS) {
    while (1) {
        int TokPrec = GetTokPrecedence();
        if (TokPrec < ExprPrec)
            return LHS;

        int BinOp = CurTok;
        getNextToken();

        auto RHS = ParsePrimary();
        if (!RHS)
            return nullptr;

        int NextPrec = GetTokPrecedence();
        if (TokPrec < NextPrec) {
            RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
            if (!RHS)
                return nullptr;
        }

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

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");

    std::vector<std::string> ArgNames;
    while (getNextToken() == tok_identifier)
        ArgNames.push_back(IdentifierStr);
    if (CurTok != ')')
        return LogErrorP("Expected ')' in prototype");

    getNextToken();

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

std::unique_ptr<FunctionAST> ParseDefinition() {
    getNextToken();
    auto Proto = ParsePrototype();
    if (!Proto) return nullptr;

    if (auto E = ParseExpression())
        return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
    return nullptr;
}

std::unique_ptr<PrototypeAST> ParseExtern() {
    getNextToken();
    return ParsePrototype();
}

std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
    if (auto E = ParseExpression()) {
        auto Proto = std::make_unique<PrototypeAST>("", std::vector<std::string>());
        return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
    }
    return nullptr;
}




신고

설정

트랙백

댓글

1. Kaleidoscope: Tutorial Introduction and the Lexer 한글 번역

컴퓨터공부/엘엘비엠 2017.07.20 16:01
크리에이티브 커먼즈 라이선스
Creative Commons License

1.1 Tutorial Introduction


이 튜토리얼은 LLVM을 이용해 자신만의 프로그래밍 언어를 만들어 볼 수 있도록 아주 쉽고 간단하게 단계별로 설명합니다

만들 언어의 이름은 Kaleidoscope고, 이 언어를 파싱해 LLVM IR로 바꿔주는 프론트엔드, 만들어진 IR을 이용해 프로그램을 최적화시키는 Optimizer, 그리고 최종 결과 IR을 원하는 아키텍쳐의 머신코드, 혹은 우리가 원하는 커스텀 아키텍쳐의 머신코드로 바꿔주는 백엔드단까지, 모든 레이어를 순서대로 구현해볼것입니다


튜토리얼 진행 순서는 아래와 같습니다

챕터 1. 튜토리얼 소개 및 Lexer 구현 : (이 글입니다) Kaleidoscope언어에 대한 소개와, 소스코드 토큰을 분석하는 Lexer를 구현합니다.


챕터 2. 파서, AST 구현 : 이전 장에서 구현한 Lexer(어휘분석기)를 바탕으로, Parser(구문분석기)를 구현하고, 소스코드의 AST를 구축합니다.이 튜토리얼에서는 재귀하향파싱과 연산자우선순위 분석에 대해 설명합니다. 여기까지는 LLVM의 기능을 이용하지 않는, 완전히 프론트엔드 구현만 합니다


챕터 3. LLVM IR 생성 : 이전 장에서 구현한 AST를 이용해 소스코드를 LLVM IR로 변환해봅니다


챕터 4. JIT, 최적화 기능 추가 : LLVM은 clang과 더불어 단독 컴파일러로도 많이 사용되지만, LLVM의 JIT기능 사용에 관심있는 사람들도 굉장히 많습니다. 심지어 JIT기능을 추가하는데는 3줄만 넣어주면 되기 때문에 먼저 설명합니다.


챕터 5. 실행 흐름 기능 추가 : 이전까지 구현한 컴파일러는 선형 소스코드만 지원합니다. 이 장에서는 if, for 등과 같은 분기문을 언어에 추가해줍니다.


챕터 6. 사용자지정 연산자 추가 : C++에서 처럼 연산자들을 커스터마이징 할 수 있는 기능을 우리 언어에 추가합니다.


챕터 7. 변수 추가 : 대입연산자를 이용해 변수를 만드는 기능을 추가합니다. 


챕터 8. 컴파일 : LLVM IR을 오브젝트 파일로 컴파일시켜주는 코드를 우리 컴파일러에 추가합니다.


챕터 9. 디버깅정보 추가 : 오브젝트 파일에 소스코드 디버깅정보를 추가시켜봅니다


챕터 10. 여러 기능 추가 : 여기서는 자세하게는 다루진 않지만 가비지컬렉션, 예외처리, 디버깅지원 등 유용한 기능들을 구현하려면 어떻게 공부해야 하는지 설명합니다.





1.2 The Basic Language

우리가 만들 언어의 이름은 Kaleidoscope입니다.

Kaleidoscope는 절차지향 언어고, 함수를 정의할 수 있고, 조건분기를 할 수 있으며, 수학계산이 가능한 간단한 언어입니다

처음에는 단순한 선형계산밖에 하지 못하지만, 조건분기, 연산자 오버로딩등의 기능들을 점점 추가할겁니다.


언어 구현을 간결하게 하기 위해 모든 변수 타입은 double형입니다(64비트 실수). 그리고 파이썬처럼 변수 선언시에 타입선언을 필요로 하지 않습니다


코드 예시:

# 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는 외부 라이브러리 함수를 호출할 수 있는 기능도 있습니다

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

atan2(sin(0.4), cos(42))




1.2 The Lexer

소스코드를 컴파일하기 위해선, 텍스트파일과 다름없는 소스코드에 들어있는 언어의 요소들을 분석해야합니다. 예를들어 int i = 3; 이라면, int가 무엇이고 i가 무엇이고 = 가 무엇이고 3이 무엇인지, 그리고 각 요소들이 어떻게 서로 상호작용하는지 분석해야 합니다


소스코드를 분석하는 맨 첫 단계를 Lexical Analysis(어휘분석)이라고 하고, 어휘분석을 하는 툴을 Lexer라고 합니다.

Lexer에서는 예로 든 것 처럼, int i = 3; 이 있을 때, int가 type specifier고, i가 variable name이고, =이 operator고, 3이 constant int라는것을 분석하는 작업을 하고 각각을 토큰이라고 합니다


렉서를 구현할때는 우선 토큰의 종류부터 정리합니다

#include <iostream>
enum Token {
    tok_eof = -1,

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

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

std::string IdentifierStr; // Filled when token == tok_identifier
double NumVal;             // Filled when token == tok_number


우리가 구현할 Lexer는 현재 문자가 EOF, def, extern, identifier, number라면 각각 tok_~~을 리턴하고, tok_identifier일 경우 IdentifierStr 변수에 identifier의 이름을 저장해주고, tok_number일 경우에는 NumVal에 그 숫자를 저장해둡니다.

'+' 같이, 현재 Lexer에서 처리되지 않는 토큰들은 그 문자 자체를 리턴해 별도로 처리합니다(주석의 경우 '#' 이 리턴되면 주석으로 처리)


이제 코드에서 토큰을 가져오는 코드를 작성해봅니다. 원문에서는 standard input에서만 입력받게 돼있지만, 본 튜토리얼에서는 임의의 file stream에서 읽어오게 바꿨습니다

위의 코드 바로 밑에부터 작성을 하시면됩니다.

int gettok(FILE *fp){
    static int lastChar = ' ';

    while(isspace(lastChar))
        lastChar = fgetc(fp);
}

우선 공백은 모두 건너뜁니다.



int gettok(FILE *fp){
    static int lastChar = ' ';

    while(isspace(lastChar))
        lastChar = fgetc(fp);

    if(isalpha(lastChar)){
        IdentifierStr = lastChar;
        while(isalnum(lastChar = fgetc(fp)))
            IdentifierStr += lastChar;

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

현재 문자가 알파벳이라면 identifier로써 취급해 처리합니다

그 중, 예약어인 def와 extern에 대해서는 따로 처리를 하고, 나머지는 모두 tok_identifier로 리턴합니다

따로 언급되진 않았지만, 숫자가 아닌 모든 문자는 숫자로 시작하면 안됩니다.(3cakes 같은 변수명 불가)

그리고 IdentifierStr에 현재 식별자가 저장됩니다.



int gettok(FILE *fp){
    static int lastChar = ' ';

    while(isspace(lastChar))
        lastChar = fgetc(fp);

    if(isalpha(lastChar)){
        IdentifierStr = lastChar;
        while(isalnum(lastChar = fgetc(fp)))
            IdentifierStr += lastChar;

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

    if(isdigit(lastChar)){
        std::string numStr;
        do {
            numStr += lastChar;
            lastChar = fgetc(fp);
        } while(isdigit(lastChar) || lastChar == '.');

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

만약 첫 시작이 숫자라면, 쭉 수를 받고, NumVal에 설정해줍니다.

int나 float 상관없이 모두 double로 처리합니다(strtod)


이 코드는 123, 123.123 등은 정상적으로 처리하지만, 12.34.56또한 숫자로 처리합니다. 원문 튜토리얼에서는 이 문제를 직접 고쳐보라고 돼있습니다


아래는 제가 고친 예시입니다


    if(isdigit(lastChar)){
        std::string numStr;
        bool dotAppeared = false;
        bool numErr = false;
        do {
            numStr += lastChar;
            lastChar = fgetc(fp);
            if(lastChar == '.'){
                if(dotAppeared)
                    numErr = true;
                else
                    dotAppeared = true;
            }
        } while(isdigit(lastChar) || lastChar == '.');

        if(numErr){
            printf("%s is not a number\n", numStr.c_str());
            exit(1);
        }
        NumVal = strtod(numStr.c_str(), 0);
        return tok_number;
    }


다음으로 주석을 처리합니다


    if(lastChar == '#'){
        do lastChar = fgetc(fp);
        while(lastChar != EOF && lastChar != '\n' && lastChar != 'r');

        if(lastChar != EOF)
            return gettok(fp);
    }


#이 나오면 주석으로 취급해 그 줄의 끝이나 파일끝이 나올때까지 스킵합니다


마지막으로 다른 모든 문자들을 단일문자로 리턴합니다.


    if(lastChar == EOF)
        return tok_eof;

    int thisChar = lastChar;
    lastChar = fgetc(fp);
    return thisChar;


바로 lastChar를 리턴하지 않는 이유는 gettok함수 맨 처음에서 lastChar변수를 static으로 선언했기 때문입니다. 위 다섯줄가량을 읽어보시면 이해하실 수 있습니다.



여기까지 Lexer를 구현해봤습니다. 다음 글에서는 이 Lexer를 도구로 이용해 Parser를 구현하고 Abstract Syntax Tree를 구현해보겠습니다



여기까지 하시면서 실수가 없었는지 확인해보시려면 clang -c Lexer.cpp를 해보시면 됩니다. 문제가 있으면 에러가 뜰것이고 없다면 Lexer.o가 만들어질것입니다

아래는 Lexer의 full code입니다.


Lexer.cpp

#include "Lexer.h"

std::string IdentifierStr; // Filled when token == tok_identifier
double NumVal;             // Filled when token == tok_number

int gettok(FILE *fp){
    static int lastChar = ' ';

    while(isspace(lastChar))
        lastChar = fgetc(fp);

    if(isalpha(lastChar)){
        IdentifierStr = lastChar;
        while(isalnum(lastChar = fgetc(fp)))
            IdentifierStr += lastChar;

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

    if(isdigit(lastChar)){
        std::string numStr;
        bool dotAppeared = false;
        bool numErr = false;
        do {
            numStr += lastChar;
            lastChar = fgetc(fp);
            if(lastChar == '.'){
                if(dotAppeared)
                    numErr = true;
                else
                    dotAppeared = true;
            }
        } while(isdigit(lastChar) || lastChar == '.');

        if(numErr){
            printf("%s is not a number\n", numStr.c_str());
            exit(1);
        }
        NumVal = strtod(numStr.c_str(), 0);
        return tok_number;
    }

    if(lastChar == '#'){
        do lastChar = fgetc(fp);
        while(lastChar != EOF && lastChar != '\n' && lastChar != 'r');

        if(lastChar != EOF)
            return gettok(fp);
    }

    if(lastChar == EOF)
        return tok_eof;

    int thisChar = lastChar;
    lastChar = fgetc(fp);
    return thisChar;
}


Lexer.h


#ifndef __LEXER_H__
#define __LEXER_H__
#include <iostream>
enum Token {
    tok_eof = -1,

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

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

int gettok(FILE *fp);
#endif


Lexer구현한것이 잘 작동하는지 보기 위해 간단한 드라이버를 작성해보겠습니다


main.cpp


#include "Lexer.h"
#include <stdio.h>
extern std::string IdentifierStr;
extern double NumVal;
int main(int argc, char *argv[]){
    while(1){
        int tokType = gettok(stdin);
        switch(tokType){
            case tok_eof:
                printf("[tok_eof]\n");
                return 0;
            case tok_def:
                printf("[tok_def]\n");
                break;
            case tok_extern:
                printf("[tok_extern]\n");
                break;
            case tok_identifier:
                printf("[tok_identifier] %s\n", IdentifierStr.c_str());
                break;
            case tok_number:
                printf("[tok_number] %lf\n", NumVal);
                break;
            default:
                printf("[default] %c\n", tokType);
        }
    }
}


컴파일은 

clang++ -o main main.cpp Lexer.cpp

로 하시면 됩니다.

Lexer에서는 LLVM기능을 사용하지 않았기 때문에 따로 할건 없습니다




신고

설정

트랙백

댓글


티스토리 툴바