[컴파일러] LL파싱과 First set

LL파싱에서 First Set이란? 

Top down 방식으로 유도하는 과정을 생각해보자. 

생성 규칙이 이렇게 존재한다고 하자. 
S=>aA, S=>Bc, B=>bx

 

시작 심볼 S로부터 유도를 시작해야 한다.
S로 시작하는 생성 규칙이 두개 존재하는데, 둘 중 어떤 생성 규칙을 선택하여 유도해야 할까? 
이때 입력값을 보고 선택하면 된다. 만약 a가 입력으로 들어왔다면 S=>aA라는 생성 규칙을 선택해야 한다.

 

++ recall : 단순한 Top down 방식과 달리 LL파싱은 생성규칙을 결정적으로 선택하므로 하나의 입력문자에 대해 유일한 생성규칙을 선택할 수밖에 없다. 반면 결정적으로 선택하지 않는 Top down 방식의 구문분석은 하나의 입력문자에 대해 가능한 생성규칙을 모두 적용해보고 되는대로 구문분석을 완료하므로 backtracking이 존재한다. 

 

아!! 그러면 LL파싱을 위해서는 생성규칙의 첫번째로 나타나는 terminal symbol을 관찰&파악해야겠다. 그래야만 어떤 인풋 문자에 대하여 적용할 생성규칙을 '결정적으로' 선택할 수 있기 때문이다. 

(참고: LL파싱? 생성규칙을 결정적으로 선택?)

* LL파싱

1. LL파싱의 의미 : Left to right scanning & Leftmost Derivation 즉 좌에서 우로 읽으며 좌측유도를 통해 좌파스를 생성하는 구문분석 방법이다.

2. backtracking이 없다는 장점

단순한 Top down 방식과 다르게 backtracking이 없는 이유는, 하나의 입력 문자에 대해서 단 하나의 생성 규칙만 적용되게 하기 때문이다. 이를 "결정적으로(deterministic) 파싱"한다고 한다. 결정적 구문 분석을 가능하게 하는 이유는 문맥 자유 문법에 LL조건을 붙이기 때문이다. First set과 Follow set을 사용하여 생성규칙을 선택하도록 하여 결정적인 구문 분석을 가능하게 한다. (참고)

예를들어 인풋으로 문자 a가 들어왔다고 하자. 만약 다음의 생성규칙 S→aAd, S→aB 두개가 존재한다면 "파싱 불가능 하다." 다시 말해 LL파싱은 입력문자:생성규칙이 일대일로 매치되는 깔끔한 입력문자만 파싱 가능하다. 즉 파싱의 범위가 매우 좁다.

학습 링크 : https://splendidlolli.tistory.com/515

 

이 개념을 "어떤 Non-terminal에 대하여 Fisrt set을 찾는다"고 한다. 

(교수님이 일단 이정도만 이해하라고 하셨다.)

 

Non-terminal S라고 하면 First(S) = {~~}와 같이 표현한다.
예시를 한번 보면 잘 이해될 것이다.

 

---

완전 간단한 예시

Let : 생성규칙
1. S -> aAd
2. S -> aB
3. A -> b
4. A -> C
5. B -> ccd
6. B -> ddc

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

★ if : 생성규칙 S -> Abe가 추가된다면?
First(S) = {a, b, c}
∵ 맨앞 non-terminal A에 대하여 생성규칙을 끝까지 적용해보아야 한다. 

일반적으로 이 예제처럼 First set을 찾는 것은 그리 단순하지 않으며, 조심히 잘 파악해야 한다.

 

---

First set

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

각 Non-terminal에 대하여 First set을 구해보자.

First set을 찾는 이유는 LL파싱을 위해서라고 간단히만 알아두고 일단 First set을 찾는 것을 익히자.

 

FIRST(X) 찾는 방법 (▶ 4가지)

①▶ X가 terminal이면 X의 FIRST는 자기 자신이 된다.

②▶ 생성규칙 X -> aα의 형태면 terminal인 a가 FIRST(X)에 포함된다.

③▶ Nonterminal X가 ε-생성규칙을 가지면 X의 FIRST에 ε가 포함된다.

: X->ε 형태의 생성규칙을 ε-생성규칙이라고 한다.

: 참고) non-terminal A가 ε을 유도할 수 있으면 A를 nullable하다고 한다.

여기까지는 그냥 이거다.

FIRST(X)를 구할 때 X->□에서 □의 첫번째가 terminal이면 그 terminal을 갖고,

X에서 ε을 생성할 수 있으면 ε를 갖는다.

 

④▶ (★) X -> Y1Y2...Yk 생성규칙에서 FIRST(X) = FIRST(X) ∪ FIRST(Y1Y2...Yk)이다.

: def. FIRST(Y1Y2...Yk) = FIRST(Y1)⊕FIRST(Y2)...⊕FIRST(Yk)

: ring sum 연산(⊕)을 통해 모든 Non-terminal의 FIRST가 변하지 않을 때까지 반복 적용한다.

: def. ring sum
if ε∉A then A⊕B = A
if ε∈A then A⊕B = (A-{ε})∪B

 

 

[+ 유의하기 ]

∨ 맨 처음 시작할 때 모든 non-terminal의 FIRST는 Ø로 시작!

∨ 일반적으로 생성규칙이 A->a1 | a2 | ... | an일 때,

FIRST(A) = FIRST(a1)∪FIRST(a2)∪...∪FIRST(an)

 

 

---

★ 예제

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

FIRST(S)를 찾아보자.

일단 딱 보이는 것은 FIRST(S) = {c}, FIRST(A) = {ε} 이다.

그리고 FIRST(S) = FIRST(Ab) 를 좀 더 살펴보아야 한다.

FIRST(S) = FIRST(Ab) = FIRST(A)⊕FIRST(b) = {ε}⊕{b} = {b}

그럼 이제 최종적으로 FIRST(S) = {c} ∪ {b} = {b, c}가 된다.

 

※ 어떤 Non-terminal의 FIRST는 또다른 Non-terminal의 FIRST로 정의되어가는 상황이다.

그러므로 사용된 모든 Non-terminal의 FIRST가 변하지 않을 때까지 반복해야 함을 유의하자.

한번만 쭉 구하고 끝내면 안된다는 것이다. 끝까지 유심히 FIRST들을 검토해야 한다.

▼ 이것에 대한 예제를 보자 ▼

★ 예제

S -> ABe,

A -> dB|aS|c,

B -> AS|b

 

1단계, 일단 가장 먼저 쉽게 보이는 FIRST를 찾아보자. (by 위의 찾는방법 ①, ②, ③)

  FIRST(S) = {} 일단 ABe는 생각이 필요하니까 다음단계에서 보자.

  FIRST(A) = {d, a, c} 깔끔하게 완성!

  FIRST(B) = {b} 일단 AS에 대해서는 생각이 필요하니까 다음단계에서 보자.

 

2단계, FIRST(S)와 FIRST(B)를 다시 생각하자

  FIRST(S)

  = FIRST(S) ∪ FIRST(ABe)

  = FIRST(S) ∪ (FIRST(A)⊕FIRST(B)⊕FIRST(e))

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

  = FIRST(S) ∪ ({d, a, c}⊕FIRST(B)⊕FIRST(e)) ring sum의 정의에 의함

  = {} ∪ {d, a, c}

  = {d, a, c}

  FIRST(B)

  = FIRST(B) ∪ FIRST(AS)

  = FIRST(B) ∪ (FIRST(A)⊕FIRST(S))

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

  = FIRST(B) ∪ ({d, a, c}⊕FIRST(S)) ring sum의 정의에 의함

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

  = {a, b, c, d}

  이렇게 FIRST(S)와 FIRST(B)에 변동이 생겼다. 

  그럼 다시 FIRST(S)와 FIRST(B)를 체크해야 한다. 

  왜냐하면 FIRST(S) 정의에 FIRST(B)가 들어가고, FIRST(B)의 정의에 FIRST(S)가 들어가기 떄문이다.

  recall) 어떤 Non-terminal의 FIRST는 다른 Non-terminal의 FIRST로 정의된다.

 

3단계, FIRST(S)와 FIRST(B)를 다시 생각하자 (반복!!!!)

  FIRST(ㅁ) 값이 변하지 않을 때까지 반복해야 한다.

  FIRST(S) =  FIRST(S) ∪ FIRST(ABe) = {d, a, c} ∪ ({d, a, c}⊕{a, b, c, d}) = {d, a, c} (변경되지 않음!!)

 

  FIRST(B) =  FIRST(B) ∪ FIRST(AS) = {a, b, c, d} ∪({d, a, c}⊕{d, a, c}) = {a, b, c, d} (변경되지 않음!!)

 

더이상 고려대상 FIRST가 변경되지 않으므로 최종 FIRST는 다음과 같다.

  FIRST(S) = {a, c, d}

  FIRST(A) = {a, c, d}

  FIRST(B) = {}

 

---

ε-생성규칙에 관련된 예제 하나 & Follow set의 인트로!

S->Ab, A->a, A->ε일 경우

인풋에 따라 어떻게 유도해야 할지 S로부터 시작해보자.

1. 인풋 문자열이 a일 경우

S->Ab, A->a 생성규칙 적용

2. 인풋 문자열이 b일 경우

S->Ab, A->ε 생성규칙 적용

※A->a를 선택하면 안 됨. 인풋 문자열을 만들어내지 못하는 유도임.

  A->ε를 선택해야 다음과 같이 b가 나오도록 유도 가능. S=Ab=>εb=>b

 

★ 그럼.. b가 들어올 때 A->ε 생성규칙을 선택하면 된다는 것을 어떻게 알까?

  S->Ab를 잠시 관찰해보자.

  Non-terminal A가 null(ε)로 간다면 문자열 b를 생성할 수 있음을 기대할 수 있다.

  또한 FIRST(ε) = {ε}이므로 b를 생성하는 것이 가능하다.

  => 다시말해 S->Ab에서 b부분도 중요한 의미를 가졌음을 확인했다! A가 null로 갈 때 b를 생성한다는 사실을 안다!

  => 즉, First(A) 말고도 뒤에나오는 b에 대한 것도 구문분석의 힌트가 될 수 있다.

  => Follow set을 배우게 된다!

 

★ 다시 말해

S->Ab에서 Non-terminal A가 nullable한 경우 (ex. 생성규칙 S->Ab, A->a, A->ε일 경우)

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

A 다음 나오는 symbol에 따라 '어느 생성 규칙으로 유도할 것인가' 결정해야 한다.

A 다음 b가 나와서 A->ε 규칙을 선택한 것처럼 말이다.

그래서 Follow set을 배우게 된다.

---

First 마무리 문제

FIRST 구하기 문제 3개 

1. S->aB|Bb, B->aB|ε

2. S->(S)S|ε

3. E->a|L, L->(Q), Q->LQ', Q'->,Q|ε

 

---

다음엔 Follow set이 뭔지 보자. 

https://splendidlolli.tistory.com/517

LL파싱과 Follow set