Compiler - Syntax Analysis(02)
이번에는 Syntax Analysis의 Top-down parsing 과 backtracking, LL(1) parsing에 대해 다룬다.
Syntax Analysis (Part 2)
임의의 CFG에 대해, 파싱하는 시간은 O(n^3) 이 걸린다.
하지만, O(n) 이 걸리는 방법이 있는데, 다음 두 개와 같다.
- LL grammars : Top-Down 파싱의 LL parsing Algorithm
- LR grammars : Bottom-Up 파싱의 LR parsing Algorithm
OverView
- Top-Down Parsing
시작 심볼(Start Symbol)에서 출발하여 파싱 규칙을 따라가며 입력을 유도함.
즉, 위에서 아래로 문장을 예측하며 만들어감.
(사용기술)
- Recursive Descent Parser : 재귀 하강 파서
- Predictive Parsing : LL Parser, LL(1)
(특징)
- 왼쪽부터 유도하는 Leftmost Derivation을 사용
- Left Recursion 문제가 존재하기에 제거가 필요함.
- Bottom-Up Parsing
입력 문자열로부터 시작해서 거꾸로 규칙을 적용하여 시작기호까지 올라가는 방식
아래에서 위로 감지하며 만들어감
(사용기술)
- Shift-Reduce Parser
- LR Parser : LR(0) , SLR, LALR, Canonical LR
(특징)
- 오른쪽부터 유도하는 Rightmost Derivation을 사용
- Left Recursion을 허용 가능함.
- 구현하기에 더 복잡하지만, 더 강력함
Left Recursion 허용 관점으로 보는 것으로 알 수 있지만, LR grammar가 LL grammar보다 더 큰 개념
- LL grammar 는 LR grammar의 subset
Top-Down Parsing
Top-Down Parsing은 LL Parsing이라고 부르기도 함.
LL Parsing의 LL의 의미
- 앞 글자 L : Left to Right scanning of input
- 뒷 글자 L : Leftmost Derivation
Recursive Descent Parsing
Top-Down 파싱 기법 중 하나로, 각 문법 규칙에 대해 하나의 재귀 함수를 만들어 문장을 분석하는 방식
말 그대로 재귀적으로 앞의 non-terminal부터 input terminal과 같도록 찾는 과정을 수행하는데, 적절하지 않을 때 Backtracking을 하게 됨.
- Backtracking
문장을 파싱할 때 규칙 하나로 해보다가 실패하면 다른 규칙을 시도하는 것, 올바른 규칙을 찾을 때까지 규칙을 되돌아가며 다른 경로를 탐색하는 과정을 말함.
주로 공통 접두사가 있을 때 사용함.
- 문제점
- 비효율적 (가능한 모든 규칙들을 다 시도하기 때문)
- 재귀 호출이 많아짐 => 성능이 떨어짐
function E() {
T();
E_();
}
function E_() {
if (nextToken == '+') {
match('+');
T();
E_();
}
// else: ε (아무 것도 안 함)
}
function T() {
if (nextToken == 'int') {
match('int');
} else {
error();
}
}
장점 : 구현이 직관적이고 쉬움, 코드도 명확함
단점 : Left Recursion 제거가 필요함. (요구사항)
즉, backtracking으로 인해 비효율적임.
모든 input 문자열이 같을 때 => Accept
그 외의 경우 => Reject
LL(1) Parsing
- L: 입력을 Left to right (왼쪽에서 오른쪽)으로 읽는다
- L: Leftmost derivation (왼쪽에서부터 유도)을 만든다
- (1): lookahead가 1. 즉, 다음 한 글자(토큰)만 보고 어떤 규칙을 적용할지 결정한다
입력ㅇ르 왼쪽부터 한 글자씩 읽어가며 왼쪽부터 유도해나가는 파서고, 미리보기 토큰이 1개인 아주 효율적인 방식
-
장점
Fast
O(n)로, linear time을 만족 -
요구사항
non-ambiguous, no left recursive, left-facotred를 만족해야함.
이 요구사항을 만족할 때, backtracking을 하지 않아, 빠르고 예측 가능한 파서의 역할을 가능
- 한계
모든 문법이 LL(1) 으로 표현되지 않음.
좌측 재귀가 있거나, 선택 규칙들이 겹칠 때 사용이 불가능함. => **LR parser **사용해야함.
Parsing Table
파싱 테이블(=cheating sheet)
- LL(1) 파서가 문법에 따라 어떤 규칙을 적용할지를 결정하기 위한 표
- 행(Row) : Non-terminal
- 열(Col) : Terminal + $ (입력의 끝 기호)
- 셀(Cell) : 어떤 생성 규칙을 적용할 것인지
사용방법
- 현재 스택의 top이 non-terminal일 때,
- 현재 입력 토큰을 확인한다.
- 파싱 테이블에서 [논터미널, 입력 토큰] 위치의 생성 규칙을 따라간다.
- 오른쪽을 스택에 push하고 이어서 진행한다.
만드는 방법 : FIRST와 Follow set을 사용
FIRST 집합
어떤 비단말 기호로 시작되는 파생 규칙들이 있을 때, 그 파생된 문자열이 시작할 수 있는 터미널 기호들을 모아놓은 집합
즉, 쉽게 말해 문장을 만들 때 가장 처음에 나올 수 있는 단어
(정의)
FIRST(X) =
-
만약 X가 터미널 기호면 FIRST(X) = {X}
-
만약 X가 ε (빈문자열)을 유도한다면 ε을 포함
-
만약 X가 비단말 기호 A이고 A → α1 α2 … 이라면, - 각 α의 맨 앞 토큰들의 FIRST 집합을 합집합으로 만든다
- 만약 α가 ε을 유도할 수 있다면, FIRST에 ε도 포함시킴
FOLLOW 집합
어떤 비단말 기호 A 뒤에 올 수 있는 터미널 기호들의 집합으로 파생 과정에서 A 다음에 올 수 있는 기호들을 모은 것
(정의)
- 시작 기호의 FOLLOW 집합에 항상 $ 포함
- $는 입력의 끝을 의미하는 EOF(End of File) 기호
- 규칙 B → α A β 가 있을 때
- FOLLOW(A)에 FIRST(β)를 ε 제외하고 모두 추가
- 만약 FIRST(β) 에 ε이 있거나 β가 없을 경우
- FOLLOW(A)에 FOLLOW(B)를 추가
(집합 계산 규칙)
- 시작 기호 S의 FOLLOW 집합에는 항상
$포함
$ ∈ FOLLOW(S)- S는 문법 전체의 시작, 입력이 끝나는 지점에 $에서 S뒤에는 아무것도 올 수 없기 때문
- 문장이 종료될 때 종료 조건을 인식하기 위함.
- 모든 곳에 다 포함되는 것이 아닌 오직 시작 기호의 FOLLOW 집합에만 포함되어야 있어야함.
- 그렇기에, FOLLOW set 끼리 비교하는 3번째 규칙을 활용해 $가 같이 들어가 있을 수 있음.
- 규칙 A → α B β 가 있을 때
FIRST(β) - {ε} ⊆ FOLLOW(B)- B 뒤에 실제로 올 수 있는 기호들로 이를 등록해줘야 함.
- ε은 실제 기호가 아니므로 제외
- 규칙 A → α B β 에서
ε ∈ FIRST(β)이거나, A → α B 인 경우
FOLLOW(A) ⊆ FOLLOW(B)- 만약 β가 ε이 된다면, 즉 β가 사라진다면, B는 A의 마지막 기호처럼 행동
- 그러면 A 다음에 올 수 있는 기호들은 그대로 B 뒤에 오는 기호로 간주
Parsing Table 생성 방법
- A → α에 대해 FIRST(α)의 모든 터미널 a에 대해 Table[A, a] = α
- ε ∈ FIRST(α) 이고, b ∈ FOLLOW(A)라면 Table[A, b] = α
FIRST/FOLLOW를 사용해 파싱 시 production 결정
LL(1) parser 실행 알고리즘
- 스택에
$, 시작 기호 push - 반복:
- 스택 top이 터미널이면, 입력과 일치 여부 확인
- 비터미널이면, LL(1) 테이블 참고해 대응 production push
- 입력 끝 & 스택이 empty → Accept
- 파싱 예시 :
id * id + id
| 스택 | 입력 | 작업 설명 |
|---|---|---|
| D $ | id * id + id $ | 시작 기호 push |
| E D’ $ | id * id + id $ | D → E D’ 적용 |
| G E’ D’ $ | id * id + id $ | E → G E’ |
| id E’ D’ $ | id * id + id $ | G → id |
| E’ D’ $ | * id + id $ | id 매칭, 포인터 이동 |
| * E D’ $ | * id + id $ | E’ → * E |
| G E’ D’ $ | id + id $ | E → G E’ |
| id E’ D’ $ | id + id $ | G → id |
| E’ D’ $ | + id $ | id 매칭, 포인터 이동 |
| ε D’ $ | + id $ | E’ → ε |
| + D $ | + id $ | D’ → + D |
| E D’ $ | id $ | D → E D’ |
| G E’ D’ $ | id $ | E → G E’ |
| id E’ D’ $ | id $ | G → id |
| E’ D’ $ | $ | id 매칭, 포인터 이동 |
| ε D’ $ | $ | E’ → ε |
| ε $ | $ | D’ → ε → 끝 |
Stack과 입력 모두 비었으므로 Accept!
- LL(1) Parser의 구현
# 예제 문법:
# E → T E'
# E' → + T E' | ε
# T → id
# Parsing Table (M[Non-terminal][Terminal])
parsing_table = {
'E': {'id': ['T', "E'"]},
"E'": {'+': ['+', 'T', "E'"], '$': ['ε']},
'T': {'id': ['id']}
}
# 입력 문자열: id + id (토큰화된 리스트 + EOF 기호 $)
input_tokens = ['id', '+', 'id', '$']
# 파서 스택 초기화
stack = ['$', 'E'] # 시작 기호는 E
def parse(input_tokens):
index = 0
while stack:
top = stack.pop()
current = input_tokens[index]
if top == current == '$':
print("Accepted!")
return
if top == current:
print(f"Matched terminal: {top}")
index += 1
elif top in parsing_table:
rule = parsing_table[top].get(current)
if rule is None:
print(f"Error: No rule for {top} with input {current}")
return
if rule != ['ε']:
stack.extend(reversed(rule))
print(f"Apply rule: {top} → {' '.join(rule)}")
else:
print(f"Error: Unexpected symbol {top}")
return
print("Error: Stack empty before input consumed.")
parse(input_tokens)
핵심 요점 요약
LL(1) 문법의 조건
- Left-Recursive 하지 않아야한다.
- 좌측 재귀는 top-down 방식에서 무한 루프를 유발할 수 있음.
FIRST(α) ∩ FIRST(β) = ∅인 상황에 어떤 결정을 할지 불가능함.
=> 결국 Left Factoring이 되어있고, Ambiguity가 없어야함.
| Left Recursion 제거 | Recursive Descent Parser에서 무한 루프 방지 |
|---|---|
| FIRST 집합 충돌 확인 | 어떤 production을 사용할지 결정 가능해야 함 |
| ε-derivation 시 FOLLOW 고려 | 공백을 사용하는 경우 파싱 결정성이 흔들릴 수 있으므로 FOLLOW로 구분 |