Theoretical Compilation Phases (이론적 컴파일 단계)

Compilation Phases

#	단계	입력	출력	비고 (Remarks)
1	Lexical Analysis	문자 스트림	토큰 스트림	소스 코드를 문자 단위로 읽어 의미 있는 최소 단위인 토큰으로 분리. 정규표현식 기반으로 동작하며, 공백·주석은 이 단계에서 제거.
2	Syntax Analysis	토큰 스트림	Parse Tree (CST)	Context-Free Grammar(CFG) 규칙에 따라 토큰 시퀀스의 구조적 유효성을 검증. 문법 오류(Syntax Error)가 이 단계에서 탐지되며, 전체 문법 전개 구조를 Parse Tree로 표현. Parse Tree = Concrete Syntax Tree (CST)
3	AST Construction	Parse Tree (CST)	Abstract Syntax Tree	Parse Tree에서 괄호·세미콜론 등 의미 없는 문법 노드를 제거하여 간결한 AST를 생성. 이후 모든 분석 단계는 AST를 기반으로 수행.
4	Semantic Analysis	AST	Annotated AST	Type Checking, Scope Resolution, Symbol Table 구성을 수행. 의미적 오류(Semantic Error: 타입 불일치, 미선언 변수)가 이 단계에서 탐지.
5	IR Generation	Annotated AST	IR	플랫폼 독립적인 중간 표현(IR)으로 변환하여 이후 최적화와 코드 생성이 용이하도록 한다. Three-Address Code 또는 SSA(Static Single Assignment) 형식 등이 대표적으로 사용.
6	Optimization	IR	Optimzied IR	IR 수준에서 프로그램의 의미를 보존하면서 성능을 향상시키는 변환을 수행. Dead code elimination, Constant folding, Loop invariant motion, Function inlining 등이 대표적인 최적화 기법.
7	Code Generation	Optimized IR	기계어 / 어셈블리	최적화된 IR을 대상 아키텍처(x86, ARM 등)에 종속적인 기계어 또는 어셈블리 코드로 변환. Register Allocation과 Instruction Selection이 핵심 작업.

 

---

Overall flow summary:

$$\text{Source Code} \rightarrow \text{Tokens} \rightarrow \text{CST} \rightarrow \text{AST} \rightarrow \text{IR} \rightarrow \text{Optimized IR} \rightarrow \text{Machine Code}$$

---

Theory vs. Practice

구분	이론적 모델	실제 구현	비고 (Remarks)
Parse Tree	명확히 생성	대부분 생략	메모리 절약을 위해 parsing 즉시 AST로 변환
AST 생성	CST 이후 별도 생성	Parsing 중 직접 생성	Recursive descent parser에서 흔한 방식
Semantic 분석	별도 단계	AST 생성과 같이 수행됨	심볼 테이블을 AST 노드에 직접 부착
IR	단일 계층	다중 계층	LLVM: AST → LLVM IR → Machine IR → Target IR
최적화	단일 단계	다단계, 동적	JIT는 실행 중 핫 코드 감지 후 재컴파일
실행 모델	정적 컴파일 (AOT)	JIT / AOT 혼합	V8: Ignition(바이트코드) → TurboFan(최적화)

---

용어 설명

CST (Concrete Syntax Tree)

• 소스 코드의 문법 규칙을
• 괄호(parentheses)·세미콜론(semicolons) 등 모든 노드를 포함하여 있는 그대로 트리 구조로 표현한 것.
• Parse Tree라고도 불림.

AST (Abstract Syntax Tree)

• CST에서 의미 없는 문법 노드를 제거하고 프로그램의 의미 구조만을 추출한 트리.
• The semantically meaningful structure of the program

IR (Intermediate Representation)

• AST를 플랫폼 독립적인 선형 명령어 형태로 변환한 중간 표현으로,
• 최적화와 기계어 생성에 특화된 구조.

---

같이 보면 좋은 자료들

2024.01.18 - [CE] - [CE] Compilation 의 종류

[CE] Compilation 의 종류

2026.01.16 - [ML] - JAX (Just After eXecution)소개

JAX (Just After eXecution)소개