# 0. INTRODUCTION TO COMPILER
| 항목 | 내용 |
| -------------- | --------------------------------------- |
| **컴파일러 정의** | 언어를 언어로 변환하는 소프트웨어 |
| **현대 컴파일러 구조** | 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
```
| 구분 | 컴파일러 (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 컴파일러) | 실행 결과 |
컴파일러의 목표
| 목표 | 정의 | 중요도 |
| --------------------- | -------------------------------------- | --------------------- |
| **정확성 (Correctness)** | 컴파일된 프로그램은 원래 프로그램과 동일한 의미를 가져야 한다 | ⭐⭐⭐ 최우선 — 성능보다 훨씬 중요 |
| **개선 (Improvement)** | 컴파일러는 입력 프로그램을 어떤 기준에 대해서 더 나아지게 해야 한다 | ⭐⭐ 중요 — 단, 정확성이 보장된 후 |
## 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 분석 및 최적화.
"입력 언어를 이해하는 과정"
- 이해
- 검사
- 변환
"IR을 변환하는 과정"
- 분석
- 최적화
- 이론적 기반: 프로그래밍 언어론
"출력 언어를 생성하는 과정"
- IR을 기반으로 출력 언어(CPU 아키텍처)에 맞는 코드 생성
- 이론적 기반: 알고리즘
> 최적화 예시 보기
---
# 1. Lexer
문제 유형
- [ ] RE에 속하는 문자열 쓰기
- [ ] RE to NFA
- [ ] NFA to DFA
- [ ] DFA transition table
- **Lexer의 역할**: `string → Token list` (실제 시그니처는 `string → Result<Token list, Info>`)
- **Token = 문법적으로 의미를 갖는 최소 단위 문자열**
- Token 종류: ID / NUM / PAREN / IF / OP / SEMICOLON 등
- Lexeme = Token의 실제 값 (string)
- Info = `{ FilePath; Line; Col }` (에러 위치 표시용)
- **Lexer가 잡는 오류 vs Parser가 잡는 오류 구분**
- **어휘 오류 → Lexer** (예: `1x23` 같이 token 자체가 정의 안 된 문자열)
- **문법 오류 → Parser** (예: `of (b == 0) ...` — `of`는 ID로 잘 파싱됨, 단지 문법이 틀린 것)
- **Chomsky 계층**: Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable
- **Regular = Lexer**, **Context-Free = Parser**
|표기|정의|예시|
|---|---|---|
|$\epsilon$|$L(\epsilon) = {""}$|빈 문자열|
|$a$|$L(a) = {"a"}$|한 글자|
|$R \cdot S$|$L(R) \cdot L(S)$|concatenation|
|$R\|S$|$L(R) \cup L(S)$|alternation|
|$R^*$|$L(\epsilon) \cup L(R) \cup L(R^2) \cup \cdots$|0회 이상 반복|
|$(R)$|$L(R)$|grouping|
- **우선 순위**: `* > · > |`
- `ab|cd*` = `(ab)|(c(d*))`
- **Syntactic Sugar**
- $R^+ = RR^*$ (1회 이상)
- $R? = \epsilon | R$ (있어도 되고 없어도 됨)
- $[0-9], [a-z], [A-Z]$
| |NFA|DFA|
|---|---|---|
| $\delta$ |$S \times (\Sigma \cup {\epsilon}) \to \wp(S)$|$S \times \Sigma \to S$|
| 전이 결과 |여러 state 가능 (집합)|하나의 state|
| $\epsilon$-transition |있음|없음|
## 0.4 Thompson's Construction (RE → NFA) 5가지 규칙
모든 결과 NFA는 **start state 1개, final state 1개**를 가짐.
1. **$\epsilon$**: `(○) --ε--> (◎)`
2. **$a$ (단일 문자)**: `(○) --a--> (◎)`
3. **$RS$ (concatenation)**: `R의 final` --ε--> `S의 start`, R의 start가 새 start, S의 final이 새 final
4. **$R|S$ (alternation)**: 새 start에서 R, S의 start로 ε 두 갈래, R, S의 final에서 새 final로 ε
5. **$R^*$ (Kleene star)**: 새 start --ε--> R의 start, R의 final --ε--> R의 start (반복), 새 start --ε--> 새 final (0번), R의 final --ε--> 새 final
## 0.5 Subset Construction (NFA → DFA) 핵심
- **$\epsilon$-Closure(s)**: $s$로부터 $\epsilon$-transition만으로 도달 가능한 모든 state의 집합 (자기 자신 포함)
- **새 state = 옛 state들의 부분집합** (그래서 이름이 Subset Construction)
- **새 transition**: 어떤 새 state에서 문자 $a$로 갈 수 있는 곳 = $\epsilon\text{-Closure}(\delta(\text{집합}, a))$
- **Initial**: NFA의 $s_0$를 포함한 새 state
- **Final**: NFA의 final state를 하나라도 포함한 새 state
- **NFA state 개수가 $n$이면 DFA state 개수는 최대 $2^n$개**
### 2.2.3 Grammar: 4-tuple로 정의하기
문법은 4-tuple $(T, NT, S, P)$:
- $T$: **Terminal**들의 집합 (= Alphabet)
- 보통 소문자로 표기
- $\epsilon \in T$ (empty string, 길이 0인 특수 문자)
- 예: `{0, 1}`
- $NT$: **Non-terminal**들의 집합
- 아직 완성되지 않은 중간 상태
- 보통 대문자로 표기
- 예: `{<이진수 문자열>, ...}`
- $S$: 문자열 생성 시작을 나타내는 **특별한 기호** ($S \in NT$)
- $P$: 문법 **생성 규칙**들의 집합
- 예: `{<이진수 문자열> → <이진수 문자열> 0, ...}`
## 3.1 RE → FSM 예제
### 3.1.1 단일 문자 $a$
![[스크린샷 2026-04-26 오후 11.12.22.png]]
### 3.1.2 Kleene Star $a^*$
![[스크린샷 2026-04-26 오후 11.12.25.png]]
### 3.1.3 $(0|1)^*0$
![[스크린샷 2026-04-26 오후 11.12.28.png]]
### 3.1.4 아이디어: $\epsilon$의 활용
![[스크린샷 2026-04-26 오후 11.12.31.png]]
- "공백 문자"는 있든 없든 같음
## 3.2. RE → NFA(Non-deterministic Finite Automata) 알고리즘: Thomson's Construction
### 3.2.1 TC의 정의
- RE → NFA
- **귀납적으로 정의된 알고리즘** (RE 자체가 귀납적으로 정의되므로)
- 각 RE 케이스에 대해 다음 두 가지를 만족시키는 방법 제시:
1. RE를 FSM으로 표현 가능
2. 표현된 FSM은 **start state 1개, final state 1개**를 가짐 (이래야 다음 단계에서 합성 가능)
### 3.2.2 TC의 귀납적 정의 — Base Case $\epsilon$ & **$a$
![[스크린샷 2026-04-26 오후 11.07.04.png]]
### 3.2.3 TC의 귀납적 정의 — Inductive Case
![[스크린샷 2026-04-26 오후 11.07.37.png]]
RE $R$과 RE $S$에 대해
#### 3.2.3.1 Concatenation $RS$
![[스크린샷 2026-04-26 오후 11.07.41.png]]
> R의 final state에서 S의 start state로 $\epsilon$-transition.
> 새 start = R의 start, 새 final = S의 final.
#### 3.2.3.2 Alternation $R|S$
![[스크린샷 2026-04-26 오후 11.07.44.png]]
#### 3.2.3.3 Kleene Star $R^*$
![[스크린샷 2026-04-26 오후 11.07.48.png]]
RE $R$에 대해
![[스크린샷 2026-04-26 오후 11.07.51.png]]
RE $R^*$에 대한 FSM
### 3.2.3 TC의 성질
> 📝 $\epsilon$-transition?
> $\epsilon$을 입력으로 받아 생기는 transition
1. 각 state에 대해 최대
1. 2개의 $\epsilon$-transition과
2. 1개의 알파벳 transition이 존재
2. 시간/공간 복잡도 $O(n)$ ($n$: RE의 크기)
### 3.4.2 ⚠️ SC 알고리즘 — 직관 (예제: $(0|1)^*0$)
1. 시작
1. 입력값 X
2. $\epsilon$-Closure(${s_0}$) = ${s_0, s_1, s_2, s_4, s_5, s_6, s_7}$ ← 새 *state* $q_0$
2. 1단계
1. 입력값 `0`
2. $q_0$에서 0으로 갈 수 있는 곳? $\delta(q_0, 0) = {s_3, s_8}$
3. $\epsilon$-Closure(${s_3, s_8}$) = ${s_1, s_2, s_3, s_4, s_6, s_7, s_8}$ ← 새 *state* $q_1$
4. 새 *state* 집합의 $\epsilon$-transition?
1. $\epsilon$-transition$(\{s_3, s_8\}) = \{e_1, e_2, e_3, e_4, e_6, e_7, e_8\}$
2. ⚠️ e가 뭐임? 새 상태였나...
여기까지 나갔을 때, 새로운 FSM의 현재 모습
⚠️ 왜 왼쪽에 $s_0$이 없는 것인지? DFA는 $\epsilon$이 없어서?....
> 그럼 이렇게 변환한다고 했을 때,
> Initial / Final State는 어떻게 결정할까?
>
> 새 **state**가 NFA의 *initial state*를 포함하면 → DFA에서도 initial
> 새 **state**가 NFA의 *final state*를 포함하면 → DFA에서도 final
$\text{NFA } (\Sigma, S, s_0, \delta, F) \to \text{DFA } (\Sigma, Q, q_0, \Delta, F')$
## Transition Table 그리는 법
#### 3.4.7.2 Init
$q_0 = \{s_0, s_1, s_2, s_4, s_7\}, \quad Q = \{q_0\}, \quad \text{WorkList} = [q_0]$
Transition Table
| | 0 | 1 |
| ----------------------------------- | --- | --- |
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | | |
#### 3.4.7.3 q₀ 처리 (pop) — 입력 0
$\varepsilon\text{-Closure}(\delta(q_0, 0)) = \varepsilon\text{-Closure}(\{s_3, s_8\}) = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\} = q_1$
q0 -> q1 화살표
$\text{WorkList} = [q_1]$
Transition Table
| | 0 | 1 |
| --------------------------------------------- | ----- | --- |
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | | |
#### 3.4.7.4 q₀ 처리 — 입력 1
$\varepsilon\text{-Closure}(\delta(q_0, 1)) = \varepsilon\text{-Closure}(\{s_5\}) = \{s_1, s_2, s_4, s_5, s_6, s_7\} = q_2$
q0 -> q2 화살표
$\text{WorkList} = [q_1;\ q_2]$
Transition Table
| | 0 | 1 |
|---|---|---|
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | $q_2$ |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | | |
| $q_2 = \{s_1, s_2, s_4, s_5, s_6, s_7\}$ | | |
#### 3.4.7.5 q₁ 처리 (pop) — 입력 0
$\varepsilon\text{-Closure}(\delta(q_1, 0)) = \varepsilon\text{-Closure}(\{s_3, s_8\}) = q_1$
q1 -> q1 화살표
$\text{WorkList} = [q_2]$
Transition Table
| | 0 | 1 |
| --------------------------------------------- | ----- | ----- |
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | $q_2$ |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | $q_1$ | |
| $q_2 = \{s_1, s_2, s_4, s_5, s_6, s_7\}$ | | |
#### 3.4.7.6 q₁ 처리 — 입력 1
$\varepsilon\text{-Closure}(\delta(q_1, 1)) = \varepsilon\text{-Closure}(\{s_5\}) = q_2$
q1 -> q2 화살표
$\text{WorkList} = [q_2]$
Transition Table
| | 0 | 1 |
|---|---|---|
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | $q_2$ |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | $q_1$ | $q_2$ |
| $q_2 = \{s_1, s_2, s_4, s_5, s_6, s_7\}$ | | |
#### 3.4.7.7 q₂ 처리 (pop) — 입력 0
$\varepsilon\text{-Closure}(\delta(q_2, 0)) = \varepsilon\text{-Closure}(\{s_3, s_8\}) = q_1$
q2 -> q1 화살표
$\text{WorkList} = []$
Transition Table
| | 0 | 1 | |
| --------------------------------------------- | ----- | ----- | --- |
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | $q_2$ | |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | $q_1$ | $q_2$ | |
| $q_2 = \{s_1, s_2, s_4, s_5, s_6, s_7\}$ | $q_1$ | | |
#### 3.4.7.8 q₂ 처리 — 입력 1
$\varepsilon\text{-Closure}(\delta(q_2, 1)) = \varepsilon\text{-Closure}(\{s_5\}) = q_2$
q2 -> q2 화살표
$\text{WorkList} = [ \text{ } ]\ \Rightarrow\ \text{종료}$
Transition Table
| | 0 | 1 |
|---|---|---|
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | $q_2$ |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | $q_1$ | $q_2$ |
| $q_2 = \{s_1, s_2, s_4, s_5, s_6, s_7\}$ | $q_1$ | $q_2$ |
#### 3.4.7.9 결과
Transition Table
| | 0 | 1 |
| --------------------------------------------------- | ----- | ----- |
| $q_0 = {s_0, s_1, s_2, s_4, s_7}$ (initial) | $q_1$ | $q_2$ |
| $q_1 = {s_1, s_2, s_3, s_4, s_6, s_7, s_8}$ (final) | $q_1$ | $q_2$ |
| $q_2 = {s_1, s_2, s_4, s_5, s_6, s_7}$ | $q_1$ | $q_2$ |
> **initial state**: $q_0$ (NFA의 initial state $s_0$을 포함하므로)
> **final state:** $q_1$ (NFA의 final state $s_8$을 포함하므로)
## 4.2 `질문1` DFA는 어떻게 구현하는가? → 2D Array
- **2D Array (Table)** 로 구현 (행: state, 열: 알파벳)
- 매 transition마다 $O(1)$ 시간 복잡도
- 길이 $n$짜리 입력에 대해 $O(n)$만에 Token 판별
- 공간 복잡도: $O(|S| \cdot |\Sigma|)$
## 4.3 `질문2` Lexer는 DFA를 어떻게 사용하는가? → 코드 참고
```f#
type Token =
| ID of Lexeme * Info
| NUM of Lexeme * Info
| LPAREN of Info | RPAREN of Info | EQ of Info | ASSIGN of Info
// | ...
```
> 우리는 지금까지 "RE 하나로 하나의 Token을 인식하는 법"만 배웠는데?
> = 우리는 한 종류 토큰만 다룰 줄 아는데?
## 4.3 `질문2` 여러 Token을 동시에 판별하는 방법
지금까지는 한 종류 Token만 판별 가능. 여러 종류는?
- $R_T$: Token $T$에 대한 RE
- $L$: Lexer의 RE
$L = R_{T_1} | R_{T_2} | R_{T_3} | \cdots = R_{ID} | R_{NUM} | R_{LPAREN} | \cdots$
→ 모든 Token RE들을 `|`로 합쳐 하나의 큰 RE를 만들고, 이 RE를 DFA로 변환하면 됨.
---
# 2. Parser
문제 유형
- [ ] CFG의 Nonterminal Symbol / Terminal Symbol 구분
- [ ] Leftmost Derivation / Rightmost Derivation 과정 + 각 과정 Parse Tree로
- [ ] NT에 대해 NULLABLE / FIRST / FOLLOW 표
- [ ] CFG 보고 LL(1) Parsing Table
- [ ] LR(0) Parsing을 위한 Viable Prefix DFA
- [ ] LR(0) Action / Goto Table
- [ ] Shift/Reduce Conflict 발생 Production + 이유 (위 테이블 기반)
- [ ] SLR(1) 알고리즘으로 Parsing하기 위해 각 NT에 대한 Follow set 구하기
## 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.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.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$ 라고 쓴다.
### 1.5.1 언어의 재정의
$L(G) = \{s \mid \exists(S \to^* s)\}$
- **"문장 $s$가 언어 $L(G)$의 문장이다"** = **"문법 $G$가 문장 $s$를 받아들인다(accept)"
### 1.6.1 촘스키 계층 (Chomsky Hierarchy)
컴파일러 강의에서 관심 있는 범위: **Regular**과 **Context-Free**.
```
recursively enumerable
└─ context-sensitive
└─ context-free ← 컴파일러 강의 관심사
└─ regular ← 컴파일러 강의 관심사
```
### 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과 동치**
기억 장치 필요한 언어는 표현 불가 $a^nb^n$ 같은 거
### 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이 달라짐
### 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.10 CTG를 더 간단하게 표현하기 위한 Parse Tree → 유도 순서가 달라도 Parse Tree는 같을까?
유도 순서 자체는 크게 중요하지 않음. 정형적인 두 가지 방법:
|방법|설명|
|---|---|
|**Left-most derivation**|가장 왼쪽의 Non-terminal을 찾아서 production 적용|
|**Right-most derivation**|가장 오른쪽의 Non-terminal을 찾아서 production 적용|
## 1.11 ⚠️ 서로 다른 유도가 서로 다른 Parse Tree를 만든다 — Ambiguous Grammar
### 1.11.1 Ambiguous Grammar — 정의
- **Ambiguity**: 이렇게도, 저렇게도 해석될 수 있는 모호함
- **Ambiguous Grammar**: 서로 다른 유도가 **서로 다른 parse tree**를 만들어내는 문법
### 1.11.4 Ambiguous Grammar — 모호함 제거 방법 예시
**모든 문법에 대해 작동하는 일반적인 모호함 제거법은 없다.**
left recursive로 재작성할 수도 있음
Parser의 추상적 타입 시그니처는 다음과 같다.
```fsharp
val parser: Token list -> AST
```
이론적 기반은 **오토마타 이론**이며, 구체적으로는 **Context-Free Grammar(CFG)** 를 사용한다.
Lexer가 Regular Language 기반의 토크나이저라면, Parser는 그보다 강력한 CFG 기반의 구조 인식기다.
### 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.1.2 CST의 문제 → AST로 해결하자!
1. **불필요한 정보가 많다**
- 괄호 토큰 자체는 의미 분석에 필요 없다
- Child가 1개인 노드 (예: `S → E` 단독 유도) 는 정보가 없다
2. **특정 언어에 종속적인 표현이다**
- 같은 의미를 가진 코드라도 문법이 다르면 CST가 달라진다
- 모듈화된 컴파일러 구조에서는 Middle-End, Back-End가 Front-End와 독립적이어야 하므로, 언어 종속적인 표현은 재사용성을 해친다
AST → **컴파일러의 핵심 자료구조**: 의미 분석, IR 변환 등의 기반
예시: **CST-Generator 테스트 케이스**
- 올바른 입력 → CST 반환
- `if` 대신 `of`처럼 문법에 맞지 않는 입력 → **구문 오류(syntax error) 발생**
- Parser는 **구문 오류를 잡아내야 한다** (Lexer는 잡지 않음)
- [[1. Lexer]]의 §1.6.3 참고.
AST
> Lexer에서 만들어진 Token은 어디로 갔는가?
> → CST는 Token을 담고 있었지만, AST-Generator 단계에서 의미 있는 값(int, string 등)만 추출하고 Token은 버린다.
```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
```
### 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이 섞인 임의의 문자열**이었다...
그 세모 그림;;
Top-down parsing은 $S$에서 시작하여 production을 선택하며 점점 확장해나가는 방식이다.
$S \to \gamma_1 \to \gamma_2 \to \cdots \to \gamma_n \to s$
**문제:** 잘못된 production을 선택하면 목표 문자열과 다른 방향으로 유도될 수 있다.
**해결책: Backtracking**
→ 잘못된 선택을 감지하면 이전 상태로 되돌아가 다른 production을 시도한다.
## 3.2 🚨 Recursive Descent Parsing — 정의
```pseudo
while (true) do
if (focus ∈ NT) then
// Non-Terminal
// focus가 Non-terminal (예: CSTExpr, CSTStmt 등)
// → 아직 확장이 안 된 노드. production을 적용해서 자식 노드들로 펼쳐야 함
// → 예: focus = S 이면 S → E + S 같은 rule을 선택해서
// E, +, S 자식으로 연결
goto Case 1
else if (idx < len(tokens) && focus = tokens[idx]) then
// Terminal
// focus가 Terminal (예: IF, LPAREN, ID 등 실제 토큰)
// && 아직 읽을 토큰이 남아 있고 (idx < len(tokens))
// && 현재 focus 노드가 현재 토큰과 일치할 때 (focus = tokens[idx])
// → "트리가 기대하는 토큰"과 "실제 입력 토큰"이 맞으므로 소비
// → 예: focus = IF, tokens[idx] = IF 이면 매칭 성공
goto Case 2
else if (idx = len(tokens) && stack = []) then
// ✅ Success!
// focus가 뭔지는 안 중요
// 토큰을 전부 소비했고 (idx = len(tokens))
// && 스택도 비어있음 (처리할 노드가 더 없음)
// → 입력 전체를 트리로 완전히 커버했으므로 파싱 성공!
return tree
else
// ⛔ Backtrack!
// 위 세 조건 모두 해당 없음. 즉:
// 1) focus는 Terminal인데 tokens[idx]와 불일치
// → 즉, 잘못된 production을 선택했음
// 2) 또는 토큰이 남았는데 스택이 비어버림 (입력이 더 남았는데 트리가 끝남)
// → 현재 선택한 production이 틀렸으므로 되돌아가서 다른 production 시도
goto Case 3
```
```pseudo
// Case 1: focus가 NT일 때 — production을 적용해서 트리를 확장
// focus를 좌변으로 뒀을 때 (NT), 우변에 오는 것들 α₁ ... αₙ 로 표시
// P[focus][focus.rule] = focus 노드에 적용할 production 선택
// 예: focus = S, focus.rule = 0 이면 P[S][0] = S → E + S
// 즉,
// α₁ = E, α₂ = +, α₃ = S
(focus -> α₁ ... αₙ) ← P[focus][focus.rule]
// 다음에 이 노드로 backtrack했을 때 다음 production을 시도하도록 +1
// 예: focus.rule = 0 → 1 로 올려놓으면, backtrack 시 P[S][1] = S → E 시도
focus.rule ← focus.rule + 1
// 선택한 production의 우변에 오는 것들(α₁...αₙ)을 전부 자식 노드로 연결
// → 트리가 이 시점에 확장됨
// 예: focus = S, P[S][0] = S → E + S 이면
// S 노드에 E, +, S 자식 노드 세 개가 연결됨
for 1 ≤ i ≤ n do
connect(focus, αᵢ)
// α₂ ~ αₙ은 스택에 push (나중에 처리할 것들)
// 그렇다는 건 α₁은 지금 처리하겠다는 거!!
// 오른쪽부터 push해야 나중에 pop했을 때 왼쪽부터 순서대로 나옴
// 예: α₂ = +, α₃ = S 이면 S를 먼저 push, +를 나중에 push
// → pop하면 +가 먼저 나옴 (left-most 순서 유지)
for n ≥ i ≥ 2 do
stack.push(αᵢ)
// α₁(가장 왼쪽 기호)로 focus 이동
// → left-most derivation: 항상 가장 왼쪽 노드부터 처리
focus ← α₁
```
```pseudo
// Case 2: T
// "트리가 기대하는 토큰"과 "실제 입력 토큰"이 맞으므로 소비
idx ← idx + 1 // 다음 토큰으로 이동
focus ← stack.pop() // 스택에서 다음 처리할 노드 꺼내기
```
```pseudo
// Case 3: Backtrack ⛔
while (true) do
// 현재 실패한 노드를 error로 저장
error ← focus
????
// 부모 기준으로 error가 몇 번째 자식인지 인덱스 저장
// → 이후 stack/idx 복원 범위를 계산할 때 사용
error_idx ← focus.children.index(error)
// stack, idx를 이 노드(focus)를 확장하기 전 상태로 복원
// → error_idx 이후 자식들을 stack에서 pop
// → error_idx > 0 이면 idx도 왼쪽 형제가 소비한 토큰 이전으로 되돌림
goto restore 🔄
// focus의 자식 노드를 전부 제거
// → 다음 production을 새로 시도하기 위해 트리를 깨끗하게 비움
goto remove_children 🗑️
if (focus.rule = len(P[focus])) then
// focus에서 다음에 시도할 P index = Focus가 시도할 수 있는 모든 P len
// 이 NT에 대해 시도할 production이 더 이상 없음
if (focus = tree) then
// 루트 노드까지 올라왔는데도 실패
// → 어떤 production 조합으로도 파싱 불가 → 구문 오류
raise Error
else
// 아직 위에 부모 노드가 있음
// → while 반복하여 한 단계 더 위로 올라가서 backtrack 계속
continue
else
// 아직 시도 안 한 production이 남아 있음
// → while 탈출 후 메인 루프에서 다음 production으로 재시도
break
```
**🔄 restore** (상태 복원):
```pseudo
// focus 복원
// → 실패한 노드에서 부모로 올라감
// → 이제 이 부모 노드의 다음 production을 시도할 것
focus ← focus.parent
// stack 복원
// → error_idx 이후 자식들(아직 처리 안 한 오른쪽 형제들)은
// Case 1에서 stack.push 했던 애들이므로 다시 pop해서 되돌림
// → 예: error_idx = 1 이고 자식이 [E, +, S] 면
// +, S 는 아직 처리 안 했으니 stack에서 pop
for (error_idx + 1 ≤ i < len(focus.children)) do
stack.pop()
// idx 복원
// → error_idx = 0 이면 왼쪽 형제가 없으므로
// 소비한 토큰이 없음 → idx 복원 불필요
// → error_idx ≠ 0 이면 왼쪽 형제들이 이미 토큰을 소비했으므로
// 가장 왼쪽 자식(children[0])의 제일 왼쪽 끝 terminal을 찾아서
// 그 토큰 위치로 idx를 되돌림
// → follow_left_child = 해당 노드에서 왼쪽 자식을 타고 내려가
// 가장 첫 번째 terminal 노드를 반환하는 함수
if (error_idx ≠ 0) then
terminal ← follow_left_child(focus.children[0])
idx ← tokens.index(terminal)
```
**🗑️ remove_children** (자식 제거):
```pseudo
for (child ∈ focus.children) do
disconnect(focus, child)
```
### 3.2.6 예시: (순서를 바꾼) 덧셈 문법
> 토큰은 가장 왼쪽부터 보고, stack 그려서 쌓아가면서 이해 ㄱㄱ
> 한 번 이해한 거라 ㄱㅊ을듯
```
tree : S
focus : S
idx : 0 → (
stack : []
```
위 형식 맞춰서 따라가기
**Success!** — `idx = len(tokens) && stack = []`
## 3.3 Recursive Descent Parsing — 특징
### 3.3.1 `특징1` Left-most derivation
Recursive Descent Parsing은 항상 Left-most derivation)를 따른다.
→ 스택 구조상 항상 가장 왼쪽의 Non-terminal을 먼저 처리하기 때문.
### 3.3.2 `특징2` 특징 2: 종료 여부
특별한 문법이 아닌 경우엔 알고리즘은 끝난다.
하지만 다음 절에서 볼 수 있듯, 특정 문법에서는 **무한 루프**에 빠질 수 있다.
### 3.3.3 `특징3` Backtracking의 비효율성
매번 실패할 때마다 이전 상태로 돌아가서 다시 시도하므로, 최악의 경우 지수 시간이 걸릴 수 있다.
→ 실용적인 파서에서는 Backtracking을 피하기 위한 최적화(look-ahead 등)가 필요하다.
## 3.4 Recursive Descent Parsing — Left-Recursion 문제와 해결
**왜 이런 일이 생기나?**
→
1. Recursive Descent Parsing은 Left-most derivation을 따르는데,
2. left-recursive 문법에서는
3. Terminal을 만나기 전에
4. 계속 같은 Non-terminal로 깊게 파고들기 때문.
### 3.4.2 `해결` 새로운 NT 도입해 Right-Recursive로 만들기
#### 3.4.2.1 $S \to Sa,\quad S \to b$ 예시
기존:
$S \to Sa,\quad S \to b$
변환:
$S \to bS'$
$S' \to aS' \mid \epsilon$
이 문법은 left-recursive가 없으므로 Recursive Descent Parsing 가능.
### 3.4.3 `해결` 일반적인 Left-recursive → Right-recursive
```pseudo
// Non-terminal들을 임의의 순서로 정렬
// (순서에 따라 결과 문법이 달라질 수 있음)
Non-terminal NT = {A₁, ..., Aₙ}을 적당한 순서로 정렬
for i = 1 to n do
for j = 1 to i - 1 do
// Aᵢ → Aⱼγ 형태의 production이 있을 때
// Aⱼ의 모든 production을 대입해서
// 간접 left-recursion을 직접 형태로 드러냄
// 예: Aⱼ → δ₁ | δ₂ 이고 Aᵢ → Aⱼγ 이면
// Aᵢ → δ₁γ | δ₂γ 로 바꿈
// → 이 시점에서 Aⱼ는 이미 처리가 끝난 NT (j < i 이므로)
// 즉 Aⱼ의 production에는 Aᵢ보다 앞선 NT만 등장이 보장됨
Aⱼ → δ₁ | δ₂ | ... | δₖ와 Aᵢ → Aⱼγ에 대해
Aᵢ → δ₁γ | δ₂γ | ... | δₖγ로 대체
// j 루프가 끝나면 Aᵢ의 모든 간접 left-recursion이
// 직접 left-recursion 형태로 변환된 상태
// → 이제 직접 left-recursion만 제거하면 됨
Aᵢ에 대해서 직접 Left-recursion 제거
```
> **단, 이 알고리즘도 항상 작동하는 건 아니다.** 문법에 $\epsilon$-production이나 사이클(예: $A \to B,\ B \to A$)이 있으면 별도 처리가 필요하다.
## 4.1 Backtracking의 원인 → Production 선택을 LL(k) Parsing으로 풀어보자
Recursive Descent Parsing은 non-terminal을 만날 때마다 production을 하나 골라 expand한다. 문제는 **어떤 production을 골라야 할지 모른다는 것**이다. 잘못 선택하면 틀린 것을 인식하고 되돌아와야 한다(backtracking).
이 비효율을 없애려면,
1. lookahead token을 보고
2. **올바른 production을 미리 예측**할 수 있어야 한다.
### 4.1.1 LL(k) Parsing
- **L**eft-to-right으로 입력을 읽으면서
- **L**eft-most derivation을 구성하고
- **k**개의 token을 미리 살펴보고(lookahead) production을 결정한다.
- 덧셈 문법에서, E의 P를 선택할 때
- 다음 token이 1이니까
- \[number] 선택
우리가 다루는 것은 k=1인 **LL(1) Parsing**이다.
### 4.1.2 LL(1)에서 우리가 풀어야 할 핵심 문제
$A \to \alpha \mid \beta$ 와 $a = \text{tokens}[\text{idx}+1]$ 이 주어졌을 때,
- `idx`가 뭐였지? [[#3.2.1 입력 및 변수]] 참고!
$A \to \alpha$ 와 $A \to \beta$ **중 하나를 backtracking 없이 선택**하는 것.
직관적으로 a를 소비하고 싶다면
`S → A a`에서 `A → `를 얻을 수 있으니 `S → A a`로 가는 게 맞지만, 그럴 수가 없다.
알 방법이 없으니까 ;;
A가 nullable이라 `A a` 에서 첫 토큰이 `a`가 될 수 있고,
B는 nullable이지만 `B b` 에서 첫 토큰은 `y` 아니면 `b`지 `a`가 될 수 없다.
즉 이걸 판단하려면,
"`A a` 로부터 첫 번째로 나올 수 있는 terminal이 뭔가"를 **체계적으로 계산**해야 한다
→ 우선, FIRST라는 개념을 도입해보자.
## 4.2 FIRST(γ) → ε 유도 가능성은 어떻게 찾지?
> §4.1에서 "lookahead token을 보고 production을 예측하자"는 아이디어를 얻었다.
> §4.2에서는 그 예측의 근거가 되는 FIRST 집합을 정의하고 계산하는 법을 다룬다.
>
> 그런데 §4.2.3에서 보듯,
> FIRST만으로는 ε-production이 있는 경우를 처리하지 못한다.
> 이 문제는 §4.3의 NULLABLE과 §4.4의 FOLLOW로 이어진다.
### 4.2.1 FIRST(γ) 정의
> 💡 $\gamma \in (T \cup NT)^+$ 였다. NT, T 다 포함된 무언가인데 $\epsilon$은 아닌 것.
$\text{FIRST}(\gamma) = { a \in T \mid \gamma \Rightarrow^* a\beta \text{ for some } \beta }$
γ로부터 유도될 수 있는 모든 문장의 **가장 처음에 등장할 수 있는 terminal들의 집합**이다.
### 4.2.2 FIRST(γ) 계산 아이디어 — NT를 계속 확장하자
| 규칙 형태 | 귀결 |
| --------------------------------------- | ------------------------------------------- |
| $A \to a$ (T) | $\{a\} \subseteq \text{FIRST}(A)$ |
| $A \to B$ (NT) | $\text{FIRST}(B) \subseteq \text{FIRST}(A)$ |
| $A \to BC$, $B \to \epsilon \vert ...$ | $\text{FIRST}(C) \subseteq \text{FIRST}(A)$ |
세 번째 경우, $B$가 $\epsilon$을 만들 수 **있을 때만** C의 FIRST가 A의 FIRST에 포함된다. 이것이 NULLABLE의 필요성으로 이어진다.
### 4.2.3 FIRST 계산의 한계 → NULLABLE이 필요한 이유
$A \to B,C$ 이고 $B \to \epsilon$ 이 직접 없지만 $B \Rightarrow^* \epsilon$ 인 경우,
그 경우에도 B가 사라질 수 있으니까 마찬가지로 FIRST(C) ⊆ FIRST(A) 가 성립해야 한다.
하지만, 단순히 production 규칙만 보아서는
B가 *최종적으로* 사라질 수 있는지 알 수 없다.
즉, ε 유도 가능성 - **NULLABLE** - 을 별도로 계산해야 한다.
### 4.3.1 NULLABLE(X) 정의
$X$로부터 $\epsilon$을 유도할 수 있다면, NULLABLE($X$) = true.
수식으로 쓰면,
$\text{NULLABLE}(X) = \text{true} \iff X \Rightarrow^* \epsilon$
→ 그럼 이건 어떻게 계산할까?
```
// NULLABLE(X) 계산 알고리즘
입력: (T, NT, S, P) // Grammar
변수:
// Map<T ∪ NT, bool>
// 초기값: 모든 α에 대해 NULLABLE[α] = false
NULLABLE ← {}
NULLABLE' // 이번 iteration에서 변화가 있었는지 체크하기 위한 복사본
do
// 이번 루프 시작 전 상태를 저장
NULLABLE' ← copy(NULLABLE)
// T, NT 중 하나인 α에 대해
for α ∈ T ∪ NT do
// 이미 nullable로 판명난 건 스킵
if NULLABLE[α] = true then continue
// α가 T일 경우
elif α ∈ T then
// 터미널은 절대 ε을 유도할 수 없음
// 좌변이니까~
NULLABLE[α] = false; continue
// α가 T일 경우 다 걸러졌으니까
// 여기서부터 α는 NT A
// A의 P 집합 중 하나 γ를 A로 두고, A에 대해
for A ← γ ∈ P[A] do
// γ = γ₁γ₂...γₙ 이라 할 때
if γ = ε then
// production이 직접 ε이면 바로 nullable
NULLABLE[A] = true; break
elif all NULLABLE[γᵢ] = true then
// γ를 구성하는 모든 기호가 nullable이면
// A → γ₁γ₂...γₙ →* ε 이 가능
// 즉 A도 nullable
NULLABLE[A] = true; break
// NULLABLE이 이번 루프에서 한 번도 안 바뀌었으면 종료
// (더 이상 새로 nullable로 판명될 기호가 없음)
while (NULLABLE ≠ NULLABLE')
```
NULLABLE 맵의 값은 `false → true` 방향으로만 바뀔 수 있다.
$T \cup NT$가 유한하므로 변경 가능한 횟수는 유한하고,
그러므로 알고리즘은 반드시 종료된다.
| | NULLABLE |
| --- | -------- |
| S | false |
| E | false |
| E' | false |
| T | false |
| T' | false |
| F | false |
```
입력: (T, NT, S, P) // Grammar
NULLABLE // 앞서 계산한 NULLABLE 맵. Map<NT, bool>
변수:
// 각 기호의 FIRST 집합을 저장. 초기값은 모두 공집합
FIRST ← {} // Map<T ∪ NT, Set<T>>
FIRST' // 이번 iteration에서 변화가 있었는지 체크하기 위한 복사본
do
FIRST' ← copy(FIRST)
for α ∈ T ∪ NT do
if α ∈ T then
// 터미널 a의 FIRST는 자기 자신
// ex) FIRST(+) = {+}
FIRST[a] = {a}; continue
// 여기서부터 α는 non-terminal A
for A ← γ ∈ P[A] do
// γ = γ₁γ₂...γₙ (각 γᵢ는 T 또는 NT)
// γ를 돌며
for 1 ≤ i ≤ n do
if i = 1 then
// 첫 번째 기호의 FIRST는 무조건 A의 FIRST에 포함
// ex) A → B C 에서 FIRST(B) ⊆ FIRST(A)
FIRST[A] = FIRST[A] ∪ FIRST[γ₁]
elif NULLABLE[γᵢ₋₁] = false then
// 바로 앞 기호 γᵢ₋₁이 nullable하지 않으면
// γᵢ₋₁이 반드시 뭔가를 만들어내므로
// γᵢ 이후는 첫 번째로 올 수 없음 → 더 볼 필요 없음
break
else
// γᵢ₋₁이 nullable하면 γᵢ₋₁이 사라질 수 있으므로
// γᵢ가 첫 번째로 올 수 있음
// → FIRST[γᵢ] ⊆ FIRST[A]
FIRST[A] = FIRST[A] ∪ FIRST[γᵢ]
// FIRST가 이번 루프에서 한 번도 안 바뀌었으면 종료
// (더 이상 추가될 원소가 없음)
while (FIRST ≠ FIRST')
```
### 4.4.3 FIRST 알고리즘 — 종료성
FIRST 집합의 원소는 추가만 되고 삭제되지 않는다.
Terminal 집합이 유한하므로 반드시 종료된다.
| 기호 | NULLABLE | FIRST |
| --- | -------- | ----- |
| S | false | |
| E | false | |
| E' | true | |
| T | false | |
| T' | true | |
| F | false | |
| 기호 | NULLABLE | FIRST |
| --- | -------- | ------------------ |
| S | false | { [id], [num], ( } |
| E | false | { [id], [num], ( } |
| E' | true | { +, - } |
| T | false | { [id], [num], ( } |
| T' | true | { *, / } |
| F | false | { [id], [num], ( } |
> §4.4까지 구한 FIRST만으로도 많은 경우 production을 결정할 수 있다.
> 그러나 §4.5.1의 예시처럼, focus가 NULLABLE한 non-terminal이고 lookahead token이 FIRST에 없을 때는 "ε-production을 선택해도 되는가?"를 판단할 수 없다. §4.5에서는 이 판단을 가능하게 하는 FOLLOW를 정의하고 계산한다. FIRST와 FOLLOW가 모두 준비되면 §4.6의 select 함수를 완성할 수 있다.
### 4.5.1 FOLLOW가 필요한 상황
다시 Recursive Descent Parsing을 수행 중일 때,
```
Focus = E'
Tokens[idx] = )
E' ::= + T E'
| - T E'
|
```
lookahead `)`는 FIRST(E')에 없다. 그렇다면 $E' \to \epsilon$을 선택해도 되는가?
→ `)` 가 E' 다음에 올 수 있는 token이라면 가능하다. 이것이 FOLLOW이다.
### 4.5.2 FOLLOW(γ) 정의
$\text{FOLLOW}(\gamma) = { a \in T \mid \exists, \alpha, \beta,, S \Rightarrow^* \alpha,\gamma,a,\beta }$
γ의 **바로 오른쪽에 등장할 수 있는 terminal들의 집합**.
- $\{)\} \subseteq \text{FOLLOW}(E)$
- $F \to (E)$ 에서 E 오른쪽에 `)`
- $\text{FOLLOW}(S) = \{\$\}$ — S는 시작 기호이므로 오른쪽엔 EOF($)만
### 4.5.3 FOLLOW 알고리즘 — 핵심 원리
| 규칙 형태 | 귀결 |
| --------------------------------------------------------------------------------- | ------------------------------------------------------ |
| $A \to \alpha \gamma \beta \delta$, $\text{NULLABLE}(\beta) = \text{true}$ | $\text{FIRST}(\delta) \subseteq \text{FOLLOW}(\gamma)$ |
| $A \to \alpha \gamma \beta \delta$, $\text{NULLABLE}(\beta\delta) = \text{true}$ | $\text{FOLLOW}(A) \subseteq \text{FOLLOW}(\gamma)$ |
- γ 바로 다음에 β가 있는데, β가 nullable이면 β가 사라질 수 있음.
- 그러면 γ 다음에 δ가 바로 올 수 있으니까,
- δ의 첫 번째 terminal들이 γ의 FOLLOW에 포함.
- 마찬가지로, βδ가 NULLABLE이면 βδ가 모두 사라질 수 있음.
- 그러면 γ 이후가 전부 사라질 수 있음.
- 그렇다면 γ 다음에 올 수 있는 게 곧 $A$ 다음에 올 수 있는 것과 같아짐.
```
입력: (T, NT, S, P), NULLABLE, FIRST
변수: FOLLOW ← {} // MAP<T U NT, Set<T>>
FOLLOW' ← {} // 복붙해서 iteration마다 확인용
do
FOLLOW' ← copy(FOLLOW)
for α ∈ T ∪ NT do
// 터미널은 production의 좌변이 될 수 없으므로 추적할 필요 없음
if α ∈ T then continue
// 여기서부터 α는 non-terminal A
for A ← γ ∈ P[A] do
// γ = γ₁ γ₂ … γₙ
// γ 안의 각 기호 γᵢ에 대해 FOLLOW를 계산
for 1 ≤ i ≤ n do
if ∀j ∈ {i+1,…,n} NULLABLE(γⱼ) then
// γᵢ 뒤의 모든 기호(γᵢ₊₁…γₙ)가 전부 nullable이면
// γᵢ 이후가 전부 사라질 수 있음
// → γᵢ가 사실상 A의 맨 끝이 되므로
// → A 다음에 오는 것이 곧 γᵢ 다음에 올 수 있음
FOLLOW(γᵢ) = FOLLOW(γᵢ) ∪ FOLLOW(A)
for i < j ≤ n do
if ∀k ∈ {i+1,…,j-1} NULLABLE(γₖ) then
// γᵢ와 γⱼ 사이의 모든 기호가 nullable이면
// 그 사이가 전부 사라져서 γⱼ가 γᵢ 바로 다음에 올 수 있음
// → γⱼ의 첫 terminal이 γᵢ 다음에 올 수 있음
FOLLOW(γᵢ) = FOLLOW(γᵢ) ∪ FIRST(γⱼ)
while (FOLLOW ≠ FOLLOW')
```
FOLLOW 집합도 단조 증가하며 Terminal 집합이 유한하므로 반드시 종료된다.
|기호|NULLABLE|FIRST|FOLLOW|
|---|---|---|---|
|S|false|[id] [num] (|$|
|E|false|[id] [num] (|$ )|
|E'|true|+ -|$ )|
|T|false|[id] [num] (|$ + - )|
|T'|true|* /|$ + - )|
|F|false|[id] [num] (|$ + - * / )|
## 4.6 LL(1) Parsing 알고리즘 — select와 Parsing Table
> §4.2~4.5에서 NULLABLE, FIRST, FOLLOW를 모두 구했다.
> §4.6에서는 이 세 가지를 실제 production 선택 함수 select로 통합하고,
> 이를 2D 테이블로 구현하여 O(1)에 production을 결정하는 Parsing Table을 만든다.
둘 다 해당 없으면 → 이 production은 후보에서 탈락.
| 조건 | 선택 |
| -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ---------------------------- |
| $\text{lookahead} \in \text{FIRST}(\alpha)
lt;br>→ $\alpha$를 전개했을 때 첫 번째로 나올 수 있는 것들 중에<br>→ lookahead가 있으니까<br>→ **$A \to \alpha$ 선택** | focus $\leftarrow \alpha$ 선택 |
| $\text{NULLABLE}(\alpha) = \text{true}$ 이고 $\text{lookahead} \in \text{FOLLOW}(\alpha)lt;br>→ $\alpha$가 통째로 사라질 수 있고,<br>→ 사라진 후에 그 뒤로 lookahead가 바로 올 수 있으니까 <br>→ **$A \to \alpha$ 선택**<br> | focus $\leftarrow \alpha$ 선택 |
**NULLABLE / FIRST / FOLLOW 표**
| | NULLABLE | FIRST | FOLLOW |
| --- | -------- | ------------ | ----------- |
| S | false | [id] [num] ( | $ |
| E | false | [id] [num] ( | $ ) |
| E' | true | + - | $ ) |
| T | false | [id] [num] ( | $ + - ) |
| T' | true | * / | $ + - ) |
| F | false | [id] [num] ( | $ + - * / ) |
| | | | |
**select 표** = Parsing Table
| | + | - | * | / | [id] | [num] | ( | ) | $ |
| --- | ------- | ------- | ------- | ------- | ------ | ------- | ----- | --- | --- |
| S | | | | | S→E | S→E | S→E | | |
| E | | | | | E→TE' | E→TE' | E→TE' | | |
| E' | E'→+TE' | E'→-TE' | | | | | | E'→ | E'→ |
| T | | | | | T→FT' | T→FT' | T→FT' | | |
| T' | | | T'→*FT' | T'→/FT' | | | | T'→ | T'→ |
| F | | | | | F→[id] | F→[num] | F→(E) | | |
- **Row**: focus (non-terminal)
- **Column**: lookahead (terminal)
- **Entry**: 선택할 production
- **빈 칸**: 오류(Error)
## 4.7 LL(1) Parsing의 한계 — Conflict
### 4.7.1 FIRST/FIRST Conflict → Left Factoring으로 해결
$A \to \alpha \mid \beta$ 일 때 $\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) \neq \emptyset$ (서로소가 아닌) 경우
→ 같은 lookahead에 production이 두 개 대응된다. (Parsing Table의 한 칸에 두 P가 들어온다)
대표 원인은 left-recursion but 없어도 발생 가능
### 4.7.2 FIRST/FOLLOW Conflict → Substition으로 해결
NULLABLE한 production이 있을 때,
**lookahead가 FIRST에도 속하고 동시에 FOLLOW에도 속하면**
select의 경우 1과 경우 2가 동시에 적용되어 충돌이 발생한다.
NULLABLE한 production이 있을 때,
**lookahead가 FIRST에도 속하고 동시에 FOLLOW에도 속하면**
select의 경우 1과 경우 2가 동시에 적용되어 충돌이 발생한다.
### 4.7.3 FOLLOW/FOLLOW Conflict
잘 없음. 보통 문법 자체가 모호함.
($A \to B \to \epsilon$ 과 $A \to C \to \epsilon$ 이 동시에 성립하여 같은 문자열에 두 개의 파스트리가 생긴다.)
### 4.7.4 Conflict 제거 가능 범위
```
Context-Free Grammar
├── LL(1) Grammar ← Conflict를 제거할 수 있는 범위
│ └── Regular Grammar
└── Ambiguous Grammar ← Conflict 제거 불가
```
**Conflict는 LL(1) 문법인 경우에만 항상 제거 가능하다.**
## 5.1. Bottom-Up Parsing이란? → Right-most Derivation의 역순
> §5.1에서는 Bottom-up parsing이 right-most derivation을 거꾸로 읽는 과정임을 확인한다. 이 관점이 §5.2의 Shift-Reduce 연산으로 구체화되고, §5.3에서 "언제 reduce하는가"라는 핵심 질문으로 이어진다.
### 5.1.1 Bottom-Up Parsing — 개념
Bottom-up parsing은 입력 문자열 $s$에서 시작해 $S$까지 **reduce**해 나가는 과정이다. 이는 right-most derivation을 역순으로 읽는 것과 동일하다.
$s ;\to; \gamma_n ;\to; \cdots ;\to; \gamma_2 ;\to; \gamma_1 ;\to; S$
왼쪽에서 오른쪽으로 token을 읽어가면서 진행하며, right-most derivation은 가장 오른쪽 non-terminal부터 확장하므로, 역순에서는 reduce가 왼쪽부터 진행된다.
즉,
1. 왼쪽에서 오른쪽으로 token 읽어가며 진행
2. 현 위치에서 적용할 수 있는 production이 없으면 다음 토큰으로 이동
3. 현재 위치에서 올바르게 적용할 수 있는 production을 "전부 적용"
```
Right-most derivation (순방향):
S → E + S
→ E + E
→ E + 3
→ ( S ) + 3
→ ( E + S ) + 3
→ ( E + E ) + 3
→ ( E + 2 ) + 3
→ ( 1 + 2 ) + 3
Bottom-up (역방향):
( 1 + 2 ) + 3
→ ( E + 2 ) + 3 [E → [number] 적용]
→ ( E + E ) + 3 [E → [number] 적용]
→ ( E + S ) + 3 [S → E 적용]
→ ( S ) + 3 [S → E + S 적용]
→ E + 3 [E → ( S ) 적용]
→ E + E [E → [number] 적용]
→ E + S [S → E 적용]
→ S [S → E + S 적용]
```
### 5.1.3 Bottom-Up Parsing — 구체화된 개념
1. 왼쪽에서 오른쪽으로 토큰 읽어가면서 진행
1. 지금까지 확인한 위치를 `. (Marker)`로 표시
1. $\alpha \beta. \gamma \delta$: 지금까지 $\alpha \beta$까지 읽었고, 앞으로 $\gamma \delta$가 남음
2. $\gamma \delta$는 터미널의 나열.
1. 핵심은 **"아직 읽지 않았다"** 는 것. 아직 읽지 않은 부분은 lexer가 뱉어낸 **raw token 그대로**일 것.
2. 현재 위치에서 적용할 수 있는 P가 없으면 다음 토큰으로 이동
1. $\alpha A. \gamma \delta$에서 $\alpha A \gamma . \delta$로 진행.
3. 현재 위치에서 올바르게 적용할 수 있는 P를 전부 적용
1. $A \to \beta$에 대해 유도 $S \to^* \alpha A \gamma \delta \to \alpha \beta \gamma \delta$가 존재하면,
1. 즉, $\alpha \beta \gamma \delta$ 라는 현재 상태가 **진짜로 S에서 유도 가능한 중간 단계**라는 것
2. $A \to \beta$ 를 적용하면 **결국 S까지 reduce할 수 있는 올바른 경로**가 있다는 것
3. 거꾸로 가는 거라는 걸 잊지 말자!
2. $\alpha \beta. \gamma \delta$에서 $\alpha A. \gamma \delta$로 진행.
4.
## 5.2. Shift-Reduce Parsing — Bottom-Up의 보다 구체적 구현 → Reduce는 언제 하지?
> §5.1에서 bottom-up parsing이 역방향 유도임을 봤다. §5.2에서는 이것을 실제로 어떻게 수행하는지, 두 가지 연산(Shift·Reduce)으로 정형화한다. 이 연산의 "타이밍"을 결정하는 문제가 §5.3의 Handle로 이어진다.
### 5.2.1 Marker
현재까지 확인한 위치를 `.` (Marker)로 표시한다.
- $\alpha\beta ;.; \gamma\delta$: 지금까지 $\alpha\beta$를 읽었고, 앞으로 $\gamma\delta$가 남음
- $\gamma\delta$는 아직 읽지 않은 부분이므로 terminal들의 나열
### 5.2.2 Shift 연산과 Reduce 연산
| 연산 | 조건 | 동작 |
| ---------- | -------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------- |
| **Shift** | 현재 위치에서 적용할 production이 없음 | 다음 token으로 이동<br>$\alpha A. \gamma \delta$에서 $\alpha A \gamma . \delta$로 진행. |
| **Reduce** | $A \to \beta$에 대해 $S \Rightarrow^* \alpha A a\delta \to \alpha\beta a\delta$가 존재 | 현재 위치에서 올바르게 적용할 수 있는 P를 모두 적용.<br>production 우변을 좌변 NT로 치환<br>$\alpha \beta. \gamma \delta$에서 $\alpha A. \gamma \delta$로 진행. |
### 5.2.3 Stack 사용
**Marker 기준 왼쪽의 token list를 Stack으로 표현한다.**
즉, 지금까지 읽고 처리한 모든 것의 현재 상태가 Stack에 들어있음 (shift, reduce 처리 구분 X)
- **Shift**: Terminal을 stack에 `push`
- **Reduce**: T or NT들을 stack에서 `pop`한 후, 적절한 NT를 `push`
- $A \to \alpha\beta\gamma$라면 $\gamma, \beta, \alpha$ 순으로 pop하고 (stack top부터) $A$를 push
## 5.3. Handle → 언제 Reduce해야 하는지 확정
### 5.3.1 Reduce가 필요한 타이밍 정의
- Right-most derivation $S \Rightarrow^* \alpha A s \to \alpha\beta s$ 가 존재하고,
- Marker가 production 우변의 **끝**에 위치할 때
- `.` 기준으로 왼쪽이 stack, 오른쪽이 남은 입력.
- "Marker가 production 우변의 끝에 위치한다"는 건, **어떤 production $A \to \gamma$의 우변 $\gamma$ 전체가 이미 stack에 들어와 있고, 그 직후에 marker가 찍혀있다**는 뜻.
- 즉, production 우변이 **stack top**에 있을 때
- 예시: $\alpha \gamma . \beta$
- - $\gamma$ = production $A \to \gamma$의 우변
- $\gamma$ 전체가 stack top에 있음
- marker `.`가 $\gamma$ 바로 뒤에 있음 = **우변의 끝에 위치**
- Reduce가 가능해짐.
### 5.3.2 Handle 정의
1. reduce될 수 있고,
2. 그 결과 궁극적으로
3. $S$까지 reduce되게 하는 token list와 production의 쌍.
1. 반대로 말하면, **handle만 reduce를 해야 한다.**
### 5.3.3 Handle은 항상 Stack Top에만 존재한다
귀납법으로 증명:
1. Base Case - Stack 비어 있음
2. Induction Hypothesis - Handle이 Stack Top에 있다고 가정
3. Reduce를 하면 $\alpha A . \beta$
```
Base case: Stack이 비어있는 경우 — trivially 성립
Stack이 비어있으면 handle도 없으니까
"handle이 stack top에 있다"는 명제가 그냥 성립.
Induction hypothesis: 현재 handle이 stack top에 있다고 가정
α γ . β 일 때 handle: γ, A → γ
Reduce 후 → α A . β
- A가 가장 오른쪽에 존재하는 NT
- 다음 handle이 A보다 왼쪽에 있다고 가정하면 right-most derivation이 아니게 됨. Right-Most는 항상 가장 오른쪽 NT부터 전개. right-most 반대가 bottom-up이니까 오른쪽부터 reduce해야 함. α 안에 다음 handle이 있음. 즉, A보다 왼쪽에 있는 걸 다음에 reduce한다는 뜻. 근데 right-most derivation의 역순이라면 A보다 왼쪽에 있는 건 A보다 먼저 reduce됐어야 함 → 모순
- 따라서 다음 handle도 stack top (혹은 shift 후 stack top)에 위치
```
> ⚠️ `tryFindHandle`을 일반적으로 효율적으로 구현하는 방법은 없다 — 일반적인 방법은 Backtracking으로 비효율적이다. §6에서 이 문제를 Viable Prefix DFA로 해결한다.
# 6. 🚨 Bottom-Up Parsing (2) — LR(0) Parser
> §5.4에서 Bottom-Up Parsing 알고리즘의 기본 틀을 보았는데,
> 여기서 Handle을 찾는 tryFindHandle의 알고리즘은 다루지 않았다.
>
> §6에서는 Handle을 효율적으로 찾기 위한 방법을 소개하고,
> 그걸 적용한 LR(0) Parser에 대해 다룬다.
## 6.1. Handle을 효율적으로 찾을 수 없다 → 관찰에 의한 Heuristic이 필요하다
## 6.2. Stack 관찰 — Stack에는 항상 Production들의 Prefix만 존재한다 → 뭐라고 부를까?
## 6.3 Viable Prefix — 아직 파싱 오류가 없다는 게 보장된, stack에 올라올 수 있는 올바른 문자열
> 말로 이해하기
"handle이 완성되기까지의 과정에서 stack에 올라오는 모든 중간 상태"
"아직 파싱 오류가 없다는 게 보장된, stack에 올라올 수 있는 올바른 문자열"
> 수식으로 이해하기
**정의:** $\alpha \in (T \cup NT)^*$, $s \in T^*$ 일 때, $S \to^* \alpha . s$ 이면 $\alpha$를 **viable prefix**라고 한다.
$S \to^* \alpha . s$ 의 의미
- $S$에서 시작해서 유도를 거듭하다 보면
- 어떤 중간 단계에서 $\alpha s$ 라는 문자열이 나오고
- 그 중 $\alpha$는 이미 stack에 쌓인 부분, $s$는 아직 안 읽은 나머지 입력
즉 **"$S$로부터 올바르게 유도되는 과정 중에 실제로 등장할 수 있는 stack의 내용"** 이 viable prefix.
> "S로부터 올바르게 유도되는 과정 중에 실제로 등장할 수 있는 stack의 내용" = viable prefix인데, 그 stack 내용이 결국 어떤 production 우변(= 결과적으로 S까지 reduce되게 하는 handle)의 prefix이기 때문에 "viable"이라고 부름.
**특징**
- Stack에 viable prefix들만 있다는 것 = 아직 parsing error를 만나지 않았다는 뜻
**예시**
문법 `S ::= E + E`, `E ::= [num] | ( S )` 의 viable prefix 예시 (문법 3개 각각)
- $\epsilon$, `E`, `E +`, `E + E`
- $\epsilon$, `[num]`
- $\epsilon$, `(`, `( S`, `( S )`
### 6.3.2 Viable Prefix — 활용 아이디어: Viable prefix를 인식하면 handle을 찾을 수 있다 → 어떻게 인식할 것인가?
- 현재 Stack에 Viable Prefix만 있을 때 알 수 있는 것
- 지금까지 읽은 입력은 정상적
- 마지막 viable prefix (prefix$_n$)의 상태에 따라 reduce 여부 결정 가능
- 그러므로,
- **아이디어:** Viable prefix를 인식하면 handle을 찾을 수 있다
- prefixₙ이 **완전한 production**(= handle) → **Reduce**
- prefixₙ이 **불완전한 prefix** 수준 → **Shift**
### 6.3.3 Viable Prefix — 인식 아이디어: Viable Prefix는 RL이니, FSM으로 인식해보자
#### 6.3.3.1 왜 Viable Prefix가 Regular Language인가?
> P에 마커로 현재 상태를 표시한 것을 item (or LR(0) item 이라고 함)
1. RL은 FSM으로 표현 가능한 언어다. ([[1. Lexer]]을 떠올려보자!)
2. P $A \to \gamma_1 \gamma_2 \ldots \gamma_n$ 에 대해 viable prefix를 인식하는 과정을 이렇게 생각해보자 (마커의 위치에 주목!)
1. $A \to . \gamma_1 \gamma_2 \ldots \gamma_n$
2. $A \to \gamma_1 . \gamma_2 \ldots \gamma_n$
3. ...
4. $A \to \gamma_1 \gamma_2 \ldots \gamma_n .$
3. 이걸 보면 각 item이 FSM의 **상태**이고, γᵢ를 읽으면 다음 상태로 전이하는 구조.
4. 즉 이 과정 자체가 FSM이고,
5. FSM으로 표현 가능한 언어 = Regular Language이므로
6. viable prefix들의 집합이 RL이 됨.
즉, **FSM(유한 상태 기계)으로 표현 가능**하다.
이것이 LR(0) Parser의 핵심 이론적 기반이다.
### 6.4.2. 단일 Production에 대한 Viable Prefix FSM → 여러 개는?
Production $A \to \gamma_1\gamma_2\dots\gamma_n$에 대한 FSM $(\Sigma, S, s_0, \delta, F)$:
- $\Sigma = {\gamma_1, \dots, \gamma_n} \subseteq T \cup NT$
- $S$ = item들의 집합 ${A \to .\gamma_1\gamma_2\dots\gamma_n,; A \to \gamma_1.\gamma_2\dots\gamma_n,; \dots,; A \to \gamma_1\gamma_2\dots\gamma_n.}$
- $A \to \epsilon$이면 item 집합은 ${A \to .}$
- $s_0 = A \to .\gamma_1\gamma_2\dots\gamma_n$
- $\delta(A \to \gamma_1\dots\gamma_{i-1}.\gamma_i\dots\gamma_n,; \gamma_i) = A \to \gamma_1\dots\gamma_i.\gamma_{i+1}\dots\gamma_n$
- $F = S$ (모든 상태가 accepting)
**예제:** `S → E + E`에 대한 FSM
![[스크린샷 2026-04-28 오후 2.13.15.png]]
### 6.4.3 여러 Production에 대한 Viable Prefix FSM → ε-transition은?
#### 6.4.3.1 여러 Production에 대한 Viable Prefix FSM 만드는 규칙
각각의 production에 대해 viable prefix FSM을 만든 후, ε-transition으로 연결한다.
**규칙 1:** $A \to \alpha.B\beta$와 $B \to \gamma$라는 두 Production이 있다면
$\delta(A \to \alpha.B\beta, \epsilon) = B \to .\gamma$
의미: $B$를 인식하러 가는 순간, $B$의 production 시작 상태로 점프할 수 있음.
**규칙 2:** 또한 $S' \to S$라는 **특별한 production**을 하나 추가한다.
- $S$를 인식했다는 것을 나타내기 위한 장치
- Items: $S' \to .S$ 와 $S' \to S.$
#### 6.4.3.2 FSM 예시
**예제:** `S → E + E`, `E → ( S )` 두 production을 합친 NFA
![[스크린샷 2026-04-28 오후 2.20.34.png]]
**S → E + E, E → ( S ) 에 대한 NFA**
$\Sigma = {E, +, (, S, )}$
$S = {S \to .E+E,\ S \to E.+E,\ S \to E+.E,\ S \to E+E.,\ E \to .(S),\ E \to (.S),\ E \to (S.),\ E \to (S).}$
$s_0 = S \to .E+E$
$\delta$:
| 현재 상태 | 입력 | 다음 상태 | 합쳐진 부분들 |
| ------------ | ---------- | ------------ | ------- |
| $S \to .E+E$ | $E$ | $S \to E.+E$ | |
| $S \to E.+E$ | $+$ | $S \to E+.E$ | |
| $S \to E+.E$ | $E$ | $S \to E+E.$ | |
| $E \to .(S)$ | $($ | $E \to (.S)$ | |
| $E \to (.S)$ | $S$ | $E \to (S.)$ | |
| $E \to (S.)$ | $)$ | $E \to (S).$ | |
| $S \to .E+E$ | $\epsilon$ | $E \to .(S)$ | ✅ |
| $S \to E+.E$ | $\epsilon$ | $E \to .(S)$ | ✅ |
| $E \to (.S)$ | $\epsilon$ | $S \to E.+E$ | ✅ |
[[#6.4.3.1 여러 Production에 대한 Viable Prefix FSM 만드는 규칙]] 이랑 같이 보자!
$F = S$ (모든 상태가 accepting)
## 6.5. 🚨 NFA → DFA (Subset Construction) — Viable Prefix DFA → 어떻게 활용할까?
**Transition Table**
- **행(State)**: 현재 DFA 상태. 각 상태는 item들의 집합.
- **Items 열**: 그 상태에서 "지금 어떤 production들을 인식 중인가"
- **나머지 열(S, E, +, \[num], (, ))**: "이 상태에서 해당 기호를 읽으면 어느 상태로 전이하는가"
초기
| State | Items | S | E | + | [num] | ( | ) |
| ----- | ----- | --- | --- | --- | ----- | --- | --- |
| 0 | | | | | | | |
| 1 | | | | | | | |
| 2 | | | | | | | |
| 3 | | | | | | | |
| 4 | | | | | | | |
| 5 | | | | | | | |
| 6 | | | | | | | |
| 7 | | | | | | | |
| 8 | | | | | | | |
완성
| State | Items | S | E | + | [num] | ( | ) |
| ----- | ----------------------------------------------------- | --- | --- | --- | ----- | --- | --- |
| 0 | $S' \to .S,\ S \to .E+E,\ E \to .[num],\ E \to .(S)$ | 1 | 2 | | 3 | 4 | |
| 1 | $S' \to S.$ | | | | | | |
| 2 | $S \to E.+E$ | | | 5 | | | |
| 3 | $E \to [num].$ | | | | | | |
| 4 | $E \to (.S),\ S \to .E+E,\ E \to .[num],\ E \to .(S)$ | 6 | 2 | | 3 | 4 | |
| 5 | $S \to E+.E,\ E \to .[num],\ E \to .(S)$ | | 7 | | 3 | 4 | |
| 6 | $E \to (S.)$ | | | | | | 8 |
| 7 | $S \to E+E.$ | | | | | | |
| 8 | $E \to (S).$ | | | | | | |
**DFA 다이어그램:**
![[스크린샷 2026-04-28 오후 2.40.13.png]]
### 6.6.1 DFA를 보고 실행시키는 과정
**상태 전이 규칙**
stack에 쌓인 기호들을 왼쪽부터 순서대로 DFA에 입력한다. 즉 $\delta$를 반복 적용해서 최종 상태를 구한다.
$\text{State}_0 \xrightarrow{x_1} \text{State}_1 \xrightarrow{x_2} \cdots \xrightarrow{x_n} \text{State}_n$
여기서 $x_1 x_2 \cdots x_n$이 현재 stack의 내용이고, $\text{State}_n$이 현재 DFA 상태다.
**Shift / Reduce 결정 규칙**
최종 상태의 items를 보고 결정한다.
| 최종 상태의 item 형태 | 의미 | 결정 |
| -------------------------------- | -------------------------- | ---------- |
| $A \to \alpha . \beta$ (`.`이 중간) | 아직 불완전한 prefix | **Shift** |
| $A \to \gamma .$ (`.`이 맨 끝) | 완전한 production = handle 발견 | **Reduce** |
상태 0부터 입력해가면서 움직이면 됨
## 6.7 DFA 상태를 Stack에 함께 저장 → Action & Goto Table
### 6.7.1 아이디어 — DFA 상태를 Stack에 함께 저장
**아이디어:** 같은 prefix에 대해서는 항상 같은 DFA 상태가 나온다. 따라서 DFA 상태를 stack element에 함께 저장하면 매번 처음부터 돌릴 필요가 없다.
- Stack element: $(T \cup NT) \to (T \cup NT, \text{DFA State})$
- 기존 $(T \cup NT)$ 단순 기호에서
- 변형 $(T \cup NT, \text{DFA State})$ 기호와 상태 쌍을 같이 저장
- Stack bottom에 `(dummy symbol, DFA start state = 0)`을 미리 push
- stack이 비어있을 때도 "현재 DFA 상태가 뭔가"를 참조할 수 있어야 하기 때문
- 비어있을 경우에는 시작 상태인 $s_0$에서 시작해야 하니까, 참조할 더미 심볼!
이를 위해 총 2개의 테이블이 필요하다
- Action
- Shift/Reduce에 대한 결정
- Goto
- DFA 구현
Reduce가 일어난 후를 생각해보면 됨
Reduce가 일어나면,
1. stack에서 우변을 pop하고
2. **NT를 push**
1. 이 NT를 push할 때 DFA 상태도 함께 저장해야 하는데, NT는 입력 token이 아니라 reduce 결과물이라서 Action table로는 처리 불가능.
그래서:
- **Action**: "지금 읽은 terminal을 보고 Shift할지 Reduce할지" 결정
- **Goto**: "Reduce 후 나온 NT를 보고 다음 DFA 상태가 어디인지" 결정
두 역할이 처리하는 입력 종류 자체가 다르기 때문에 테이블을 분리.
### 6.7.2 DFA 상태를 Stack에 함께 저장 — 필요한 Table 2개 (Action, Goto)
**Action Table** — terminal 기준, Shift/Reduce/Accept 결정
| 표기 | 의미 |
| ---- | --------------------- |
| `SN` | state N으로 shift |
| `RN` | production N으로 reduce |
| `A` | accept |
**Goto Table** — non-terminal 기준, DFA 상태 이동
|표기|의미|
|---|---|
|`GN`|state N으로 이동|
```
Production
(1) S ::= E + E
(2) E ::= [num]
(3) E ::= ( S )
```
![[스크린샷 2026-04-29 오후 12.16.13.png]]
| | Goto | | Action | | | | |
| ----- | ----- | ----- | ------ | --------- | ----- | ----- | ----- |
| State | **S** | **E** | **+** | **[num]** | **(** | **)** | **$** |
| **0** | G1 | G2 | | S3 | S4 | | |
| **1** | | | | | | | A |
| **2** | | | S5 | | | | |
| **3** | | | R2 | R2 | R2 | R2 | R2 |
| **4** | G6 | G2 | | S3 | S4 | | |
| **5** | | G7 | | S3 | S4 | | |
| **6** | | | | | | S8 | |
| **7** | | | R1 | R1 | R1 | R1 | R1 |
| **8** | | | R3 | R3 | R3 | R3 | R3 |
> 💡 State 3, 7, 8처럼 `A → γ .` (완전한 production)인 상태에서는 다음 token에 관계없이 모두 Reduce — 이것이 LR(**0**)의 의미다. lookahead 없이(0개) 결정.
**LR(k) Parsing:**
- **L**: Left-to-right으로 입력을 읽음
- **R**: Right-most derivation을 역방향으로 탐색
- **k**: Reduce 결정 시 미리 살펴보는 lookahead token의 수
|Parser|Lookahead|처리 가능 문법 범위|특징|
|---|---|---|---|
|LR(0)|0|가장 좁음|완전한 production 상태에서 무조건 Reduce|
|SLR|1 (FOLLOW)|중간|FOLLOW set으로 Reduce 조건 제한|
|LALR|1|중간~넓음|LR(1) DFA를 병합해 크기 절감|
|LR(1)|1|가장 넓음|DFA 상태 수 많아짐|
> 💡 LR(0)의 한계: `A → γ .` 형태의 item이 있는 상태에서는 다음 token을 보지 않고 항상 Reduce한다. 동일한 상태에 Shift item과 Reduce item이 공존하면 **Shift-Reduce conflict**, Reduce item이 2개 이상 공존하면 **Reduce-Reduce conflict**가 발생 → 이를 해결하는 것이 다음 강의(LR(1), SLR, LALR)의 주제다.
### 7.2.1 예제 1 — Shift/Reduce Conflict (같은 상태에 shift, reduce 모두 가능)
|State|Items|S|a|b|
|---|---|---|---|---|
|0|S' → . S, S → . a, S → . a b|1|2||
|1|S' → S .||||
|2|**S → a .** , **S → a . b**|||3|
|3|S → a b .||||
문제는 **상태 2**다. 이 상태에는 두 개의 LR(0) item이 함께 있다.
각각의 마커 위치를 보면,
- `S → a .` : 이미 handle이 완성되었으니 **reduce** 해야 한다.
- `S → a . b` : 아직 handle이 미완성이고 다음에 b가 오면 **shift** 해야 한다.
handle 완성된 게 있는데 미완성된 것도 같이 있을 경우 ㅇㅇ
같은 상태에서 두 가지 행동(shift / reduce)이 모두 가능한 상황이 **Shift/Reduce Conflict**다.
| State | Items | S | A | B | a |
| ----- | -------------------------------------------- | --- | --- | --- | --- |
| 0 | S' → . S, S → . A, S → . B, A → . a, B → . a | 1 | 2 | 3 | 4 |
| 1 | S' → S . | | | | |
| 2 | S → A . | | | | |
| 3 | S → B . | | | | |
| 4 | **A → a .** , **B → a .** | | | | |
이번에는 **상태 4**가 문제다. 두 개의 reduce 가능한 item이 함께 들어있다.
handle 완성된 게 2개일 경우 ㅌ
- `A → a .` 으로 reduce 해야 할까?
- `B → a .` 으로 reduce 해야 할까?
같은 상태에서 두 가지 reduce 후보가 존재하는 상황이 **Reduce/Reduce Conflict**다.
### 7.2.3 두 Conflict의 비교
| 구분 | Shift/Reduce Conflict | Reduce/Reduce Conflict |
| --------------- | ----------------------------------- | --------------------------- |
| 충돌하는 행동 | shift vs reduce | reduce vs reduce |
| 한 상태 안의 item 형태 | `A → α .` 와 `B → β . γ` 가 공존 | `A → α .` 와 `B → β .` 가 공존 |
| 예제 | `S ::= a \| a b` (상태 2) | `A ::= a`, `B ::= a` (상태 4) |
| SLR(1)로 해결 가능? | 일부 가능 (lookahead가 FOLLOW와 겹치지 않을 때) | 일부 가능 |
## 7.3 Shift/Reduce 충돌이 일어나면 어떻게 해야 하나? — Lookahead Token의 도입
### 7.3.1 Top-Down에서 가져온 아이디어
Top-down parsing의 LL(1)에서, `A → ε` 인 production을 안심하고 적용하기 위해 우리가 살펴본 것은 무엇이었나?
→ **FOLLOW(A)**
`A` 뒤에 올 수 있는 token이 현재 input의 다음 token과 일치할 때만 ε-production을 적용했다. 같은 아이디어를 Bottom-Up parsing에도 적용해 보자.
> ✅ Reduce action `A → γ`를 수행하려면, **lookahead token이 FOLLOW(A)에 속해야 한다**.
## 7.4 SLR(1) Parsing — Simple LR(1)
### 7.4.1 핵심 규칙
`A → γ` 를 기반으로 한 reduce 연산을 수행할 때, **FOLLOW(A)** 를 확인한다.
- lookahead token `a` 가 `a ∈ FOLLOW(A)` 일 때만 reduce!
## 8.1 SLR(1)은 항상 잘 작동할까? → 작동하지 않는 예시를 분석해보자
| State | Items | = | * | [id] | S | L | R |
| ----- | ----------------------------------------- | --- | --- | ---- | --- | --- | --- |
| 0 | S'→.S, S→.L=R, S→.R, L→.*R, L→.[id], R→.L | | 4 | 5 | 1 | 2 | 3 |
| 1 | S'→S. | | | | | | |
| 2 | S→L.=R, R→L. | 6 | | | | | |
| 3 | S→R. | | | | | | |
| 4 | L→\*.R, R→.L, L→.*R, L→.[id] | | 4 | 5 | | 7 | 8 |
| 5 | L→\[id]. | | | | | | |
| 6 | S→L=.R, R→.L, L→.*R, L→.[id] | | 4 | 5 | | 7 | 9 |
| 7 | R→L. | | | | | | |
| 8 | L→*R. | | | | | | |
| 9 | S→L=R. | | | | | | |
Action/Goto table로 펼치면:
| State | Action = | Action * | Action [id] | Goto S | Goto L | Goto R | Goto $ |
| ----- | --------- | -------- | ----------- | ------ | ------ | ------ | ------ |
| 0 | | S4 | S5 | G1 | G2 | G3 | |
| 1 | | | | | | | A |
| **2** | **S6/R5** | R5 | R5 | | | | |
| 3 | R2 | R2 | R2 | | | | |
| 4 | | S4 | S5 | | G7 | G8 | |
| 5 | R4 | R4 | R4 | | | | |
| 6 | | S4 | S5 | | G7 | G9 | |
| 7 | R5 | R5 | R5 | | | | |
| 8 | R3 | R3 | R3 | | | | |
| 9 | R1 | R1 | R1 | | | | |
**State 2, `=` 칸: S6/R5 → Shift/Reduce Conflict 발생.**
State 2는 `S → L . = R`(shift 가능)과 `R → L .`(reduce 가능)이 공존하는 상태다.
### 8.1.3 SLR(1)으로 해소를 시도하면 → 여전히 실패
SLR(1) 방식: `R → L .`으로 reduce하려면 lookahead가 `FOLLOW(R)`에 속해야 한다.
[[#5.3.1 Reduce가 필요한 타이밍 정의]]와 [[#7.4.1 핵심 규칙]] 참고.
NULLABLE / FIRST / FOLLOW를 계산하면:
| |NULLABLE|FIRST|FOLLOW|
|---|---|---|---|
|S|false|`*`, `[id]`|`