![[7. Parser (1) - Post-lecture.pdf]] # Part 1: Language & Grammar ## 왜 이걸 배워야 하는가? ### Lexer와 Parser는 "언어/문법"에 대한 것. - Parser는 당연히 문법에 대한 것 - Lexer도 작게 보면 토큰을 표현하는 문법에 대한 것 --- ## 언어란 무엇인가? ### 언어 - 문법 + 어휘로 이루어진 체계적 커뮤니케이션 시스템 - 우리가 관심있는 건? ### TL;DR (Too long; Don't Read 라네... 신기...): Instance vs Type Code는 Instance, Language는 Type - C Code / Language - C Code: Instance - C Language: Type (특정한 규칙을 갖는 string의 집합) - C Language / Context-Free Language - C Language는 Instance (Language) - Context-Free Language는 Type (Language들의 집합) --- ## String vs Language ### 기본 개념 - Alphabet: 언어를 구성하는 글자들의 집합 $\Sigma$ - Grammar: 언어를 이루고 있는 규칙들의 집합 $G$ - Language: 특정 규칙을 만족하는 문자열의 집합 $L(G)$ - Sentence: $L(G)$의 $G$를 따르는 Alphabet Sequence ### 문법(Grammar) - 문법 생성 규칙: Production - 좌변 → 우변 - 좌변의 문자가 나타나면 우변의 것으로 대체 가능 - 좌변: 항상 가상의 문자 = 변수 - 우변: 가상의 문자일 수도, 실제 문자 ($\Sigma$의 원소)일 수도 - $A \to \epsilon$도 됨 ### Terminal과 Non-Terminal - Terminal: Production에 의해 더 이상 대체 불가 - 문자, $\epsilon$ - Non-terminal: Production에 의해 대체할 수 있는 것 - 변수 - Terminal과 Non-terminal은 Production을 조사함으로써 구성 가능 ### Production의 시작: Non-terminal $S$ ### 언어 문법의 형식적 정의 - 문법의 $P$: 문법 생성 규칙 Production의 집합 ### 예시: 이진수 문법 생성 규칙 - $T = \{0, 1, \epsilon\}$ - $NT = \{A, B, S\}$ - $P = \{\}$ - $G = (T, NT, S, P)$ - $L(G) =$ ### BNF(Backus-Naur Form): 문법의 표현법 - Meta-syntax(Syntax를 표현하기 위한 syntax)의 한 종류 ### BNF 표현법 - Terminal: "..." - Non-Terminal: <어쩌고 저쩌고> - Production: - <...> ::= ... // 좌변 → 우변 ### 이 강의 내 표현 약속 - "" 없이 bold + underline - \[...\] : ...에 해당하는 임의의 문자 1개 - Non-Terminal: 기호 $S$ 이런 걸로 ### 예제: 덧셈 문법 - Production: - Terminal: - Non-Terminal: - 어떤 문장에 대한?: (1+2+(3+4))+5 이런 거 ### 문장의 유도: $S$로부터 Production을 따라서 문장을 만들어내는 과정 1. $S$로부터 시작 2. 한 단계 유도 과정마다, Non-Terminal $A$를 선택하고, $A$에 대한 production $A \to \alpha$에 대해 $A$를 $\alpha$로 대 3. 오직 Terminal로만 이루어질 때까지 반복 $S \to \gamma_1 \to \gamma_2 \to \cdots \to \gamma_n \to s$ - $\gamma_i \in (T \cup NT)^+$ - $s \in T^+$ 문장의 유도 과정이 존재하면 간단히 $S \to^* s$ 라고 씀 ### 문장의 유도 예제: (1+2(3+4))+5 --- ## Language vs Language Type ### 학부 오토마타 수업의 핵심 컴파일러 강의의 관심사: 촘스키 hierarchy의 regular / context-free ### Right-Regular Grammar의 직관적 이해 - $S \to aA \to abB \to abcC \to abcdD \to \cdots$ - Non-terminal A의 의미: a를 입력 받은 상태... - 즉 각각의 Non-Terminal을 하나의 "상태"로 인식 가능, 즉 FSM ### 예시: 이진수 문법 생성 규칙: Regular Grammar ### 어떤 문법이 Regular인지 아닌지? 1. Right-regular grammar라는 조건을 ### 이 문법은 Regular Grammar일까요? 1. 균형 잡힌 괄호 1. (), (()), ()()() 이런 애들 2. 회문어(palindrome) 1. aba, abcba, abba 3. 개수/비교 1. $\{a^nb^b | n \ge 00\}$ 아님~~~ 표현이 안됨~~~ ### 왜 $a^nb^n$은 Regular가 아닌가요? - $S ::= aSb\ |\ \epsilon$ - Left-Regular, Right-Regular도 아님.... - 어케 유도할 수. ㅣㅆ나? - 이게 Regular라면, FSM도 있을 것 - 그럼 뭔지는 몰라도 상태는 k개라고 가정해보자. - $a^{2k}b^{2k}$를 생각해보자. - $k+1$개의 $a$를 읽을 때 그 중 두 상태는 같을 수밖에 없음. - 즉, 상태 전이에 loop가 있다는 것. - loop의 길이를 $l$이라고 하면, 중간에 $a^l$을 추가해도 어차피 똑같음. - $a^{2k+l}b^{2k}$는 우리의 문법에 맞는 언어가 아님. 별로 안 중요해서 넘어간다... ### Regular Language의 한계: 기억 장치 없이 만들 수 있는 문자열들의 집합! - 균형 잡힌 괄호, 회문어, $a^nb^n$, $a^mb^n$ 다 기억장치가 필요함. ### Context-Free Grammar ### 최대 Context-Free Language만 고려 - 지금까지 설명한 내용도 RL / CFL만 고려한 내용. 컴파일러 강의니까~ ### 예시: 균형 잡힌 괄호 문법 $S ::= (\ S\ )\ S\ |\ \epsilon$ - 괄호를 나란히 추가하거나 - 괄호 안으로 들어가거나 ### Context-Free가 아니면? - Free vs Sensitive - Production의 형태가 다름. - Free: $A \to a$ (NT만 좌변) - Sensitive: 그렇진 않음 ### 두 언어 타입: Regular vs Context-Free | Type | Language | Automata | Production | Example | | ---- | -------- | -------- | ------------------- | -------- | | 2 | Free | ? | $A \to a$ | $a^nb^n$ | | 3 | Regular | FSM | $A \to a, A \to aB$ | $a^*b^*$ | --- ## 유도에 대해 ### 복습: 문장의 유도 예제 훨씬 간단하게 표현할 수 있는 방법 O ### Parse Tree - 구성 - Leaf = T - Internal node = NT - 문장: **In-order traversal** 후 leaf만 확인 - 왼쪽을 타고 들어가서... 왼쪽부터 leaf만 확인 - 유도 순서에 대한 정보 X ### 유도 순서 - 크게 중요하지 X - 문법으로 원하는 문장을 만들어 낼 수 있는지가 더 중요 - 정형적 2가지 방법 - Left-most derivation - 가장 왼쪽의 NT를 찾아서 production을 적용 - Right-most derivation - 가장 오른쪽의 NT를 찾아서 production을 적용 ### 예제들: 트리 생기는 순서 보기 ### Left-most vs Right-most Derivations 똑 같 음 - 근데 그럼 parse tree가 다른 경우도 있음? ### 예제: 이런 문법은 어떨까요? 다르네...;; 이런 걸 뭐라고 하냐면 ### 모호한(Ambiguous) 문법 - Ambiguity: 이렇게도, 저렇게도 해석될 수 있는 모호함 (사실 애매한거지) - Ambiguous Grammar: 서로 다른 유도가 서로 다른 parse tree를 만들어내는 문법 ### 덧셈 문법이 모호하지 않은 이유 1. 덧셈은 항상 $S \to E + S$로만 유도 2. 그런데 덧셈의 양 변 중 우변에만 S가 존재. 1. 오른쪽으로만 깊어질 수 있음. 2. right-recursive 3. 보통 이러면 not ambiguous 4. 결합은 오로지 (문장, 문법 X) parse tree에서만 관찰 가능. ### 모호함이 있었던 문법? - 덧셈, 곱셈 모두 - $S$로부터 유도 (선택지가 2개) - 양 변에 $S$를 가짐. (왼/오 에서 다 뻗어나갈 수 있음) ### 모호함을 없애는 방법? - 일반적인 모호함 제거법은 없음 (푸는 게 불가능한 문제) - 그럼 어떻게? ### 문법을 고쳐봅시다 - 요구사항 - 곱셈을 덧셈보다 우선 - 덧셈, 곱셈 모두 왼쪽으로 결합 ### 1. Non-terminal 구분하기 - $E$ Expression 덧셈이 포함된 식 - $T$ Term 곱셈이 포함된 항 - $F$ Factor 곱해지는 숫자 우선순위 $E < T < F$ ### 2. 문법을 다시 쓰기 (1) - S ::= E - E ::= E + E -> 여전히 양쪽으로 퍼질 수 있음 ### 2. 문법을 다시 쓰기 – Left-recursive - S ::= E - E ::= E + T | T - T ::= T * F | F - F ::= \[number\] 오른쪽 거를 더 중요한 걸로 두고, 왼쪽으로 타게 Left-recursive ### 다시 쓴 문법으로 확인해봅시다 parse tree가 똑같음. (직접 해보기) 모호하지 않냐? 라는 문제도 되게 어려운 문제. 다 해보면 not ambiguous ### 또 다른 모호한 문법 if 어쩌고 then if then 어쩌고 else 어쩌고 그럼 else는ㄴ 어디에붙음? 모호하네~;; # ✅✅✅✅✅✅✅✅ 숙제!!!! ✅✅✅✅✅✅✅✅✅