22- LL Parsing (FIRST operation)

LL Parsing은 Left to Right 왼쪽에서 부터 오른쪽으로 스캔한다는 의미의 L과

Left-most derivation의 L을 합쳐 LL Parsing 이라고 한다.

 

LL 파싱에는 FIRST와 FOLLOW라는 연산자가 있는데,

이번엔 LL파싱을 알기 전 알아야 할 정의와 FIRST연산에 대한 개념을 정리 할 것이다.

 

 

 

Nullable Set

nullable set은 epsilon을 통해 null 이 될 수 있는 집합을 말한다.

B -> epsilon 은 nullable set이며,

S -> aBA | BB | ABc와 같은 경우도 B가 epsilon이기 때문에 B가 둘다 epsilon일 수 있어서

Nullable Set으로 판정된다.

한가지의 경우라도 Null이 나올 수 있으면 Nullable Set이라고 부른다.

 

Ring Sum

⊕ 기호로 표현되며, 두 집합간의 연산으로 사용된다.

왼쪽 집합에 epsilon이 없는 경우에는 A ⊕ B 는 무조건 A가 나오며,

{a,b,c,epsilon} ⊕ {c, d} 경우와 같이 왼쪽에 epsilon이 있는 경우 다른 집합의 없는 원소가 epsilon을 대체한다.

결과는 {a,b,c,d}이다.

둘다 epsilon이 있는 경우 {a,b,epsilon} ⊕ {c,d,epsilon} 은

{a, b, c, d, epsilon} 이 된다.

 

 

FIRST

---

FIRST 에는 적용되는 4가지의 정의와 규칙이 있다.

 

1. (정의) 한 non-terminal에서 FIRST란 tree 형식으로 전개하였을때 가장 앞의 statement 원소를 말한다.

 

2. (규칙) A -> a 와 같이 바로 터미널을 가리키는 경우 FIRST가 무조건 a이기 때문에 a로 바로 처리한다.

 

3. (규칙) A -> ... -> ... -> epsilon 과 같이 결론이 epsilon에 도달할 수 있을 때 nullable set으로 판단하여

FIRST set에 epsilon을 포함시킨다.

 

4. (규칙) A -> BCD...와 같이 terminal이 나오지 않고 non-terminal이 계속해서 나오는 경우 Ring Sum 개념을 이용하여

FIRST(B) ⊕ FIRST(C) ⊕ FIRST(D).. 이렇게 해서 A 에서 출발하여 terminal 이 나올때 까지 전개한 다음

제일 왼쪽에 있는 요소를 찾는다.

중간에 B가 epsilon으로 가거나 terminal로 결론이 안나는 경우 C로 가고를 반복하여 Ring Sum을 묶어주는 것이다.

 

 

 

FIRST의 알고리즘 의사코드

if FIRST(A) 가 공집합이 아닐때:
	for A->aP:
    	if A 가 terminal로 시작할 때:
        	FIRST(A) <- {a} and P - {A -> a} //FIRST(A)를 a로 설정하고 A->a라는 설정을 제거
        else if A가 epsilon으로 끝남:
        	FIRST(A) <- {epsilon} and P - {A -> epsilon} //위와 동일
            
	for A-> BCD..Z
    	FIRST(A) <- FIRST(B) ⊕ FIRST(C)... FIRST(Z) // 전체 Ring Sum 하여 적용

 

terminal로 시작할 땐 2번 규칙을 적용,

epsilon으로 끝날 땐 3번 규칙을 적용

 

그리고 다시 돌려 non-terminal로만 이루어졌을때 4번 규칙을 적용한다.