#컴파일러 #compiler #파서 #parser
![[12. Parser (6) - Post-lecture.pdf]]
# Viable Prefix DFA의 의미
## Bottom-Up Parsing 과정 다시 보기
- `(1 + 2) + 3`을 $S ::= E + E,; E ::= [num] \mid (S)$로 파싱하는 과정
- 매 단계마다 Stack은 지금까지 인식한 **Parse Tree의 일부분(subtree)** 을 표현
- Shift → leaf 추가
- Reduce → subtree를 하나로 묶음
- 결국 전체 parse tree가 `S`로 root까지 올라가면 accept
### 관찰: Stack은 Parse Tree의 "지금까지 완성된 부분"
- 초록색 표시가 완성된 subtree, 빨간색 표시가 현재 stack 위에 있는 viable prefix
- Shift/Reduce 연산은 parse tree를 bottom-up으로 짓는 과정 그 자체
## Viable Prefix DFA = 올바른 파싱 여부를 알려주는 DFA
- `핵심 통찰` Stack의 symbol들을 DFA에 먹이면 → 현재 상태가 곧 "어떤 viable prefix를 인식했는지"를 알려줌
- DFA가 accepting state에서 멈추면 → 올바른 viable prefix
- DFA가 dead state로 빠지면 → parsing error
- 즉, **Viable Prefix DFA는 현재까지의 파싱이 정상인지를 판별하는 validator**
### DFA 상태의 의미
- 각 상태는 item들의 집합 (closure)
- `A → α . β` 형태 item이 있다 = viable prefix `α`를 인식했고, 앞으로 `β`가 올 수 있음
- `A → α .` (marker가 끝) 형태 item = 완전한 production → **Reduce 가능**
- `A → α . β` (β가 남음) 형태 item = 아직 불완전 → **Shift 해야 함**
---
# Part VII: Bottom-Up Parsing (3) - SLR(1) Parser
## 다루고자 하는 내용
- LR(0) 파서에서 발생할 수 있는 **Conflict**
- Shift/Reduce Conflict
- Reduce/Reduce Conflict
- **SLR(1) Parsing**: Shift/Reduce Conflict를 해결할 수 있는 Heuristic
## LR(0)는 항상 잘 작동할까?
- `아니요.` 문법에 따라 DFA 한 상태 안에 서로 충돌하는 item이 들어올 수 있음.
### 예제 1: Shift/Reduce Conflict
```f#
문법:
S' ::= S
S ::= a | a b
Viable Prefix DFA (subset construction 후):
| | 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 . | | |
문제의 State 2:
- S → a . ← 완전한 production이니까 Reduce 가능
- S → a . b ← b가 남았으니까 Shift 가능
→ 같은 상태에서 Reduce도 가능, Shift도 가능 → SHIFT/REDUCE Conflict!
```
### 예제 2: Reduce/Reduce Conflict
```f#
문법:
S' ::= S
S ::= A | B
A ::= a
B ::= a
Viable Prefix DFA:
| | S | A | B | a
0 | S' → . S, S → . A, S → . B, | 1 | 2 | 3 | 4
| A → . a, B → . a | | | |
1 | S' → S . | | | |
2 | S → A . | | | |
3 | S → B . | | | |
4 | A → a . , B → a . | | | |
문제의 State 4:
- A → a . ← A로 reduce 가능
- B → a . ← B로도 reduce 가능
→ 둘 중 뭘 골라야 할지 모름 → REDUCE/REDUCE Conflict!
```
## SHIFT/REDUCE 충돌이 일어나면 어떻게 해야 할까?
### 아이디어: Lookahead Token을 살펴보자
- Top-down parsing에서 $A \to \epsilon$인 production을 안심하고 적용하려고 본 것 → **FOLLOW(A)**
- 같은 아이디어를 Bottom-Up Parsing에도 적용해보자!
### 직관: 예제 1로 다시 보기
```f#
문법: S' ::= S, S ::= a | a b
NULLABLE | FIRST | FOLLOW
S false | [num] ( | $
상황: Stack = a, State = 2 = {S → a . , S → a . b}
Case 1: 입력이 "a . b
quot;인 경우
- Lookahead = b
- S → a .로 reduce하면? S가 나온 뒤에 b가 따라오는데, FOLLOW(S) = {$}
- b ∉ FOLLOW(S) → Reduce하면 안 됨!
- 이 경우에는 Shift (S → a . b 진행)
Case 2: 입력이 "a . quot;인 경우
- Lookahead = $
- S → a .로 reduce하면? $ ∈ FOLLOW(S) → OK!
- 이 경우에는 Reduce
```
- Lookahead token을 보고 **FOLLOW 집합에 속하는지** 확인하면 shift/reduce를 올바르게 선택 가능!
## SLR(1) Parsing: Simple LR(1) Parsing
- **Simple LR(1)**인 이유: LR(0)에 아주 작은 변화만 가해 만들었기 때문
- 핵심 규칙
- $A \to \gamma$를 기반으로 한 **reduce 연산을 수행할 때**, FOLLOW($A$)를 확인
- lookahead token $a$가 $a \in \text{FOLLOW}(A)$일 때만 **reduce**!
- Shift는 LR(0)와 동일하게 처리
### SLR(1) Parsing 알고리즘
```f#
입력:
(T, NT, S, P) // Grammar
tokens // Token들의 list
FOLLOW // FOLLOW Table: Map<NT, Set<T>>
Action // Action Table: Map<State, Map<T, Set<Action>>>
// Set<Action>인 이유: 같은 칸에 여러 action이 들어올 수 있음
Goto // Goto Table: Map<State, Map<NT, State>>
변수:
idx ← 0
stack ← [(_, 0)]
while (true) do
symb, state ← stack.top
token ← tokens[idx] // Lookahead token
if Action[state][token] ∋ 'A' then return
elif Action[state][token] ∋ 'RN' &&
token ∈ FOLLOW(A) then // RN: A ← γ₁ … γₙ
// Reduce
for 1 ≤ i ≤ n do stack.pop()
_, state' ← stack.top
M ← Goto[state'][A]
stack.push((A, M))
elif Action[state][token] ∋ 'SN' then
// Shift
stack.push((token, N))
idx ← idx + 1
else raise Error
```
- `순서가 중요:` **Reduce를 FOLLOW 조건으로 먼저 체크**한 뒤, 조건에 안 맞으면 Shift 시도
- LR(0)와 비교
- LR(0): Action 테이블 칸에 하나의 action만 → 충돌나면 conflict
- SLR(1): 여러 action이 있을 수 있음, FOLLOW로 걸러서 결정
## 예제: 덧셈 문법에 SLR(1) 적용
```f#
문법:
(1) S ::= E + S
(2) | E
(3) E ::= [number]
(4) | ( S )
FIRST/FOLLOW:
| NULLABLE | FIRST | FOLLOW
S | false | [num] ( | $ )
E | false | [num] ( | $ + )
문제의 상태 (State with conflict):
{ S → E . + S, S → E . }
- Lookahead가 '+'면 Shift (S → E + S 진행)
- Lookahead가 '