# 0. 요약
| 항목 | 내용 |
| -------------- | --------------------------------------- |
| **컴파일러 정의** | 언어를 언어로 변환하는 소프트웨어 |
| **현대 컴파일러 구조** | 3단계 (Front-End / Middle-End / Back-End) |
| **Front-End** | 입력 언어를 다룸 |
| **Middle-End** | 중간 언어(IR)를 다룸 |
| **Back-End** | 출력 언어를 다룸 |
| 구분 | Front-End | Middle-End | Back-End |
| ---------- | --------- | ---------- | --------- |
| **의존성** | 입력 언어에 의존 | 둘 다에 독립적 | 출력 언어에 의존 |
| **주요 작업** | 이해 | 개선 | 변환 |
| **이론적 배경** | 오토마타 이론 | 프로그래밍 언어론 | 알고리즘 |
```mermaid
flowchart TB
SRC([Source Program])
TGT([Target Program])
SRC --> Lexer
subgraph Compiler
subgraph Front-End
Lexer --> TOK([Tokens]) --> Parser --> AST1([AST]) --> SA["Semantic<br/>Analyzer"] --> AST2([AST]) --> IRT["IR<br/>Translator"]
end
IRT --> IR1([IR Program])
subgraph Middle-End
IR1 --> OPT1["Optimizer #1"] --> IR2([IR Program]) --> DOT["..."] --> IR3([IR Program]) --> OPTN["Optimizer #N"]
end
OPTN --> IR4([IR Program])
subgraph Back-End
IR4 --> SEL[Selector] --> P1(["Pseudo Target"]) --> SCH[Scheduler] --> P2(["Pseudo Target"]) --> ALLOC[Allocator]
end
end
ALLOC --> TGT
style SRC fill:#6366f1,color:#fff,stroke:#4f46e5
style TGT fill:#6366f1,color:#fff,stroke:#4f46e5
style TOK fill:#f59e0b,color:#fff,stroke:#d97706
style AST1 fill:#f59e0b,color:#fff,stroke:#d97706
style AST2 fill:#f59e0b,color:#fff,stroke:#d97706
style IR1 fill:#f59e0b,color:#fff,stroke:#d97706
style IR2 fill:#f59e0b,color:#fff,stroke:#d97706
style IR3 fill:#f59e0b,color:#fff,stroke:#d97706
style IR4 fill:#f59e0b,color:#fff,stroke:#d97706
style P1 fill:#f59e0b,color:#fff,stroke:#d97706
style P2 fill:#f59e0b,color:#fff,stroke:#d97706
style Lexer fill:#10b981,color:#fff,stroke:#059669
style Parser fill:#10b981,color:#fff,stroke:#059669
style SA fill:#10b981,color:#fff,stroke:#059669
style IRT fill:#10b981,color:#fff,stroke:#059669
style OPT1 fill:#3b82f6,color:#fff,stroke:#2563eb
style OPTN fill:#3b82f6,color:#fff,stroke:#2563eb
style DOT fill:#3b82f6,color:#fff,stroke:#2563eb
style SEL fill:#ec4899,color:#fff,stroke:#db2777
style SCH fill:#ec4899,color:#fff,stroke:#db2777
style ALLOC fill:#ec4899,color:#fff,stroke:#db2777
```
---
# 1. 컴파일러가 필요한 이유
## 1.1 소스코드 vs. 기계어
| 구분 | 소스코드 (Source Code) | 기계어 (Machine Code) |
| ---------- | ---------------------- | --------------------- |
| **사용 주체** | 사람 (Human) | 컴퓨터 (Computer) |
| **언어 수준** | 고수준 언어 (High-level PL) | 저수준 언어 (Low-level) |
| **예시** | F#, C, Java, Python, … | Intel, ARM, RISC-V, … |
| **최적화 목표** | 인간 가독성 최적화 | 하드웨어 최적화 |
| **표현력** | 표현력(Expressiveness) 풍부 | 중복/모호성 제거 |
| **의도 전달** | 의도 명확 | 의도 정보 손실 |
→ 이 간극을 자동 번역으로 메워야 함
## 1.2 자동 번역과 관련한 역사적 배경
| 연도 | 사건 | 주요 특징 |
|------|------|----------|
| **~1950년대 초** | 어셈블리 코딩 | 손으로 직접 프로그래밍, SW 비용 > HW 비용 |
| **1953년** | Speedcoding | 초창기 High-level PL, Hand-written assembly보다 10-20배 느림 |
| **1954년** | FORTRAN I (IBM, John Backus) | High-level PL → Assembly 변환 시도, 1958년까지 전체 SW의 50% 이상 점유, 개발 시간 절반 단축, 성능은 Hand-written assembly에 근접, **최초의 컴파일러**
> **💡 컴파일러는 자동 번역 아이디어의 실현**.
> → 그렇다면, 컴파일러는 무엇일까?
# 2. 컴파일러의 정의 (c.f. 인터프리터)
## 2.1 컴파일러와 인터프리터
| 구분 | 컴파일러 (Compiler) | 인터프리터 (Interpreter) |
| ---------- | -------------------------------------- | ------------------------------------------- |
| **정의** | 한 언어로 작성된 프로그램을 다른 언어로 **번역**하는 프로그램 | 프로그램을 **직접 실행**하여 결과를 출력하는 프로그램 |
| **처리 방식** | Source Program → (번역) → Target Program | Source Program → (즉시 실행) → Execution Result |
| **출력** | 실행 가능한 Target Program (기계어) | 실행 결과 (Execution Result) |
| **일반적 변환** | High-level PL → Low-level machine code | 변환 없이 소스를 직접 해석·실행 |
| **실행 속도** | 빠름 (미리 번역된 코드 실행) | 느림 (컴파일된 코드보다 느림) |
| **관련 개념** | Transpiler (언어 → 언어 변환) | REPL (Read-Eval-Print Loop) |
### 2.1.1 예제: Java
| 단계 | 입력 | 처리 | 출력 |
| ------- | ---------- | ----------------------- | ---------- |
| **1단계** | Java 소스코드 | Java Compiler (컴파일러) | Java 바이트코드 |
| **2단계** | Java 바이트코드 | JVM (인터프리터 or JIT 컴파일러) | 실행 결과 |
> 참고: AOT 컴파일러(실행 전 전체 번역) vs JIT 컴파일러(실행 중 동적 번역)
```mermaid
flowchart LR
A([Java Src Code])
--> B[Java Compiler]
--> C([Java Bytecode])
--> D[JVM = 인터프리터 or JIT Compiler]
--> E([Execution Result])
style A fill:#e74c3c,color:#fff
style C fill:#e74c3c,color:#fff
style E fill:#e74c3c,color:#fff
style B fill:#1a5c3a,color:#fff
style D fill:#1a5c3a,color:#fff
```
# 3. 컴파일러의 기본 원칙
## 3.1 정확성과 개선
| 목표 | 정의 | 중요도 |
| --------------------- | -------------------------------------- | --------------------- |
| **정확성 (Correctness)** | 컴파일된 프로그램은 원래 프로그램과 동일한 의미를 가져야 한다 | ⭐⭐⭐ 최우선 — 성능보다 훨씬 중요 |
| **개선 (Improvement)** | 컴파일러는 입력 프로그램을 어떤 기준에 대해서 더 나아지게 해야 한다 | ⭐⭐ 중요 — 단, 정확성이 보장된 후 |
### 3.1.1 예제: 올바른 최적화 코드
```c
// ❌ Before: 매 반복마다 sin(factor) / 2.0 을 중복 계산
void mul_elems(double *arr, int n, double factor) {
for (int i = 0; i < n; i++) {
arr[i] = arr[i] * (sin(factor) / 2.0); // 루프 불변 연산이 매번 실행됨
}
}
// ✅ After: 루프 불변 코드 외부로 추출 (Loop-Invariant Code Motion)
void mul_elems(double *arr, int n, double factor) {
double same_value = (sin(factor) / 2.0); // 한 번만 계산
for (int i = 0; i < n; i++) {
arr[i] = arr[i] * same_value; // 단순 곱셈만 수행
}
}
```
### 3.1.2 예제: 위험한 최적화 코드
```c
// ❌ Before: 컴파일러가 stop_flag를 루프 불변으로 판단 → 최적화 시도
int stop_flag = 0;
void wait_for_hardware() {
while (stop_flag == 0) { // 컴파일러: "stop_flag가 바뀔 일 없다" → while(true)로 최적화
;
}
printf("Hardware signal received!\n"); // 영원히 도달 불가
}
// ⚠️ After: 컴파일러가 최적화한 결과 → 의도치 않게 무한루프로 변질
int stop_flag = 0;
void wait_for_hardware() {
while (true) { // 💥 stop_flag 체크가 사라짐 — 탈출 불가
;
}
printf("Hardware signal received!\n"); // 도달 불가 (dead code)
}
```
# 4. 컴파일러의 구조
## 4.1 가장 단순한 구조
```mermaid
flowchart LR
A([Source Program]) --> B[Compiler] --> C([Target Program])
style A fill:#e74c3c,color:#fff
style C fill:#e74c3c,color:#fff
style B fill:#1a5c3a,color:#fff
```
| 정의 | 장점 |
| -------------------------- | ------------------- |
| 모든 변환 과정을 하나의 구성 요소 안에서 처리 | 보다 빠르게 작동하는 컴파일러 구현 |
## 4.2 기본적 2단계 구조
```mermaid
flowchart LR
A([Source Program]) --> FE
IR([IR Program])
BE --> C([Target Program])
subgraph Compiler
FE[Front-End] --> IR --> BE[Back-End]
end
style A fill:#e74c3c,color:#fff
style C fill:#e74c3c,color:#fff
style IR fill:#e74c3c,color:#fff
style FE fill:#1a5c3a,color:#fff
style BE fill:#1a5c3a,color:#fff
```
| 구분 | 내용 |
|------|------|
| **구조 유형** | 전통적인 2단계 구조 (Front-End / Back-End) |
| **Front-End 역할** | 입력 언어를 이해하고 중간 언어(IR)로 변환 / 입력 언어만 담당 |
| **Back-End 역할** | IR을 출력 기계어로 변환 / 출력 언어만 담당 |
| **장점** | 언어에 따른 모듈 분리 → 관심사 분리(Separation of Concerns) |
| **확장성** | 입력 언어 n개 + 출력 아키텍처 m개 지원 시 **n+m개** 모듈만 구현 |
| **비교 (단순 구조)** | 분리 없이 구현 시 **n×m개** 모듈 필요 → 2단계 구조가 훨씬 효율적 |
## 4.3 새로운 3단계 구조
```mermaid
flowchart LR
A([Source Program]) --> FE
IR1([IR Program])
IR2([IR Program])
BE --> C([Target Program])
subgraph Compiler
FE[Front-End] --> IR1 --> ME[Middle-End] --> IR2 --> BE[Back-End]
end
style A fill:#e74c3c,color:#fff
style C fill:#e74c3c,color:#fff
style IR1 fill:#e74c3c,color:#fff
style IR2 fill:#e74c3c,color:#fff
style FE fill:#1a5c3a,color:#fff
style ME fill:#1a5c3a,color:#fff
style BE fill:#1a5c3a,color:#fff
```
> **2단계 구조에 Middle-End 추가.** 번역뿐만 아니라 '성능'도 중요해짐.
> 💡 Middle-End는 IR 분석 및 최적화.
## 4.4 3단계 구조 예시: 영→한 번역
> 🎯 목표: `"I bought bread because I was upset."` → `"우울해서 빵 샀어."`
### 4.4.1 Front-End: 영어의 이해
```mermaid
graph TD
STA["STA<br/>cl"]
S["S<br/>pron"]
P["P<br/>v"]
Od["Od<br/>n"]
A["A<br/>cl"]
DOT["."]
I["I"]
bought["bought"]
bread["bread"]
SUB["SUB<br/>conj"]
S2["S<br/>pron"]
P2["P<br/>v"]
Cs["Cs<br/>adj"]
because["because"]
I2["I"]
was["was"]
upset["upset"]
STA --> S --> I
STA --> P --> bought
STA --> Od --> bread
STA --> A
STA --> DOT
A --> SUB --> because
A --> S2 --> I2
A --> P2 --> was
A --> Cs --> upset
```
### 4.4.2 Middle-End: 내용 분석
```
원인절: A가 X하다
A = I (나)
X = upset (우울하다)
결과절: A가 Y를 Z하다
A = I (나) → 한국어 특화: 주어 생략 가능
Y = bread (빵)
Z = buy (사다)
한국어 최적화:
- 원인 → 결과 순서가 한국어에서 더 자연스러움
- 주어(나) 생략 적용
```
### 4.4.3 Back-End: 한글로 변환
```
# 변환 규칙 적용
기본 변환:
"X해서 Y를 Z해."
→ "우울해서 빵을 샀어."
추가 최적화 (목적격 조사 생략):
→ "우울해서 빵 샀어." ✅ 최종 출력
```
# 5. 3단계 구조 — Front-End
## 5.1 정의
"입력 언어를 이해하는 과정"
- 이해
- 검사
- 변환
## 5.2 Lexer: Source → Tokens [어휘 분석기]
| 항목 | 내용 |
| ---------- | ----------------------------------------- |
| **역할** | 문자열을 토큰(Token)의 나열로 변환 |
| **처리** | 공백, 주석 제거 |
| **이론적 기반** | 오토마타 이론 |
| **입력** | `if (b == 0) a = b;` |
| **출력** | `if` `(` `b` `==` `0` `)` `a` `=` `b` `;` |
## 5.3 Parser: Tokens → AST(Abstract Syntax Tree) [구문 분석기]
```mermaid
graph TD
if --> EQ["=="] & EQ2["="] & SC[";"]
EQ --> b1[b] & zero[0]
EQ2 --> a & b2[b]
```
| 항목 | 내용 |
| ---------- | ------------------------------------------------------------------------- |
| **역할** | Token의 나열을 AST(Abstract Syntax Tree)로 변환 |
| **이유** | C라는 언어의 특징을 아직 토큰들이 많이 갖고 있음.<br>언어에 특화된 형태를 줄여야 함. <br>좀 더 추상적 형태로 변환해줌. |
| **이론적 기반** | 오토마타 이론 |
| **입력** | Token 나열 |
| **출력** | AST (구문 트리) |
## 5.4 Semantic Analyzer: AST → AST [의미 분석기]
```mermaid
graph TD
if --> EQ["== : boolean"] & EQ2["="] & SC[";"]
EQ --> b1["b : int"] & zero["0 : int"]
EQ2 --> a["a : int"] & b2["b : int"]
```
| 항목 | 내용 |
| ---------- | ------------------------ |
| **역할** | AST가 올바른 의미를 표현하고 있는지 검사 |
| **이유** | int a = "김겨레" 이런 거 막아야 함 |
| **처리** | 타입 분석, 변수 선언 검사 |
| **이론적 기반** | 프로그래밍 언어론 |
| **입력** | AST |
| **출력** | 타입 정보가 추가된 AST |
# 6. 3단계 구조 — Middle-End
## 6.1 정의
ㄴ
"IR을 변환하는 과정"
- 분석
- 최적화
- 이론적 기반: 프로그래밍 언어론
## 6.2 Middle-End 구조
```mermaid
flowchart LR
A([IR Program]) --> OPT1
subgraph Middle-End
OPT1["Optimizer #1"] --> IR1([IR Program]) --> DOT["..."] --> IR2([IR Program]) --> OPTN["Optimizer #N"]
end
OPTN --> B([IR Program])
style A fill:#e74c3c,color:#fff
style B fill:#e74c3c,color:#fff
style IR1 fill:#e74c3c,color:#fff
style IR2 fill:#e74c3c,color:#fff
style OPT1 fill:#2e86ab,color:#fff
style OPTN fill:#2e86ab,color:#fff
```
## 6.3 IR 예시: AST → IR 변환
```mermaid
graph TD
if --> EQ["== : boolean"] & EQ2["="] & SC[";"]
EQ --> b1["b : int"] & zero["0 : int"]
EQ2 --> a["a : int"] & b2["b : int"]
```
```
# AST → IR 변환 결과
if b == 0 goto L1 else L2
L1: a = b
L2:
```
## 6.4 IR 최적화 예시: Constant Propagation (상수 전파)
```
# Before: b == 0이 참인 경우 a = b → a = 0으로 상수 전파 가능
if b == 0 goto L1 else L2
L1: a = b ← L1 진입 시 b == 0 이므로
L2:
# After: 상수 전파(Constant Propagation) 적용
if b == 0 goto L1 else L2
L1: a = 0 ✅ 최적화 완료
L2:
```
# 7. 3단계 구조 — Back-End
## 7.1 정의
"출력 언어를 생성하는 과정"
- IR을 기반으로 출력 언어(CPU 아키텍처)에 맞는 코드 생성
- 이론적 기반: 알고리즘
## 7.2 Back-End 구조
```mermaid
flowchart LR
A([IR Program]) --> SEL
subgraph Back-End
SEL[Selector] --> P1(["Pseudo<br/>Target Program"]) --> SCH[Scheduler] --> P2(["Pseudo<br/>Target Program"]) --> ALLOC[Allocator]
end
ALLOC --> B([Target Program])
style A fill:#e74c3c,color:#fff
style B fill:#e74c3c,color:#fff
style P1 fill:#e74c3c,color:#fff
style P2 fill:#e74c3c,color:#fff
style SEL fill:#2e86ab,color:#fff
style SCH fill:#2e86ab,color:#fff
style ALLOC fill:#2e86ab,color:#fff
```
## 7.3 명령어 선택기 (Instruction Selector)
|항목|내용|
|---|---|
|**역할**|IR 코드를 타겟 머신의 명령어로 변환|
|**특징**|레지스터는 아직 정해지지 않음 (가상 레지스터 사용)|
|**이론적 기반**|알고리즘|
```
# Before (IR)
if b == 0 goto L1 else L2
L1: a = b
L2:
# After (가상 레지스터 사용)
cmp r_b, 0
jnz L2
L1: mov r_a, r_b
L2:
```
## 7.4 레지스터 할당기 (Register Allocator)
|항목|내용|
|---|---|
|**역할**|타겟 명령어의 가상 레지스터에 물리 레지스터를 할당|
|**이론적 기반**|알고리즘|
```asm
; Before: 가상 레지스터
cmp r_b, 0
jnz L2
L1: mov r_a, r_b
L2:
; After: 물리 레지스터 할당
cmp eax, 0
jnz L2
L1: mov [ebp+8], ecx
L2:
```
## 7.5 정리: 컴파일러 3단계 구조 비교
|구분|Front-End|Middle-End|Back-End|
|---|---|---|---|
|**의존성**|입력 언어에 의존|둘 다에 독립적|출력 언어에 의존|
|**주요 작업**|이해|개선|변환|
|**이론적 배경**|오토마타 이론|프로그래밍 언어론|알고리즘|
```mermaid
flowchart LR
A([Source Program]) --> FE
IR1([IR Program])
IR2([IR Program])
BE --> C([Target Program])
subgraph Compiler
FE[Front-End] --> IR1 --> ME[Middle-End] --> IR2 --> BE[Back-End]
end
style A fill:#e74c3c,color:#fff
style C fill:#e74c3c,color:#fff
style IR1 fill:#e74c3c,color:#fff
style IR2 fill:#e74c3c,color:#fff
style FE fill:#1a5c3a,color:#fff
style ME fill:#1a5c3a,color:#fff
style BE fill:#1a5c3a,color:#fff
```
# 8. 컴파일러를 공부하는 이유
## 8.1 컴파일러는 모든 이론의 집합체
|분야|관련 컴파일러 구성 요소|
|---|---|
|**이론**|오토마타 이론 (Lexer, Parser), 프로그래밍 언어론 (Semantic Analyzer, Middle-End)|
|**시스템**|OS, 메모리 관리, 링커|
|**아키텍처**|CPU 명령어 집합 (ISA), 레지스터 할당|
|**공학**|최적화 알고리즘, 코드 생성|
## 8.2 컴파일러는 많은 곳에 사용됩니다
|분야|예시|
|---|---|
|**웹 서버**|V8 (JavaScript), JIT 컴파일|
|**데이터베이스**|SQL 쿼리 컴파일러, 실행 계획 최적화|
|**머신러닝 컴파일러**|XLA (Google), TVM (Apache)|
## 8.3 컴파일러를 알면 좋은 코드를 작성할 수 있다
```c
// 컴파일러 동작을 모르면 쓸 수 있는 코드
void mul_elems(double *arr, int n, double factor) {
for (int i = 0; i < n; i++) {
arr[i] = arr[i] * (sin(factor) / 2.0); // 루프마다 중복 계산
}
}
// 컴파일러를 알면 직접 최적화하거나, 컴파일러가 최적화할 수 있도록 코드를 유도
void mul_elems(double *arr, int n, double factor) {
double same_value = (sin(factor) / 2.0); // Loop-Invariant Code Motion
for (int i = 0; i < n; i++) {
arr[i] = arr[i] * same_value;
}
}
```