# 1. Language & Grammar
## 1.1 왜 언어와 문법에 대해 다루어야 하는가?
Lexer와 Parser는 모두 "언어/문법"에 대한 것이다.
- **Parser**: 당연히 문법에 대한 것
- **Lexer**: 작게 보면 토큰을 표현하는 문법에 대한 것
## 1.2 Language — 사전적 정의 → 우리가 다루는 건?
언어(言語)는 **문법**과 **어휘**로 이루어진 체계적인 커뮤니케이션 시스템이다.
## 1.3 Language — 형식적 정의 (특정 $G$를 만족하는 $\Sigma$ Sequence 집합)
혼동하지 말아야 할 것: **Instance와 Type의 구분**
| 비교 | Instance | Type |
| ----------------------------------- | ------------------------ | ----------------------------------------------- |
| C Code vs C Language | C Code (string 하나) | C Language (특정 규칙을 갖는 string들의 집합) |
| C Language vs Context-Free Language | C Language (Language 하나) | Context-Free Language (특정 규칙을 갖는 Language들의 집합) |
| 개념 | 설명 | 표기 |
| ------------ | -------------------------------------------------------------------------------------- | -------------------------------------- |
| **Alphabet** | 언어를 구성하는 글자들의 집합 | $\Sigma$ |
| **Grammar** | 언어를 이루고 있는 규칙들의 집합 | $G$ |
| **Language** | 특정 규칙(Grammar)을 만족하는 문자열의 집합<br>= Grammar를 만족하는 Alphabet Sequence 집합 | $L(G) = \{s \mid \exists(S \to^* s)\}$ |
| **Sentence** | Language의 Grammar를 따르는 Alphabet sequence<br>= Language의 Grammar를 따르는 Alphabet Sequence | $s \in L(G)$ |
> C 언어 = **Language**, C 코드 = **Sentence**
## 1.4 Language의 조건 — Grammar (문법)
### 1.4.1 구성 요소 — Production (문법 생성 규칙)
```
좌변 → 우변
```
- **좌변**: 항상 가상의 문자 = 변수 (Non-terminal)
- **우변**: 가상의 문자일 수도, 실제 문자($\Sigma$의 원소)일 수도
- $A \to \epsilon$ 도 허용
- 좌변의 문자가 나타나면, 우변의 것으로 대체할 수 있음
- 예: $A \to a$, $B \to bA$ 라는 규칙이 있다면 $B \to ba$ 로도 쓸 수 있음
### 1.4.2 구성 요소 — Terminal과 Non-terminal
| 구분 | 설명 | 예 |
| ---------------- | ------------------------------ | -------------- |
| **Terminal** | Production에 의해 더 이상 대체할 수 없는 것 | 문자, $\epsilon$ |
| **Non-terminal** | Production에 의해 더 대체할 수 있는 것 | 변수 |
Terminal과 Non-terminal은 Production을 조사함으로써 구성 가능하다.
> 예: $A \to a$, $B \to b$ → Terminal = $\{a, b\}$, Non-terminal = $\{A, B\}$
Production의 시작은 항상 특별한 **Non-terminal $S$ 로부터 시작**한다.
### 1.4.3 형식적 정의 — $(T, NT, S, P)$
문법은 **4-tuple $(T, NT, S, P)$** 로 정의된다.
- $T$: Terminal들의 집합 ($\Sigma \subset T$, $\epsilon \in T$)
- $NT$: Non-terminal들의 집합
- $S$: 시작 기호 ($S \in NT$)
- $P$: Production들의 집합
#### 1.4.3.1 기호 약속
- $a, b, c, \ldots \in T$
- $A, B, C, \ldots \in NT$
- $\alpha, \beta, \gamma, \ldots \in (T \cup NT)^+$
- $A \to \alpha \in P$
#### 1.4.3.2 예시: 이진수 문법 생성 규칙
$A =$ 모든 이진수, $B =$ 첫 번째 자리 제외한 이진수일 때,
$A \to 0, A \to 1B$
$B \to \epsilon, B \to 0B, B\to 1B$
$S \to A$
- $T = \{0, 1, \epsilon\}$
- $NT = \{A, B, S\}$
- $P = \{A \to 0,\ A \to 1B,\ B \to \epsilon,\ B \to 0B,\ B \to 1B,\ S \to A\}$
- $L(G) = \{\text{"}0\text{"}, \text{"}1\text{"}, \text{"}00\text{"}, \text{"}01\text{"}, \text{"}10, \ldots\}$
### 1.4.4 표현법 — BNF (Backus-Naur Form)
문법을 표현하기 위한 **Meta-syntax** (Syntax를 표현하기 위한 syntax)의 한 종류.
| 요소 | BNF 표기 |
| ------------ | --------------- |
| Terminal | `"..."` |
| Non-terminal | `<...>` |
| Production | `<...> ::= ...` |
#### 1.4.4.1 이 강의에서의 표기 약속
- **Terminal**: `""` 없이 **bold + underline**
- `[...]`: `...`에 해당하는 임의의 문자 1개
- 예: `[hexdigit]` = $a \in$ {"0", "1", ... "9", "a", ..., "f"}
- **Non-terminal**: <> 대신 기호 $S$, $E$, $T$, $F$ 등으로 표기
#### 1.4.4.2 예제: 덧셈 문법
```
S ::= E + S
| E
E ::= [number]
| ( S )
```
- **Production**: $S \to E + S$, $S \to E$, $E \to [\text{number}]$, $E \to (S)$
- **Terminal**: `+`, `(`, `)`, `[number]`
- **Non-terminal**: $S$, $E$
- **대상 문장 예**: $(1+2+(3+4))+5$
## 1.5 Language의 조건 — Derivation (문장의 유도)
> G를 '만족하는' 문장(알파벳 시퀀스)를 만든다 = 문장 s가 언어 L(G)의 문장이다
$S$로부터 Production을 따라서 문장을 만들어내는 과정.
1. 처음에 $S$로부터 시작
2. 한 단계마다, Non-terminal $A$를 선택하고, $A \to \alpha$에 대해 $A$를 $\alpha$로 대체
3. 오직 Terminal로만 이루어질 때까지 반복
$S \to \gamma_1 \to \gamma_2 \to \cdots \to \gamma_n \to s$
- $\gamma_i \in (T \cup NT)^+$
- $s \in T^+$
어떤 경로로든 $S$로부터 $s$까지 유도 과정이 존재하면 간단히 $S \to^* s$ 라고 쓴다.
```plain
// 예제: 덧셈 문법
// BNF
S ::= E + S
| E
E ::= [number]
| ( S )
// Derivation
(1+2+(3+4))+5
S → E + S → ( S ) + S → ( E + S ) + S
→ ( 1 + S ) + S
→ ( 1 + E + S ) + S
→ ( 1 + 2 + S ) + S
→ ( 1 + 2 + ( S ) ) + S
→ ( 1 + 2 + ( E + S ) ) + S
→ ( 1 + 2 + ( 3 + S ) ) + S
→ ( 1 + 2 + ( 3 + E ) ) + S
→ ( 1 + 2 + ( 3 + 4 ) ) + S
→ ( 1 + 2 + ( 3 + 4 ) ) + E
→ ( 1 + 2 + ( 3 + 4 ) ) + 5
```
> 이건 무슨 Language/Grammar로 정의될까?
> 이걸 설명하기 위해 §1.6 ~ §1.8 끼어듦
### 1.5.1 언어의 재정의
$L(G) = \{s \mid \exists(S \to^* s)\}$
- **"문장 $s$가 언어 $L(G)$의 문장이다"** = **"문법 $G$가 문장 $s$를 받아들인다(accept)"**
## 1.6 Language의 구분 — Context-Free와 Regular
### 1.6.1 촘스키 계층 (Chomsky Hierarchy)
컴파일러 강의에서 관심 있는 범위: **Regular**과 **Context-Free**.
```
recursively enumerable
└─ context-sensitive
└─ context-free ← 컴파일러 강의 관심사
└─ regular ← 컴파일러 강의 관심사
```
## 1.7 어떤 것을 Regular Language라고 하는가? → RL이 다루지 못하는 건 무엇으로 다룰까?
### 1.7.1 Regular Grammar의 정의
Regular Grammar $(T, NT, S, P)$는 다음 두 성질 중 하나를 만족:
**(1) Right-regular grammar (right-linear grammar)**
- $A \to \epsilon$
- $A \to a$
- $A \to aB$
- 우리는 이거 다룸
- 예시: 아까 본 이진수 문법 생성 규칙
**(2) Left-regular grammar (left-linear grammar)**
- $A \to \epsilon$
- $A \to a$
- $A \to Ba$
### 1.7.2 Right-Regular의 직관적 이해: Right-Regular ≈ FSM
Right-regular grammar의 유도를 보면:
$S \to aA \to abB \to abcC \to abcdD \to \cdots$
각각의 NT를 T를 입력 받은 하나의 **"상태"** 로 인식 가능 → **FSM과 동치**
### 1.7.3 Regular Grammar가 아닌 예시들
아래는 **Regular로 표현 불가** (기억 장치가 필요하기 때문):
| 예시 | 이유 |
| ------------------------- | ------------------------------ |
| 균형 잡힌 괄호 `(), (()), ()()` | 괄호가 열렸으면 닫아야 함 |
| 회문어 `aba, abba` | 앞에 나온 글자가 뒤에 반드시 짝 맞춰 나와야 함 |
| $a^nb^n$ | $a$가 $n$번 나왔으면 $b$가 $n$번 나와야 함 |
| $a^mb^n\ (m \ge n)$ | $a$의 개수가 $b$보다 같거나 많아야 함 |
> **Regular Language = 기억 장치 없이 만들 수 있는 문자열들의 집합**
#### 1.7.3.1 왜 $a^nb^n$은 Regular가 아닌가? (pumping lemma)
- 문법: `S ::= aSb | ε` → left-regular도, right-regular도 아님
- 만약 이 언어가 Regular라면 대응하는 FSM이 존재할 것
- FSM의 상태 수를 $k$개라 가정하면, $a^{2k}b^{2k}$를 읽을 때 $k+1$개의 $a$를 읽는 과정에서 **반드시 두 상태가 같아진다**(=반드시 어떤 상태는 두 번 지나감)
- 두 상태가 같다 = 상태 전이에 **loop**가 있다. 루프가 있으면 그 루프를 **몇 번을 돌아도 FSM 입장에선 똑같음.** 그러니까 루프 구간의 $a$를 더 추가해도 FSM은 accept.
- loop 길이 $l$만큼 $a$를 추가하면 $a^{2k+l}b^{2k}$도 accept되어야 하는데, 이는 $a^nb^n$의 언어가 아님 → **모순**
### 1.7.4 Right-Regular Grammar Type → Regular Language Type
어떤 문법이 Regular인지 아닌지
= 어떤 문법이 Regular 문법 Type인지 아닌지
= 어떤 언어가 Regular Language Type인지 아닌지
Right-Regular Grammar 조건 만족시키는 **문법** 집합 = Regular Grammar
Right-Regular Grammar 조건 만족시키는 **언어** 집합 = Regular Language
### 1.7.5 Regular Language의 한계
Regular Language는 '기억 장치 없이' 만들 수 있는 문자열들의 집합
> 🤔 기억 장치가 필요한 건 어떤 언어로 다루어야 할까?
## 1.8 어떤 것을 Context-Free Grammar라고 하는가?
Regular로 표현할 수 없는 언어들을 다루기 위한 더 넓은 Grammar 타입.
### 1.8.1 Context-Free Grammar의 정의
구조는 일반 Grammar 4-tuple $(T, NT, S, P)$와 동일하지만, **Production 형태에 제약이 없다**:
$A \to \alpha \quad (A \in NT,\ \alpha \in (T \cup NT)^*)$
좌변에 NT 하나만 오면 Context-Free.
> Context-Sensitive와의 차이: Context-Sensitive는 $\gamma_1 A \gamma_2 \to \gamma_1 \alpha \gamma_2$ 형태로, **주변 문맥(Context)에 따라** production이 달라짐
```plain text
// CF Grammar 예시: 균형 잡힌 괄호
S ::= ( S ) S | ε
// 괄호를 나란히 추가하는 예시
S → ( S ) S
→ ( ε ) S ← 첫번째 S를 ε으로
→ ( ) S
→ ( ) ( S ) S ← 두번째 S를 또 ( S ) S로
→ ( ) ( ε ) S
→ ( ) ( ) S
→ ( ) ( ) ε
= ()()
// 괄호 안으로 들어가는 예시
S → ( S ) S
→ ( S ) ε ← 오른쪽 S를 ε으로
→ ( ( S ) S )
→ ( ( S ) ε )
= (( S ))
```
- 괄호를 나란히 추가하거나 (`S` 뒤에 `S`)
- 괄호 안으로 들어가거나 (`( S )`)
### 1.8.2 Regular vs. Context-Free
| Type | Language | Automata | Production | Example |
| ---- | ------------ | -------- | --------------------- | -------- |
| 2 | Context-Free | ? | $A \to \alpha \ldots$ | $a^nb^n$ |
| 3 | Regular | FSM | $A \to a,\ A \to aB$ | $a^*b^*$ |
## 1.9 다시 유도로 돌아와서, Context-Free로 정의된 덧셈 문법 → 복잡하다!
```plain
// 예제: 덧셈 문법
// BNF
S ::= E + S
| E
E ::= [number]
| ( S )
// Derivation
(1+2+(3+4))+5
S → E + S → ( S ) + S → ( E + S ) + S
→ ( 1 + S ) + S
→ ( 1 + E + S ) + S
→ ( 1 + 2 + S ) + S
→ ( 1 + 2 + ( S ) ) + S
→ ( 1 + 2 + ( E + S ) ) + S
→ ( 1 + 2 + ( 3 + S ) ) + S
→ ( 1 + 2 + ( 3 + E ) ) + S
→ ( 1 + 2 + ( 3 + 4 ) ) + S
→ ( 1 + 2 + ( 3 + 4 ) ) + E
→ ( 1 + 2 + ( 3 + 4 ) ) + 5
```
> 🤔 더 간단하게 표현할 수 있는 방법이 없을까?
## 1.10 간단한 표현을 위한 Parse Tree → 유도 순서가 달라도 Parse Tree는 같을까?
### 1.10.1 Parse Tree — 정의 → 유도 순서에 대한 정보는 없네?
유도 과정을 **트리** 로 표현한 것.
- **Leaf** = Terminal
- **Internal node** = Non-terminal
- **문장 복원**: In-order traversal 후 leaf만 확인
- 유도 **순서**에 대한 정보는 없음
### 1.10.2 Parse Tree — 덧셈 문법 예시
```plain
// 예제: 덧셈 문법
// BNF
S ::= E + S
| E
E ::= [number]
| ( S )
// Parse Tree
(1+2+(3+4))+5
S
/|\
E + S
/|\ |
( S ) E
/|\ |
E + S 5
| /|\
1 E + S
| |
2 E
/|\
( S )
/|\
E + S
| |
3 E
|
4
```
### 1.10.3 Parse Tree — 유도 순서 → 유도가 달라도 같은 Parse Tree?
유도 순서 자체는 크게 중요하지 않음. 정형적인 두 가지 방법:
|방법|설명|
|---|---|
|**Left-most derivation**|가장 왼쪽의 Non-terminal을 찾아서 production 적용|
|**Right-most derivation**|가장 오른쪽의 Non-terminal을 찾아서 production 적용|
> 🤔
> 그렇다면,
> 같은 문장에 대한 유도는 언제나 같은 Parse Tree를 만들까?
## 1.11 ⚠️ 서로 다른 유도가 서로 다른 Parse Tree를 만든다 — Ambiguous Grammar
### 1.11.1 Ambiguous Grammar — 정의
- **Ambiguity**: 이렇게도, 저렇게도 해석될 수 있는 모호함
- **Ambiguous Grammar**: 서로 다른 유도가 **서로 다른 parse tree**를 만들어내는 문법
### 1.11.2 Ambiguous Grammar — 예시
```
// Ambiguous Grammar 예시
// BNF
S ::= S + S
| S * S
| [number]
// Derivation
[S + S 선택]
유도 1: S → S + S → 1 + S → 1 + S * S
→ 1 + 2 * S → 1 + 2 * 3
[S * S 선택]
유도 2: S → S * S → S * 3 → S + S * 3
→ S + 2 * 3 → 1 + 2 * 3
// Parse Tree
// 1+2*3
// 둘 모두 Left-Most지만, 처음 선택이 달라지니 Parse Tree가 달라짐
[ S + S 선택 ] [ S * S 선택 ]
S S
/|\ /|\
S + S S * S
| /|\ /|\ |
1 S * S S + S 3
| | | |
2 3 1 2
```
`1 + 2 * 3`에 대해 두 가지 parse tree가 생성됨:
- 유도 1: `S → S + S` 먼저 → `+`가 루트 → `1 + (2*3)` 해석
- 유도 2: `S → S * S` 먼저 → `*`가 루트 → `(1+2) * 3` 해석
→ **parse tree가 다르면 해석(의미)이 달라진다!**
### 1.11.3 Ambiguous Grammar — 덧셈 문법이 모호하지 않았던 이유
```
S ::= E + S | E
E ::= [number] | ( S )
```
- 덧셈은 항상 `S → E + S` 로만 유도
- 우변에만 $S$가 있음 → **Right-recursive**
- 오른쪽으로만 깊어질 수 있어 parse tree가 유일하게 결정됨
- 결합 방향은 parse tree에서만 관찰 가능
### 1.11.4 Ambiguous Grammar — 모호함 제거 방법 예시
**모든 문법에 대해 작동하는 일반적인 모호함 제거법은 없다.**
케이스별로 문법을 재설계해야 한다.
```plain
// Ambiguous Grammar 예시
// BNF
S ::= S + S
| S * S
| [number]
```
#### 1.11.4.1 Non-terminal 계층 구분
연산자 우선순위를 Non-terminal 계층으로 표현:
|Non-terminal|의미|우선순위|
|---|---|---|
|$E$ (Expression)|덧셈이 포함된 식|낮음|
|$T$ (Term)|곱셈이 포함된 항|중간|
|$F$ (Factor)|곱해지는 숫자|높음|
$E \to T \to F$ 로 갈수록 우선순위가 높아진다.
#### 1.11.4.2 Left-recursive 문법으로 재작성
```
// BNF
S ::= E
E ::= E + T
| T
T ::= T * F
| F
F ::= [number]
// Derivation
// Left-Most
S → E → E + T → T + T → F + T → 1 + T
→ 1 + T * F → 1 + F * F → 1 + 2 * F
→ 1 + 2 * 3
// Right-Most
S → E → E + T → E + T * F → E + T * 3
→ E + F * 3 → E + 2 * 3
→ T + 2 * 3 → F + 2 * 3 → 1 + 2 * 3
// Parse Tree
// Left-Most
S
|
E
/|\
E + T
| /|\
T T * F
| | |
F F 3
| |
1 2
// Right-Most
S
|
E
/|\
E + T
| /|\
T T * F
| | |
F F 3
| |
1 2
```
- **Left-recursive**: 왼쪽에 같은 Non-terminal 재귀 → **왼쪽 결합** 표현
- `E + T`: 오른쪽이 더 높은 우선순위의 $T$ → **덧셈보다 곱셈 우선** 표현
- 이 문법은 Not Ambiguous (증명은 어렵지만 확인 가능)
### 1.11.5 ⚠️ Ambiguous Grammar — 실제 언어에서 문제가 되는 예시
```
// Sentence
if E_1 then if E_2 then S_1 else S_2
→ else가 어디 붙는 거야?
// BNF
S ::= if E then S
| if E then S else S
| ...
// Derivation
// else가 안쪽에 붙음
// else가 바깥쪽에 붙음
// Parse Tree
// else가 안쪽에 붙음
// else가 바깥쪽에 붙음
```
`if E1 then if E2 then S1 else S2` 에서 `else`가 어느 `if`에 붙는지 모호함:
- 유도 1: `else`가 **안쪽** `if`에 붙음
- 유도 2: `else`가 **바깥쪽** `if`에 붙음
#### 1.11.5.1 ⚠️ 모호하지 않게 바꾸기
## 1.12 정리
- 언어는 문자열들의 타입
- 문법 규칙으로부터 문장이 유도되는 조건이기도 함
- Regular Language, Context-free Language 언어의 타입
- 문법이 Left/Right Regular Grammar면 Regular Language에 속함
- 문법이 우리가 이야기한 형태면 Context-Free Language에 속함
- 문장의 유도는 Parse Tree로 표현 가능
---
# 2. Parser Overview
## 2.1 Parser의 위치와 역할 → Lexer가 준 Token list를 AST로
> 이 절은 전체 파트의 도입부다. Parser가 컴파일러 파이프라인에서 어디에 위치하며 무슨 일을 하는지를 명확히 하는 것이 출발점이다. §2.2 이후에서는 Parser가 다루는 핵심 자료구조인 Syntax Tree를 구체적으로 살펴본다.
현대 컴파일러는 크게 세 단계로 구분된다. [[0. INTRODUCTION TO COMPILER]] 참고.
```
Source Program
→ Front-End (Lexer → Parser → Semantic Analyzer → IR Translator)
→ Middle-End (IR 분석 및 최적화)
→ Back-End (Target Program 생성)
```
Parser는 **Front-End** 에 속하며, Lexer가 만들어낸 Token 나열을 받아 **AST(Abstract Syntax Tree)** 로 변환하는 역할을 한다.
```
Source Program → [Lexer] → Token list → [Parser] → AST → [Semantic Analyzer] → ...
```
Parser의 추상적 타입 시그니처는 다음과 같다.
```fsharp
val parser: Token list -> AST
```
이론적 기반은 **오토마타 이론**이며, 구체적으로는 **Context-Free Grammar(CFG)** 를 사용한다.
Lexer가 Regular Language 기반의 토크나이저라면, Parser는 그보다 강력한 CFG 기반의 구조 인식기다.
> CFG를 쓰는 이유: RL(Regular Language)로는 표현할 수 없는 것이 있다. [[#1.7.5 Regular Language의 한계]] 와 [[#1.8 어떤 것을 Context-Free Grammar라고 하는가?]] 참고.
## 2.2 AST를 왜 쓸까? — Syntax Tree의 두 종류, AST/CST
### 2.2.1 Syntax Tree의 정의와 종류
> §2.1에서 Parser의 출력이 AST임을 확인했다. 그렇다면 AST가 정확히 무엇인지, 그리고 왜 CST 대신 AST를 사용하는지를 이해해야 한다. §2.3에서는 AST의 타입을 실제로 어떻게 정의하는지 살펴본다.
Syntax Tree는 **소스코드의 구문(syntax) 구조를 트리로 표현한 것**이다. 두 종류가 있다.
1. CST (Concrete Syntax Tree)
2. AST (Abstract Syntax Tree)
비교하면 아래와 같다.
| 항목 | CST (Concrete Syntax Tree) | AST (Abstract Syntax Tree) |
| ------------- | ----------------------------- | -------------------------- |
| **소속** | **Syntax Tree** | **Syntax Tree** |
| 다른 이름 | Parse Tree | - |
| 포함 정보 | 문장의 모든 표현 (괄호, SEMI 등 터미널 전부) | 핵심적인 표현만 추상화 |
| 괄호 노드 | ✅ 존재 | ❌ 제거 |
| Child 1개짜리 노드 | ✅ 존재 (`S → E` 단독 유도 등) | ❌ 제거 |
| 중첩 구조 표현 | ✅ 가능 | ✅ 가능 (보존) |
| 언어 종속성 | ✅ 종속적 (문법 구조 = 트리 구조) | ❌ 독립적 |
| 의미적 요소 | ❌ 미포함 | ✅ 포함하기 시작 |
| 컴파일러 내 역할 | Parser 내부 중간 단계 | 의미 분석, IR 변환 등의 핵심 자료구조 |
### 2.2.2 Syntax Tree 종류 — CST (Concrete Syntax Tree) = Parse Tree
문장의 **모든 표현**이 트리에 나타나 있는 형태다.
우리가 봤던 Parse Tree가 여기 속한다.
#### 2.2.1.1 CST의 특징
- 문자열과 달리 **중첩 구조**를 표현한다 (예: 결합/association)
- Terminal 노드에 실제 토큰이 그대로 들어간다
예시: `(1+2+(3+4))+5`를 CST(Parse Tree)로 표현하면 괄호 토큰, `+` 토큰 등이 모두 노드로 존재한다. [[#1.10.2 Parse Tree — 덧셈 문법 예시]] 참고.
#### 2.2.1.2 CST의 문제 → AST로 해결하자!
1. **불필요한 정보가 많다**
- 괄호 토큰 자체는 의미 분석에 필요 없다
- Child가 1개인 노드 (예: `S → E` 단독 유도) 는 정보가 없다
2. **특정 언어에 종속적인 표현이다**
- 같은 의미를 가진 코드라도 문법이 다르면 CST가 달라진다
- 모듈화된 컴파일러 구조에서는 Middle-End, Back-End가 Front-End와 독립적이어야 하므로, 언어 종속적인 표현은 재사용성을 해친다
### 2.2.3 Syntax Tree 종류 — AST (Abstract Syntax Tree)
**핵심적인 표현만 추상화**하여 표현한 트리다. CST의 문제를 해결하기 위해 도입된다.
- `불필요한 정보 많은 문제 해결`
- 괄호, Child가 1개인 노드 → **제거**
- 중첩 구조는 **여전히 표현**됨 (구조적 정보는 보존)
- `특정 언어 종속적 표현 문제 해결`
- **언어 독립적** 표현
- 의미적 요소를 포함하기 시작
→ **컴파일러의 핵심 자료구조**: 의미 분석, IR 변환 등의 기반
예시: `1+2+(3+4)+5`의 AST
```mermaid
flowchart TD
op0["BinOp +"]
op1["BinOp +"]
n5["Num 5"]
op0 --> op1
op0 --> n5
n1["Num 1"]
op2["BinOp +"]
op1 --> n1
op1 --> op2
n2["Num 2"]
op3["BinOp +"]
op2 --> n2
op2 --> op3
n3["Num 3"]
n4["Num 4"]
op3 --> n3
op3 --> n4
```
## 2.3 AST와 CST
> §2.2에서 AST의 개념적 특성을 이해했다.
> 이제 실제로 F# 코드로 AST 타입을 어떻게 정의하는지 살펴보며,
> 구체적인 예시 문법을 기준으로 CST → AST로 이어지는 전체 타입 체계를 확인한다.
>
> §2.4에서는 Parser가 내부적으로
> CST-Generator와 AST-Generator로 나뉘는 구조를 다룬다.
```plain
// 예시 문법
<Stmt> ::= <AssignStmt>
| <IfStmt>
<AssignStmt> ::= ID ASSIGN <Expr> SEMI
<IfStmt> ::= IF LPAREN <Expr> RPAREN <Stmt>
<Expr> ::= NUM
| ID
| <Expr> <RelOpKind> <Expr>
<RelOpKind> ::= EQ
```
### 2.3.1 비교: CST — 타입 정의
CST는 **Token을 직접 들고 있다.** 모든 터미널이 포함된다.
> CST code
```fsharp
// 비교 연산자의 CST 표현 (CST Relational Operator Kind)
// 실제 Token을 그대로 들고 있음 (언어 종속적)
type CSTRelOpKind =
| CSTEq of Token // == 에 해당하는 토큰 (뒤에 다른 거 추가 가능)
// 표현식의 CST 표현 (CST Expression)
type CSTExpr =
| CSTNum of Token // 숫자 리터럴 토큰 (예: 0, 1, 42)
| CSTId of Token // 식별자 토큰 (예: a, b, foo)
| CSTRelOp of CSTExpr // 왼쪽 피연산자
* CSTRelOpKind // 비교 연산자 (예: ==)
* CSTExpr // 오른쪽 피연산자
// 구문의 CST 표현 (CST Statement)
type CSTStmt =
| CSTAssignStmt of CSTAssignStmt // 대입문
| CSTIfStmt of CSTIfStmt // if문
// 대입문: ID * ASSIGN * Expr * SEMI (CST Assign Statement)
// 예: a = b ;
and CSTAssignStmt =
Token // ID — 대입 대상 변수명 토큰
* Token // ASSIGN — = 토큰
* CSTExpr // Expr — 대입할 표현식
* Token // SEMI — ; 토큰
// if문: IF * LPAREN * Expr * RPAREN * Stmt (CST If Statement)
// 예: if ( b == 0 ) a = b ;
and CSTIfStmt =
Token // IF — if 키워드 토큰
* Token // LPAREN — ( 토큰
* CSTExpr // Expr — 조건식
* Token // RPAREN — ) 토큰
* CSTStmt // Stmt — then 절 (else 없음, 문법상 단일 Stmt)
```
> CST
```mermaid
flowchart TD
A["CSTStmt (CSTIfStmt)"]
B["CSTIfStmt"]
A --> B
B --> IF
B --> LPAREN
B --> C["CSTExpr (CSTRelOp)"]
B --> RPAREN
B --> D["CSTStmt (CSTAssignStmt)"]
C --> E["CSTExpr (CSTId)"]
C --> F["CSTRelOpKind (CSTEq)"]
C --> G["CSTExpr (CSTNum)"]
E --> ID1["ID"]
F --> EQ
G --> NUM
D --> ID2["ID"]
D --> ASSIGN
D --> H["CSTExpr (CSTId)"]
D --> SEMI
H --> ID3["ID"]
```
예시: **CST-Generator 테스트 케이스**
- 올바른 입력 → CST 반환
- `if` 대신 `of`처럼 문법에 맞지 않는 입력 → **구문 오류(syntax error) 발생**
- Parser는 **구문 오류를 잡아내야 한다** (Lexer는 잡지 않음)
- [[1. Lexer]]의 §1.6.3 참고.
### 2.3.2 비교: AST — 타입 정의
AST는 **Token 대신 의미 있는 값만** 보관하며, `Info` 타입으로 위치 정보를 부가한다.
> AST Code
```fsharp
// 비교 연산자의 AST 표현
// CST와 달리 Token을 버리고 '종류'만 남김 (언어 독립적)
type ASTRelOpKind =
| ASTEq // ==
//| ASTNeq // !=
//| ...
// 표현식의 AST 표현
// CST와 달리 Token 대신 실제 값(int, string)을 들고 있음
type ASTExpr =
| ASTNum of (value: int) // 숫자 리터럴의 실제 정수값
* Info // 소스코드 위치 정보 (에러 메시지 등에 활용)
| ASTId of (name: string) // 식별자의 실제 이름
* Info
| ASTRelOp of (op: ASTRelOpKind) // 비교 연산자의 종류 (==, != 등)
* (lhs: ASTExpr) // 왼쪽 피연산자 (left-hand side)
* (rhs: ASTExpr) // 오른쪽 피연산자 (right-hand side)
* Info
//| ...
// 구문의 AST 표현
type ASTStmt =
| ASTAssignStmt of (var: string) // 대입 대상 변수명
* (expr: ASTExpr) // 대입할 표현식
* Info
| ASTIfStmt of (cond: ASTExpr) // 조건식
* (thenBody: ASTStmt list) // 조건이 참일 때 실행할 구문 목록
* (elseBody: ASTStmt list) // 조건이 거짓일 때 실행할 구문 목록
* Info
//| ...
```
> AST
> if (b == 0) a = b; 니까
>
```mermaid
flowchart TD
A["ASTStmt (ASTIfStmt)"]
A --> B["ASTExpr (ASTRelOp)"]
A --> C["ASTStmt (ASTAssignStmt)"]
B --> D["ASTExpr (ASTId)"]
B --> E["ASTRelOpKind (ASTEq)"]
B --> F["ASTExpr (ASTNum)"]
D --> string1["string"]
F --> int["int"]
C --> string2["string"]
C --> G["ASTExpr (ASTId)"]
G --> string3["string"]
```
```
if (b == 0) a = b;
```
- 왼쪽 서브트리 (조건식 `b == 0`):
- `ASTId` → `string` : 변수 이름 `"b"`
- `ASTEq` : `==` 연산자
- `ASTNum` → `int` : 숫자 `0`
- 오른쪽 서브트리 (then절 `a = b`):
- `string` : 대입 대상 변수 이름 `"a"`
- `ASTId` → `string` : 대입할 값의 변수 이름 `"b"`
예시: `if (b == 0) a = b`의 AST 표현
> Lexer에서 만들어진 Token은 어디로 갔는가?
> → CST는 Token을 담고 있었지만, AST-Generator 단계에서 의미 있는 값(int, string 등)만 추출하고 Token은 버린다.
## 2.4 Parser의 구조 — CST-Generator (Top-Down & Bottom-Up)
### 2.4.1 Parser의 2단계 구조
> §2.3에서 CST와 AST 타입을 정의했다.
> Parser가 `Token list → AST`를 직접 수행하는 것처럼 보이지만,
> 실제로는 CST-Generator과 AST-Generator의 두 단계로 나뉜다.
>
> 이 구조를 이해하면,
> §3에서 다루는 Top-Down Parsing이
> 실질적으로 "CST를 복원하는 과정"임을 이해할 수 있다.
```mermaid
flowchart LR
TL(["Token list"])
AST(["AST"])
TL --> CG
subgraph Parser
CG["CST-Generator"]
AG["AST-Generator"]
CST(["CST"])
CG --> CST
CST --> AG
end
AG --> AST
```
```fsharp
module FrontEnd =
val cstGenerator: Token list -> Result<CST, Info>
val astGenerator: CST -> AST
// parser = cstGenerator >> astGenerator
val parser: Token list -> Result<AST, Info>
```
```
Token list → [CST-Generator] → CST → [AST-Generator] → AST
```
### 2.4.2 CST-Generator — Token List로부터 역으로 Derivation을 알아낸다 / Parse Tree를 복원한다
```fsharp
val cstGenerator: Token list -> CST
```
- 유도 과정(derivation)을 Token list로부터 역으로 알아내는 것
- 복습: 문장의 유도 — $S \to \gamma_1 \to \gamma_2 \to \cdots \to \gamma_n \to s$
- 왜 CST = Parse Tree인가?
→ Parsing하는 과정 자체가 CST를 복원하는 과정.
즉, Token 리스트로부터 역으로 유도 과정을 알아낸다 = Parse Tree/CST를 복원한다
### 2.4.3 Parse Tree (=CST) 복원 방법 두 가지 — Top-Down & Bottom-Up
문법 $G = (T, NT, S, P)$와 문자열 $s \in T^*$가 주어졌을 때:
| 방법 | 방향 | 설명 |
| ------------- | ----------------- | --------------------------------------------------------- |
| **Top-down** | $S \Rightarrow s$ | $S$에서 시작, $A \in NT$에 대해 $A \to \gamma \in P$를 선택하며 점점 확장 |
| **Bottom-up** | $s \Rightarrow S$ | $s$에서 시작, 각 production의 올바른 prefix를 인식하며 $S$까지 역방향으로 환원 |
> 참고! $\gamma$는 **terminal과 non-terminal이 섞인 임의의 문자열**이었다...
## 2.5 정리
- Parser = Token 나열 → CST(Parse Tree 복원) → AST 변환
- CST = Parse Tree (더 많은 정보, 언어 종속적)
- AST = CST보다 간결하고 언어 독립적인 표현
- Parser 구현 방향: Top-down / Bottom-up