스스로 컴파일러 만들기: lexer parser type inference

초보자의 경험담: 깊은 지식 없이 컴파일러를 처음부터 만들어보기

컴파일러는 여러 단계로 구성됩니다: 렉서, 파서, 타입 추론, 준비 단계, 코드 생성. 저자는 컴파일러 제작 경험이 전혀 없는 상태에서 Rust와 유사한 의미론을 가진 오픈소스 C# 프로젝트를 공부하며 시작했습니다. 기존 코드를 수정하는 대신, 기초를 배우면서 모든 것을 처음부터 구현했습니다. 이 과정은 엄격하게 상향식이나 하향식이 아니었습니다. 단계 간 상호 의존성 때문에 여러 번 재작업이 필요했습니다.

데이터 흐름은 다음과 같은 구조를 따릅니다: 소스 코드 → 토큰 → AST → 타입이 지정된 AST → 준비된 AST → LLVM IR.

렉서와 파서: 모호성 처리하기

렉서와 파서는 외부 프로젝트의 LR(1) 파서를 기반으로 조정했습니다. 제네릭에서 문제가 발생했습니다: var a = Test < b > c;와 같은 표현식은 템플릿 매개변수와 비교 연산자를 구분하기 위해 하나 이상의 토큰을 미리 살펴봐야 합니다. 표준 LR(1)은 컨텍스트 없이는 이를 처리할 수 없습니다.

더 복잡한 경우는 var a = Test < b > (c);입니다. 이러한 모호성은 타입 추론 단계로 미뤄집니다. 파서는 토큰이 예상 형식과 일치하지 않을 경우 오류 처리를 포함한 AST 노드를 생성합니다.

타입 추론: 다중 패스 AST 순회

타입 추론은 서로 다른 파일에 걸친 선언 간 의존성 때문에 AST를 여러 번 순회해야 합니다. 순서는 다음과 같습니다:

• 최상위 타입 선언 처리 (네임스페이스 범위에 기록).
• 제네릭 매개변수와 제약 조건 파싱.
• 상속 처리.
• 대리자, 중첩 타입, 함수.
• 필드, 속성, 초기화자.
• 특성.
• 그런 다음에야 함수 본문.

제네릭이 주요 어려움을 일으켰습니다. 재귀 생성의 예:

public class Test<T> 
{ 
    public static Test<E> GetTest<E>(); 
}

컴파일러는 무한한 Test<E>를 생성하며 루프에 빠졌습니다. 제약 조건으로 해결했습니다: 클래스 제네릭 매개변수를 가진 정적 필드/속성은 금지됩니다 (public static T CoolField;는 허용되지 않음). 이렇게 하면 링크 시 충돌을 방지할 수 있습니다.

서로 다른 타입에 대한 연산과 가상/추상 메서드는 추가적인 개선이 필요했습니다.

코드 생성을 위한 타입 준비

추가 단계에서 AST를 변환하여 IR 생성을 더 쉽게 만듭니다:

• 람다와 클로저: 컨텍스트를 캡처하기 위해 합성 클래스가 생성됩니다. 예시:

public class Test
{
    public Action ReturnFunction(int a, int b)
    {
        var action = () => 
        { 
            Console.WriteLine($"Result: {a + b}"); 
        };
        return action;
    }
}

다음과 같이 변환됩니다:

public class __SyntheticClass0
{
    public int a;
    public int b;
    public void Lambda0()
    {
        Console.WriteLine($"Result: {a + b}"); 
    }
}

public class Test
{
    public Action ReturnFunction(int a, int b)
    {
        __SyntheticClass0 tmpVar = new __SyntheticClass0();
        tmpVar.a = a;
        tmpVar.b = b;
        return tmpVar.Lambda0;
    }
}

• 속성에 대한 get/set 생성.
• 속성 접근을 호출로 대체.
• 데드 코드 제거 (라이브러리 제외).
• 정적 생성자.
• 클래스를 포인터로 변환.
• 가상 테이블(vtables) 추가.

LLVM IR로의 코드 생성

LLVM IR 생성은 준비 단계로 인해 단순화됩니다: 플랫폼별 세부 사항(setjmp, va_list)은 일찍 해결됩니다. 주요 문제는 링크와 제네릭입니다.

정적 제네릭 필드를 금지하는 것은 라이브러리 의존성으로 정당화됩니다. A → B(int), A → C(int) → App 구조에서 각 라이브러리는 자체 SomeType<int>를 생성합니다. B의 변경 사항은 C와 동기화되지 않으며, 링커는 어떤 것을 선택해야 할지 모릅니다.

기타 세부 사항: x86 Windows에서 전역 이름의 밑줄 (LLVM 링커로 해결), vtables. AST 준비 후에는 LLVM IR 구문을 빠르게 익힐 수 있습니다.

핵심 요약

• 제네릭은 신중한 설계가 필요합니다: 파서의 lookahead, 다중 패스 타입 추론, 정적 요소에 대한 제약 조건.
• IR 이전의 준비 단계는 포인터, 람다, 데드 코드에 중요합니다.
• LLVM은 크로스 플랫폼 개발을 단순화하지만 링크 충돌을 완전히 제거하지는 않습니다.
• 단계의 병렬 개발은 재작업으로 이어집니다. 언어의 간단한 하위 집합으로 시작하는 것이 더 좋습니다.
• 클로저를 위한 합성 클래스는 클로저에 대한 깊은 지식 없이도 의미를 보존합니다.

— Editorial Team