[CS] Swift로 AST 구현하기(with SIL)

안녕하세요, 루피입니다.

 

오늘은 AST에 대해 학습하고 Swift로 구현해본 내용을 정리하려합니다. 바로 시작합니다.

---

1. 컴파일러란?

본격적으로 시작하기에 앞서 컴파일러가 무엇인지에 대해 아주 간략하게 짚고 가겠습니다. 우리가 개발에 사용하는 Swift, C++, JS 같은 언어들은 고급 언어라고 부릅니다. 하지만 사실 컴퓨터는 이 언어들을 전혀 이해하지 못한다는 사실을 아시나요??

컴퓨터는 오직 0과 1로 이루어진 기계어만 알아들을 수 있기 때문입니다.

바로 여기서 컴파일러가 등장하게 되는 겁니다. 컴파일러는 우리가 작성한 코드를 컴퓨터가 이해할 수 있는 기계어를 번역해주는 역할을 하게됩니다.

 

즉, Swift로 프로그램을 짜고, 프로그램을 컴파일러가 컴파일 해서 컴퓨터가 이해할 수 있게 만들어주는 것이죠!!

---

2. 컴파일러가 기계어로 만드는 과정

컴파일러는 소스 코드를 기계어로 변환하기 위해 여러 전통적인 단계를 거칩니다. 이는 크게 렉싱(Lexing), 파싱(Parsing), 의미 분석(Semantic Analysis), 그리고 로워링(Lowering) 단계로 나눌 수 있습니다.

1) 렉싱

렉싱 단계는 쉽게 말하자면 코드를 잘게 쪼개는 단계입니다.

 

프로그램의 텍스트를 입력받아 " 토큰이라는 의미 있는 단위"로 변환하는 역할을 합니다. 이 단계에서 공백, 주석, 유니코드 등 모든 텍스트 관련 요소가 처리됩니다. 이 과정을 거치게되면 코드는 키워드 (var), 식별자 (a), 연산자(=), 구두점(;) 같은 추상화된 토큰의 연속으로 변환됩니다.

2) 파싱

파싱 단계는 쉽게 말하자면, AST 구조로 만드는 단계입니다.

 

렉서가 만든 토큰들을 입력받아, 프로그램의 구조를 나타내는 AST로 변환합니다. 이때, 토큰 간의 중첩, 구조, 관계 등을 처리하면서 어떤 관계와 구조를 가지는지 파악하여 뼈대를 세우는 것이죠.

 

😎 AST(추상 구문 트리)란?

AST는 소스 코드의 구조를 트리 형태로 추상화한 자료구조입니다.

각 노드는 코드의 구문을 의미하며, 트리의 구조를 통해 코드의 계층 관계를 표현합니다. 추상이라는 말은 코드의 모든 세부 사항을 담지 않고, 의미상 중요한 정보만 남긴다는 뜻입니다. 컴파일러는 이 AST를 통해 코드의 구조를 이해하고 분석합니다.

let a = 5
print(a)

위 코드를 AST로 바꾸면, let a = 5는 '변수 선언 노드'로, print(a)는 '함수 호출 노드'로 트리 구조에 들어가게 되는 것이죠.

3) 의미 분석

의미 분석단계는 구조가 만들어진 AST에 의미를 부여하는 단계입니다.

 

이 단계는 이름 확인, 타입 검사, 입력 프로그램 유효성 검사, 그리고 프로그램의 의미를 나타내기 위한 AST 변환 및 확장을 담당합니다.

4) 로워링

로워링 단계는 의미 분석까지 마친 AST를 입력받아, 점점 더 낮은 수준의 표현으로 변환하여 기계어를 생성합니다.

 

이 단계에서는 프로그램의 원래 의도보다는 실제 실행에만 관심이 있으므로, 이전, 단계보다 더 많은 정보를 버릴 수 있습니다.

---

3. SIL (Swift Intermediate Language)

그렇다면 우리가 매일 사용하는 Swift 컴파일러는 어떤 특별한 점이 있을까요? 바로 의미 분석과 로워링 사이에서 SIL이라는 중간 언어(IR)를 사용한다는 것입니다. Clang 같은 다른 컴파일러는 소스 코드와 LLVM IR 사이의 추상화 격차가 커서 의미 분석에 어려움을 겪기도 했지만, Swift는 SIL을 통해 이 간극을 효과적으로 메웁니다.

 

즉, 파싱으로 만들어진 AST를 바로 LLVM IR로 만드는 것이 아니라 중간에 SIL이라는 IR 을 활용함으로써

고수준의 의미를 보존,최적화,진단 할 수 있게 만듭니다.

1) 초기 SIL

이 단계에서는 주로 코드의 안전성을 보장하고, 명백한 오류를 잡아내는 최적화가 이루어집니다.

• 데이터의 흐름을 분석하여 변수가 사용되기 전에 확실히 초기화 되었는지 확인하고 그렇지 않다면 컴파일 오류를 발생시킵니다.
• 1 + 2 처럼 컴파일 타임에 계산 가능한 값은 미리 계산해버립니다(상수 폴딩).
• 정수 오버플로가 발생하면 프로그램이 반드시 trap되는 것을 보장하는데, SIL은 내장 함수를 통해 오버플로 가능성을 미리 진단하고 정확한 오류 메시지를 생성합니다.
• 클로저가 변수를 캡처할 때, 원래는 힙에 할당해야 하지만, SIL 단계에서 분석을 통해 가능하다면 더 빠른 스택에 할당하도록 최적화합니다.

2) 후기 SIL

이 단계에서는 본격적인 성능 최적화가 이루어지며, 특히 Swift의 강력한 기능인 제네릭을 처리하는 데 핵심적인 역할을 합니다.

• 고수준의 타입 시스템을 유지하고 있기 때문에, <T>와 같이 추상적으로 작성된 제네릭 코드를 String, Int 등 구체적인 타입에 맞춰 최적화된 코드로 각각 생성해낼 수 있습니다.
• 모든 최적화가 끝난 SIL은 최종적으로 LLVM IR로 변환되고, 이를 통해 실행 가능한 바이너리 파일이 생성됩니다.

---

4. 구현 과정

AST의 각 노드를 프로토콜과 구조체를 사용하여 표현했습니다. 전체 소스 파일부터 가장 작은 표현식 단위까지 계층적으로 설계했습니다.

// var luffy = Luffy.init()
struct SourceFile {
    let codeBlockItems: [CodeBlockItem]
}

struct CodeBlockItem {
    let item: ASTNode
}

protocol ASTNode { }

• 코드 블록 내의 하나의 선언 또는 구문을 나타내는 CodeBlockItem이 있습니다.
  • 이 때 코드 블록 내의 모든 아이템은 ASTNode 형태입니다.
  • AST 노드는 하위 모든 코드들이 AST를 준수해야하기 때문에 프로토콜로 선언합니다.
• 프로젝트는 여러개의 코드 블록으로 이루어져 있기에 이를 리스트로 담습니다.
• 전체 코드블록을 SourceFile이 가지고 있습니다. 즉, 루트 노드입니다.

struct VariableDecl: ASTNode {
    let modifiers: [String]           // AttributeList, DeclModifierList 등
    let patternBindings: [PatternBinding]
}

// 패턴 바인딩 (var luffy = ...)
struct PatternBinding {
    let pattern: Pattern
    let initializer: InitializerClause?
}

// 패턴 (여기서는 IdentifierPattern만 사용)
protocol Pattern { }
struct IdentifierPattern: Pattern {
    let identifier: String
}

• var 는 변수를 선언하는 구문이기에 variableDeclSyntax를 따릅니다.
• VariableDeclSyntax는 하위에 Attribute, modifiers,bindings를 자식으로 가지고 있습니다. 여기서는 Attribute는 필요하지 않기에 modifiers, bindings만 구현하겠습니다.
• pattern binding은 변수 선언의 각 패턴과 초기화 구문을 묶어 표현합니다. 여러 변수 선언이 한 줄에 있을 수 있기에 리스트로 설계합니다.
• 패턴에서는 변수명 등 다양한 패턴을 표현할 수 있습니다. 여기서는 IdentifierPattern만 사용합니다. (”luffy”)

// 초기화 구문 (= ...)
struct InitializerClause {
    let value: Expr
}

// 모든 표현식의 기반 프로토콜
protocol Expr: ASTNode { }

// 함수 호출 표현식 (Luffy.init())
struct FunctionCallExpr: Expr {
    let calledExpression: Expr      // MemberAccessExpr
    let arguments: [LabeledExpr]    // LabeledExprList
}

// 멤버 접근 표현식 (Luffy.init)
struct MemberAccessExpr: Expr {
    let base: Expr                  // DeclReferenceExpr (Luffy)
    let member: DeclReferenceExpr   // DeclReferenceExpr (init)
}

// 선언 참조 표현식 (Luffy, init)
struct DeclReferenceExpr: Expr {
    let name: String
}

• 초기화 구문은 표현식으로 설계합니다.
• 모든 표현식의 기반 프로토콜을 만듭니다. 그리고 표현식은 이를 준수합니다.
• Luffy.init()을 단계적으로 해석
  • () : 함수를 호출합니다.
  • Luffy.init() : Luffy의 멤버 함수에 접근합니다.
  • Luffy, init : 선언

AST 시각화

SourceFile
└── CodeBlockItem
    └── VariableDecl (modifiers: ["var"])
        └── PatternBinding
            ├── Pattern: IdentifierPattern (identifier: "luffy")
            └── Initializer: InitializerClause
                └── Value: FunctionCallExpr
                    ├── CalledExpression: DeclReferenceExpr (name: "Luffy")
                    └── Arguments: []

---

5. 전체 코드

let ast = SourceFile(codeBlockItems: [
    CodeBlockItem(item:
        VariableDecl(
            modifiers: ["var"],
            patternBindings: [
                PatternBinding(
                    pattern: IdentifierPattern(identifier: "luffy"),
                    initializer: InitializerClause(
                        value: FunctionCallExpr(
                            calledExpression: MemberAccessExpr(
                                base: DeclReferenceExpr(name: "Luffy"),
                                member: DeclReferenceExpr(name: "init")
                            ),
                            arguments: [] // init() 호출에 인자가 없으므로 비어있음
                        )
                    )
                )
            ]
        )
    )
])

---

오늘도 화이팅입니다!

https://ko.wikipedia.org/wiki/추상_구문_트리

추상 구문 트리 - 위키백과, 우리 모두의 백과사전

https://www.youtube.com/watch?v=ZI198eFghJk

 

https://swift-ast-explorer.com/

Swift AST Explorer