![[8. Parser (2) - Post-lecture.pdf]] # Part 2: Parser Overview `val parser: Token list -> AST` ## Syntax Tree - `정의` Syntax 구문을 다루고 있는 Tree 구조 - Syntax와 Semantics - Syntax: 구문, 형태 - Semantics: 의미 - 우리의 관심사: CFG - `왜?` RL로 표현할 수 없는 것, 기억 장치가 필요한 것들이 있음. 괄호 같은 거 특히! 괄호가 제대로 맞는지를 체크할 수 있어야 함. - `종류` - CST(Concrete Syntax Tree) = parse tree의 다른 이름 - `특징` - 문장의 모든 표현이 Tree에 표현 (Terminal로) - 문자열과 달리 중첩 구조를 표현 - 예: 결합 (or association) - `단점` - **불필요한** 정보가 많음 - `예시` 괄호, Child가 1개인 Node - 특정한 언어에 **종속적인** 표현 - 같은 의미를 가진 코드인데, CST는 다 달라짐. - 컴파일러를 만드는 입장에서는 좋지 않음. 우리의 목적: 재사용을 최대한 많이 하는 게 좋은 것임. 같은 의미의 코드들을 받았으면 각각 작성할 필요가 없음. - AST(Abstract Syntax Tree) 즉 추상적 - `특징` - 핵심적인 표현만 추상화하여 표현한 Tree - 괄호, Child 1개인 node X - 여전히 문법적으로 중요한 요소 포함 - 중첩구조 확인 가능 - 특정 언어와 독립적 - 의미적 요소를 포함하기 시작 - 컴파일러 내 핵심 자료구조 (의미 분석, IR로의 변환) ```mermaid flowchart TD op0["BinOp +"] op1["BinOp +"] n5["Num 5"] op0 --> op1 op0 --> n5 n1["Num 1"] op2["BinOp +"] op1 --> n1 op1 --> op2 n2["Num 2"] op3["BinOp +"] op2 --> n2 op2 --> op3 n3["Num 3"] n4["Num 4"] op3 --> n3 op3 --> n4 ``` ## AST Type의 정의 ```mermaid flowchart TD ifNode["if"] cond["=="] thenNode["="] elseNode[";"] ifNode --> cond ifNode --> thenNode ifNode --> elseNode %% condition: b == 0 b1["b"] zero["0"] cond --> b1 cond --> zero %% then: a = b a["a"] b2["b"] thenNode --> a thenNode --> b2 ``` ```f# type RelOpKind = Eq | Neq //| ... // 비교 연산자 type Expr = | IntLit of int | Var of (name: string) | RelOp of (op: RelOpKind) * (lhs: Expr) * (rhs: Expr) //| ... // 표현식 type Stmt = | AssignStmt of (var: string) * (expr: Expr) | IfStmt of (cond: Expr) * (thenBody: Stmt list) * (elseBody: Stmt list) //| ... // 대입 연산자 let ast = IfStmt (RelOp (Eq, Var "b", IntLit 0), [AssignStmt ("a", Var "b")]) ``` 토큰의 정의가 안 보임... Lexer에서 만들어진 Token은 어디로 갔나요? -> Parser의 추상적 정의: `var parser: Token list -> AST` -> 더 자세히 보면, `Token list` $\to$ `CST-Generator` $\to$ `CST` $\to$ `AST-Generator` $\to$ `AST` ## Parser가 AST를 만드는 과정 **문법** ```ebnf <Stmt> ::= <AssignStmt> | <IfStmt> <AssignStmt> ::= ID ASSIGN <Expr> SEMI <IfStmt> ::= IF LPAREN <Expr> RPAREN <Stmt> <Expr> ::= NUM | ID | <Expr> <RelOpKind> <Expr> <RelOpKind> ::= EQ ``` CST 정의 (코드) ```f# type CSTRelOpKind = | CSTEq of Token type CSTExpr = | CSTNum of Token | CSTId of Token | CSTRelOp of CSTExpr * CSTRelOpKind * CSTExpr type CSTStmt = | CSTAssignStmt of CSTAssignStmt | CSTIfStmt of CSTIfStmt // ID * ASSIGN * Expr * SEMI and CSTAssignStmt = Token * Token * CSTExpr * Token // IF * LPAREN * Expr * RPAREN * Stmt and CSTIfStmt = Token * Token * CSTExpr * Token * CSTStmt ``` ### 예제: CST-Generator Test Case if 대신 of로 들어오면 Lexer와 다르게 CST-Generator는 오류 던짐 즉, 구문 오류를 잡아내야 함! AST Type 정의 ```f# type ASTRelOpKind = | ASTEq //| ... type ASTExpr = | ASTNum of (value: int) * Info | ASTId of (name: string) * Info | ASTRelOp of (op: ASTRelOpKind) * (lhs: ASTExpr) * (rhs: ASTExpr) * Info //| ... type ASTStmt = | ASTAssignStmt of (var: string) * (expr: ASTExpr) * Info | ASTIfStmt of (cond: ASTExpr) * (thenBody: ASTStmt list) * (elseBody: ASTStmt list) * Info //| ... ``` ## Parser의 정의 ```f# module FrontEnd = val cstGenerator: Token list -> Result<CST, Info> val astGenerator: CST -> AST // should be a composition of cstGenerator and astGenerator val parser: Token list -> Result<AST, Info> ``` CST-Generator의 정의 `val cstGenerator: Token list -> CST` - 유도 과정을 Token List로부터 알아내는 것 - 복습: 문장의 유도: $S \to \gamma_1 \to \gamma_2 \to \cdots \to \gamma_n \to s$ - 왜 CST = Pase Tree인가? - Parsing 과정이 CST 복원 과정이기 때문 Parse Tree를 복원하는 두 가지 방법 - 문법 $G = (N, 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$ # Part 3: Top-Down Parsing(1) - Recursive Descent Parser ## Top-Down Parsing이 가능할까? - 잘못된 문장으로 유도할 수 있음 - 아이디어: 잘못되면 되돌아가면 됨. 즉, Backtracking. ### 예제: 덧셈 문법 - 존나 처음부터 문제임. $S \to E$부터 문제였음. 근데 직접적인 문제는 $E \to (\ S\ )$ - 여기서 다른 걸 써보자. $S \to E \to 1$. 또 1이 문제. E에서 갈 수 있는 두 가지가 다 문제. - 처음부터 문제였구나! 를 알게 되는 것.... ## Recursive Descent Parsing - `입력` - $(T, NT, S, P)$ // Grammar - tokens // 토큰 리스트 - `변수` - tree $\leftarrow S$ // Tree node (속성: parent, children, rule) - focus $\leftarrow S$ // Tree node - idx $\leftarrow 0$ // 현재 Token 위치 - stack $\leftarrow [\ ]$ // stack 전체 ```pseudo while (true) do if (focus ∈ NT) then goto Case 1 // Non-terminal else if (idx < len(tokens) && focus = tokens[idx]) then goto Case 2 // Terminal else if (idx = len(tokens) && stack = []) then return tree // Success! else goto Case 3 // Backtrack ``` Case 1: NT ```pseudo (focus -> α₁ ... αₙ) ← P[focus][focus.rule] focus.rule ← focus.rule + 1 for 1 ≤ i ≤ n do connect(focus, αᵢ) for n ≥ i ≥ 2 do stack.push(αᵢ) focus ← α₁ ``` Case 2: T ```pseudo idx ← idx + 1 focus ← stack.pop() ``` Case 3: Backtrack ```pseudo while (true) do error ← focus error_idx ← focus.children.index(error) (부모노드로 가서 부모 기준 포커스가 몇번째 인덱스인지.) goto restore // restore focus, stack, idx goto remove_children if (focus.rule = len(P[focus])) then if (focus = tree) then raise Error else continue else break ``` restore ```pseudo // focus focus ← focus.parent // stack for (error_idx + 1 ≤ i < len(focus.children)) do stack.pop() // idx 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) ``` ### Recursive Descent Parsing의 특징 - Left-most derivation 과정 - `왜?` 그냥 제일 왼쪽부터 매칭하려면 제일 왼쪽에 있는 것부터 유도를 해야함... - 알고리즘은 끝날까요? 특별한 문법이 아닌 경우엔 끝남. - Backtracking은 비효율적일 수 있음 ### Recursive Descent Parsing으로 항상 Parsing이 가능할까요? (알고리즘이 끝날까요?) `예제` $S \to Sa, S \to b$ - 이 Production에 기반한 문법이 표현하는 언어는? $ba^*$ - 이 문법은 Regular? ㅇㅇ Left-Regular - S다음에 계속 S로 처가서 안끝나고 길어짐.... 한도끝도없이... 루프가 생기지 않으면 됨 - 왜 이러는 걸까? **이 문법이 루프를 포함하고 있음** `예제 변경` $S \to S', S' \to aS', S' \to \epsilon$. 위에 거랑 같은 거. - 변경 과정 - $S \to b, S \to Sa$ - $S'$을 만들어서 ... - 이 문법은 괜찮음 - 루프에 빠지기 전에 터미널을 검사함... 백트랙킹은 Left-most derivation을 따라가는데, left-recursive를 따라가면 깊게 들어갈수밖에 없음... - 결국 left-recursion 문법을 right-recursive로 고쳐주면 됨. ### Left-recursive -> Right-recursive - 위에 거랑 비슷한 방식으로 - $S \to \beta_1 S' |\ \beta_2 S' |\ \cdots |\ \beta_m S'$ 그럼 $S \to A\alpha | \delta, A \to S\beta$ - 한눈에 봤을 때 Left-Recursive할까 싶을 수 있는데... 직접 대입해가면서 직접적 형태로 바꿔놓고, 그다음에 체크해보겠다는 것 일반적인 Left-Recursive -> Right-Recursive (별로안중요) ```pseudo Non-terminal NT = {A₁, ..., Aₙ}을 적당한 순서로 정렬 for i = 1 to n do for j = 1 to i - 1 do Aⱼ → δ₁ | δ₂ | ... | δₖ와 Aᵢ → Aⱼγ에 대해 Aᵢ → δ₁γ | δ₂γ | ... | δₖγ로 대체 Aᵢ에 대해서 Left-recursive 제거 ``` 항상 작동하는 걸까? ㄴㄴ 계속 S가 나온 것들...