#컴파일러 #compiler #파서 #parser ![[10. Parser (4) - Post-lecture.pdf]] # Part V: Bottom-Up Parsing (1) - Overview ## Parse Tree를 복원하는 두 가지 방법 (복습) - 문법 $G = (T, NT, S, P)$와 문자열 $s \in T^*$가 주어졌을 때, - Top-down: $S$로부터 시작해서 $A \in NT$에 대한 $A \to \gamma \in P$를 선택하며 $s$까지 확장 - $S \to \gamma_1 \to \gamma_2 \to \cdots \to \gamma_n \to s$ - Bottom-up: $s$로부터 시작해서 각 production의 올바른 prefix를 인식하며 $S$까지 축소 - $s \to \gamma_n \to \cdots \to \gamma_2 \to \gamma_1 \to S$ ## Bottom-Up Parsing = Right-most Derivation의 반대 과정 - 왼쪽에서 오른쪽으로 token을 읽어가면서 진행 - Right-most derivation은 오른쪽 NT부터 확장하니, 거꾸로 가면 왼쪽부터 reduce가 진행됨 ### 예제: 덧셈 문법으로 `(1 + 2) + 3` 유도 ```f# 문법: S ::= E + S | E E ::= [number] | ( S ) Right-most derivation (S → ... → s): 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 + E ) + 3 → ( E + S ) + 3 → ( S ) + 3 → E + 3 → E + E → E + S → S ``` ## Shift-Reduce Parsing - 현재까지 확인한 위치를 `.` (Marker)으로 표시 - $\alpha \beta . \gamma \delta$: 지금까지 $\alpha \beta$까지 읽었고, 앞으로 $\gamma \delta$가 남음 - $\gamma \delta$는 terminal들의 나열 (`왜?` 아직 안 읽은 부분은 token이기 때문) - **Shift 연산** - 현재 위치에서 적용할 수 있는 production이 없으면 다음 token으로 이동 - $\alpha \beta . a \delta$에서 $\alpha \beta a . \delta$로 진행 - **Reduce 연산** - 현재 위치에서 올바르게 적용할 수 있는 production을 전부 적용 - $A \to \beta$에 대해 유도 $S \Rightarrow^* \alpha A a \delta \to \alpha \beta a \delta$가 존재하면, $\alpha \beta . a \delta$에서 $\alpha A . a \delta$로 진행 ### Stack으로 구현 - Marker를 기준으로 왼쪽의 token list는 Stack으로 구현 가능 - **Shift**: Terminal을 stack에 push - **Reduce**: production 우변의 기호(T, NT)들을 pop한 후 좌변 NT를 push - $A \to \alpha \beta \gamma$에 대해 reduce하면? - $\gamma, \beta, \alpha$ 순으로 pop하고 (stack top부터 거꾸로) $A$를 push ### 예제: `(1 + 2) + 3` 파싱 흐름 (일부) ```f# 문법: 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] ( E . + 2 ) + 3 / ( E / + 2 ) + 3 / shift + ( E + . 2 ) + 3 / ( E + / 2 ) + 3 / shift 2 ( E + 2 . ) + 3 / ( E + 2 / ) + 3 / reduce E → [number] ( E + E . ) + 3 / ( E + E / ) + 3 / reduce S → E ( E + S . ) + 3 / ( E + S / ) + 3 / reduce S → E + S ( S . ) + 3 / ( S / ) + 3 / shift ) ( S ) . + 3 / ( S ) / + 3 / reduce E → ( S ) E . + 3 / E / + 3 / shift + E + . 3 / E + / 3 / shift 3 E + 3 . / E + 3 / / reduce E → [number] E + E . / E + E / / reduce S → E E + S . / E + S / / reduce S → E + S S . / S / / accept ``` ## 언제 Shift하고, 언제 Reduce하나요? - 아무 때나 reduce하면 안 됨. `(E + 2) + 3` 상태에서 `S → E`를 바로 적용하면 틀림. ### Reduce해야 하는 타이밍 - Right-most derivation: $S \Rightarrow^* \alpha A s \to \alpha \beta s$ - 현재 상태: $\alpha \beta . s$ - 올바른 right-most derivation이 존재하고, **Marker가 production의 우변 끝에 위치할 때** - = production의 우변이 stack top에 있을 때 - → 이때 reduce 가능 ### Handle - **Handle**: reduce될 수 있고, 결과적으로 $S$까지 reduce되게 하는 token list와 production - 반대로 말하면, **handle만 reduce를 해야 함** - Shift-Reduce parsing에서 handle은 항상 **stack top에서만 발견 가능** - 귀납법으로 증명: - Base case: Stack이 비어있으면 trivial - Induction hypothesis: handle이 stack top에 있다고 가정 - Reduce 후에도 다음 handle은 stack top (혹은 shift 후 stack top)에 존재 - `왜?` 다음 handle이 방금 reduce한 $A$보다 왼쪽에 있으면 right-most가 아니게 됨 → 모순 ## Bottom-Up Parsing 알고리즘 (Handle을 찾는 과정) ```f# 입력: (T, NT, S, P) // Grammar tokens // Token들의 list 변수: idx ← 0 // 현재 Token 위치 stack ← [] // Stack while (true) do if len(stack) = 1 && stack.top = S then return S else match tryFindHandle stack with | Some ([γ₁ ; γ₂ ; ...; γₙ], A → γ₁γ₂…γₙ) -> // Reduce for 1 ≤ i ≤ n do stack.pop() stack.push(A) | None -> // Shift stack.push(tokens[idx]) idx ← idx + 1 ``` ## Part V 정리 - Bottom-up parsing = right-most derivation의 반대 과정 - Bottom-up parsing = Shift-Reduce parsing - **Shift**: 입력 token을 stack에 push - **Reduce**: production의 우변을 stack에서 pop하고, 좌변을 stack에 push - Handle이 stack top에 위치하면 reduce 수행 - **Bottom-up parsing의 핵심은 handle을 찾는 것** --- # Part VI: Bottom-Up Parsing (2) - LR(0) Parser ## Handle은 어떻게 찾나요? - 일반적으로 handle을 찾는 효율적인 방법은 없음 - 일반적 방법: Backtracking (비효율적) - → Heuristic 알고리즘 사용 - 대부분의 경우 잘 작동한다고 알려져 있음 - 관찰(observation)에 의해 만들어짐 ## 관찰: Stack엔 항상 Production들의 Prefix만 존재 ### 예제로 관찰하기: `(1 + 2) + 3` 파싱 중 Stack 추적 ```f# 문법: S ::= E + E E ::= [num] | ( S ) Stack 변화 (각 prefix가 어떤 production의 시작 부분인지): ( 1 → ( : E ::= ( S )의 prefix, 1: E ::= [num]의 prefix ( E → ( : E ::= ( S )의 prefix, E: S ::= E + E의 prefix ( E + → ( : E ::= ( S )의 prefix, E +: S ::= E + E의 prefix ( E + 2 → ( : E ::= ( S )의 prefix, E +: S ::= E + E의 prefix, 2: E ::= [num]의 prefix ( E + E → ( : E ::= ( S )의 prefix, E + E: S ::= E + E의 prefix ( S → ( : E ::= ( S )의 prefix ( S ) → ( S ): E ::= ( S )의 prefix (완전) E → E: S ::= E + E의 prefix ``` - Stack엔 항상 production들의 prefix들이 존재: `prefix₁ prefix₂ … prefixₙ` - 완전한 production이 될 수 있는 것: `prefixₙ` (가장 오른쪽 prefix) - `왜?` handle은 stack top에서만 발견 가능하므로 - `prefixₙ`이 몇 번의 shift를 거쳐 완전한 production이 되면 `prefixₙ₋₁`의 부족한 부분을 채워줌 ## Viable Prefix - $\alpha \in (T \cup NT)^*, s \in T^*$일 때, $S \Rightarrow^* \alpha . s$이면 $\alpha$를 **viable prefix**라고 정의 - 예: $\epsilon$, E, E +, E + E, (, ( S, ( S ) ... - `왜 viable prefix?` **Handle의 prefix**이기 때문 - Stack에 viable prefix들만 있다는 것 = 아직 parsing error를 만나지 않았다는 뜻 ## 아이디어: Viable Prefix를 인식하면 Handle을 찾을 수 있다 - 현재 Stack에 viable prefix들만 있을 때 알 수 있는 것: - 지금까지 읽은 입력은 정상적 - 마지막 viable prefix (`prefixₙ`)의 상태에 따라 reduce 여부 결정 가능 - `prefixₙ`이 production 그 자체(handle)라면 → **reduce** - 완전한 production이 아닌 prefix 수준이면 → **shift** ## Viable Prefix의 집합은 Regular Language - Regular Language = FSM으로 표현 가능한 언어 - → FSM으로 viable prefix를 인식할 수 있음 ### LR(0) Item - (정의) Production에 marker로 현재 상태를 표시한 것을 **item** (혹은 **LR(0) item**) - $A \to \gamma_1 \dots \gamma_i . \gamma_{i+1} \dots \gamma_n$: viable prefix $\gamma_1 \dots \gamma_i$를 인식한 상태 ### Viable Prefix에 대한 State Machine (단일 production) - 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 = {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 .}$: Item들의 집합 - $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) ![[스크린샷 2026-04-17 오후 12.18.23.png]] ### 여러 Production 합치기 (NFA 만들기) - 각각의 production에 대해 viable prefix FSM을 만들고, - $A \to \alpha . B \beta$와 $B \to \gamma$라는 두 production이 있다면 - $\delta(A \to \alpha . B \beta,; \epsilon) = B \to . \gamma$를 추가 (ε-transition) - 의미: $B$를 인식하러 가는 순간 $B$의 production 시작 상태로 점프할 수 있음 - 그리고 $S' \to S$라는 특별한 **augmented production**을 하나 추가 - $S$를 인식했다는 것을 나타내는 장치 ($S' \to .S$, $S' \to S.$) ![[스크린샷 2026-04-17 오후 12.19.11.png]] ## NFA → DFA (Subset Construction) - 위에서 만든 건 ε-transition을 가진 NFA - Subset construction으로 DFA로 변환 ### 예제: Viable Prefix DFA ```f# 문법: S' ::= S S ::= E + E E ::= [num] | ( S ) 상태 (각 상태는 item들의 closure): State 0: S' → . S, S → . E + E, E → . [num], E → . ( S ) State 1: S' → S . State 2: S → E . + E State 3: E → [num] . State 4: E → ( . S ), S → . E + E, E → . [num], E → . ( S ) State 5: S → E + . E, E → . [num], E → . ( S ) State 6: E → ( S . ) State 7: S → E + E . State 8: E → ( S ) . Transition Table: S E + [num] ( ) 0 1 2 3 4 1 2 5 3 4 6 2 3 4 5 7 3 4 6 8 7 8 ``` ## Viable Prefix DFA 활용 - Stack에 있는 symbol들을 차례로 DFA에 먹여서 상태 계산 - 최종 상태의 item들을 보고 결정: - Item이 `A → γ .` 형태 (완전한 production) → **Reduce** - Item이 `A → α . β` 형태 (아직 불완전) → **Shift** ### 예제 단계 - 상태 `( E + . 2 ) + 3`, stack = `( E +` - DFA 돌려보면 State 5에 도달: `S → E + . E, E → . [num], E → . ( S )` - 아직 불완전한 Prefix이므로 → **Shift** - 다음 단계: `( E + 2 . ) + 3`, stack = `( E + 2` - 이번엔 State 3에 도달: `E → [num] .` - 완전한 Production이므로 → **Reduce** ## 매번 Viable Prefix DFA를 돌려야 하나요? - 최적화: **Stack에 DFA 상태를 함께 저장** - 같은 prefix에 대해서는 항상 같은 DFA 상태가 나옴 - Stack element: $T \cup NT \to (T \cup NT,; \text{DFA State})$ - Stack bottom에 `(dummy, DFA start state)`를 미리 push ### 필요한 Table 2개 - **Action Table**: Shift/Reduce에 대한 결정 (terminal 기준) - `SN`: state N으로 shift - `RN`: production N으로 reduce - `A`: accept - **Goto Table**: DFA 구현 (non-terminal 기준) - `GN`: state N으로 이동 ### 예제: Action & Goto Table ```f# Grammar: (1) S ::= E + E (2) E ::= [num] (3) | ( S ) Goto | Action 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 ``` ## LR(0) Parsing 알고리즘 ```f# 입력: (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 elif Action[state][token] = 'SN' then // Shift 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 ``` ## LR(k) Parsing - **L**eft-to-right으로 읽으면서, **R**ight-most derivation을 찾는 parsing - **k**개의 token을 미리 살펴보고 (lookahead) parsing - 우리는 LR(0) Parsing을 살펴봤음 (lookahead = 0) - `LR(0) Parser가 못하는 것들이 있겠죠?` → 다음 강의에서 LR(1), SLR, LALR 등을 다룰 예정 ## Part VI 정리 - 올바른 token list를 인식 중이면 stack에는 viable prefix들이 존재 - Viable prefix들의 집합은 **Regular Language** - LR(0) Parsing은 Stack과 Action, Goto table을 가지고 수행 - Action, Goto table은 Viable prefix DFA로부터 생성 ## LL(1) vs LR(0) 비교 (개인 정리) - **LL(1)**: Top-down, Left-most derivation, lookahead 1 - FIRST/FOLLOW로 parsing table 구성 - Left-recursion 불가 → right-recursion으로 변환 필요 - **LR(0)**: Bottom-up, Right-most derivation 역순, lookahead 0 - Viable prefix DFA로 Action/Goto table 구성 - Left-recursion 처리 가능 (오히려 선호됨) - 일반적으로 LL(1)보다 더 많은 문법을 처리 가능