#컴파일러 #compiler #파서 #parser ![[9. Parser (3) - Post-lecture.pdf]] # Part 4: Top-Down Parsing (2) - LL(1) Parser ## 왜 Backtracking이 일어날까요? 잘못 선택했으니까.... ## Production 선택에 개선이 필요하다 -> 이걸 이제 ## LL(k) Parsing = Predictive top-down parser - Left to Right, Left-most derivation - k개의 token을 미리 살펴보고 (lookahead) parsing ## 우리가 풀고자 하는 문제 - $A \to \alpha | \beta$ 와 $a = tokens[idex + 1]$가 주어짐. - $A \to \alpha$와 $A \to \beta$ 중에 하나를 선택하는 것 ### 예제: 사칙연산 문법 - `문제` Left-recursive해서 루프를 돌 수밖에 없음 ### 예제: Right-recursive 사칙연산 문법 - 앞에 있는 `Tokens[idx]`를 보고 고름. - 32p의 경우 뭘 골라야 할까? 토큰을 봐도 Rule에 없는 애면 어떻게 해야 할지 모름. - 33p의 경우에도 왼쪽만 봐서는 모름, 오른쪽 식들 입실론으로 가서 a로 가야 함... ## Lookahead token을 보고 어떻게 Production을 결정? ### FIRST($\gamma$) - $\gamma$로부터 유도될 수 있는 모든 문장의 가장 **처음**에서 발견할 수 있는 terminal들의 집합 - FIRST(F) = {\[id\], \[num\], (} - $A \to \gamma_1 | \gamma_2 | \cdots | \gamma_n$일 때 - FIRST($\gamma_1$), FIRST($\gamma_2$), ... FIRST($\gamma_n$)이 쌍마다 서로소이면 - ∀𝑖, 𝑗, FIRST($\gamma_i$) ∩ FIRST($\gamma_j$) = ∅ - Lookahead token을 보고 backtracking 없이 production 결정 가능 ### FIRST($\gamma$) 구하기 - 아이디어: NT를 계속 확장 - 만약, $B \to \epsilon$은 있지만 $B \to^* \epsilon$이면? ### NULLABLE($X$) - $X$로부터 $\epsilon$을 유도할 수 있으면 NULLABLE($X$) = true - NULLABLE(T') = true ### NULLABLE($X$) 구하기 - 터미널로 시작하면 nullable일 수가 없음 ```f# 입력: (T, NT, S, P) // Grammar 변수: // Map<T ∪ NT, bool>, NULLABLE[α] = false NULLABLE ← {} NULLABLE’ // Map<T ∪ NT, bool> do NULLABLE’ ← copy(NULLABLE) // 이번 iteration에서 변화 있었는지 체크 for α ∈ T ∪ NT do // 모든 기호 다 확인 (terminal + non-terminal) if NULLABLE[α] = true then continue // 이미 true면 스킵 elif α ∈ T then // suppose α = a NULLABLE[α] = true; continue for A ← γ ∈ P[A] do // suppose α = A // suppose γ = γ₁γ₂ ... γₙ, γᵢ ∈ T ∪ NT if γ = ε then NULLABLE[A] = true; break elif all NULLABLE[γᵢ] = true then NULLABLE[A] = true; break while (NULLABLE <> NULLABLE’) ``` ### FIRST 구하는 알고리즘의 핵심 - $A \to \alpha \gamma \beta$일 때 NULLABLE($\alpha$) = true면 - FIRST($\gamma$) $\subseteq$ FIRST($A$) ### FIRST 구하는 알고리즘 ```f# 입력: (T, NT, S, P) // Grammar NULLABLE // Map<NT, bool> 변수: FIRST ← {} // Map<T ∪ NT, Set<T>>, FIRST[α] = ∅ FIRST’ // Map<T ∪ NT, Set<T>> do FIRST’ ← copy(FIRST) for α ∈ T ∪ NT do if α ∈ T then // suppose α = a FIRST[α] = {a}; continue for A → γ ∈ P[A] do // suppose α = A // suppose γ = γ₁γ₂ ... γₙ, γᵢ ∈ T ∪ NT for 1 ≤ i ≤ n do if i = 1 then FIRST[A] = FIRST[A] ∪ FIRST[γ₁] elif NULLABLE[γᵢ₋₁] = false then break // 앞에 게 NULLABLE이 아니면 걍 다 넘어감 (break) else FIRST[A] = FIRST[A] ∪ FIRST[γᵢ] // NULLABLE이면 FIRST를 합쳐준다 while (FIRST <> FIRST’) ``` - 초기값은 공집합으로 초기화 - 계속해서 FIRST의 카피를 갖고 있으면서, 달라지면 다시 돌아와서 처음부터. - 알파가 터미널일 때와 논터미널일 때로 나눠서 생각 - 터미널: 그대로 - 이 알고리즘은 끝남 ### 예제: FIRST ## FIRST까지 구했으니, 이제 Top-Down Parsing이 가능하네요? ### 예제: Right-recursive 사칙연산 문법 (E') - Recursive descent parsing을 수행 중 - Focus = E' - Tokens\[idx\] = ) - 어떤 production을 택해야 할까요? - 아직도 대답할 수 없는 상황. - $E' \to \epsilon$이 올바른 production일까요? ### FOLLOW($\gamma$) - $S$로부터 $\gamma$를 거쳐 유도되는 모든 문장에서 $\gamma$의 바로 다음에 발견할 수 있는 terminal들의 집함 - $\exists s \in T^*,\; S \Rightarrow^* \alpha \gamma a \beta \Rightarrow^* s \text{ for some } \alpha, \beta \in (T \cup NT)^*$ - $a \in \mathrm{FOLLOW}(\gamma)$ - {)} $\subseteq$ FOLLOW(E) - FOLLOW($S$) = {$} - $: EOF(End-Of-File)를 나타내는 기호 (or Stack bottom) ### FOLLOW 구하는 알고리즘의 핵심 - $A \to \alpha \gamma \beta \delta$일 때, NULLABLE($\beta$) = true이면, FIRST($\delta$) $\subseteq$ FOLLOW($\gamma$) - $A \to \alpha \gamma \beta \delta$일 때, NULLABLE($\beta \delta$) = true이면, FOLLOW($A$) $\subseteq$ FOLLOW($\gamma$) - NULLABLE($\beta \delta$) = NULLABLE($\beta$) $\wedge$ NULLABLE($\delta$) ### FOLLOW 구하는 알고리즘 ```f# 입력: (T, NT, S, P) // Grammar NULLABLE // Map<NT, bool> FIRST // Map<T ∪ NT, Set<T>> 변수: // Map<T ∪ NT, Set<T>>, FOLLOW[S] ← {$}, FOLLOW[α] ← ∅ FOLLOW ← {} FOLLOW’ ← {} // Map<T ∪ NT, Set<T>> do FOLLOW’ ← copy(FOLLOW) for α ∈ T ∪ NT do if α ∈ T then continue // skip for A ← γ ∈ P[A] do // suppose α = A // suppose γ = γ₁γ₂ ... γₙ, γᵢ ∈ T ∪ NT for 1 ≤ i ≤ n do if ∀j ∈ {i + 1, ..., n} NULLABLE(γⱼ) then FOLLOW(γᵢ) = FOLLOW(γᵢ) ∪ FOLLOW(A) for i < j ≤ n do if ∀k ∈ {i + 1, ..., j - 1} NULLABLE(γₖ) then FOLLOW(γᵢ) = FOLLOW(γᵢ) ∪ FIRST(γⱼ) while (FOLLOW <> FOLLOW’) ``` ## FIRST와 FOLLOW를 어떻게 알고리즘에 적용할까요? ### select($P$, focus, lookahead) - 앞에서 구한 FIRST와 FOLLOW를 사용하여 select를 구현해봅시다 - focus $\leftarrow \alpha$ 에 대해, - 경우 1: lookahead $\in$ FIRST($\alpha$)이면 - focus, lookahead가 주어졌을 때 focus $\leftarrow \alpha$ 선택 - 경우 2: NULLABLE($\alpha$) = true이고 lookahead $\in$ FOLLOW($\alpha$)이면 - focus, lookahead가 주어졌을 때 focus $\leftarrow \alpha$ 선택 ### parsing table - select를 table로 구현한 것 - Row: focus - Column: lookahead - Entry: production - Empty entry: Error ### Case 1: Non-terminal (LL(1) Parsing 버전) ```f# lookahead ← tokens[idx] (focus → α₁ ... αₙ) ← ParsingTable[focus][lookahead] for 1 ≤ i ≤ n do connect(focus, αᵢ) for n ≥ i ≥ 2 do stack.push(αᵢ) focus ← α₁ ``` ## LL(1) Parsing은 언제나 잘 작동하나요? ### FIRST/FIRST 충돌 (Conflict) - $A \to \alpha | \beta$일 때, - FIRST($\alpha$), FIRST($\beta$)가 서로소가 아니면 - FIRST($\alpha$) $\cap$ FIRST($\beta$) $\neq \emptyset$ ### FIRST/FIRST 충돌 (Conflict) 예시 - Left-recursion - 해결 방법은? Right-recursion으로 바꿔주면 됨. - Left Factoring! ### FIRST/FOLLOW 충돌 - focus $\leftarrow \alpha$에 대해, - 경우 1: lookahead $\in$ FIRST($\alpha$)이면 - focus, lookahead가 주어졌을 때 focus $\leftarrow \alpha$ 선택 - 경우 2: NULLABLE($\alpha$) = true이고 lookahead $\in$ FOLLOW($\alpha$)이면 - focus, lookahead가 주어졌을 때 focus $\leftarrow \alpha$ 선택 ### FIRST/FOLLOW 충돌 (Conflict) 예시 - 해결 방법? substitution - 근데 결과로 다시 FIRST/FIRST Conflict 발생 가능 ### FOLLOW/FOLLOW 충돌은 잘 고려하지는 않음.