[컴개/CI] Top-Down 구문 분석, LL파싱과 FIRST

LL parsing(LL 파싱)

Top-down으로 구문 분석하기

Top-down 방법으로 구문 분석하는 것은 직관적이고, 좌측 유도 과정과 비슷하다는 특징이 있다.

 

Top-down 방법으로 구문을 분석하는 순서는 아래와 같다.

1. 시작 심벌의 첫 번째 생성 규칙으로 유도하여 문자열을 생성한다.

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

    이때, 유도된 문자열과 입력된 문자열이 같으면 계속 비교해 나가고,

    유도 과정에서 생성된 문자열에 non-terminal이 나오면,

    이 non-terminal의 첫 번째 생성 규칙으로 다시 유도하여 새 문자열을 생성한 후 비교한다.

3. 생성된 문자열과 입력 문자열이 다르다면 backtracking를 통해 원상 복구한다.

 

Backtracking

비교한 두 문자열이 같지 않을 경우,

직전 생성 규칙을 잘못 적용한 것이므로 원위치시키고,

다른 생성 규칙을 적용하는 것을 backtracking이라 한다.

 

즉, 직전 규칙은 적용하지 않았던 것으로 하고 생성된 문자열도 직전 규칙 적용 전으로 환원시킨다.

입력 문자열도 직전 규칙 적용 후에 비교되었던 문자 개수만큼 원위치 시킨다.

 

다른 생성 규칙을 가지고 유도했을 때 마찬가지로 같은 문자가 나온다면 이 과정을 반복하는데,

위와 같은 과정을 반복하다가 더 이상 적용할 생성 규칙이 없는 경우,

입력된 문자열은 틀린 문자열로 인식한다.

하지만, backtracking과정에서 overhead가 많이 들기 때문에,

틀린 문자열로 인식하는 경우가 최악의 경우라고 할 수 있다.

 

아래 예제는 입력으로 'accd'가 들어온 경우이다.

 

LL 파싱

왼쪽에서 오른쪽으로 읽어가며(Left to right scanning) 좌파스(Left parse)를 생성하는 것이다.

 

이 LL파싱은 결정적으로(deterministic) 파싱한다는 특징이 있는데,

입력 문자를 보고 적용될 생성 규칙을 결정적으로 선택하여 유도 준비가 필요하다.

즉, 각 입력 문자 당 적용될 생성 규칙을 미리 뽑아두고 시작하는데,

한 입력 문자에 대해 두 개 이상의 규칙이 해당되면 파싱이 불가능하다는 단점이 있다.

(= 파싱의 범위가 좁다.)

 

하지만, 이러한 LL파싱은 backtracking과정이 없다는 장점이 있는데,

현재의 입력 문자와 생성된 terminal 심벌이 같지 않으면 틀린 것으로 간주하여

Top-down 방식의 시간 낭비를 줄일 수 있다.

 

결정적 파싱

입력 문자를 보고 적용될 생성 규칙을 결정적으로 선택하여 유도하는 것을 결정적 파싱이라고 한다.

LL파싱도 결정적 파싱에 해당되는데, 앞서 언급했듯이 LL파싱은

결정적 파싱이 되는 문법을 선별하거나 다듬어,

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

이를 위해 규칙으로부터 필요한 정보(set)를 파악해서 모아둘 필요가 있는데,

각 set은 FIRST, FOLLOW, LOOKAHEAD 등이 있지만

이번 포스트에서는 FIRST까지만 언급하겠다.

 

FIRST

FIRST(A) = {a ∈ Vt ∪ {ε} | A =>* aγ, γ∈V*}

FIRST는 non-terminal A로부터 유도되어 첫 번째로 나타날 수 있는 terminal의 집합이다.

위의 예에서 S, A, B의 FIRST를 구해보자.

FIRST(S) = {a} (S -> aAd, S -> aB)

FIRST(A) = {b, c} (A -> b, A -> c)

FIRST(B) = {c, d} (B -> ccd, B -> ddc)

 

이때, 위의 규칙에서 'S -> Abe'의 규칙이 추가되면 FIRST(S) = {a, b, c}가 되는데,

이 결과를 내기 위해서는 계산이 필요하다.

 

FIRST(X)를 계산하는 방법

(1) X가 terminal이면 X의 FIRST는 자기 자신이 된다.

      FIRST(a) = {a | if a ∈ Vt}

 

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

       FIRST(X) = FIRST(X) ∪ FIRST(a) if X -> aα ∈ P and a ∈ Vt

 

 

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

      FIRST(X) = FIRST(X) ∪ {ε} if X -> ε ∈ P

 

(4) X -> Y1Y2...Yk인 생성 규칙이 있는 경우 FIRST(X) = FIRST(X) ∪ FIRST(Y1Y2...Yk)이다.

      단, FIRST(A1A2...An) = FIRST(A1) ⊕ FIRST(A2) ⊕ ... ⊕ FIRST(An)

      모든 non-terminal의 FIRST가 변하지 않을 때까지 반복

 

정의

ε-생성규칙

X -> ε 형태의 생성 규칙을 의미한다.

non-terminal A가 ε를 유도할 수 있으면, A를 nullable하다고 부흔다.즉, A =>* ε가 가능하면 A가 nullable하다.

 

LHS, RHS

생성규칙 A -> XXX에서

LHS(left hand side): A

RHS(right hand side): XXX

화살표를 기준으로 좌우를 나누는 것이다.

 

⊕(Ring Sum)ring sum의 정의는 다음과 같다.

- if ε ∉ A, then A ⊕ B = A

- if ε ∈ A, then A ⊕ B = (A - ε) ∪ B

 

ex)

{a, b, c} ⊕ {c, d} = {a, b, c}

{a, b, c, ε} ⊕ {c, d} = {a, b, c, d}

{a, b, ε} ⊕ {c, d, ε} = {a, b, c, d, ε}

 

위의 예시를 통해 ring sum에 대해 알아보았는데,

이러한 ring sum은 어떻게 쓰는 것일까?

또, 하나의 예를 들어 보겠다.

 

S -> Ab, S -> c, A -> ε 라면

'b' 입력 시 S -> Ab로, c 입력 시 S -> c로 유도하면 된다.

FIRST(S) = {c}, FIRST(A) = {ε}를 구할 수 있으며

FIRST(Ab) = FIRST(A) ⊕ FIRST(b) = {b}이므로

FIRST(S) = {b, c}로 업데이트 해줄 수 있다.

 

FIRST 구하는 방법 정리

1. 초기의 모든 non-terminal의 FIRST는 공집합이다.
2. rhs에서 첫 번쨰로 terminal이 나오는 생성 규칙(ε-생성규칙 포함)에서 FIRST를 구한다. 이후 이 형태의 생성 규칙은 다시 고려할 필요가 없으므로 FIRST를 확정한다.
3. 남은 생성 규칙의 형태는 모두 non-terminal로 시작하므로 ring sum연산을 이용하여 모든 non-terminal의 FIRST가 변하지 않을 때까지 반복한다.
4. 일반적으로 A-생성규칙이 A -> α1 | α2 | ... | αn ∈ P와 같은 형태일 때 FIRST(A) = FIRST(α1) ∪ FIRST(α2) ∪ ... ∪ FIRST(αn)와 같은 형태를 갖게 된다.

아래 예제 문제를 풀면서 FIRST에 대해 이해해보자

토글을 통해 답을 작성하겠다.

1.

앞서 FIRST 정의 중 (1), (2), (3)에서

FIRST(S) = {}, FIRST(A) = {a, c, d}, FIRST(B) = {b}

 

앞서 FIRST 정의 중 (4)에서

FIRST(S) = FIRST(S) ∪ FIRST(A) ⊕ FIRST(B) ⊕ FIRST(e) = {} ∪ {a, c, d} = {a, c, d}

FIRST(B) = FIRST(B) ∪ FIRST(A) ⊕ FIRST(S) = {b} ∪ {a, c, d} = {a, b, c, d}

 

위의 과정을 값이 변하지 않을 때까지 반복하면

FIRST(S) = {a, c, d}, FIRST(A) = {a, c, d}, FIRST(B) = {a, b, c, d}

의 값을 구할 수 있다.

 

2.

앞서 FIRST 정의 중 (1), (2), (3)에서

FIRST(E) = {}, FIRST(E') = {+, ε}, FIRST(T) = {a}

 

앞서 FIRST 정의 중 (4)에서

FIRST(E) = FIRST(E) ∪ FIRST(T) FIRST(E') = {} ∪ {a} = {a}

 

위의 과정을 값이 변하지 않을 때까지 반복하면

FIRST(E) = {a}, FIRST(E') = {+, ε}, FIRST(T) = {a}

의 값을 구할 수 있다.