#컴파일러 #compiler #파서 #parser ![[13. Parser (7) - Post-lecture.pdf]] # Part VIII: Bottom-Up Parsing (4) - LR(1) Parser ## 다루고자 하는 내용 - SLR(1) 파서의 근본적인 문제 - **LR(1) Parsing**: lookahead token을 보다 섬세하게 고려한 파서 ## SLR(1)은 항상 잘 작동할까? ### 예제: 대입 문법 (Assignment Grammar) ```f# 문법: S ::= L = R | R L ::= * R | [id] R ::= L (좌변은 L-value, 우변은 R-value. C에서 *p = x 같은 대입문) FIRST/FOLLOW: NULLABLE FIRST FOLLOW S false *, [id] $ L false *, [id] $, = R false *, [id] $, = ← 주목! ``` ### LR(0) DFA를 만들어보면 Conflict 발생 ```f# Parsing Table (LR(0)): Action Goto = * [id] S L R $ 0 S4 S5 G1 G2 G3 1 A 2 S6/R5 R5 R5 ← SHIFT/REDUCE Conflict! 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: { S → L . = R, R → L . } - '=' 받으면 Shift (S → L = R 진행)하거나 - '=' 받으면 R → L로 Reduce할 수도 있음 (R의 FOLLOW에 '='가 있으니까) → SHIFT/REDUCE Conflict ``` ### SLR(1)로도 해결 안 됨! - SLR(1)은 `R → L`로 reduce할 때 lookahead ∈ FOLLOW(R) = {$, =}인지 확인 - lookahead가 `=`면 FOLLOW(R)에 속하므로 **Reduce를 허용** - 그런데 실제로는 **`=`가 오면 Reduce하면 안 됨** (여전히 충돌) ### 왜 문제인가? `a = b` 예제로 추적 ```f# 올바른 derivation: S → L = R → [id] = R (a = R) → [id] = L (a = L) → [id] = [id] (a = b) Parse Tree: S / | \ L = R | | a L | b 그런데 SLR(1)로 파싱하면: Stack: L, lookahead: = → R의 FOLLOW에 =가 있으니 R → L로 reduce할 수 있음 → 결과: Stack이 R이 됨 Stack: R, lookahead: = → 이제 뭘 할 수가 없음! R 다음에 =가 올 수 없는데 파싱은 진행됨 → "뭔가 이상한데요?" ``` ## 문제의 원인 - **`R` 뒤에는 `=`가 올 수 없음** - `* R = R` (ok): S → L = R → (*R) = R - `R = R` (no): R 바로 뒤에 =가 나오는 derivation은 없음 - 그런데 FOLLOW(R) = {$, =}라서 SLR(1)은 reduce를 허용해버림 - **FOLLOW Set은 과하게 근사한 결과** - `R 뒤에 항상 따라오는 문자들의 집합`이 아니라 - `경우에 따라 올 수도, 안 올 수도 있는 문자들의 집합` ## SLR(1)의 근본적인 문제 - **근본 원인: LR(0) item 기반이기 때문** - Viable prefix DFA를 lookahead를 고려하지 않고 설계 - Reduce가 일어날 수 있는 상황에서 부정확한 FOLLOW를 사용하여 lookahead를 고려 - **상황에 따라 FOLLOW가 달라질 수 있음을 인식 불가** - → **Lookahead token을 고려하여 Item을 설계하자!** = LR(1) Item ## LR(1) Item - LR(1) item은 LR(0) item의 **세분화된** 개념 - LR(0) item: `L → [id] .` - LR(1) item: `L → [id] . , =` 와 `L → [id] . , (lookahead에 따라 구분) - LR(1) item은 LR(0) item과 lookahead token $a$의 pair - `type LR1Item = LR0Item * T` - $A \to \alpha . \beta,; a$의 형태 - $\alpha$: stack top에 존재 - $\beta a$: 남은 입력 token list는 $\beta a$로부터 유도된 문자열을 prefix로 가짐 - $A \to \alpha \beta$를 reduce하고 나면, 남은 입력의 제일 처음은 **반드시 $a$여야 한다** ### 각 LR(1) Item의 의미 - $A \to .\alpha \beta,; a$: 지금까지 읽은 입력은 $A \to \alpha \beta$로 reduce하기에 문제 없는 상태 - $A \to \alpha . \beta,; a$: 위 + $\alpha$까지 인식한 상태 - $A \to \alpha \beta .,; a$: 위 + $\alpha \beta$까지 인식한 상태이고, **lookahead가 $a$이면 reduce 가능** ## LR(1) Item 계산: 어떤 lookahead가 올까? - LR(0) item은 모든 경우가 바로 보임: `L → . [id], L → [id] .` - LR(1) item은 **어떤 lookahead token이 올지 알아야 함** - 예: `S → . L = R, [id]`는 의미 없음 — S 뒤에 [id]가 올 수 없음 (FOLLOW(S) = {$}) ### 아이디어: LR(1) Item의 정의로부터 계산 - LR(1) Item $(A \to \alpha . \beta,; a)$의 의미: $\alpha$를 읽었고, 다음 입력은 $\beta a$로부터 유도됨 - = $\alpha$까지 읽었을 때, 다음에 올 첫 입력은 **FIRST($\beta a$)** ### Closure 규칙 - LR(1) Item $(A \to \alpha . B\beta,; a)$가 주어지면, - 모든 $b \in \text{FIRST}(\beta a)$에 대해 $(B \to . \gamma,; b)$는 유효한 LR(1) Item - 예: `(L → * . R, =)`가 주어지면 `(R → . L, =)`는 유효 - 시작점: $(S' \to . S,; $)$로부터 따라가면서 만들면 됨 ### LR(1) Item 구하는 알고리즘 ```f# 입력: (T, NT, S, P) // Grammar FIRST // Map<T ∪ NT, Set<T>> 변수: Items ← {} // Set<LR1Item> WorkList ← {(S' → S, $)} // Set<P * T> pairs ← {(S' → S, $)} // 이미 처리한 pair // 1. (prod, lookahead) pair들을 BFS로 확장 while (WorkList ≠ ∅) do WorkList, (prod, t) ← pop(WorkList) // prod = A → γ₁ γ₂ … γₙ for X ∈ {γ₁, …, γₙ} ∩ NT do // X = γᵢ, α = γ₁…γᵢ₋₁, β = γᵢ₊₁…γₙ for prod' in P[X] && a ∈ FIRST(β · t) do if (prod', a) ∉ pairs then pairs ← pairs ∪ {(prod', a)} WorkList ← WorkList ∪ {(prod', a)} // 2. 각 pair에 대해 LR(0) item들을 LR(1) item으로 승격 for (prod, t) ∈ pairs do for item ∈ LR0(prod) do // prod의 모든 LR(0) item (marker 위치별) Items ← Items ∪ {(item, t)} ``` ## 예제: 대입 문법의 LR(1) DFA ```f# 문법: S ::= L = R | R L ::= * R | [id] R ::= L LR(1) DFA 핵심 관찰 (LR(0) vs LR(1) 비교): LR(0)에서는 하나의 state에 { L → [id] . } 하나만 있어서 reduce 시 FOLLOW(L) = {$, =} 전체를 허용. LR(1)에서는 L → [id]가 등장하는 context에 따라 lookahead가 다름: - L이 S ::= L = R의 시작에서 왔을 땐 (L → [id] ., =) - L이 R ::= L을 거쳐 우변에 있을 땐 (L → [id] ., $) → 이제 state가 분리되어 conflict 발생 안 함! ``` ### LR(1) Parsing Table (주요 state) ```f# State 내용 S L R = * [id] 0 (S'→.S, $), (S→.L=R, $), (S→.R, $), (L→.*R, =), (L→.[id], =), 1 2 3 4 5 (R→.L, $), (L→.*R, $), (L→.[id], $) 1 (S'→S., $) 2 (S→L.=R, $), (R→L., $) 6 3 (S→R., $) 4 (L→*.R, =), (L→*.R, $), (R→.L, =), (R→.L, $), ... 7 8 4 5 5 (L→[id]., =), (L→[id]., $) 6 (S→L=.R, $), (R→.L, $), (L→.*R, $), (L→.[id], $) 9 10 11 12 7 (R→L., =), (R→L., $) 8 (L→*R., =), (L→*R., $) 9 (R→L., $) 10 (S→L=R., $) 11 (L→*.R, $), ... 9 13 11 12 12 (L→[id]., $) 13 (L→*R., $) 핵심: State 2에서 이제 (R → L ., $)만 있고 '='는 없음! → lookahead가 '='일 때 S → L = R로 shift만 하면 됨 → Conflict 해결! ``` ## LR(1) Parsing의 장단점 - **장점**: 더 정확한 LR(1) item 기반으로 더 많은 문법 분석 가능 - 많은 Programming Language가 LR(1) 문법에 속함 - **C / C++ / Java / Python** 등 - **단점**: **Viable Prefix DFA 상태 개수가 엄청 많아짐** - LR(0)에서 state가 10개라면 LR(1)에서는 100개+ 될 수도 있음 - → 상태 수를 줄이는 heuristic: **LALR(1)** (같은 core를 가진 state들을 병합) ## Reduce/Reduce Conflict는? - 문법이 **모호(ambiguous)** 해서 생기는 경우가 많음 - 해결: **문법 자체를 고치거나, 우선순위(precedence)를 통해 해결** ## LR(1) 문법 계층 ```f# 포함 관계: Regular Grammar ⊊ SLR(1) Grammar ⊊ LR(1) Grammar ⊊ Context-Free Grammar Ambiguous Grammar는 CFG 안에 있지만 LR(1)과 disjoint (모호한 문법은 LR(1)로도 처리 불가) ``` ## Part VIII 정리 - SLR(1)의 근본 문제: LR(0) item 기반, FOLLOW가 과하게 근사 - **LR(1) Item** = (LR(0) item, lookahead token) pair - Closure 규칙: $(A \to \alpha . B \beta, a)$ → 모든 $b \in \text{FIRST}(\beta a)$에 대해 $(B \to . \gamma, b)$ 추가 - LR(1) parser는 더 많은 문법을 커버하지만 state 수가 폭발함 --- # Part IX: Parser 마무리 ## 다루고자 하는 내용 - AST 생성 과정: CST→AST, Token list→AST - Parser 생성기 – Yacc - Parser 구현에서의 고민거리들 ## Parser의 추상적 정의 (복습) - `val parser: Token list -> AST` - 내부 구조: `Token list → [CST-Generator] → CST → [AST-Generator] → AST` ## CST vs AST - **CST** (Concrete Syntax Tree = Parse Tree): 문법의 모든 세부사항 포함 (괄호, 세미콜론 등) - **AST** (Abstract Syntax Tree): 핵심 표현만 추상화 - 괄호 X - Child 1개인 node X (예: `CSTExpr → CSTNum → NUM`은 AST에선 `ASTNum` 하나로) - 여전히 문법적으로 중요한 요소는 포함 (중첩 구조 확인 가능) - 특정 언어와 독립적인 표현 - **의미적(semantic) 요소들을 포함하기 시작** - 컴파일러에서 사용되는 **핵심 자료구조 중 하나** - 의미 분석, IR로의 변환 등 ### 예: `if (x == 0) y = 1;` ```f# CST (parse tree) AST ───────────────── ─── CSTStmt(CSTIfStmt) ASTStmt(ASTIfStmt) CSTIfStmt ASTExpr(ASTRelOp) IF ASTExpr(ASTId "x") LPAREN ASTRelOpKind(ASTEq) CSTExpr(CSTRelOp) ASTExpr(ASTNum 0) CSTExpr(CSTId) → ID ASTStmt(ASTAssignStmt) CSTRelOpKind(CSTEq) → EQ ASTExpr(ASTId "y") CSTExpr(CSTNum) → NUM ASTExpr(ASTId "1") ← 대입값 RPAREN CSTStmt(CSTAssignStmt) ID, ASSIGN, ID, SEMI ``` ## CST → AST 변환 - CST를 순회하면서 불필요한 node 제거, 의미적인 구조만 남김 - Recursive하게 각 CST node 타입마다 변환 함수 작성 - `CSTIfStmt → ASTIfStmt` - `CSTRelOp → ASTRelOp` 같은 식 ## Token list → AST (직접 변환) - CST를 안 거치고 **바로 AST를 생성**하는 방식 - Shift-Reduce parsing 중에 **두 개의 stack**을 운영 - **CST Stack**: 원래의 파싱 stack - **AST Stack**: CST와 병렬로 AST node를 쌓음 - Reduce할 때: - CST Stack: production 우변을 pop하고 CST node 생성 후 push - AST Stack: 대응되는 AST node 생성 후 push (필요한 정보만 추출) - 장점: 메모리 절약, CST를 구축할 필요 없음 - 실전 컴파일러들은 보통 이 방식 사용 ## Parser 생성기: Yacc - **Yacc**: Context Free Grammar → Parser - **Y**et **A**nother **C**ompiler-**C**ompiler - 1970년대 Stephen C. Johnson 제안 - C언어를 위한 도구 (생성되는 parser는 C 코드) - 각 언어마다 다양한 버전 존재 - **FsYacc**: F#을 위한 Yacc - `Parser.fsy` (grammar 정의) → `Parser.fs` 생성 - 비슷한 도구들 (Spring/Java 생태계 연결) - **Bison** (GNU의 Yacc 확장판, C/C++) - **CUP** (Java용 Yacc) - **ANTLR** (Java 기반, LL(*) — 가장 널리 쓰이는 parser generator) - Spring Expression Language(SpEL), Hibernate HQL 파서가 ANTLR 기반 ## Parsing을 굳이 배우는 이유 (Yacc 쓰면 되는데?) - **문법을 잘못 디자인하면 Conflict가 발생** - LR(1) 문법이 아닌 경우 등 - Yacc로 해결되는 부분도 있지만, **문법 구조를 고쳐야 해결되는 경우**가 존재 - 즉, 문법을 **어떻게 고쳐야 할지 이해하기 위함** ## Parser 구현에서의 고민거리들 ### 1. LR(1) Parser의 DFA 상태 수 - LR(1) item을 쓰니 state 수가 폭발 → **LALR(1)** heuristic - 같은 LR(0) core를 공유하는 state들을 병합 - lookahead set만 합치면 됨 → state 수는 LR(0) 수준으로 유지 - **대부분의 실전 parser generator (Yacc/Bison)가 LALR(1) 사용** ### 2. 여전히 다루지 못하는 Conflict - LL(1): First/First, First/Follow conflict - LR(1): Shift/Reduce, Reduce/Reduce conflict - → 연산자 우선순위 선언, precedence directive로 해결 (Yacc의 `%left`, `%right` 등) ### 3. 어떤 문법을 사용하여 언어를 디자인할 것인가? - 언어 설계 시 파싱 난이도 고려 - 보통 **LR(1) 또는 LL(*)** 급 문법으로 설계 - C/C++/Java: LR(1) 계열 - Python: LL(1) 기반 (단, indentation은 lexer에서 처리) - 문법을 너무 자유롭게 설계하면 파서 구현이 불가능하거나 복잡해짐 ### 4. 파싱 에러 복구 (Error Recovery) - `IDE의 Linter를 구현하고 싶은데 중간에 오류가 나면 그 이후는 검사 못하나요?` - **Panic mode recovery**: 에러 발생 시 synchronizing token(예: `;`, `}`)까지 skip 후 재개 - **Error productions**: 문법에 에러 패턴을 미리 정의 - IDE용 parser는 이 error recovery가 핵심 (IntelliJ, VSCode 언어 서버 등) ## Part IX 정리 - **AST는 컴파일러의 핵심 자료구조** — 이후 단계(의미 분석, 최적화, 코드 생성)의 입력 - CST→AST 변환, Token→AST 직접 변환 두 가지 방식 존재 - Yacc 같은 parser generator가 있지만, **문법 설계와 conflict 해결을 위해 이론 공부 필요** - 실전 고민: 상태 수 최적화(LALR(1)), 남은 conflict 처리, 에러 복구 --- # 전체 Parser 시리즈 정리 (개인 복습용) ```f# Parsing 방식 요약: Top-down (LL 계열): ├─ Recursive Descent + Backtracking : 비효율적 └─ LL(1) : FIRST/FOLLOW로 lookahead 1개 └─ Left-recursion 불가 → right-recursion 변환 필요 Bottom-up (LR 계열): ├─ LR(0) : lookahead 없음, conflict 많음 ├─ SLR(1) : FOLLOW로 reduce 결정 (느슨한 근사) ├─ LALR(1) : LR(1) state를 core 기준 병합 (실전 표준) └─ LR(1) : 정확한 lookahead, state 수 폭발 문법 포함 관계: Regular ⊊ LL(1) ⊊ ? ⊊ LR(1) ⊊ Unambiguous CFG ⊊ CFG SLR(1) ⊊ LALR(1) ⊊ LR(1) 도구: LL(*) → ANTLR (Java 생태계 최강) LALR(1) → Yacc, Bison, CUP, FsYacc ``` ## Spring/Java 개발자 관점 실무 연결 - **직접 파서를 짤 일**: 드묾. 하지만 다음 경우엔 필수 - 커스텀 DSL 설계 (비즈니스 규칙 DSL, 쿼리 DSL) - 템플릿 엔진, Expression Language 확장 - 코드 생성기 / 정적 분석 도구 - **ANTLR 활용 예시** (Spring 생태계) - SpEL, Hibernate HQL/JPQL, Drools 룰 엔진 - `@Query` 어노테이션의 JPQL 파싱 - **이 강의에서 얻을 것** - ANTLR/Yacc 문법 작성 시 conflict 경고 이해 - Left-recursion, 우선순위 declaration이 왜 필요한지 - AST 기반 작업(AOP 프록시, 바이트코드 조작) 시 tree 구조 이해