Compiler의 구조 알아보기 (Front-end)

Compiler란?

컴파일러도 결국은 컴퓨터 프로그램입니다. 그중에서도 인간이 알아듣기 편한 프로그래밍 언어를 컴퓨터가 알아들을 수 있는 기계어 (0/1로 이루어진 명령어들)로 바꿔 주는 프로그램입니다.

모든 프로그램이 그렇듯 컴파일러도 재사용성을 높이고 유지보수를 편하게 하기 위해 3개 부분으로 역할이 나눠져 있습니다. 이 각 부분을 차례대로 알아보겠습니다!

1. Front-end
2. Middle-end (예정)
3. Back-end (예정)

 

먼저 그 전에, 형식언어라는 개념에 대해 알아두면 이해가 더 편하기 때문에 형식언어에 대해 가볍게 알아보시기를 추천드립니다.

형식 언어 (Formal Language)

 

 

형식 언어와 연관이 큰 오토마타도...

오토마타 (Automata), 그게 대체 뭔데?

 

---

Front-end란?

코드가 문법적, 의미론적으로 맞는지 확인하고
IR로 변환

 

프로그래밍 언어의 소스코드 (Source Code)는 결국 텍스트입니다. 이 컴퓨터에겐 아무 의미 없는 텍스트를 묶고, 문법에 맞게 배치하고, 의미적론적으로 (Semantic) 잘못된 부분이 없는지 확인한 후 최종적으로 Middle-end가 쓸 수 있는 IR (Intermediate Representation)로 변환하는 게 Front-end의 역할입니다.

언어의 모든 개성은 Front-end에 들어있다고 해도 과언은 아닙니다.

 

---

1 - Scanner

소스 코드 (Source Code)인 텍스트를 토큰 (Token)이라는 단위로 묶는 작업입니다. 토큰은 2가지로 구분 돼 있습니다.

1. Token Type: 토큰의 종류 (오른쪽 괄호, Boolean true, String/Number 등의 Literal, 예약어 등)
2. Lexeme: 실제 문자열

 

 

이 과정은 생각보다 간단하게 이루어집니다. 말 그대로 문자열을 받아서, 1개씩 처리하면 됩니다. 이 과정에서 전/후 문자열을 봐야 하는 경우도 있지만 그 이상의 동작은 없는 간단한 과정입니다. (그래서 촘스키 위계의 가장 아래인 Regular Language로 나타낼 수 있습니다.)

switch (c) {
    // 이 문자열들은 특정 용도로만 쓰여서 등장하면 무조건 특정한 Token Type
    case '(':
        addToken(TokenType.LEFT_PAREN);
        break;
    case ')':
        addToken(TokenType.RIGHT_PAREN);
        break;
    case '{':
        addToken(TokenType.LEFT_BRACE);
        break;
    case '}':
        addToken(TokenType.RIGHT_BRACE);
        break;
    case ',':
        addToken(TokenType.COMMA);
        break;

    // /가 나올 경우 연속으로 /가 나오면 //가 돼 주석이라 무시하고, 이 이외의 경우는 나누기로 취급
    case '/':
        if (match('/')) {
            // 주석이여서 무시
            while (peek() != '\n' && !isAtEnd()) advance();
        } else {
            addToken(TokenType.SLASH);
        }
        break;
        
    // 의미 없는 공백은 무시
    case ' ':
    case '\r':
    case '\t':
        break;

    // 등등 생략
}

---

2 - Parser

다음으로 Parser는 Scanner가 예쁘게 묶어 놓은 토큰 (Token)을 받아 문법 규칙들 (Formal Grammar)을 적용해서 AST (Abstract Syntax Tree)를 만드는 과정입니다.

 

프로그래밍 언어의 문법을 트리 (Tree) 구조로 나타내는 건 형식 문법 (Formal Grammar)의 구조가 재귀적이라는 것과 관련이 있습니다. 형식 문법은 Terminal과 Nonterminal로 이루어져 있고, 모든 요소가 Terminal로 이루어질 때까지 Nonterminal을 재귀적으로 호출하는 구조입니다.

예를 들어 Kotlin 언어의 함수 부분을 형식 문법으로 나타내 보겠습니다. BNF라는 표기법을 쓴 건데, 뭔지 구체적으로 아실 필요는 없습니다. 

• function     → "fun" identifier "(" parameters ")" returnType block ;
• parameters   → parameter ;
• parameters   → parameter "," parameters ;
• parameter    → identifier ":" type ;
• returnType   → ":" type ;
• block        → "{" statements "}" ;
• statements   → statement ;
• statements   → statement statements ;
• statement    → variableDeclaration ;
• statement    → returnStatement ;
• variableDeclaration → "val" identifier ":" type "=" expression ";" ;
• returnStatement     → "return" expression ";" ;
• expression   → literal ;
• expression   → identifier ;
• type         → "Int" ;
• type         → "String" ;
• type         → "Boolean" ;

먼저 화살표 (->) 앞부분은 규칙의 이름입니다. 지금 하려는 게 Kotlin의 함수 문법을 나타내는 것이니 첫 줄은 함수라는 규칙을 이제부터 묘사하겠다!라는 뜻입니다. 화살표 오른쪽 부분이 규칙의 형식입니다. Kotlin 함수는 fun이라는 문자로 시작합니다. ""로 구성된 문자가 Terminal입니다. 그 외의 모든 문자는 Nonterminal이라, 아래 다른 규칙의 이름을 보고 Nonterminal이 나올 때까지 재귀적으로 호출해야 합니다. 아무튼, fun 키워드 다음에 identifier라는 애가 나오고, 그 뒤에 다시 Nonterminal인 (, 다시 Terminal인 parameters, 다시 Nonterminal인 ), 등등이 나옵니다. 

아무튼, 예시로 Nonterminal인 paramters를 호출해 보겠습니다. paramters는 2가지 선택지가 있습니다. parameter 1개로 구성되던가, parameter 1개와 , 다음에 다시 parameters로 구성되던가. 이건 Kotlin 함수에서 인자를 여러 개 넣을 수 있기 때문에 당연한 정의입니다.

fun test(test1: String) {} // 가능
fun test(test1: String, test2: String) {} // 가능

parameter 1개는 identifier 다음 : 다음 type이 나옵니다. identifier를 가면 또 이름을 짓는 규칙이 나오고, 최종적으로 Terminal이 나옵니다. Type도 간단히 하기 위해 Int, String, Boolean 3개 중 1개를 선택하게 했습니다. 결국 Type도 최종적으로는 Terminal입니다. 

이런 애매함 없이 완벽하게 정의된 규칙을 따라서 AST를 만듭니다. 만약 이 규칙들을 따르지 않는다면 오류가 납니다.

---

3 - Semantic Analysis

Parser에서 모든 형식 문법을 완벽하게 따라서 AST를 만드는 데 성공했다고 해도 이게 오류가 없는 프로그램이라는 건 아닙니다. 아래와 같은 많은 경우가 문법적으로는 오류가 없는데 의미적으로는 오류가 있습니다.

• 모든 변수는 쓰기 전에 선언해야 한다.
• (프로그래밍 언어에 따라 다르지만) 같은 Type 끼리만 연산을 할 수 있다.
• Scope 내에 있는 변수만 사용할 수 있다.
• 함수 호출 시 Return 타입이 일치해야 한다.

이러한 정보들은 프로그램을 읽으면서 규칙을 지켰는지 하나하나 확인해야 합니다. (이 과정은 촙스키 위계의 Regular Language에 해당합니다.)

---

4 - IR Generation

위 과정이 모두 끝나면 이제 이 프로그램은 문법적으로 (Syntax), 의미론적으로 (Semantic) 모두 올바른 프로그램이라고 할 수 있습니다. 이제 Middle-end가 사용할 수 있도록 IR (Intermediate Representation) 형식으로 변환해야 합니다.

여기서 바로 컴퓨터가 이해할 수 있는 기계어로 번역하지 않는 건 여러 가지 이유가 있습니다.

• 중간 과정 없이 바로 변환하면 각 CPU Architecture에 맞게 노동을 해야 한다.
• 코드의 비효율적인 부분을 최적화할 수 있는 기회가 없다.

특히 컴파일러가 하는 여러 최적화는 보통 Middle-end에서 일어납니다.

컴파일러가 기본적으로 하는 최적화를 알아보자

 

가장 유명한 IR은 LVVM이 있습니다. Swift, Rust, Zig 등이 LVVM을 사용합니다.

---