[컴파일러개론] 중간고사 정리 - Syntax Analysis-Top Down

Top-down으로 구문 분석하기

- 직관적, 좌측 유도 과정과 유사하다.

- 시작 심벌의 첫번째 생성 규칙으로 유도하여 문자열 생성

- 유도 과정에서 생성된 문자열과 입력 문자열을 차례로 비교

- 다르면 backtracking

 

Backtracking

생성규칙을 잘못 적용한 경우 원위치 시키고 다른 생성규칙을 적용하는 것

=> overhead가 크다.

 

더이상 적용할 생성규칙이 없는 경우, 입력 문자열을 틀린 문장으로 인식

---

LL파싱

왼쪽에서 오른쪽으로 읽어가며(Left to right scanning)

Left Parse 생성

=> LL 파싱

 

결정적으로 파싱한다.

- 입력 문자를 보고 적용될 생성 규칙을 결정적으로 선택하여 유도

    - 각 입력 문자당 적용될 생성 규칙을 미리 뽑아 두고 시작

    - 한 입력 문자에 두 개 이상의 규칙이 해당되면 파싱이 불가능

 

장점은 Backtracking이 없다는 것

- 현재 입력 문자와 생성된 terminal 시벌이 같지 않으면 그냥 틀린 것으로 간주

- top down 방식의 시간 낭비를 줄인다.

 

---

결정적 파싱

LL 파싱은 각 입력 문자당 적용될 생성 규칙을 미리 뽑아 두고 시작한다.

- 이를 위해 규칙으로부터 필요한 정보를 파악하여 모으기

- FIRST, FOLLOW, LOOKAHEAD ...

 

First

First는 nonterminal A로부터 유도되어 첫번째로 나타날 수 있는 terminal들의 집합

 

1) X가 terminal이면 X의 FIRST는 자기 자신이 됨

2) X->aα의 생성규칙이 존재하면 a가 FIRST(X)에 포함됨

3) X->ε 즉, X가 ε-생성규칙을 가지면 X의 FIRST에 e이 포함됨

4) X->Y1Y2...YK인 생성규칙이 있다면, FIRST(X)는 FIRST(X) ∪ FIRST(Y1Y2...YK)

 

위 과정을 모든 nonterminal의 FIRST가 변하지 않을 때 까지 반복한다.

 

Nullable nonterminal

Nonterminal A가 ε를 유도할 수 있으면 A를 nullable하다고 부른다.

 

Ring sum

A가 ε을 포함하지 않으면, A ring sum B는 A

A가 ε을 포함한다면, A ring sum B는 (A - ε)∪B

 

FIRST의 한계

nonterminal A가 nullable한 경우에 문제 발생

FIRST만 가지고는 생성규칙을 결정적으로 선택할 수 없다.

=> A의 다음에 나오는 심벌에 따라 유도를 결정

 

FOLLOW

시작 심벌로부터 유도될 수 있는 모든 문장 형태에서 A 다음에 나오는 terminal 심벌의 집합

 

1) 시작심벌은 $를 초기값으로 갖는다.

2) 생성규칙의 형태가 A-> αBβ, β ≠ ε일 때, FIRST(β)에서 ε을 제외한 terminal 심벌을 B의 FOLLOW에 추가

3) A->αB이거나 A->αBβ에서 FIRST(β)에 ε이 속하는 경우, A의 FOLLOW 전체를 B의 FOLLOW에 추가

 

LL조건

A-> α | β 에 대해

FIRST(α) ∩ FIRST(β) = Φ

If ε ∈ FIRST(α) then FOLLOW(A) ∩ FIRST(β) = Φ

 

각 순간 적용할 생성 규칙이 유일하게(결정적으로) 정해짐

 

LL(1) 문법

1 -> LOOKAHEAD가 1개이다. 즉, 입력 토큰만 보고 결정

 

LL(1) 문법이 될 수 없는

1. 모호하거나

2. left-factoring 될 부분을 가지고 있거나

3. left-recursive

 

- 모호성 해결에는

1) 연산자 우선순위

2) 결합법칙 반영

 

- Left Factoring 해결

공통 앞부분을 새로운 nonterminal을 도입하여 인수분해

 

- Left-Recursion

무한루프의 가능성 => Right recursion으로 해결

간접 left recursion은 대입하여 직접 reft-recursion으로 변환 => recursion 없애기

 

LOOKAHEAD(...)

맨 처음 나올 수 있는 terminal symbols

 

Strong LL(1) 조건

LOOKAHEAD(A->α) ∩ LOOKAHEAD(A->β) = Φ