# 3. 🚨 Top-Down Parsing (1) - Recursive Descent Parser ## 3.1 Top-Down Parsing → Backtracking 필요 > §2.4에서 Parse Tree(=CST)를 복원하는(=CST Generator에서 하는 일) > 두 가지 방법(Top-down / Bottom-up)을 소개했다. > > 이 절부터는 Top-down 방식을 구체적으로 다룬다. > 먼저 단순히 시도하면 어떤 문제가 생기는지, 그 해결책이 Backtracking임을 확인한다. > > §3.2에서 Backtracking을 체계화한 알고리즘인 Recursive Descent Parsing을 다룬다. Top-down parsing은 $S$에서 시작하여 production을 선택하며 점점 확장해나가는 방식이다. $S \to \gamma_1 \to \gamma_2 \to \cdots \to \gamma_n \to s$ **문제:** 잘못된 production을 선택하면 목표 문자열과 다른 방향으로 유도될 수 있다. **예시: 덧셈 문법** ```ebnf S ::= E + S | E E ::= [number] | ( S ) ``` 입력: `(1+2+(3+4))+5` ``` S → E → ( S ) → ( E ) → ( 1 ) ← 잘못된 유도! ``` 어떤 규칙이 문제였을까? ``` // 되돌아가기 S → E → ( S ) → ( E ) → ( 1 ) // 괄호를 유발한 친구를 찾자 S → E → ( S ) ← 여기가 문제? S → E → 1 ← 이렇게 가도 이상함 S → E ← 문제는 여기! ``` **해결책: Backtracking** → 잘못된 선택을 감지하면 이전 상태로 되돌아가 다른 production을 시도한다. ## 3.2 🚨 Recursive Descent Parsing — 정의 > §3.1에서 Backtracking이 Top-down parsing의 핵심 아이디어임을 확인했다. > 이 절에서는 Backtracking을 구체적인 알고리즘으로 체계화한 > Recursive Descent Parsing을 정의한다. > §3.3에서는 이 알고리즘의 특징과 한계를 분석한다. ### 3.2.1 입력 및 변수 > 🤓☝️ 이건 결국 Parser 내부 CST Generator의 동작임을 잊지 말자! Token이 뭐였는지 헷갈린다면? [[1. Lexer]] 중 §1.4 Grammar가 뭐였는지 헷갈린다면? [[#1.4 Language의 조건 — Grammar (문법)]]과 [[#1.8 어떤 것을 Context-Free Grammar라고 하는가?]] 참고. Tree가 뭐였는지 헷갈린다면? [[#2.2.2 Syntax Tree 종류 — CST (Concrete Syntax Tree) = Parse Tree]] 참고. ```pseudo 입력: (T, NT, S, P) // Grammar tokens // Token 리스트 변수: tree ← S // Tree node (속성: parent, children, rule) // return 되는 Parse Tree(=CST) focus ← S // 현재 처리 중인 Tree node // CST를 만들어가는 과정에서 // "지금 어느 노드를 확장/매칭하고 있는가? idx ← 0 // 현재 Token 위치 // 입력 Token list에서 어디까지 소비했는가? stack ← [] // 아직 처리하지 않은 노드들의 스택 ``` ### 3.2.2 메인 루프 ```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 ``` ### 3.2.3 Case 1: Non-terminal 처리 → Production 현재 focus가 Non-terminal인 경우, 해당 Non-terminal의 rule 번호에 해당하는 production을 적용한다. ```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 ← α₁ ``` ### 3.2.4 Case 2: Terminal 처리 → 다음으로 현재 focus가 Terminal이고 현재 Token과 일치하는 경우: ```pseudo // Case 2: T // "트리가 기대하는 토큰"과 "실제 입력 토큰"이 맞으므로 소비 idx ← idx + 1 // 다음 토큰으로 이동 focus ← stack.pop() // 스택에서 다음 처리할 노드 꺼내기 ``` ### 3.2.5 🚨 Case 3: Backtrack → 백트랙 or 매칭 실패 시, 가장 최근 Non-terminal로 올라가 다음 production을 시도한다. ```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 그려서 쌓아가면서 이해 ㄱㄱ > 한 번 이해한 거라 ㄱㅊ을듯 입력: `(1+2+(3+4))+5` ```ebnf S ::= E | E + S E ::= ( S ) | [number] ``` production 인덱스 정리: - `P[S][0]` = `S → E` - `P[S][1]` = `S → E + S` - `P[E][0]` = `E → ( S )` - `P[E][1]` = `E → [number]` #### 초기 상태 ``` tree : S focus : S idx : 0 → ( stack : [] ``` #### STEP 1 `Case 1` — focus=S (NT), `P[S][0]` = `S → E` 적용 ``` tree : S | E ← focus idx : 0 → ( stack : [] ``` #### STEP 2 `Case 1` — focus=E (NT), `P[E][0]` = `E → ( S )` 적용 ``` tree : S | E / | \ ( S ) ← focus=( idx : 0 → ( stack : [S, )] ``` #### STEP 3 `Case 2` — focus=`(`, tokens\[0]=`(` ✅ 매칭 ``` tree : S | E / | \ ( S ) ← focus=S idx : 1 → 1 stack : [)] ``` #### STEP 4 `Case 1` — focus=S (NT), `P[S][0]` = `S → E` 적용 ``` tree : S | E / | \ ( S ) | E ← focus idx : 1 → 1 stack : [)] ``` #### STEP 5 `Case 1` — focus=E (NT), `P[E][0]` = `E → ( S )` 적용 ``` tree : S | E / | \ ( S ) | E / | \ ( S ) ← focus=( idx : 1 → 1 stack : [S, ), )] ``` #### STEP 6 `Case 3` ⛔ — focus=`(`, tokens[1]=`1` ❌ 불일치 → Backtrack `E → ( S )` 실패. `P[E][1]` = `E → [number]` 로 재시도. restore: focus=E (부모로), idx=1 유지, 자식 제거. ``` tree : S | E / | \ ( S ) | E ← focus (자식 제거됨, rule=1로 올라감) idx : 1 → 1 stack : [)] ``` #### STEP 7 `Case 1` — focus=E (NT), `P[E][1]` = `E → [number]` 적용 ``` tree : S | E / | \ ( S ) | E | 1 ← focus idx : 1 → 1 stack : [)] ``` #### STEP 8 `Case 2` — focus=`1`, tokens[1]=`1` ✅ 매칭 ``` tree : S | E / | \ ( S ) | E | 1 ← focus=) (stack.pop) idx : 2 → + stack : [] → pop 하면 ) ``` #### STEP 9 `Case 3` ⛔ — focus=`)`, tokens[2]=`+` ❌ 불일치 → Backtrack `S → E` 로는 `1` 만 소비하고 끝났는데 `)` 가 와야 하는데 `+` 가 옴. restore: focus=S (부모), idx=1, 자식(E) 제거. `P[S][1]` = `S → E + S` 로 재시도. ``` tree : S | E / | \ ( S ) | S ← focus (rule=1, 자식 제거됨) idx : 1 → 1 stack : [)] ``` #### STEP 10 `Case 1` — focus=S (NT), `P[S][1]` = `S → E + S` 적용 ``` tree : S | E / | \ ( S ) | S / | \ E + S ← focus=E idx : 1 → 1 stack : [+, S, )] ``` #### STEP 11 `Case 1` — focus=E (NT), `P[E][1]` = `E → [number]` 적용 (이전에 `E → ( S )` 가 실패한 적 있고, 지금 tokens[1]=`1` 이므로 바로 [number] 선택) ``` tree : S | E / | \ ( S ) | S / | \ E + S | 1 ← focus idx : 1 → 1 stack : [+, S, )] ``` #### STEP 12 `Case 2` — focus=`1`, tokens[1]=`1` ✅ ``` focus : + (stack.pop) idx : 2 → + stack : [S, )] ``` #### STEP 13 `Case 2` — focus=`+`, tokens[2]=`+` ✅ ``` focus : S (stack.pop) idx : 3 → 2 stack : [)] ``` #### STEP 14 `Case 1` — focus=S (NT), `P[S][1]` = `S → E + S` 적용 ``` tree : S | E / | \ ( S ) | S / | \ E + S | \ 1 E + S ← focus=E idx : 3 → 2 stack : [+, S, )] ``` #### STEP 15 `Case 1` — focus=E, `P[E][1]` = `E → [number]` 적용 ``` E | 2 ← focus idx : 3 → 2 ``` #### STEP 16 `Case 2` — focus=`2`, tokens[3]=`2` ✅ ``` focus : + (stack.pop) idx : 4 → + stack : [S, )] ``` #### STEP 17 `Case 2` — focus=`+`, tokens[4]=`+` ✅ ``` focus : S (stack.pop) idx : 5 → ( stack : [)] ``` #### STEP 18 `Case 1` — focus=S, `P[S][0]` = `S → E` 적용 ``` S | E ← focus idx : 5 → ( stack : [)] ``` #### STEP 19 `Case 1` — focus=E, `P[E][0]` = `E → ( S )` 적용 ``` E / | \ ( S ) ← focus=( idx : 5 → ( stack : [S, ), )] ``` #### STEP 20 `Case 2` — focus=`(`, tokens[5]=`(` ✅ ``` focus : S (stack.pop) idx : 6 → 3 stack : [), )] ``` #### STEP 21 `Case 1` — focus=S, `P[S][1]` = `S → E + S` 적용 ``` S / | \ E + S ← focus=E idx : 6 → 3 stack : [+, S, ), )] ``` #### STEP 22 `Case 1` — focus=E, `P[E][1]` = `E → [number]` 적용 ``` E | 3 ← focus idx : 6 → 3 ``` #### STEP 23 `Case 2` — focus=`3`, tokens[6]=`3` ✅ ``` focus : + idx : 7 → + ``` #### STEP 24 `Case 2` — focus=`+`, tokens[7]=`+` ✅ ``` focus : S idx : 8 → 4 ``` #### STEP 25 `Case 1` — focus=S, `P[S][0]` = `S → E` 적용 ``` S | E ← focus idx : 8 → 4 ``` #### STEP 26 `Case 1` — focus=E, `P[E][1]` = `E → [number]` 적용 ``` E | 4 ← focus idx : 8 → 4 ``` #### STEP 27 `Case 2` — focus=`4`, tokens[8]=`4` ✅ ``` focus : ) (stack.pop) idx : 9 → ) stack : [), )] ``` #### STEP 28 `Case 2` — focus=`)`, tokens[9]=`)` ✅ ``` focus : ) (stack.pop) idx : 10 → ) stack : [)] ``` #### STEP 29 `Case 2` — focus=`)`, tokens[10]=`)` ✅ ``` focus : + (stack.pop) idx : 11 → + stack : [S] ``` #### STEP 30 `Case 2` — focus=`+`, tokens[11]=`+` ✅ ``` focus : S (stack.pop) idx : 12 → 5 stack : [] ``` #### STEP 31 `Case 1` — focus=S, `P[S][0]` = `S → E` 적용 ``` S | E ← focus idx : 12 → 5 stack : [] ``` #### STEP 32 `Case 1` — focus=E, `P[E][1]` = `E → [number]` 적용 ``` E | 5 ← focus idx : 12 → 5 stack : [] ``` #### STEP 33 `Case 2` — focus=`5`, tokens[12]=`5` ✅ ``` focus : stack.pop() → 스택 비어있음 idx : 13 (= len(tokens)) stack : [] ``` #### STEP 34 ✅ **Success!** — `idx = len(tokens) && stack = []` 최종 CST: ``` S └── E ├── ( ├── S │ └── S │ ├── E │ │ └── 1 │ ├── + │ └── S │ ├── E │ │ └── 2 │ ├── + │ └── S │ └── E │ ├── ( │ ├── S │ │ └── S │ │ ├── E │ │ │ └── 3 │ │ ├── + │ │ └── S │ │ └── E │ │ └── 4 │ └── ) └── ) + S └── E └── 5 ``` ## 3.3 Recursive Descent Parsing — 특징 > §3.2에서 Recursive Descent Parsing 알고리즘을 완전히 정의했다. > > 이제 이 알고리즘의 성질을 분석하고, > 항상 올바르게 동작하는지 질문을 던진다. > > §3.4에서는 종료를 보장하지 못하는 Left-recursion 문제와 그 해결책을 다룬다. ### 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 문제와 해결 > §3.3에서 Recursive Descent Parsing이 > 특정 문법에서 종료되지 않을 수 있다는 점을 지적했다. > > 구체적으로 어떤 문법이 문제가 되는지, > 그리고 어떻게 고칠 수 있는지를 다룬다. > > 이후 강의에서는 Backtracking 자체를 없애는, > 보다 효율적인 Top-down parsing 방법을 다룬다. "Recursive Descent Parsing으로 항상 Parsing이 가능한 것은 아니다." ### 3.4.1 `문제` Left-recursion **문제 예시:** $S \to Sa,\quad S \to b$ - 이 문법이 표현하는 언어: $ba^*$ (이 언어는 Regular — Left-Regular 문법) - 하지만 Recursive Descent Parsing을 적용하면: ``` S → Sa → Saa → Saaa → ... ``` $S$에서 출발하면 가장 먼저 $S \to Sa$를 적용 → 다시 $S$가 나오고 → 또 $S \to Sa$ → **무한 루프** **왜 이런 일이 생기나?** → 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.2.2 $S \to S\alpha_1 \mid S\alpha_2 \mid \cdots \mid S\alpha_n \mid \beta_1 \mid \beta_2 \mid \cdots \mid \beta_m$ 예시 기존: $S \to S\alpha_1 \mid S\alpha_2 \mid \cdots \mid S\alpha_n \mid \beta_1 \mid \beta_2 \mid \cdots \mid \beta_m$ 변환: $S \to \beta_1 S' \mid \beta_2 S' \mid \cdots \mid \beta_m S'$ $S' \to \alpha_1 S' \mid \alpha_2 S' \mid \cdots \mid \alpha_n S' \mid \epsilon$ #### 3.4.2.3 $S \to A\alpha \mid \delta, \quad A \to S\beta$ 예시 다음과 같이 직접적으로 보이지 않는 경우도 있다: $S \to A\alpha \mid \delta, \quad A \to S\beta$ 대입하면: $S \to S\beta\alpha \mid \delta$ → 사실상 left-recursive. ### 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 제거 ``` #### 3.4.3.1 $S \to A\alpha \mid \delta,\quad A \to S\beta$ 예시 1. Non-terminal 정렬: $A, S$ 순서 2. $A$에 대해: 아무 일도 일어나지 않음 1. $A$가 `i=1`일 때, 안쪽 루프가 `j = 1 to 0`. **0번 돔** → 루프 자체가 실행이 안 됨. 3. $S$에 대해: - $A \to S\beta$이고 $S$에는 $A$를 앞에 쓰는 production이 있으므로 대입: $S \to S\beta\alpha \mid \delta$ - Direct left-recursion 제거: $S \to \delta S',\quad S' \to \beta\alpha S' \mid \epsilon$ 4. 최종 문법: $S \to \delta S',\quad S' \to \beta\alpha S' \mid \epsilon$ > **단, 이 알고리즘도 항상 작동하는 건 아니다.** 문법에 $\epsilon$-production이나 사이클(예: $A \to B,\ B \to A$)이 있으면 별도 처리가 필요하다. ## 3.5 정리 > §3.4에서 Left-recursion을 제거하는 방법을 다뤘다. > 이로써 Recursive Descent Parsing의 개념, 알고리즘, 한계, > 그리고 한계를 극복하는 방법(문법 변환)을 모두 다뤘다. > > 다음 강의에서는 Backtracking 자체를 없애는 > 보다 효율적인 Top-down parsing — **LL(1) Parsing** 을 다룬다. - Recursive Descent Parsing은 **Top-down parsing의 한 방법** - 핵심 아이디어: **Backtracking** - **Left-recursion이 있는 문법에서는 동작하지 않는다** (무한 루프) - 해결: Left-recursive 문법을 Right-recursive 문법으로 변환 - Backtracking은 비효율적 → 보다 효율적인 Top-Down Parsing이 필요함 --- # 4. Top-Down Parsing (2) - LL(1) Parser ## 4.1 Backtracking의 원인 → Production 선택을 LL(k) Parsing으로 풀어보자 > §4.1에서는 Recursive Descent Parsing의 핵심 한계인 backtracking이 왜 발생하는지 짚는다. 이 원인 파악이 §4.2 이후에 등장하는 LL(1) 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 없이 선택**하는 것. ### 4.1.3 Recursive Descent Parsing과의 비교 — 사칙연산 문법 아래의 문제를, 이미 알고 있는 Recursive Descent Parsing으로 풀어보자. ```plain // 사칙연산 문법 1: Left-Recursive E ::= E + T | E - T | T T ::= T * F | T / F | F F ::= [id] | [num] | ( E ) ``` `사칙연산 문법 1`은 Left-Recursive함. → Recursive Descent Parsing은 Left-Most Derivation을 따르는데, [[#4.1.1 LL(k) Parsing]] → Left-Recursive는 T를 만나기 전에 계속 NT로 감 → 무한 루프 [[#3.4.1 `문제` Left-recursion]] 해결을 위해서는, [[#3.4.3 `해결` 일반적인 Left-recursive → Right-recursive]] 처럼 Right-Recursive로 변환해야 함. ```plain // 사칙연산 문법 2: Left-Recursive를 Right-Recursive로 변환 E ::= T E' E' ::= + T E' | - T E' | T ::= F T' T' ::= * F T' | / F T' | F ::= [id] | [num] | ( E ) ``` `사칙연산 문법 2`는 Right-Recursive → 이제 Recursive Descent Parsing 시도 가능. ```plain // Recursive Descent Parsing 과정 1 Focus = E' Tokens[idx] = - ``` 여기서 어떤 Production을 택해야 할까? > [[#3.2 🚨 Recursive Descent Parsing — 정의]] 의 과정을 다시 복기해보면, > Focus가 NT에 있을 경우 Case 1로 넘어가 Production을 결정한다. > 여기서는 Focus가 E'에 있으니 Case 1로 넘어가 Production을 결정해야 한다. 여기서는 1번째(0-base) rule인 `E' → - T E'` 선택하면, `Tokens[idx] = -` 이므로, 백트래킹은 좀 하겠지만 Production 고르는 데 성공한다. ```plain // Recursive Descent Parsing 과정 2 Focus = E Tokens[idx] = ( ``` 다음 과정으로 넘어와서, 여기서는 어떤 Production을 해야 할까? 직관적으로 `(` 를 소비하고 싶다면 `F → ( E )`가 맞는 선택이지만, 더 복잡한 과정이 필요하다. E의 production이 `E → T E'` 하나니까 이걸 선택해 보자. → production이 하나라서 괜찮을까? → 근데 `E → T E'`를 선택하면 T로 내려가고, → `T → F T'`로 내려가고 → `F → ( E )`... 이렇게 계속 expand해야 한다. → 결국, 같은 문제를 다음 단계에서 계속 반복. ### 4.1.4 Recursive Descent Parsing과의 비교 — 간단한 문법 다른 예시를 보자. 이번에도 Recursive Descent Parsing을 시도한다. ```plain // 간단한 문법 S ::= A a | B b | c A ::= x | B ::= y | ``` 파싱 실행 중에 이런 과정도 있을 수 있다. ```plain // Recursive Descent Parsing 과정 1 Focus = S Tokens[idx] = a ``` 여기서는 어떤 Production을 택해야 할까? 직관적으로 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.1.1 FIRST(γ) 예시 — 사칙연산 문법 ``` // 사칙연산 문법 F ::= [id] | [num] | ( E ) // FIRST(γ) 예시 FIRST(F) = { [id], [num], ( } ``` #### 4.2.1.2 FIRST(γ) 효과 - $A \to \gamma_1 \mid \gamma_2 \mid \cdots \mid \gamma_n$ 일 때, - 모든 쌍에 대해 $\text{FIRST}(\gamma_i) \cap \text{FIRST}(\gamma_j) = \emptyset$ 이면 (서로소이면) - $\forall i, j, \text{FIRST}(\gamma_i) \cap \text{FIRST}(\gamma_j) = \emptyset$ - lookahead token 하나만 보고 backtracking 없이 production을 결정할 수 있다. → 그럼 이건 어떻게 계산할까? ### 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 NULLABLE(X) — ε 유도 가능성 판별 > §4.2.3에서 FIRST 계산이 막히는 지점을 확인했다. > P 여럿을 거쳐 ε으로 유도될 경우, 문법만 봐서는 알 수 없다는 것이다. > > §4.3에서는 그 막힌 지점을 뚫어주는 NULLABLE을 정의하고 알고리즘으로 계산한다. > 이 결과는 §4.2의 FIRST 알고리즘과 §4.4의 FOLLOW 알고리즘 모두에서 사용된다. ### 4.3.1 NULLABLE(X) 정의 $X$로부터 $\epsilon$을 유도할 수 있다면, NULLABLE($X$) = true. 수식으로 쓰면, $\text{NULLABLE}(X) = \text{true} \iff X \Rightarrow^* \epsilon$ → 그럼 이건 어떻게 계산할까? ### 4.3.2 NULLABLE(X) 계산 아이디어 — NT를 계속 확장하자 [[#4.2.2 FIRST(γ) 계산 아이디어 — NT를 계속 확장하자]] 와 같은 아이디어! 최종적으로 $\epsilon$에 닿는 게 목표니까, NT를 쭉쭉쭉 P로 확장하며 T를 찾아가면 된다. ### 4.3.3 NULLABLE(X) 알고리즘 — 코드 ``` // 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') ``` ### 4.3.4 NULLABLE(X) 알고리즘 — 종료성 NULLABLE 맵의 값은 `false → true` 방향으로만 바뀔 수 있다. $T \cup NT$가 유한하므로 변경 가능한 횟수는 유한하고, 그러므로 알고리즘은 반드시 종료된다. ### 4.3.4 NULLABLE(X) 알고리즘 — 예시 ```plain // 사칙연산 문법 3 S ::= E E ::= T E' E' ::= + T E' | - T E' | T ::= F T' T' ::= * F T' | / F T' | F ::= S [id] | [num] | ( E ) ``` NULLABLE을 표로 표현하며 따라가 보자. 시작 상태 | | NULLABLE | | --- | -------- | | S | false | | E | false | | E' | false | | T | false | | T' | false | | F | false | 과정 ```plain α = S α가 NT이므로 P[S]의 production 순회: - S → E γ = E, γ = ε 아님 NULLABLE[E] = false이므로 all NULLABLE[γᵢ] = true 불만족 → NULLABLE[S] 변화 없음 (false 유지) α = E α가 NT이므로 P[E]의 production 순회: - E → T E' γ = TE', γ = ε 아님 NULLABLE[T] = false이므로 all NULLABLE[γᵢ] = true 불만족 → NULLABLE[E] 변화 없음 (false 유지) α = E' α가 NT이므로 P[E']의 production 순회: - E' → + T E' γ = +TE', γ = ε 아님 NULLABLE[+] = false이므로 불만족 - E' → - T E' γ = -TE', γ = ε 아님 NULLABLE[-] = false이므로 불만족 - E' → ε γ = ε → NULLABLE[E'] = true; break → NULLABLE[E'] = true로 변경! ✅ α = T α가 NT이므로 P[T]의 production 순회: - T → F T' γ = FT', γ = ε 아님 NULLABLE[F] = false이므로 불만족 → NULLABLE[T] 변화 없음 (false 유지) α = E' 이미 NULLABLE이므로 스킵 α = T' α가 NT이므로 P[T']의 production 순회: - T' → * F T' γ = *FT', γ = ε 아님 NULLABLE[*] = false이므로 불만족 - T' → / F T' γ = /FT', γ = ε 아님 NULLABLE[/] = false이므로 불만족 - T' → ε γ = ε → NULLABLE[T'] = true; break → NULLABLE[T'] = true로 변경! ✅ α = F α가 NT이므로 P[F]의 production 순회: - F → [id] NULLABLE[[id]] = false이므로 불만족 - F → [num] NULLABLE[[num]] = false이므로 불만족 - F → ( E ) NULLABLE[(] = false이므로 불만족 → NULLABLE[F] 변화 없음 (false 유지) // 1회 순회 결과: // E', T'만 true로 바뀜 → NULLABLE ≠ NULLABLE' → 루프 계속 // ----------------------------------------------- // 2번째 iteration α = S - S → E NULLABLE[E] = false → 불만족 → 변화 없음 α = E - E → T E' NULLABLE[T] = false → 불만족 (T'가 true여도 T가 false라 안됨) → 변화 없음 α = E' → 이미 true → continue α = T - T → F T' NULLABLE[F] = false → 불만족 → 변화 없음 α = T' → 이미 true → continue α = F - F → [id], [num], (E) 전부 false → 변화 없음 // 2회 순회 결과: // 아무것도 안 바뀜 → NULLABLE = NULLABLE' → 종료! // 최종 결과: // E' = true, T' = true, 나머지 전부 false ``` 최종 결과 | | NULLABLE | | --- | -------- | | S | false | | E | false | | E' | false | | T | false | | T' | false | | F | false | ## 4.4 FIRST(γ) — NULLABLE을 반영한 완전한 버전 > §4.3에서 NULLABLE을 구했다. > §4.4에서는 그것을 입력으로 받아 FIRST를 올바르게 계산하는 알고리즘을 제시한다. > 이 FIRST 결과는 §4.5의 FOLLOW 알고리즘과 §4.6의 select 함수에서 사용된다. ### 4.4.1 FIRST 알고리즘 — 핵심 원리 $A \to \alpha,\gamma,\beta$ 일 때, $\text{NULLABLE}(\alpha) = \text{true}$ 이면 즉, $\alpha$가 NULLABLE이면 $\alpha$가 전부 사라지고 $\gamma$가 첫 자리에 올 수 있는데, 그렇다면 "$A$로부터 유도되는 문장의 맨 첫 terminal이 $\gamma$에서 나올 수 있으므로" $\text{FIRST}(\gamma) \subseteq \text{FIRST}(A)$ ### 4.4.2 FIRST 알고리즘 — 코드 ``` 입력: (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 집합이 유한하므로 반드시 종료된다. ### 4.4.4 FIRST 알고리즘 — 예시 초기 상태 (모두 비어 있음) | 기호 | 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.5 FOLLOW(γ) — NULLABLE한 production 선택을 위한 도구 > §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$ 다음에 올 수 있는 것과 같아짐. > 💡 $\text{NULLABLE}(\beta\delta) = \text{NULLABLE}(\beta) \wedge \text{NULLABLE}(\delta)$ ### 4.5.4 FOLLOW 알고리즘 — 코드 ``` 입력: (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') ``` ### 4.5.5 FOLLOW 알고리즘 — 종료성 FOLLOW 집합도 단조 증가하며 Terminal 집합이 유한하므로 반드시 종료된다. ### 4.5.6 FOLLOW 알고리즘 — 예시 아 이것도 나중에 ㅈㄴ급함지금 |기호|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을 만든다. ### 4.6.1 LL(1) Parsing 알고리즘 — 코드 → select가 뭘까? ```pseudo // 전체 입력: (T, NT, S, P) // Grammar tokens // Token들의 list (Lexer가 줬으니!) 변수: tree ← S // 파스트리의 루트 노드 (속성: parent, children, rule) focus ← S // 현재 처리 중인 트리 노드 idx ← 0 // 현재 읽고 있는 token의 위치 stack ← [] // 아직 처리하지 않은 노드들을 쌓아두는 스택 while (true) do if (focus ∈ NT) then // focus가 non-terminal이면 production을 선택해 expand goto Case 1 else if (idx < len(tokens) && focus = tokens[idx]) then // focus가 terminal이고 현재 token과 일치하면 소비 goto Case 2 else if (idx = len(tokens) && stack = []) then // 모든 token을 소비했고 스택도 비었으면 파싱 성공 return tree // LL(1)에서는 backtracking 없음 // else goto Case 3 // Backtrack → 삭제됨 ``` ```pseudo // Case 1 // Recursive Descent 버전 (삭제됨): // (focus → α₁...αₙ) ← P[focus][focus.rule] // focus.rule ← focus.rule + 1 // → production을 순서대로 하나씩 시도했음 (backtracking 발생 원인) // 기존 Recursive Descent와의 차이 // production을 `focus.rule` 순서로 시도하는 대신, // Parsing Table 조회 한 번으로 production을 바로 결정. // 그러므로 Backtracking도 사라진다. // LL(1) 버전: // select로 lookahead token을 보고 production을 딱 하나 결정 (focus → α₁...αₙ) ← select(P, focus, tokens[idx+1]) for 1 ≤ i ≤ n do // 선택한 production의 기호들을 트리에 자식으로 연결 connect(focus, αᵢ) for n ≥ i ≥ 2 do // 첫 번째(α₁) 빼고 나머지를 역순으로 스택에 push // (나중에 순서대로 처리하기 위해) stack.push(αᵢ) // 첫 번째 자식을 다음 focus로 focus ← α₁ ``` ```pseudo // Case 2 // focus가 terminal이고 현재 token과 일치하는 상황 // 현재 token을 소비하고 다음 token으로 이동 idx ← idx + 1 // 스택에서 다음으로 처리할 노드를 꺼냄 focus ← stack.pop() ``` ### 4.6.2 LL(1) Parsing 알고리즘 — select(P, focus, lookahead) #### 4.6.2.1 select — 아이디어 select는 결국 어떤 Production을 골라야 하는지 선택함. focus가 A고, A -> a | b | c ... 뭐 이런 식으로 있다고 치면, production이 여러 개일 때, lookahead token을 보고 **어떤 production을 골라야 하는가**를 결정! focus $\leftarrow \alpha$ 에 대해: focus가 $\alpha$로 전개되는 경우에, focus가 A일 때, $A \to \alpha$ 라는 production 후보에 대해: **경우 1:** $\text{lookahead} \in \text{FIRST}(\alpha)$ 이면 → $\alpha$를 전개했을 때 첫 번째로 lookahead가 나올 수 있으니까 → **$A \to \alpha$ 선택** **경우 2:** $\text{NULLABLE}(\alpha) = \text{true}$ 이고 $\text{lookahead} \in \text{FOLLOW}(\alpha)$ 이면 → $\alpha$가 통째로 사라질 수 있고, 사라진 후에 lookahead가 바로 올 수 있으니까 → **$A \to \alpha$ 선택** 둘 다 해당 없으면 → 이 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$ 선택 | #### 4.6.2.2 select — 예제 **문법** ``` S ::= E E ::= T E' E' ::= + T E' | - T E' | ε T ::= F T' T' ::= * F T' | / F T' | ε F ::= [id] | [num] | ( E ) ``` **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) | | | ### 4.6.3 LL(1) Parsing 알고리즘 — Parsing Table select를 2차원 테이블로 구현한 것. - **Row**: focus (non-terminal) - **Column**: lookahead (terminal) - **Entry**: 선택할 production - **빈 칸**: 오류(Error) | | + | - | * | / | [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) | | | ## 4.7 LL(1) Parsing의 한계 — Conflict > §4.6의 Parsing Table이 잘 동작하려면 각 칸에 production이 **정확히 하나**여야 한다. §4.7에서는 칸에 production이 두 개 이상 들어오는 충돌(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** ``` E ::= E + a | b → FIRST(E + a) = FIRST(E) = { b } → FIRST(b) = { b } → 충돌! ``` **Left-recursion이 없어도 발생 가능** ``` S ::= E | E a E ::= b | ``` E가 nullable이니까: - FIRST(E) = {b} 이고 NULLABLE(E) = true - FIRST(E a) = FIRST(E) ∪ {a} = {b, a} (E가 nullable이니까 a도 포함) 그러면 select 표에서 focus = S, lookahead = `b` 일 때: (문법 보고 생각해보면) - S→E : b ∈ FIRST(E) → 경우 1 → 해당 - S→E a : b ∈ FIRST(E a) → 경우 1 → 해당 → 같은 칸에 두 개 → **FIRST/FIRST Conflict** **해결: Right-recursion으로 변환 + Left Factoring** 공통 prefix를 factoring하여 분리한다. ``` // 원본 (충돌) S ::= E | E a E ::= b | // Left Factoring 후 // S의 우변이 E, E a므로 E라는 공통 prefix가 있음 // 그러니까 나머지 부분을 S'로 뺌 S ::= E S' S' ::= | a E ::= b | ``` 그러면 select 표에서: - focus = S일 때는 무조건 S→E S' 하나뿐 → conflict 없음 - focus = S'일 때 lookahead가 `a`면 S'→a, `나 다른 거면 S'→ → conflict 없음 ### 4.7.2 FIRST/FOLLOW Conflict → Substition으로 해결 NULLABLE한 production이 있을 때, **lookahead가 FIRST에도 속하고 동시에 FOLLOW에도 속하면** select의 경우 1과 경우 2가 동시에 적용되어 충돌이 발생한다. **예시:** ``` // 문법 S ::= A a b A ::= a | // 충돌 예시 → FIRST(A) = { a }, FOLLOW(A) = { $, a } → lookahead = a 일 때: A→a (경우 1)와 A→ (경우 2) 모두 해당 → 충돌 ``` **해결: Substitution → 이후 Left Factoring** A의 production을 A가 쓰인 자리에 **직접 대입**. ``` // 원래 문법 S ::= A a b A ::= a | // Substitution 적용 S ::= a a b | a b // 이러니까 FIRST/FIRST Conflict 추가 발생 // Left Factoring 추가 적용 S ::= a S' S' ::= a b | b ``` > 💡 > Substitution의 결과로 FIRST/FIRST Conflict가 새로 발생할 수 있다. > 그 경우 Left Factoring을 추가로 적용한다. ### 4.7.3 FOLLOW/FOLLOW Conflict ``` A ::= B | C B ::= C ::= → FOLLOW(B) ∩ FOLLOW(C) ≠ ∅ ``` $A \to B \mid C$ 인데 B도 C도 둘 다 nullable일 때, 같은 lookahead에 대해 B를 선택해야 할지 C를 선택해야 할지 결정할 수 없는 상황. 둘 다 어차피 ε이 되니까 FOLLOW(B)랑 FOLLOW(C)가 둘 다 FOLLOW(A)를 포함하게 되고, Conflict 발생하게 됨. 이 경우는 **문법 자체가 모호(ambiguous)함**을 의미하므로 통상적으로는 별도로 다루지 않는다. ($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) 문법인 경우에만 항상 제거 가능하다.** ## 4.8 종합 예제 — 덧셈 문법의 LL(1) 변환과 Parsing > §4.7까지 배운 FIRST/FIRST Conflict와 Left Factoring을 실제 문법에 적용하고, > §4.2~4.5에서 배운 NULLABLE·FIRST·FOLLOW 계산을 거쳐 > 최종 Parsing Table을 완성하는 전체 흐름을 확인한다. ### 4.8.1 원본 문법 → FIRST/FIRST Conflict 확인 ``` S ::= E | E + S E ::= ( S ) | [number] ``` $\text{FIRST}(E) = \text{FIRST}(E + S) = {(,, [\text{number}]}$ → **FIRST/FIRST Conflict** 발생. ### 4.8.2 Left Factoring으로 문법 변환 ``` S ::= E S' S' ::= | + S E ::= ( S ) | [number] ``` ### 4.8.3 NULLABLE · FIRST · FOLLOW 계산 |기호|NULLABLE|FIRST|FOLLOW| |---|---|---|---| |S|false|(, [number]|$, )| |S'|**true**|+|$, )| |E|false|(, [number]|$, +, )| ### 4.8.4 Parsing Table 완성 | |+|(|)|[number]|$| |---|---|---|---|---|---| |S||S→ES'||S→ES'|| |S'|S'→+S||S'→ε||S'→ε| |E||E→(S)||E→[number]|| 각 칸에 production이 하나씩만 들어있다 → **Conflict 없음, LL(1) 문법**. ### 4.8.5 입력 `(1+2+(3+4))+5` 파싱 결과 Parsing Table에 따라 backtracking 없이 파스트리를 유일하게 복원한다: ``` S ├── E → ( S ) │ └── S │ ├── E → [1] │ └── S' → + S │ └── S │ ├── E → [2] │ └── S' → + S │ └── S │ ├── E → ( S ) │ │ └── S │ │ ├── E → [3] │ │ └── S' → + S │ │ └── S │ │ ├── E → [4] │ │ └── S' → ε │ └── S' → ε └── S' → + S └── S ├── E → [5] └── S' → ε ```