# 5. Bottom-Up Parsing (1) — Overview
## 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을 "전부 적용"
### 5.1.2 Bottom-Up Parsing — 예제
문법 `S ::= E + S | E`, `E ::= [number] | ( S )` 로 `(1 + 2) + 3` 파싱
```
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 적용]
```
```mermaid
graph TD
S["S"]
S --> E["E"]
S --> p1["＋"]
S --> S2["S"]
E --> lp["("]
E --> Si["S"]
E --> rp[")"]
Si --> Ei["E"]
Si --> p2["＋"]
Si --> Sii["S"]
Ei --> one["1"]
Sii --> Eii["E"]
Eii --> two["2"]
S2 --> E2["E"]
E2 --> three["3"]
```
### 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$로 진행.
## 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.2.4 예제: `(1 + 2) + 3` 파싱 흐름
> 마커 기준으로 왼쪽 = 스택. 오른쪽 = 아직 읽을 거 (토큰)
> stack top은 오른쪽
```
// 문법
S ::= E + S
| E
E ::= [number]
| ( S )
Marker 상태 Stack Input 연산
. ( 1 + 2 ) + 3 ( 1 + 2 ) + 3 shift (
( . 1 + 2 ) + 3 ( 1 + 2 ) + 3 shift 1
( 1 . + 2 ) + 3 ( 1 + 2 ) + 3 reduce E → [number]
// +를 shift하면 stack이 ( 1 +가 되는데, 이걸로 완성할 수 있는 P는 없음.
// 1 +로 시작하는 우변은 어디에도 없으니까.
// 반면 지금 당장 E → [number]를 적용하면 1 → E로 reduce되고,
// 이후 ( E + ...로 이어지면서
// E → ( S ) 나 S → E + S 같은
// production을 완성할 수 있는 경로가 열림
( E . + 2 ) + 3 ( E + 2 ) + 3 shift +
( E + . 2 ) + 3 ( E + 2 ) + 3 shift 2
( E + 2 . ) + 3 ( E + 2 ) + 3 reduce E → [number]
// 2를 그냥 shift하면 stack이 ( E + 2가 되는데,
// 다음 token이 )이므로 stack은 ( E + 2 )가 됨.
// 그런데 ( E + 2 )로 완성할 수 있는 production은 없음.
// E + 2 나 ( E + 2 같은 우변은 어디에도 없으니까.
// 반면 지금 E → [number]를 적용하면 2 → E로 reduce되고,
// stack이 ( E + E가 되면서
// S → E + S, S → E 같은 production을 완성할 수 있는 경로가 열림.
( E + E . ) + 3 ( E + E ) + 3 reduce S → E
// ( E + E . ) 상태에서 )를 shift하면 stack이 ( E + E )가 되는데,
// ( E + E )로 완성할 수 있는 production은 없음.
// ( E + E 같은 우변은 어디에도 없으니까.
// 반면 지금 S → E를 적용하면 E → S로 reduce되고,
// stack이 ( E + S가 되면서
// S → E + S production을 완성할 수 있는 경로가 열림.
( E + S . ) + 3 ( E + S ) + 3 reduce S → E + S
// ( E + S . ) 상태에서 )를 shift하면 stack이 ( E + S )가 되는데,
// ( E + S )로 완성할 수 있는 production은 없음.
// ( E + S 같은 우변은 어디에도 없으니까.
// 반면 지금 S → E + S를 적용하면 E + S → S로 reduce되고,
// stack이 ( S가 되면서
// E → ( S ) production을 완성할 수 있는 경로가 열림.
( S . ) + 3 ( S ) + 3 shift )
( S ) . + 3 ( S ) + 3 reduce E → ( S )
// ( S ) . 상태에서 +를 shift하면 stack이 ( S ) +가 되는데,
// ( S ) +로 완성할 수 있는 production은 없음.
// ( S ) + 같은 우변은 어디에도 없으니까.
// 반면 지금 E → ( S )를 적용하면 ( S ) → E로 reduce되고,
// stack이 E가 되면서
// S → E + S, S → E production을 완성할 수 있는 경로가 열림.
E . + 3 E + 3 shift +
E + . 3 E + 3 shift 3
E + 3 . E + 3 reduce E → [number]
// 3을 그냥 놔두면 다음 token이 $（입력 끝）이므로
// shift할 것도 없는 상황.
// 지금 E → [number]를 적용하면 3 → E로 reduce되고,
// stack이 E + E가 되면서
// S → E + S, S → E production을 완성할 수 있는 경로가 열림.
E + E . E + E reduce S → E
// E + E 상태에서 S → E를 바로 적용하면 안 됨.
// 오른쪽 E만 S로 reduce해야 하는데, 왼쪽 E까지 건드리면
// S → E + S production을 완성할 수 없게 됨.
// 오른쪽 E에만 S → E를 적용하면 E → S로 reduce되고,
// stack이 E + S가 되면서
// S → E + S production을 완성할 수 있는 경로가 열림.
E + S . E + S reduce S → E + S
// 입력이 끝났고（$）, stack에 E + S가 있음.
// 지금 S → E + S를 적용하면 E + S → S로 reduce되고,
// stack이 S 하나만 남으면서
// accept 조건（stack = [S], 입력 = $）을 만족함.
S . S accept
// stack = [S], 입력 = $ 만족 ✅
```
## 5.3. Handle → 언제 Reduce해야 하는지 확정
> §5.2에서 Shift·Reduce 연산을 정의했지만,
> "아무 때나 reduce하면 안 된다"는 문제가 남아 있다.
>
> §5.3은 그 타이밍 기준인 Handle을 정의하고,
> §6의 LR(0) Parser가 이 Handle을 자동으로 찾는 방법을 제시한다.
아무 때나 reduce하면 틀린다. 예를 들어 `( E + 2 ) + 3` 상태에서 첫 번째 `E`에 `S → E`를 바로 적용하면 `( S + 2 ) + 3`이 되고, `( S + ...` 꼴은 어떤 production 우변과도 매칭되지 않아서 오류가 난다.
### 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)에 위치
```
## 5.4 Shift-Reduce 기반 Bottom-Up Parsing 알고리즘 → Handle은 어떻게 찾지?
### 5.4.1 전체
```fsharp
입력:
(T, NT, S, P) // Grammar
tokens // Token들의 list (입력 문자열)
변수:
idx ← 0 // 현재 읽고 있는 token의 위치
stack ← [] // Marker 기준 왼쪽, 즉 지금까지 읽고 처리한 것들
while (true) do
// Stack에 S 하나만 남아있으면 파싱 성공
if len(stack) = 1 && stack.top = S then return S
else
// 현재 stack top에서 handle을 찾아봄
match tryFindHandle stack with
// handle을 찾은 경우 → Reduce
// stack top에서 발견된 우변 기호들의 리스트, 그 우변에 해당하는 production
// 예를 들어 E → ( S )라면,
// [γ₁; γ₂; ...; γₙ] = [ (; S; ); ]
// A → γ₁γ₂…γₙ = E → ( S )
| Some ([γ₁; γ₂; ...; γₙ], A → γ₁γ₂…γₙ) ->
// production 우변(γ₁…γₙ)을 stack에서 pop
// stack top부터 꺼내므로 γₙ, γₙ₋₁, ..., γ₁ 순서로 pop
for 1 ≤ i ≤ n do stack.pop()
// 우변 대신 좌변 NT(A)를 push
// 예: ( 1 → E → [number] 적용 후 ( E 가 됨
stack.push(A)
// handle을 못 찾은 경우 → Shift
| None ->
// 다음 token을 stack에 push
stack.push(tokens[idx])
// 다음 token으로 이동
idx ← idx + 1
```
> ⚠️ `tryFindHandle`을 일반적으로 효율적으로 구현하는 방법은 없다 — 일반적인 방법은 Backtracking으로 비효율적이다. §6에서 이 문제를 Viable Prefix DFA로 해결한다.
### 5.4.2 Reduce
```fsharp
// Handle: [γ₁; γ₂; ...; γₙ], A → γ₁γ₂…γₙ
// production 우변의 길이(n)만큼 pop
for 1 ≤ i ≤ n do
stack.pop() // stack top부터 꺼내므로 γₙ → γₙ₋₁ → … → γ₁ 순서로 pop
stack.push(A) // 우변을 다 꺼낸 자리에 좌변 NT를 push
```
### 5.4.3 Shift
```fsharp
stack.push(tokens[idx]) // 현재 위치의 token을 stack에 push
idx ← idx + 1 // 다음 token으로 이동
```
---
# 6. 🚨 Bottom-Up Parsing (2) — LR(0) Parser
> §5.4에서 Bottom-Up Parsing 알고리즘의 기본 틀을 보았는데,
> 여기서 Handle을 찾는 tryFindHandle의 알고리즘은 다루지 않았다.
>
> §6에서는 Handle을 효율적으로 찾기 위한 방법을 소개하고,
> 그걸 적용한 LR(0) Parser에 대해 다룬다.
## 6.1. Handle을 효율적으로 찾을 수 없다 → 관찰에 의한 Heuristic이 필요하다
> §5.3에서 Handle을 찾는 것이 bottom-up parsing의 핵심임을 확인했다.
> §6.1은 일반적 방법(Backtracking)이 비효율적이므로 heuristic이 필요함을 설명하고,
> 그 heuristic의 출발점인 Stack 관찰로 넘어간다.
일반적인 handle 탐색 방법은 Backtracking이지만 비효율적이다. 대신 **heuristic 알고리즘**을 사용한다.
- 항상 완벽하게 작동하지 않을 수 있음 (증명 X)
- 대부분의 경우 잘 작동함
- **관찰(observation)에 의해 만들어짐**
## 6.2. Stack 관찰 — Stack에는 항상 Production들의 Prefix만 존재한다 → 뭐라고 부를까?
> §6.1에서 heuristic이 관찰에 의해 만들어진다고 했다. §6.2는 그 핵심 관찰을 제시한다. 이 관찰에서 Viable Prefix 개념이 등장하고(§6.3), 이것이 Regular Language임이 밝혀지면서 FSM 기반의 LR(0) Parser(§6.4 이후)가 가능해진다.
문법 `S ::= E + E`, `E ::= [num] | ( S )` 로 `(1 + 2) + 3`을 파싱할 때의 stack:
```
문법: S ::= E + E, E ::= [num] | ( S )
입력: ( 1 + 2 ) + 3
```
| Stack | Prefix 상태 | 연산 |
| --------- | ------------------------------------------------------------------------------------------------------- | ------------------ |
| (빈) | — | shift `(` |
| `(` | `(` → `E ::= ( S )`의 prefix | shift `1` |
| `( 1` | `(` → `E ::= ( S )`의 prefix<br>`1` → `E ::= [num]`의 prefix → **완전 매칭** | reduce `E → [num]` |
| `( E` | `(` → `E ::= ( S )`의 prefix<br>`E` → `S ::= E + E`의 prefix | shift `+` |
| `( E +` | `(` → `E ::= ( S )`의 prefix<br>`E +` → `S ::= E + E`의 prefix | shift `2` |
| `( E + 2` | `(` → `E ::= ( S )`의 prefix<br>`E +` → `S ::= E + E`의 prefix<br>`2` → `E ::= [num]`의 prefix → **완전 매칭** | reduce `E → [num]` |
| `( E + E` | `(` → `E ::= ( S )`의 prefix<br>`E + E` → `S ::= E + E` → **완전 매칭** | reduce `S → E + E` |
| `( S` | `(` → `E ::= ( S )`의 prefix | shift `)` |
| `( S )` | `( S )` → `E ::= ( S )` → **완전 매칭** | reduce `E → ( S )` |
| `E` | `E` → `S ::= E + E`의 prefix | shift `+` |
| `E +` | `E +` → `S ::= E + E`의 prefix | shift `3` |
| `E + 3` | `E +` → `S ::= E + E`의 prefix<br>`3` → `E ::= [num]`의 prefix → **완전 매칭** | reduce `E → [num]` |
| `E + E` | `E + E` → `S ::= E + E` → **완전 매칭** | reduce `S → E + E` |
| `S` | — | **accept** |
**관찰 요약:**
- Stack에는 항상 production들의 prefix들이 `prefix₁ prefix₂ … prefixₙ` 형태로 존재
- ( E + 2
- 완전한 production이 될 수 있는 것은 **prefixₙ** (가장 오른쪽 prefix) — handle은 stack top에서만 발견 가능하기 때문
- 교수님 설명: 같은 맥락의 설명을 다르게 하면 다음과 같습니다: Bottom-up parsing의 shift / reduce 원칙을 잘 따라서 parsing이 수행되었다면 stack 중간에는 완전한 production이 있을 수 없습니다. 완전한 production이 stack에 있다면 shift하기 이전에 reduce가 되었어야 합니다. 그러니까 완전한 production이 될 수 있는 것은 가장 바깥쪽에 있는 prefix n만 될 수 있는거죠.
- prefixₙ이 shift를 거쳐 완전한 production이 되면 prefixₙ₋₁의 부족한 부분을 채워줌
- 채워진 형태: ( E + E
## 6.3 Viable Prefix — 아직 파싱 오류가 없다는 게 보장된, stack에 올라올 수 있는 올바른 문자열
> §6.2의 관찰에서 Stack에는 항상 올바른 prefix들만 있음을 봤다.
> §6.3은 이것을 Viable Prefix로 정의하고,
> 그 집합이 Regular Language임을 밝힌다.
>
> 이것이 §6.4에서 FSM을 구성하는 이론적 근거가 된다.
### 6.3.1 Viable Prefix — 정의
> 말로 이해하기
"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.3.3.2 그렇다면, Viable Prefix에 대한 State Machine은 어떻게 정의될까?
정의
- Production $A \to \gamma_1\gamma_2 \ldots \gamma_n$에 대한 FSM $(\Sigma, S, s_0, \delta, F)$
- $\Sigma = \{\gamma_1, \ldots, \gamma_n\} \subseteq T \cup NT$
- $S = \{A \to .\gamma_1\gamma_2 \ldots \gamma_n,\ A \to \gamma_1.\gamma_2 \ldots \gamma_n,\ \ldots,\ A \to \gamma_1\gamma_2 \ldots \gamma_n.\}$: Item들의 집합
- 만약 $A \to \epsilon$이면 Item 집합은 $\{A \to .\}$ 로 정의.
- $s_0 = A \to .\gamma_1\gamma_2 \ldots \gamma_n$
- $\delta(A \to \gamma_1 \ldots \gamma_{i-1}.\gamma_i \ldots \gamma_n,\ \gamma_{i-1}) = A \to \gamma_1 \ldots \gamma_i.\gamma_{i+1} \ldots \gamma_n$
- $F = S$ (어느 아이템에서 멈추든 viable prefix로 인정)
예시: `S → E + E` 에 대한 FSM
- $\Sigma =$ {E, +}
- $S =$ {$S \to . E + E$, $S \to E. + E$, $S \to E +. E$, $S \to E + E.$}
- $s_0$ = $S \to . E + E$
- $\delta$는 오히려 수식이 직관적이라 냅둠
- $F = S$. 모든 상태가 viable prefix로 인정.
![[스크린샷 2026-04-28 오후 2.13.15.png]]
밑에서 더 자세하게 ㄱㄱ
## 6.4. LR(0) Item과 Viable Prefix FSM 구성
> §6.3에서 viable prefix들의 집합이 Regular Language임을 확인했다.
> §6.4에서는 이를 FSM으로 실제로 구성하는 방법을 다룬다.
> 먼저 단일 production에 대한 FSM을 만들고,
> §6.5에서 여러 production을 합쳐 NFA를 만든다.
### 6.4.1. LR(0) Item
**(정의)** Production에 marker `.`로 현재 상태를 표시한 것을 **item** (혹은 **LR(0) item**)이라 한다.
$A \to \gamma_1 \dots \gamma_i . \gamma_{i+1} \dots \gamma_n$
이 item은 viable prefix $\gamma_1 \dots \gamma_i$를 인식한 상태를 나타낸다.
### 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)
**예제:** 간단해진 덧셈 문법의 모든 production을 합친 NFA
```
// 문법
S ::= E + E
E ::= [num]
| ( S )
```
![[스크린샷 2026-04-28 오후 2.28.54.png]]
## 6.5. 🚨 NFA → DFA (Subset Construction) — Viable Prefix DFA → 어떻게 활용할까?
> §6.4에서 ε-transition을 가진 NFA를 만들었다.
> §6.5에서 subset construction으로 DFA로 변환한다.
> 이 DFA가 §6.6에서 실제 parsing에 사용되고, §6.7에서 Action/Goto Table로 최적화된다.
Subset construction으로 NFA를 DFA로 변환한다. 각 DFA 상태는 NFA 상태들의 집합(closure)이다.
**예제:** 문법 `S' ::= S`, `S ::= E + E`, `E ::= [num] | ( S )` 에 대한 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 Viable Prefix DFA 활용 → Shift/Reduce 판단 → 매번 DFA를 실행시켜야 할까?
> §6.5에서 Viable Prefix DFA를 구성했다.
> §6.6에서는 이 DFA를 실제로 어떻게 써서 Shift/Reduce를 판단하는지 예제로 확인한다.
> §6.7에서는 "매번 DFA를 처음부터 돌려야 하는가"라는 비효율성을 해결한다.
### 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** |
### 6.6.2 DFA - 간단해진 덧셈 문법 예시
간단해진 덧셈 문법의 예시를 보자.
#### 문법
```
S ::= E + E
E ::= [num]
| ( S )
```
#### STEP 1 — 현재 상태와 DFA 시작
현재 파싱 상태는 `( E + . 2 ) + 3`, stack = `( E +` 이다. 이 stack을 DFA에 입력해서 현재 어느 상태에 있는지 찾아야 한다.
> 슬라이드 121 page
![[스크린샷 2026-04-28 오후 3.01.16.png]]
#### STEP 2 — stack을 DFA에 입력: `(` 읽기
State 0에서 `(`를 읽으면 State 4로 전이한다.
> 슬라이드 122 page
![[스크린샷 2026-04-28 오후 3.01.30.png]]
State 4의 items: $E \to (.S),\ S \to .E+E,\ E \to .[num],\ E \to .(S)$
State 0과 구조가 똑같아 보이는 이유는, `(`를 읽고 나서도 다시 E나 S를 기다려야 하기 때문이다.
#### STEP 3 — stack을 DFA에 입력: `E` 읽기
State 4에서 `E`를 읽으면 State 2로 전이한다.
> 슬라이드 123 page
![[스크린샷 2026-04-28 오후 3.01.44.png]]
State 2의 items: $S \to E.+E$
#### STEP 4 — stack을 DFA에 입력: `+` 읽기
State 2에서 `+`를 읽으면 State 5로 전이한다.
> 슬라이드 124 page
![[스크린샷 2026-04-28 오후 3.01.56.png]]
State 5의 items: $S \to E+.E,\ E \to .[num],\ E \to .(S)$
모든 item이 아직 `.`이 우변 끝에 없다 → **불완전한 prefix** → **Shift**
- 완성된 production = handle = reduce 가능한 상태는 `A → γ .` 처럼 `.`이 **맨 끝**에 있을 때.
> 슬라이드 124,5 page
![[스크린샷 2026-04-28 오후 3.01.56.png]]
#### STEP 5 — Shift 후 다음 상태: `2` 읽기
`2`를 shift해서 stack = `( E + 2`. 이제 DFA를 다시 돌린다.
State 5에서 `[num]`을 읽으면 State 3으로 전이한다.
> 슬라이드 126 page
![[스크린샷 2026-04-28 오후 3.02.28.png]]
#### STEP 6 — stack을 DFA에 입력: 경로 재추적
`( E + 2` 전체를 처음부터 다시 DFA에 입력하면:
State 0 → (State 4) → (State 2) → (State 5) → **State 3**
> 슬라이드 127 page
![[스크린샷 2026-04-28 오후 3.02.39.png]]
> 슬라이드 128 page
![[스크린샷 2026-04-28 오후 3.02.51.png]]
> 슬라이드 129 page
![[스크린샷 2026-04-28 오후 3.03.03.png]]
> 슬라이드 130,1 page
![[스크린샷 2026-04-28 오후 3.03.12.png]]
#### STEP 7 — State 3 도달: 완전한 Production 발견
> 슬라이드 130,1 page
![[스크린샷 2026-04-28 오후 3.03.12.png]]
State 3의 items: $E \to [num].$
`.`이 우변 끝에 있다 → **완전한 production** → **Reduce!**
$E \to [num]$ 을 적용해서 `2`를 `E`로 reduce한다.
## 6.7 DFA 상태를 Stack에 함께 저장 → Action & Goto Table
> §6.6에서 매번 DFA를 stack 처음부터 돌려야 했다.
> §6.7은 "같은 prefix에 대해서는 항상 같은 DFA 상태가 나온다"는 사실을 이용해
> DFA 상태를 stack element에 함께 저장하는 최적화를 도입한다.
>
> 이를 통해 Action Table과 Goto Table이 만들어지고,
> §6.8의 최종 LR(0) Parsing 알고리즘으로 완성된다.
### 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으로 이동|
### 6.7.3 Action & Goto Table — 예제
![[스크린샷 2026-04-28 오후 3.16.37.png]]
```
Production
(1) S ::= E + E
(2) E ::= [num]
(3) E ::= ( S )
```
| | 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개) 결정.
## 6.8 LR(0) Parsing 알고리즘
> §6.7에서 Action/Goto Table을 구성했다. §6.8은 이 Table을 이용한 최종 LR(0) Parsing 알고리즘을 제시한다. 이 알고리즘은 §5.4의 일반 알고리즘을 Table 기반으로 최적화한 것이다.
```fsharp
입력:
(T, NT, S, P) // Grammar
tokens // Token들의 list
Action // Action Table: Map<State, Map<T, Action>>
Goto // Goto Table: Map<State, Map<NT, State>>
변수:
idx ← 0 // 현재 Token 위치
stack ← [(_, 0)] // Stack bottom에 (dummy, start state) 미리 push
while (true) do
(symb, state) ← stack.top
token ← tokens[idx]
if Action[state][token] = 'A' then
return // Accept
elif Action[state][token] = 'SN' then
// Shift: state N으로 이동
stack.push((token, N))
idx ← idx + 1
elif Action[state][token] = 'RN' then
// Reduce: RN이 A ← γ₁ … γₙ이라면
for 1 ≤ i ≤ n do
stack.pop()
(_, state') ← stack.top
M ← Goto[state'][A]
stack.push((A, M))
else
raise Error
```
**예제: `(1+2)+3` 파싱 trace (문법: `S::=E+E`, `E::=[num]|(S)`)**
```
Stack (symbol, state) Input Action
─────────────────────────────────────────────────────────────
(_, 0) (1+2)+3$ S4 → push ((, 4)
(_, 0)( 4) 1+2)+3$ S3 → push (1, 3)
(_, 0)( 4)(1, 3) +2)+3$ R2 → pop 1개, Goto[4][E]=2, push (E,2)
(_, 0)( 4)(E, 2) +2)+3$ S5 → push (+, 5)
(_, 0)( 4)(E, 2)(+, 5) 2)+3$ S3 → push (2, 3)
(_, 0)( 4)(E, 2)(+, 5)(2, 3) )+3$ R2 → pop 1개, Goto[5][E]=7, push (E,7)
(_, 0)( 4)(E, 2)(+, 5)(E, 7) )+3$ R1 → pop 3개, Goto[4][S]=6, push (S,6)
(_, 0)( 4)(S, 6) )+3$ S8 → push (), 8)
(_, 0)( 4)(S, 6)(), 8) +3$ R3 → pop 3개, Goto[0][E]=2, push (E,2)
(_, 0)(E, 2) +3$ S5 → push (+, 5)
(_, 0)(E, 2)(+, 5) 3$ S3 → push (3, 3)
(_, 0)(E, 2)(+, 5)(3, 3) $ R2 → pop 1개, Goto[5][E]=7, push (E,7)
(_, 0)(E, 2)(+, 5)(E, 7) $ R1 → pop 3개, Goto[0][S]=1, push (S,1)
(_, 0)(S, 1) $ A → Accept
```
## 6.9 LR(k) Parsing과 LR(0)의 한계
> §6.8에서 LR(0) Parsing 알고리즘을 완성했다.
> §6.9은 LR(0)가 "lookahead 0개"로 동작하기 때문에
> 모든 문법을 처리할 수 없음을 정리하고,
> 다음 강의에서 다룰 LR(1), SLR, LALR의 방향을 제시한다.
**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)의 주제다.
## 6.10 LL(1) vs LR(0) 비교
> (개인 정리) §5~6에서 다룬 LR(0)와 이전 강의에서 다룬 LL(1)을 핵심 차원에서 비교한다.
| 비교 항목 | LL(1) | LR(0) |
| -------------- | ------------------------------ | ---------------------------- |
| 방향 | Top-down | Bottom-up |
| Derivation | Left-most | Right-most (역순) |
| Lookahead | 1 | 0 |
| Table 구성 | FIRST / FOLLOW | Viable Prefix DFA |
| Left-recursion | ❌ 불가 (right-recursion으로 변환 필요) | ✅ 처리 가능 (별 상관 ㄴ bottom-up이라) |
| 처리 가능 문법 범위 | 상대적으로 좁음 | LL(1)보다 넓음 |
| Stack 내용 | 아직 파생할 NT | 지금까지 읽은 viable prefix |
---
# 7. Bottom-Up Parsing (3) - SLR(1) Parser
## 7.1 이번 장에서 다루는 내용
> 이전 장(LR(0))에서 우리는 Viable Prefix DFA를 만들고,
> 이를 바탕으로 Action / Goto Table을 구성하여
> Shift-Reduce parsing을 자동화하는 방법을 배웠다.
>
> 그런데 LR(0)는 한 가지 큰 가정을 깔고 있었다
> "DFA의 각 상태에서 해야 할 행동(shift인지 reduce인지)이 항상 명확히 하나로 결정된다"는 것.
>
> 이번 장에서는 그 가정이 깨지는 경우, 즉 **Conflict**가 발생하는 상황을 살펴보고,
> 그것을 lookahead 한 글자로 해결하는 **SLR(1) Parser**를 다룬다.
>
> SLR(1)은 다음 장에서 배울 본격적인 LR(1) 파서로 가기 위한 디딤돌이기도 하다.
- LR(0) 파서에서 발생할 수 있는 Conflict
- Shift/Reduce Conflict
- Reduce/Reduce Conflict
- SLR(1) Parsing
- Shift/Reduce Conflict를 해결할 수 있는 Heuristic
## 7.2 LR(0)는 항상 잘 작동할까? — Conflict의 발견
> 💡 LR(0)는 stack의 상태(= Viable Prefix DFA의 상태)만 보고 shift/reduce를 결정한다. 이 정보가 부족한 경우가 있을 수 있는데, 그것이 바로 **Conflict**다.
### 7.2.1 예제 1 — Shift/Reduce Conflict (같은 상태에 shift, reduce 모두 가능)
다음 문법을 보자.
```
S' ::= S
S ::= a
| a b
```
LR(0) Item을 이용해 Viable Prefix FSM을 만들고, ε-transition은 `A → α . B β`와 `B → γ` 사이에 추가한다.
초기: 세 개 따로
![[스크린샷 2026-04-28 오후 5.05.22.png]]
여기에 ε-transition을 추가해 연결하면 이렇게 된다
![[스크린샷 2026-04-28 오후 5.06.26.png]]
이건 NFA니, Subset Construction으로 DFA를 만들면:
![[스크린샷 2026-04-28 오후 5.06.45.png|440]]
|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** 해야 한다.
같은 상태에서 두 가지 행동(shift / reduce)이 모두 가능한 상황이 **Shift/Reduce Conflict**다.
### 7.2.2 예제 2 — Reduce/Reduce Conflict (같은 상태에 두 가지 reduce 후보)
다음 문법을 보자.
```
S' ::= S
S ::= A
| B
A ::= a
B ::= a
```
초기: 5개 따로
![[스크린샷 2026-04-28 오후 5.08.02.png]]
epsilon transition 추가한 NFA 상태
![[스크린샷 2026-04-28 오후 5.08.47.png]]
DFA로 변환하면:
![[스크린샷 2026-04-28 오후 5.09.04.png|434]]
| 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이 함께 들어있다.
- `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.2에서 우리는 LR(0)의 한계를 보았다.
> stack 상태(= DFA 상태)만으로는 행동을 결정할 수 없는 경우가 있다는 것.
> 그렇다면 한 가지 정보를 더 보면 어떨까?
> 바로 **다음에 올 token(lookahead)**이다.
> 이 아이디어는 사실 우리가 이미 Top-Down parsing에서 본 적이 있다.
### 7.3.1 Top-Down에서 가져온 아이디어
Top-down parsing의 LL(1)에서, `A → ε` 인 production을 안심하고 적용하기 위해 우리가 살펴본 것은 무엇이었나?
→ **FOLLOW(A)**
`A` 뒤에 올 수 있는 token이 현재 input의 다음 token과 일치할 때만 ε-production을 적용했다. 같은 아이디어를 Bottom-Up parsing에도 적용해 보자.
### 7.3.2 예제 1로 직관 잡기 — Shift는 언제? Reduce는 언제?
다시 [[#7.2.1 예제 1 — Shift/Reduce Conflict (같은 상태에 shift, reduce 모두 가능)]]로 돌아가, 충돌이 일어나는 상태 2에서 어떤 입력이 들어왔을 때 shift / reduce가 옳은지 생각해 보자.
![[스크린샷 2026-04-28 오후 5.06.45.png|440]]
**Shift가 옳은 경우 — 입력이 `a . b
일 때**
```
입력: a . b $
스택 상태: 2 (S → a . / S → a . b)
다음 token: b
→ b가 들어오면 a b로 가서 S → a b 로 reduce 해야 하므로 SHIFT
```
**Reduce가 옳은 경우 — 입력이 `a .
일 때**
```
입력: a . $
스택 상태: 2 (S → a . / S → a . b)
다음 token: $
→ $는 입력의 끝, S로 환원하고 끝내야 하므로 S → a 로 REDUCE
```
핵심은 — **lookahead가 b이면 shift**, **lookahead가 \$이면 reduce**. 그리고 `
는 정확히 `FOLLOW(S)`에 들어있는 token이다.
### 7.3.3 개선된 Parsing 알고리즘 — FOLLOW 확인 → 이걸 뭐라고 부를까?
LR(0)의 reduce 결정에 한 가지 조건을 추가한다.
> ✅ Reduce action `A → γ`를 수행하려면, **lookahead token이 FOLLOW(A)에 속해야 한다**.
예제 1에 적용해보면, `S`에 대한 NULLABLE / FIRST / FOLLOW는:
| |NULLABLE|FIRST|FOLLOW|
|---|---|---|---|
|S|false|a|$|
상태 2에서:
- `S → a .` 으로 reduce는 lookahead가 `
일 때만 (∵ FOLLOW(S) = {$})
- `S → a . b` 의 shift는 lookahead가 `b`일 때만
서로 겹치지 않으므로 충돌 해소!
## 7.4 SLR(1) Parsing — Simple LR(1)
> 💡
> §7.3의 아이디어를 정식 알고리즘으로 정리한 것이 SLR(1) 파서다.
> 이름이 "Simple" LR(1)인 이유는,
> LR(0)의 자료구조(Viable Prefix DFA, Action/Goto Table)는 그대로 두고
> **reduce 시점에 FOLLOW 한 번 더 보는** 아주 작은 변경만 가했기 때문이다.
### 7.4.1 핵심 규칙
`A → γ` 를 기반으로 한 reduce 연산을 수행할 때, **FOLLOW(A)** 를 확인한다.
- lookahead token `a` 가 `a ∈ FOLLOW(A)` 일 때만 reduce!
### 7.4.2 알고리즘 — 입력과 변수
```
입력:
(T, NT, S, P) // Grammar
tokens // Token들의 list
FOLLOW // FOLLOW Table: Map<NT, Set<T>>
Action // Action Table: Map<State, Map<T, Set<Action>>>
Goto // Goto Table: Map<State, Map<NT, State>>
변수:
idx ← 0 // 현재 Token 위치
stack ← [(_, 0)] // Stack (symbol, state)
```
LR(0)와 비교했을 때 새로 추가된 입력은 `FOLLOW` 하나뿐이다.
### 7.4.3 알고리즘 — 메인 루프
[[#6.7 DFA 상태를 Stack에 함께 저장 → Action & Goto Table]] 참고해 비교해 보자.
```
while (true) do
symb, state ← stack.top // 스택의 top에서 (심볼, 상태) 쌍을 읽음 (pop 아님, peek)
token ← tokens[idx] // 현재 lookahead token (아직 소비하지 않음)
if Action[state][token] ∋ 'A' then
return // Accept: 입력을 모두 읽고 시작 심볼로 reduce 완료 → 파싱 성공
// ── SLR(1)과 LR(0)의 유일한 차이점 ──────────────────────────────────
// LR(0): Reduce item이 있으면 lookahead에 무관하게 무조건 Reduce
// SLR(1): Reduce item이 있어도 token ∈ FOLLOW(A) 일 때만 Reduce
// → lookahead를 한 번 더 확인하여 불필요한 Reduce를 방지
elif Action[state][token] ∋ 'RN' &&
token ∈ FOLLOW(A) then
// RN: production rule N 번으로 reduce
// A ← γ₁ γ₂ … γₙ (우변 길이 n만큼 스택에서 pop 후 A를 push)
goto Reduce
elif Action[state][token] ∋ 'SN' then
// SN: state N으로 shift
// 현재 token을 소비(idx++)하고 (token, N)을 스택에 push
goto Shift
else
raise Error // 위 세 경우 모두 해당 없음 → 문법 오류
```
LR(0) 알고리즘과의 유일한 차이는 첫 elif 블럭 — `token ∈ FOLLOW(A)` 검사가 추가되었다는 점이다. 참고: [[#6.7.3 Action & Goto Table — 예제]] 맨 마지막 인용부분 참고.
### 7.4.4 알고리즘 — Shift 동작
```
// Action[state][token] = 'SN'
stack.push((token, N))
idx ← idx + 1
```
현재 token을 stack에 쌓고, 상태 N으로 전이하며, 입력 포인터를 한 칸 전진시킨다.
### 7.4.5 알고리즘 — Reduce 동작
```
// Action[state][token] = 'RN'
// RN: A ← γ₁ … γₙ
for 1 ≤ i ≤ n do
stack.pop()
_, state ← stack.top
M ← Goto[state][A]
stack.push((A, M))
```
handle을 이루는 n개의 symbol을 stack에서 pop하고, 새로 드러난 stack top의 상태에서 Goto table을 참조해 non-terminal A로 전이한 새 상태 M을 push한다.
## 7.5 SLR(1) 적용 예제 — 덧셈 문법 심화
> 💡 복잡한 문법에서 SLR(1)이 어떻게 Shift/Reduce Conflict를 해소하는지 살펴보자.
### 7.5.1 문법 정의
```
(1) S ::= E + S
(2) | E
(3) E ::= [number]
(4) | ( S )
```
### 7.5.2 NULLABLE / FIRST / FOLLOW 계산
| |NULLABLE|FIRST|FOLLOW|
|---|---|---|---|
|S|false|[num], (|$, )|
|E|false|[num], (|$, +, )|
`E`의 FOLLOW에 `+`가 포함된 이유: `S → E + S`에서 E 바로 뒤에 `+`가 올 수 있기 때문이다.
### 7.5.3 Viable Prefix DFA 구성
초기에 epsilon transition 추가하면
![[스크린샷 2026-04-28 오후 6.33.00.png]]
NFA이므로 Subset Construction으로 DFA로 바꾸면
![[스크린샷 2026-04-28 오후 6.32.45.png]]
|State|주요 Items|
|---|---|
|0|`S' → . S`, `S → . E + S`, `S → . E`, `E → . [num]`, `E → . ( S )`|
|1|`S → E . + S`, **`S → E .`** ← Conflict 발생 상태|
|2|`S → E + . S`, `S → . E + S`, `S → . E`, `E → . [num]`, `E → . ( S )`|
|3|`S → E + S .`|
|4|`E → [num] .`|
|5|`E → ( . S )`, `S → . E + S`, `S → . E`, `E → . [num]`, `E → . ( S )`|
|6|`E → ( S . )`|
|7|`E → ( S ) .`|
**상태 1**에서 `S → E . + S`(shift 가능)와 `S → E .`(reduce 가능)가 공존 → **Shift/Reduce Conflict**.
### 7.5.4 SLR(1)으로 Conflict 해소
![[스크린샷 2026-04-28 오후 6.41.18.png]]
| |NULLABLE|FIRST|FOLLOW|
|---|---|---|---|
|S|false|[num], (|$, )|
|E|false|[num], (|$, +, )|
Conflict가 발생하는 상태 1에서 SLR(1) 규칙을 적용한다.
- `S → E .` 로 **reduce**하려면 lookahead가 `FOLLOW(S) = {$, )}`에 속해야 한다.
- `S → E . + S` 의 **shift**는 lookahead가 `+`일 때만 발동한다.
| lookahead | 행동 |
| ---------- | ------------------------------------ |
| `+` | Shift (다음에 `+`가 오면 `E + S` 형태가 계속된다) |
| `
or `)` | Reduce `S → E` |
이렇게 충돌이 해소된다.
![[스크린샷 2026-04-28 오후 6.41.30.png]]
빨간 상태에서 `E`를 받으면 conflict 상태(`S → E . + S` / `S → E .`)에 도달한다.
여기서 lookahead가 `+`이면 shift, lookahead가 `FOLLOW(S) = {$, )}`에 속하면 `S → E`로 reduce한다.
### 7.5.5 `(1 + 2) + 3` 파싱 trace with SLR(1)
아래는 상태 번호를 포함한 상세 trace다. `(state, symbol)` 쌍으로 stack을 표현한다.
```
Stack Input Action
─────────────────────────────────────────────────
(_, 0) (1+2)+3$ Shift ( → state 5
(_, 0)(( ,5) 1+2)+3$ Shift [1] → state 4
(_, 0)((,5)(1,4) +2)+3$ Reduce E→[num]; Goto[5][E]=? → push E
(_, 0)((,5)(E,…) +2)+3$ Shift + → …
… … (계속)
(_, 0)(E, 1) +3$ Shift + → state 2
(_, 0)(E,1)(+,2) 3$ Shift [3] → state 4
(_, 0)(E,1)(+,2)(3,4) $ Reduce E→[num]
(_, 0)(E,1)(+,2)(E,…) $ Reduce S→E (lookahead=$∈FOLLOW(S))
(_, 0)(E,1)(+,2)(S,3) $ Reduce S→E+S
(_, 0)(S, …) $ Accept
```
이처럼 SLR(1)은 lookahead 하나를 참조함으로써 LR(0)가 해결하지 못했던 Shift/Reduce Conflict를 올바르게 처리한다.
> 근데 이 좋은 걸 두고 왜 또 배우냐? 다음 장에 한계 나옴.
---
# 8. Bottom-Up Parsing (4) — LR(1) Parser
## 8.1 SLR(1)은 항상 잘 작동할까? → 작동하지 않는 예시를 분석해보자
> §7에서 SLR(1)은 LR(0)의 DFA를 그대로 두고
> reduce 시점에 `token ∈ FOLLOW(A)` 조건만 추가해서 conflict를 해소했다.
> 그런데 이 방식이 언제나 통하는 건 아니다.
>
> §8.1에서는 SLR(1)조차 실패하는 구체적인 예제를 보고,
> §8.2에서 그 근본 원인을 진단한다.
### 8.1.1 대입 문법 — LR(0) DFA 구성
다음 문법으로 실험한다.
```
(1) S ::= L = R
(2) | R
(3) L ::= * R
(4) | [id]
(5) R ::= L
```
LR(0) item으로 Viable Prefix DFA를 구성하면:
초기 + epsilon transition
![[스크린샷 2026-04-28 오후 7.30.51.png]]
Subset Construction으로 DFA 전환
![[스크린샷 2026-04-28 오후 7.31.12.png]]
| 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]`|`
|
|L|false|`*`, `[id]`|`
, `=`|
|R|false|`*`, `[id]`|`
, `=`|
스택 관련해서는 [[#6.7.1 아이디어 — DFA 상태를 Stack에 함께 저장]] 참고.
**16p**: 아무것도 안 읽은 초기 상태. 스택 비어있음. 상태 0번에 가 있음. 입력은 `a = b`.
스택: (\_, 0)
**17-18p**: `a`를 읽음. `a`는 `[id]`이므로 `L → [id] .` 상태에 도달. 스택엔 `a`가 쌓임. 그리고 이 상태는 **reduce item** — `L → [id] .` 이므로 SLR(1)은 reduce 여부를 판단해야 함. FOLLOW(L) = `{$, =}` 이고 다음 lookahead가 `=` 이므로 **`= ∈ FOLLOW(L)` → L로 reduce.** 스택: `L`. `L`을 쌓았으니 FOLLOW 테이블에서 `L`의 FOLLOW인 `{$, =}`가 하이라이트. 방금 이걸 근거로 reduce함.
스택: (\_, 0) (a, 5)
reduce 뒤에 (\_, 0) (L, 2)
**19p-20**: `L`로 reduce됐으니 이제 다시 stack에서 (L, 2) 빼서 0에서 시작해서 L 받고 2로 `S → L . = R` / `R → L .` 상태(분홍 테두리)에 도달. 스택: `L`. SLR(1)은 또 판단 — 다음 lookahead가 `=`이고 **FOLLOW(R) = `{$, =}`** 이므로 `= ∈ FOLLOW(R)` → **`R → L .`로 reduce.** 스택: `R` 위에 `L`. R로 reduce됐으니 이번엔 FOLLOW(R) = `{$, =}` 하이라이트. 방금 이걸 근거로 reduce했다는 것.
스택: (\_, 0) (L, 2)
reduce 뒤에 (\_, 0) (R, 3)
**21p**: "뭔가 이상한데요?" — R로 reduce한 결과 스택엔 `R`만 남았는데, 다음 입력이 `=`. 근데 `R = ...` 을 처리할 수 있는 production이 문법 어디에도 없음. 3에서도 처리 못함. **막힘.**
---
## 8.2 SLR(1) 실패의 근본 원인 — LR(0) item 기반 Follow Set 과근사 → 다른 item을 사용해야 한다
> §8.1에서 SLR(1)이 대입 문법에서 실패함을 확인했다.
> §8.2에서는 왜 구조적으로 이 문제가 생길 수밖에 없는지를 분석한다.
>
> 이 진단이 §8.3의 LR(1) 도입 동기가 된다.
### 8.2.1 `a = b`는 올바른 문장 — 올바른 parse tree가 존재한다
```
(1) S ::= L = R
(2) | R
(3) L ::= * R
(4) | [id]
(5) R ::= L
```
`a = b`는 이 문법에서 올바른 문장이다. 유도 과정:
```
S → L = R
→ [id] = R (a = R)
→ [id] = L (a = L)
→ [id] = [id] (a = b)
```
올바른 parse tree:
```
올바른 tree: SLR(1)이 시도하는 tree:
S S
/|\ |
L = R R = b ← R 뒤에 =가 오므로 막힘
| | |
[a] L L
| |
[b] [a]
```
SLR(1) 파서는 `a`를 읽고 State 2에 도달한 뒤, lookahead `=`를 보고 `FOLLOW(R) = {$, =}` 때문에 `R → L .`로 reduce해버린다. 그 결과 오른쪽 tree를 만들려 하지만, `R` 뒤에 `=`가 오는 경로는 이 문법에 없으므로 파싱 불가.
### 8.2.2 FOLLOW(R)에 왜 `=`가 들어갔나? 과하게 근사했기 때문.
R 뒤에 '항상' 따라오는 문자 집합이 아닌, '경우에 따라' 따라오는 문자 집합이기 때문.
- `= ∈ FOLLOW(R)`인 이유: `R ::= L`이고 `L`의 FOLLOW에 `=`가 있기 때문
- `L`의 FOLLOW에 `=`가 있는 이유: `S ::= L = R`에서 `L` 바로 뒤에 `=`가 오기 때문
즉 **`=`가 R 뒤에 오는 게 아니라 L 뒤에 오는 것**인데, `R ::= L`이라는 파생 관계 때문에 FOLLOW가 섞여버린 것이다.
실제로:
- `* R = R` — `L ::= * R`이므로 `*R`이 L 역할, 그 뒤 `=`가 옴 (ok)
- `R = R` — 이런 production은 없다 (no)
FOLLOW set은 **"어떤 문맥에서든 한 번이라도 뒤에 올 수 있는 token을 모두 모은 것"** 이기 때문에, 문맥에 따라 달라지는 lookahead를 표현하기엔 너무 부정확하다.
### 8.2.3 SLR(1)의 근본적 문제 — LR(0) item 기반이다
"LR(0) item 기반"인 것이 근본적 문제.
| 문제 | 설명 |
| ------------------------- | ------------------------------------ |
| DFA 설계 시 lookahead 미고려 | Viable Prefix DFA가 LR(0) item만으로 구성됨 |
| Reduce 조건에 부정확한 FOLLOW 사용 | 상황에 따라 FOLLOW가 달라질 수 있음을 인식 불가 |
| 결론 | DFA 자체를 lookahead를 고려해서 다시 설계해야 함 |
> 💡 SLR(1)은 "DFA는 그대로, table 채우는 방식만 변경"이었다.
> LR(1)은 여기서 한발 더 나아가 **DFA 설계 단계부터** lookahead를 반영한다.
---
## 8.3 LR(1) Item — Lookahead를 Item에 내재화
> §8.2에서 문제의 핵심은
> "어떤 문맥에서 이 rule을 reduce해도 되는가"를
> item 수준에서 표현하지 못한다는 것이었다.
>
> §8.3에서는 lookahead token을
> item의 구성 요소로 포함시킨 LR(1) item을 도입한다.
>
> 이를 기반으로 §8.4에서 conflict-free DFA를 새로 구성한다.
### 8.3.1 LR(0) Item vs LR(1) Item
| 구분 | 표현 | reduce 조건 |
| ---------- | ---------------------- | ---------------------- |
| LR(0) item | `L → [id] .` | 무조건 reduce |
| SLR(1) | `L → [id] .` (DFA는 동일) | `token ∈ FOLLOW(L)` |
| LR(1) item | `L → [id] . , =` | lookahead가 정확히 `=`일 때만 |
| LR(1) item | `L → [id] . ,
| lookahead가 정확히 `
일 때만 |
**타입**: `LR1Item = LR0Item × T` — LR(0) item과 terminal token의 쌍
### 8.3.2 LR(1) Item의 정의 — LR(0) item과 terminal token의 쌍 → LR(1) Item 기반 VP DFA를 만들면 LR(1) Parser → 그런데, LR(1) Item은 어떻게 계산할까?
`type LR1Item = LR0Item × T` — LR(0) item과 terminal token의 쌍
`A → α . β , a` 형태에서:
- `α` : 현재 stack top에 존재하는 부분
- `βa` : 남은 입력은 `βa`로부터 유도된 문자열을 prefix로 가짐
- **`A → αβ`를 reduce하고 나면, 남은 입력의 제일 처음은 반드시 `a`여야 한다**
dot 위치별 의미:
```
A → . αβ , a
// αβ를 인식하기 위해 대기 중인 상태
// 지금까지 읽은 입력은 A → αβ로 reduce하기에 문제 없는 상태
A → α . β , a
// α까지 인식, 아직 β가 남음
// 지금까지 읽은 입력은 A → αβ로 reduce하기에 문제 없는 상태
// α까지 인식
A → αβ . , a
// αβ를 전부 인식했고, 다음 token이 a이면 reduce 가능
// 지금까지 읽은 입력은 A → αβ로 reduce하기에 문제 없는 상태
// αβ까지 인식
// lookahead token이 a이면 reduce할 수 있는 상태
```
**예**: `(L → [id] . , =)` — `[id]`까지 읽었고, 이걸 `L`로 reduce하려면 다음 token이 반드시 `=`여야 한다.
### 8.3.3 LR(1) Item 계산 — Lookahead 계산 아이디어: `(S' → . S , $)`로부터 시작해,
LR(1) item `(A → α . β , a)`가 주어졌을 때:
- $\alpha$를 읽었고,
- 그 다음에 올 입력은 $\beta a$로부터 유도되어야 함
- 즉, $\alpha$까지 읽었을 때, 다음에 올 첫 입력은 FIRST($\beta a$)
- 그냥 FIRST의 정의를 생각하면, "어떤 문자열에서 맨 처음 나올 수 있는 terminal들의 집합"이니까 말이 됨.
LR(1) item `(A → α . Bβ , a)`가 주어졌을 때:
> B는 non-terminal이니까 실제 입력에서 읽히려면
> **어떤 production으로 전개**되어야 함.
> 그 전개의 시작점이 `(B → . γ , b)` 인데,
> 이때 lookahead b가 뭐가 될지는 —
> "B를 다 읽고 난 뒤 다음에 올 수 있는 첫 terminal이 뭔가"로 결정.
B 뒤에는 β가 오고, β 뒤에는 a가 오니까, B 다음에 올 수 있는 첫 terminal = FIRST(βa).
그래서 `b ∈ FIRST(βa)` 인 모든 b에 대해 `(B → . γ , b)` 가 유효한 LR(1) item이 되는 거예요.
- `b ∈ FIRST(βa)` — β 이후에 a가 올 때 나올 수 있는 첫 token들에 대해
- `(B → . γ , b)` 는 유효한 LR(1) Item
> 💡 예: `(L → * . R , =)`가 주어지면, R production 전개 시 lookahead는 `FIRST(ε · =) = {=}`이므로 `(R → . L , =)`가 유효한 LR(1) item.
시작점: `(S' → . S , $)` — 이것으로부터 전체를 전개한다.
## 8.4 LR(1) DFA 구성 — 대입 문법 예제
> §8.3에서 LR(1) item의 lookahead 계산 방법을 파악했다. §8.4에서는 실제로 대입 문법에 적용해 LR(1) DFA를 구성하고, §8.5에서 Parsing Table로 변환한다.
### 8.4.1 LR(0) → LR(1)에서 일어나는 일
LR(0)에서는 item `L → . * R` 하나였던 것이, LR(1)에서는 **lookahead에 따라 분리**된다:
```
LR(0): L → . * R (하나)
LR(1): (L → . * R , =) (= 가 뒤에 올 문맥)
(L → . * R , $) ($ 가 뒤에 올 문맥)
```
이것이 더 정밀한 lookahead 구분의 핵심이다.
### 8.4.2 LR(1) DFA 전체 구성 (대입 문법)
`(S' → . S , $)` 출발
#### Step 0. 시작점
> 슬라이드 40
시작 item: (S' → . S , $)
```
[경우2 — dot 다음이 NT S]
rule: b ∈ FIRST(βa) 인 모든 b에 대해 (S → . γ , b) 추가
```
β = ε (S 뒤에 아무것도 없음), a = $
→ FIRST(ε · \$) = {$}
→ b = $ 하나
→ S의 production 전개:
(S → . L = R , $)
(S → . R , $)
S를 읽으면 → (S' → S . , $) \[일반 transition]
$\epsilon$ → (S → . L = R , \$) \[$\epsilon$ transition]
#### Step 1. (S → . L = R , $) 처리
> 슬라이드 41
```
[경우2 — dot 다음이 NT L]
rule: b ∈ FIRST(βa) 인 모든 b에 대해 (L → . γ , b) 추가
```
β = = R, a = $
→ FIRST(= R · $) = {=} ← = 가 terminal이므로 바로 결정
→ b = = 하나
→ L의 production 전개:
(L → . * R , =)
(L → . \[id] , =)
L을 읽으면 → (S → L . = R , $) \[일반 transition]
= 를 읽으면 → (S → L = . R , $) \[일반 transition]
R을 읽으면 → (S → L = R . , $) \[경우1 — reduce item, lookahead $ 일 때만 reduce]
#### Step 2. (S → . R , $) 처리
> 슬라이드 42
\[경우2 — dot 다음이 NT R]
rule: b ∈ FIRST(βa) 인 모든 b에 대해 (R → . γ , b) 추가
β = ε, a = $
→ FIRST(ε · \$) = {$}
→ b = $ 하나
→ R의 production 전개:
(R → . L , $)
R을 읽으면 → (S → R . , $) \[경우1 — reduce item, lookahead $ 일 때만 reduce]
#### Step 3. (L → . * R , =) 처리
> 슬라이드 43
* 를 읽으면 → (L → * . R , =) \[일반 transition]
\[경우2 — dot 다음이 NT R]
rule: b ∈ FIRST(βa) 인 모든 b에 대해 (R → . γ , b) 추가
β = ε, a = =
→ FIRST(ε · =) = {=}
→ b = = 하나
→ R의 production 전개:
(R → . L , =)
R을 읽으면 → (L → * R . , =) \[경우1 — reduce item, lookahead = 일 때만 reduce]
#### Step 4. (R → . L , =) 처리
> 슬라이드 43~44
\[경우2 — dot 다음이 NT L]
rule: b ∈ FIRST(βa) 인 모든 b에 대해 (L → . γ , b) 추가
β = ε, a = =
→ FIRST(ε · =) = {=}
→ b = = 하나
→ L의 production 전개:
(L → . * R , =) ← 이미 Step 1에서 추가됨, 중복이므로 skip
(L → . \[id] , =) ← 이미 Step 1에서 추가됨, 중복이므로 skip
L을 읽으면 → (R → L . , =) \[경우1 — reduce item, lookahead = 일 때만 reduce]
#### Step 5. (L → . \[id] , =) 처리
> 슬라이드 44
\[경우1 — dot 다음이 terminal \[id]]
별도 expand 없음. 그냥 transition만.
\[id] 를 읽으면 → (L → \[id] . , =) \[경우1 — reduce item, lookahead = 일 때만 reduce]
#### Step 6. (R → . L , $) 처리
> 슬라이드 45~46
\[경우2 — dot 다음이 NT L]
rule: b ∈ FIRST(βa) 인 모든 b에 대해 (L → . γ , b) 추가
β = ε, a = $
→ FIRST(ε · \$) = {$}
→ b = $ 하나
→ L의 production 전개:
(L → . * R , $) ← Step 1의 = 버전과 별개! lookahead가 다름
(L → . \[id] , $) ← 마찬가지
L을 읽으면 → (R → L . , $) \[경우1 — reduce item, lookahead $ 일 때만 reduce]
※ 핵심: LR(0)에서는 R → L . 하나였는데
LR(1)에서는 (R → L . , =) 와 (R → L . , $) 로 분리됨
→ = 가 왔을 때 reduce하지 않아도 되는 문맥을 구분할 수 있게 됨
→ SLR(1)의 conflict 해소
#### Step 7. (L → . * R , $) 처리
> 슬라이드 47~48
* 를 읽으면 → (L → * . R , $) \[일반 transition]
\[경우2 — dot 다음이 NT R]
rule: b ∈ FIRST(βa) 인 모든 b에 대해 (R → . γ , b) 추가
β = ε, a = $
→ FIRST(ε · \$) = {$}
→ b = $ 하나
→ R의 production 전개:
(R → . L , $) ← 이미 Step 2에서 추가됨, 중복이므로 skip
R을 읽으면 → (L → * R . , $) \[경우1 — reduce item, lookahead $ 일 때만 reduce]
#### Step 8. (L → . \[id] , $) 처리
> 슬라이드 49
\[경우1 — dot 다음이 terminal \[id]]
별도 expand 없음. 그냥 transition만.
\[id] 를 읽으면 → (L → \[id] . , $) \[경우1 — reduce item, lookahead $ 일 때만 reduce]
#### Step 9. 재귀 구조 확인 — 전체 완성
> 슬라이드 50~52
L → . * R 에서 * 를 읽으면 L → * . R 이 되고,
거기서 R → . L 이 나오고,
거기서 다시 L → . * R , L → . \[id] 가 나오는 재귀가 발생.
단, 이미 추가된 item은 중복 추가하지 않으므로 종료 보장.
= lookahead 라인과 $ lookahead 라인이 병렬로 전개되면서
일부 transition에서 같은 상태로 합류 — 이것이 최종 LR(1) DFA의 구조.
![[스크린샷 2026-04-29 오전 12.19.41.png]]
LR(0)과 비교해보자.
![[스크린샷 2026-04-29 오전 12.20.04.png]]
### 8.4.3 LR(1) Item 구하는 알고리즘
```pseudo
입력:
(T, NT, S, P) // Grammar
FIRST // Map<T ∪ NT, Set<T>>
변수:
Items ← {} // Set<LR1Item> 결과값
WorkList ← {(S' → S, $)} // Set<P × T>
// Production, Terminal
pairs ← {(S' → S, $)} // Set<P × T>
// Production, Terminal
// 1단계: 유효한 (production, lookahead) 쌍 수집
while WorkList ≠ ∅ do
WorkList, (prod, t) ← pop(WorkList)
// prod = A → γ₁γ₂…γₙ
for X ∈ {γ₁, …, γₙ} ∩ NT do
// X = γᵢ , β = γᵢ₊₁…γₙ
for prod' ∈ P[X], a ∈ FIRST(β · t) do
if (prod', a) ∉ pairs then
pairs ← pairs ∪ {(prod', a)}
WorkList ← WorkList ∪ {(prod', a)}
// 2단계: 전체 LR(1) item 생성
for (prod, t) ∈ pairs do
// prod = A → γ₁…γₙ
for item ∈ LR0(A → γ₁…γₙ) do
Items ← Items ∪ {(item, t)}
```
## 8.5 LR(1) Parsing Table
> §8.4에서 LR(1) DFA를 구성했다.
> §8.5에서는 이를 Parsing Table로 변환하고,
> LR(0) 기반 table과 비교하여 conflict가 어떻게 해소되는지 확인한다.
### 8.5.1 LR(1) Parsing Table (대입 문법)
> 현재 상태 + 다음 token을 보고 어떤 action을 취할지
| State | Items (요약) | S | L | R | = | * | [id] |
| ----- | ---------------------- | --- | --- | --- | --- | --- | ---- |
| 0 | S'→.S,$, S→.L=R,$, ... | 1 | 2 | 3 | | 4 | 5 |
| 1 | S'→S.,$ | | | | | | |
| 2 | S→L.=R,$, **R→L.,$** | | | | 6 | | |
| 3 | S→R.,$ | | | | | | |
| 4 | L→_.R,=, L→_.R,$, ... | | 7 | 8 | | 4 | 5 |
| 5 | L→[id].,=, L→[id].,$ | | | | | | |
| 6 | S→L=.R,$, R→.L,$, ... | | 9 | 10 | | 11 | 12 |
| 7 | R→L.,=, R→L.,$ | | | | | | |
| 8 | L→*R.,=, L→*R.,$ | | | | | | |
| 9 | R→L.,$ | | | | | | |
| 10 | S→L=R.,$ | | | | | | |
| 11 | L→*.R,$, R→.L,$, ... | | 9 | 13 | | 11 | 12 |
| 12 | L→[id].,$ | | | | | | |
| 13 | L→*R.,$ | | | | | | |
- `S`, `L`, `R` : - reduce 후 어느 state로 이동할지 (state transition)
- `=`, `*`, `[id]` : shift할 state 번호 (숫자만 있으면 Shift N)
**State 2에서 `=` 입력 시: Shift 6만 존재, Reduce 없음 → Conflict 해소.**
### 8.5.2 LR(0)/SLR(1) vs LR(1) 비교
| 항목 | LR(0) / SLR(1) | LR(1) |
| ------------- | --------------------- | ------------------ |
| Item 형태 | `A → α . β` | `A → α . β , a` |
| Reduce 조건 | `a ∈ FOLLOW(A)` (SLR) | lookahead가 정확히 `a` |
| 대입문법 상태 수 | 10 | 14 |
| 대입문법 Conflict | S6/R5 (State 2) | 없음 |
| DFA 변경 여부 | 변경 없음 (SLR은 table만) | **DFA 자체를 새로 설계** |
## 8.6 LR(1)의 장단점과 문법 계층
> §8.5까지 LR(1)이 SLR(1)의 한계를 어떻게 해결하는지 확인했다.
> §8.6에서는 그 대가로 생기는 상태 수 폭발 문제와,
> LR(1) grammar가 문법 계층에서 어디에 위치하는지를 정리한다.
> 상태 수 문제는 §9.5.1에서 LALR(1) heuristic의 동기가 된다.
### 8.6.1 장점 — 더 넓은 문법을 처리
- LR(0) item 하나에 여러 lookahead가 붙어 상태가 분리되므로, **문맥에 따라 다른 reduce 조건**을 표현 가능
- C, C++, Java, Python 등 대부분의 실용 언어가 LR(1) 문법에 속함
### 8.6.2 단점 — Viable Prefix DFA 상태 수 폭발
- 대입 문법에서 LR(0) 10개 → LR(1) 14개
- 실제 언어 문법에서는 훨씬 심각하게 증가
- 실제 컴파일러에서는 LALR(1) 등 근사 방식 사용 (§9.5.1 참조)
### 8.6.3 Reduce/Reduce Conflict — 문법 모호성의 징후
```
S' ::= S
S ::= A | B
A ::= a
B ::= a
```
`a`를 읽으면 `A → a .`와 `B → a .` 중 어느 것으로 reduce할지 결정 불가 → **Reduce/Reduce Conflict.** 대부분 **문법 자체가 모호**해서 생기는 경우이며, 문법을 직접 수정하거나 우선순위(priority) 규칙으로 해결해야 한다.
### 8.6.4 LR(1) Grammar의 문법 계층
```
┌──────────────────────────────────────────────────────┐
│ Context-Free Grammar │
│ │
│ ┌──────────────────────────┐ ┌──────────────────┐ │
│ │ LR(1) Grammar │ │ Ambiguous │ │
│ │ ┌────────────────────┐ │ │ Grammar │ │
│ │ │ SLR(1) Grammar │ │ │ │ │
│ │ │ ┌──────────────┐ │ │ │ │ │
│ │ │ │ Regular │ │ │ │ │ │
│ │ │ │ Grammar │ │ │ │ │ │
│ │ │ └──────────────┘ │ │ │ │ │
│ │ └────────────────────┘ │ │ │ │
│ └──────────────────────────┘ └──────────────────┘ │
└──────────────────────────────────────────────────────┘
```
- **LR(1) ⊃ SLR(1) ⊃ Regular** (모두 CFG의 부분집합)
- **Ambiguous Grammar**는 LR(1)과 교집합 없음 — LR(1) 파서로 분석 불가
- LR(1) Grammar에 속하지 않는 (하지만 ambiguous하지 않은) CFG도 존재
---
# 9. Parser 마무리
## 9.1 Parser의 출력 — CST에서 AST로
> §8까지는 Token list를 받아 문법을 검증하는 파서의 동작 원리를 다뤘다.
> 그런데 파서의 최종 목적은 파싱 성공/실패만 알리는 것이 아니라,
> 이후 의미 분석과 코드 생성에 사용할 AST를 반환하는 것이다.
>
> §9.1에서는 CST와 AST의 차이를 살펴보고,
> §9.2에서는 CST를 경유하지 않고 Token list에서 곧바로 AST를 만드는 방법을 다룬다.
### 9.1.1 지금까지 본 것은 CST-Generator 내부 동작 — Parser의 추상적 정의 재확인
```
val parser : Token list -> AST
Token list ──► [CST-Generator] ──► CST ──► [AST-Generator] ──► AST
```
개념적으로 두 단계:
1. **CST-Generator**: Token list → CST (Concrete Syntax Tree)
2. **AST-Generator**: CST → AST (Abstract Syntax Tree)
### 9.1.2 CST — 문법 구조를 그대로 반영한 트리
CST는 문법 규칙의 적용을 그대로 트리로 표현한다. `if (x == 1) y = z;`에 대한 CST:
```
CSTStmt(CSTIfStmt)
|
CSTIfStmt
┌────────┬────────┬────────┬────────┐
IF LPAREN CSTExpr RPAREN CSTStmt(CSTAssignStmt)
(CSTRelOp) ┌──┬──┬────────┬────┐
┌──┬────────┬──┐ ID ASSIGN CSTExpr SEMI
CSTExpr CSTRelOp CSTExpr (CSTId)
(CSTId) Kind(Eq) (CSTNum)
| | |
ID EQ NUM
```
### 9.1.3 AST — 핵심 의미 구조만 추상화
CST에서 제거되는 것들:
|제거 대상|이유|
|---|---|
|LPAREN, RPAREN|괄호는 구조 파악 후 불필요|
|SEMI, ASSIGN 등 구두점|노드 타입에 이미 의미가 담김|
|Child 1개인 중간 노드|단순 래핑 (예: `CSTExpr → CSTId`) 제거|
AST에 남는 것: 중첩 구조, 연산 종류, 식별자/리터럴 값 — 의미 분석·IR 변환에 필요한 것들.
예시 — `1 + 2 + 3 + 4 + 5`의 AST:
```
BinOp(+)
/ \
BinOp(+) Num(5)
/ \
Num(1) BinOp(+)
/ \
Num(2) BinOp(+)
/ \
Num(3) Num(4)
```
### 9.1.4 AST 타입 정의 예시
`if (x == 1) y = z;`에 해당하는 AST 구조:
```
ASTStmt(ASTIfStmt)
/ \
ASTExpr(ASTRelOp) ASTStmt(ASTAssignStmt)
/ | \ / \
ASTExpr ASTRelOp ASTExpr string(y) ASTExpr(ASTId)
(ASTId) Kind(Eq) (ASTNum) string(z)
string(x) int(1)
```
### 9.1.5 CST → AST 변환 규칙
|CST 노드|AST 변환|
|---|---|
|`CSTIfStmt`|`ASTIfStmt(condition: ASTExpr, body: ASTStmt)`|
|`CSTRelOp`|`ASTRelOp(lhs, op: ASTRelOpKind, rhs)`|
|`CSTAssignStmt`|`ASTAssignStmt(lhs: string, rhs: ASTExpr)`|
|`CSTId`|`ASTId(name: string)` — ID 토큰의 lexeme 추출|
|`CSTNum`|`ASTNum(value: int)` — NUM 토큰의 값 추출|
|IF, LPAREN, RPAREN, SEMI, ASSIGN 등|**버림**|
## 9.2 Token list → AST 직접 변환 — 두 스택 병행 운용
> §9.1에서 CST를 경유해 AST를 만드는 방식을 보았다.
> §9.2에서는 CST를 명시적으로 만들지 않고,
> LR 파싱과 동시에 AST를 구성하는 방법을 다룬다.
> §9.3의 Yacc 계열 파서 생성기가 이 원리를 활용한다.
### 9.2.1 두 스택 병행 운용
LR 파싱 시 **CST Stack**과 **AST Stack**을 동시에 운용한다:
```
CST Stack │ AST Stack
──────────────────────────┼──────────────────────────
CSTIfStmt │ ASTStmt(ASTIfStmt)
... │ ...
```
- **CST Stack**: 기존 LR 파서의 parse stack 역할 (state + CST node)
- **AST Stack**: reduce 시 CST node 대신 대응하는 AST node를 push
> 슬라이드 보면 직관적으로 이해 가능
### 9.2.2 변환 과정 단계별 추적
`if (x == 1) y = z;` 파싱 과정 (주요 단계만):
```
단계 1~2: IF, LPAREN shift
CST: [IF, LPAREN] AST: [IF, LPAREN]
단계 3: ID("x") shift → CSTExpr(CSTId) reduce
CST: [IF, LPAREN, CSTExpr(CSTId)]
AST: [IF, LPAREN, ASTExpr(ASTId("x"))]
단계 4: EQ shift → CSTRelOpKind(CSTEq) reduce
CST: [..., CSTExpr(CSTId), CSTRelOpKind(CSTEq)]
AST: [..., ASTExpr(ASTId("x")), ASTRelOpKind(ASTEq)]
단계 5: NUM(1) shift → CSTExpr(CSTNum) reduce
CST: [..., CSTExpr(CSTId), CSTRelOpKind(CSTEq), CSTExpr(CSTNum)]
AST: [..., ASTExpr(ASTId("x")), ASTRelOpKind(ASTEq), ASTExpr(ASTNum(1))]
단계 6: CSTRelOp reduce (위 3개 pop → CSTExpr(CSTRelOp) push)
CST: [IF, LPAREN, CSTExpr(CSTRelOp)]
AST: [IF, LPAREN, ASTExpr(ASTRelOp(ASTId("x"), ASTEq, ASTNum(1)))]
단계 7: RPAREN — reduce 시 구두점이므로 AST에서는 버림
... (y = z 처리 후 CSTAssignStmt reduce)
CST: [IF, LPAREN, CSTExpr(CSTRelOp), RPAREN, CSTStmt(CSTAssignStmt)]
AST: [IF, LPAREN, ASTExpr(...), ASTStmt(ASTAssignStmt("y", ASTId("z")))]
단계 N: CSTIfStmt reduce
CST: [CSTIfStmt]
AST: [ASTStmt(ASTIfStmt(condition, body))]
```
**핵심**: reduce 동작 시, CST node를 AST node로 변환하는 로직을 각 production rule에 붙여 실행한다. 이것이 §9.3의 Yacc에서 **semantic action**의 역할이다.
## 9.3 자동 파서 생성기 — Yacc와 FsYacc
> §9.2까지 파서가 어떻게 AST를 만드는지 이해했다.
> §9.3에서는 CFG 명세로부터 파서를 자동 생성하는 Yacc 계열 도구를 소개한다.
> §9.4에서 "Yacc를 그냥 쓰면 되지 않냐"는 의문에 답한다.
### 9.3.1 Yacc — Context Free Grammar → Parser 자동 생성
- **Yet Another Compiler-Compiler** (1970년대 Stephen C. Johnson 제안)
- 입력: CFG 명세 (`.y` 파일) + 각 production에 대한 semantic action (AST 생성 코드)
- 출력: LR 파서 C 코드
- 각 언어마다 다양한 버전: Bison(C), FsYacc(F#), Happy(Haskell) 등
### 9.3.2 FsYacc — F#을 위한 Yacc
```
Parser.fsy ──[FsYacc]──► Parser.fs
```
`.fsy` 파일에 문법과 semantic action을 작성하면, FsYacc가 LR 파싱 테이블과 AST 생성 코드를 자동으로 F# 코드로 변환한다.
## 9.4 Parsing을 직접 배우는 이유 — Conflict 해결 능력
> §9.3에서 Yacc로 파서를 자동 생성할 수 있음을 보았다. 그러면 Parsing 이론은 몰라도 되지 않을까? §9.4에서는 그렇지 않은 이유를 설명하고, §9.5에서 실무에서 마주치는 구체적인 고민거리들을 정리한다.
- **문법을 잘못 디자인하면 Conflict가 발생한다** (LR(1) 문법이 아닌 경우 등)
- Yacc 자체 설정(우선순위, 결합성)으로 해결 가능한 경우도 있지만, **문법 구조 자체를 고쳐야 해결되는 경우** 존재
- 문법을 어떻게 수정해야 하는지 판단하려면 Parsing 이론 이해가 필수
## 9.5 파서 구현의 고민거리들
> §9.4까지 이론과 도구 전반을 다뤘다.
> §9.5에서는 실제 파서를 구현할 때 만나게 되는 네 가지 현실적 문제를 정리한다.
### 9.5.1 LR(1) DFA 상태 수 → LALR(1) Heuristic
- LR(1) item을 쓰면 상태 수가 너무 많아진다
- **LALR(1)**: 동일한 LR(0) core를 가지는 LR(1) 상태들을 병합하는 heuristic
- 상태 수를 대폭 줄이면서 대부분의 실용 문법은 LALR(1)로 처리 가능
- Yacc/Bison이 생성하는 파서가 바로 LALR(1) 파서
### 9.5.2 여전히 남는 Conflict들
|Parser 종류|발생 가능한 Conflict|
|---|---|
|LL(1)|First/First, First/Follow|
|LR(1)|Shift/Reduce, Reduce/Reduce|
이 conflict들은 문법의 모호성 또는 해당 문법 클래스의 경계를 벗어난 설계에서 비롯된다.
### 9.5.3 언어 설계 시 어떤 문법을 써야 하나?
```
┌────────────────────────────────────────────────────────┐
│ Context-Free Grammar │
│ │
│ ┌──────────────────────────┐ ┌──────────────────┐ │
│ │ LR(1) Grammar │ │ Ambiguous │ │
│ │ ┌─────────────┐ │ │ Grammar │ │
│ │ │ LL(1) │ │ │ │ │
│ │ │ Grammar │ │ │ │ │
│ │ │ ┌─────────┐ │ │ │ │ │
│ │ │ │ Regular │ │ │ │ │ │
│ │ │ │ Grammar │ │ │ │ │ │
│ │ │ └─────────┘ │ │ │ │ │
│ │ └─────────────┘ │ │ │ │
│ └──────────────────────────┘ └──────────────────┘ │
└────────────────────────────────────────────────────────┘
```
- LL(1) ⊂ LR(1) ⊂ CFG
- Ambiguous Grammar는 LR(1)과 분리 (LR 파서로 분석 불가)
- 실용 언어 설계 시 **LR(1) 문법**을 목표로 삼는 것이 일반적
### 9.5.4 에러 복구 — IDE Linter 구현의 현실
- 중간에 파싱 에러가 발생하면 그 이후 코드는 검사 불가
- IDE의 Linter처럼 에러가 발생해도 파싱을 계속 진행하고 싶은 경우
- **에러 복구(Error Recovery)** 전략 필요: 에러 발생 지점을 건너뛰거나 동기화 토큰(`;`, `}` 등)까지 skip 후 재개