Compiler - Syntax Analysis(01)
- Syntax Analysis는 파서, LL, LR 파싱으로 포스트를 나눴다. 이번 포스트는 Syntax Analysis의 역할과, Parser에 대해 다룬다.
Syntax Analysis (Part 1)
Syntax vs Semantics
- Syntax(구문) : 형식적 구조, 문법을 의미
- Semantics(의미) : 코드나 문장이 무엇을 뜻하는가에 대한 내용
Syntax는 의미가 성립하지 않아도 상관이 없음.
문법만 맞으면 가능! -> 문법 Context-Free Grammar 사용
CFGs
CFGs (Context-Free Grammars) : 문맥 자유 문법
- Regualar Language 의 한계
정규 언어는 Finite State Machine (FSM) 으로 표현 가능한 언어
FSM은 기억 능력이 없기에 중첩된 구조 를 처리할 수 없음.
**L = { aⁿbⁿ n ≥ 0 }** a와 b의 개수가 정확히 같아야 함. 이런 경우에 개수가 정확히 같아야하기에 기억 능력이 없는 Relgular Language는 표현 불가능.
- Grammar
G = (V, Σ, R, S)
Terminal Symbols : 터미널 기호, 실제 언어에 나타나는 문자들(token)
Non-terminal Symbols : syntactic variable
Start-Symbol : 문장 생성의 시작점, Non-terminal의 하나
Productions : ‘productions’ (화살표)
- Derivation : 시작기호 S부터 생성 규칙을 반복 적용하여 최종적으로 터미널(실제 문자)만 남도록 하는 과정
- Sentence : CFG의 시작 기호로부터 도출 가능한 문자열
-
Language : 모든 Sentence의 집합
- Sentential Form : CFG에서 시작 기호로부터 유도되어 나올 수 있는 중간 단계 문자열을 의미함. 터미널 기호와 논터미널 기호가 섞여 있을 수 있음.
CFG는 nested statement를 표현할 수 있음.
Parsing(파싱)
- 파서는 토큰 스트림을 받아 문법적 구조가 유효한지 판단하고 구문 트리(Parse Tree 또는 AST) 를 생성함
- 두 가지 목적
- 문법 체크 (Validity Check)
- 구문 트리 생성 (Tree Construction)
- Derivations
- Leftmost Derivation : 항상 왼쪽의 non-terminal부터 대체
- Rightmost Derivation : 항상 오른쪽의 non-terminal부터 대체
- Parse Tree
- Parent Node와 children of a nod로 구성
- 트리의 leaves는 항상 terminal, non-leaves는 non-terminal
- 파싱 시간
O(n^3)=> 비효율적이기에 다음 3가지로 효율을 최적화 할 수 있음.
- non-Ambiguous
- has no left recursion
- has only one choice of production starting from a specific input symbol for each non-terminal
Ambiguity
Ambiguity (모호성) **이란 하나의 문자열이 **둘 이상의 파싱 트리를 갖는 경우를 말함. 즉, 문법이 애매하게 해석될 수 있다.
-
예시)
E → E + E | E * E | ( E ) | id
- (id + id) * id 로 해석이 가능하고, id + (id * id) 로도 해석이 가능함.
-
모호성을 제거하는 방법
- 연산자 우선순위 (precedence) 반영
- 우선순위가 더 높은 연산자를 하위 계층으로 빼야함.
- 연산자 결합법칙(Associativity) 반영
- 왼쪽 결합(left-associative)
- 오른쪽 결합(right-associative)
대표적 예시 : if-then-else 구문 (dangling else)
stmt → if expr then stmt | if expr then stmt else stmt | other
위 derivation을 통해
if a then if b then s1 else s2로 나타낼 수 있음.
- 두 가지 해석 (Ambigutiy)
- else가 가장 가까운 if에 붙는 경우 (정상적 해석)
- else가 첫 번째 if에 붙는 경우 (모호한 해석)
- 해결 방법
각각의 else를 가장 가까운 매치되지 않은 then 과 연결
stmt → matched_stmt unmatched_stmt
matched_stmt → if expr then matched_stmt else matched_stmt other unmatched_stmt → if expr then stmt | if expr then matched_stmt else unmatched_stmt
전형적인 파싱에서 (top-down) 시작 symbol로 부터 내려갈 때, 문법에서 앞에 나오는 기호를 재귀적으로 확인하면서, 입력과 맞는 단어를 찾는다.
여기서는 크게 Left Recursion 과 common prefix의 문제가 존재한다.
Left Recursion (좌측 재귀)
문법 규칙에서 자기 자신을 왼쪽에서 재귀적으로 호출하는 것을 의미함.
expr → expr + term | term 처럼, 무한 재귀에 빠짐.
- 해결방법 : Right Recursion의 사용
expr → term expr'
expr' → + term expr' | ε
규칙을 나누고, 새로운 non-terminal을 만들기
반복이 끝낼 수 있도록 ε 추가하기
Left Factoring
문법 규칙에서 공통 접두사(prefix)를 꺼내서 예측가능한 파서가 결정적인 선택을 하도록 돕는 변형 기법
즉, 규칙들이 공통된 시작을 가질 때, 두 가지 이상의 derivation에 대해 어디로 가야할지 정해야하기 때문에 그 시작을 밖으로 꺼내 파서가 예측할 수 있도록 만드는 방법
- 사용 이유
- LL파서는 처음 몇 글자만 보고 어떤 글자를 써야하는지 결정해야함.
- 공통시작이 있으면 혼란스럽기에 Left Factoring으로 해결
- 예시
| Before | After (Left Factored) |
|---|---|
| A → αβ₁ | αβ₂ | A → α A’ A’ → β₁ | β₂ |