[컴파일러] LL조건과 LL문법 : Top-down 파싱에서 결정적으로 파싱할 조건

[사전 개념]

구문분석(파싱), 그리고 결정적 파싱이라는 것과, FIRST와 FOLLOW의 개념

 

https://splendidlolli.tistory.com/515

구문분석, Top down과 Bottom up

https://splendidlolli.tistory.com/516

LL파싱과 First set

https://splendidlolli.tistory.com/517

LL파싱과 Follow set

 

 

---

지금 배울 것 : LL조건

현재 들어오는 input 문자를 보고, 어떠한 생성 규칙을 골라서 파싱하게 된다.

그런데 그러한 생성 규칙이 결정적이지 않다면(ex. 2개중 하나를 골라야 한다면) LL파싱이 아니다!

 

++ recall) 일반적인 Top-down 파싱은 생성규칙의 선택이 결정적이지 않기 때문에 backtracking(역추적)이 발생하여 비효율적인데, 그러한 단점을 없애기 위해 '생성규칙을 결정적으로 선택해야 하는' LL파싱 방법을 배웠다. ++ 

 

 

그러면 LL파싱이 가능한 문법은 '결정적인 생성규칙 선택'이 가능한 문법일테다.

그러한 문법은 어떤 조건을 가질까?

 

 

 

---

LL조건

Context Free Grammar가 임의의 생성 규칙 A -> α | β 에 대해여 다음의 조건을 만족한다면,

LL파싱이 가능한 문법이다.

 

▶ FIRST(α) ∩ FIRST(β) = 공집합

<왜 그래야 하는가?>

<이해에 필요한 지식> (관련 링크)

LL파서는 LL 파싱테이블을 보고 파싱을 진행한다. 그 LL 파싱 테이블을 채울 때 FIRST와 FOLLOW를 보고 채우게 된다. FIRST를 보고 파싱 테이블을 채우는 방법은 다음과 같다.

- 각 Non-terminal에 N에 대하여 규칙 1이 존재하고,

- FIRST(N)에 만약 terminal a가 포함되었다면, 

- LL 파싱 테이블 M[N, a] 셀에는 규칙 1을 넣는다.

간단히 귀류법으로 증명을 해보자. FIRST(α) ∩ FIRST(β)가 공집합이 아니라고 가정하자. 

즉, A->α 와 A->β 규칙에서 FIRST(A) = FIRST(α) ∪ FIRST(β) = {a} ∪ {a} = {a}인 상황이라고 하자.

그러면 FIRST(α) ∩ FIRST(β) = {a}라서 공집합이 아닌 상태이다.

그러면 LL 파싱테이블의 M[A, a] 셀을 채울 때 규칙 A->α 와 규칙 A->β 둘다 들어갈 수 있다.

이때 만약 LL 파서가 스택 탑의 A라는 Non-terminal과 input string의 맨앞 문자 'a'를 보고 M[A, a]를 찾아가 '적용할 생성규칙'을 골라 expand <규칙넘버> 해야할 때, 규칙 A->α 와 규칙 A->β 두개중 하나를 골라야 한다. "결정적이지 않다!!!"

=> 좀 간단히 말하자면, 논터미널의 생성규칙이 여러개고 그때 FIRST가 겹치면 어떤 규칙을 적용해야 할지 모른단 거다.

=> 그래서 모든 Non-terminal의 각 생성규칙에서, 모든 생성규칙의 FIRST의 공통 원소가 없어야 한다. 

 

 

▶ if ε ∈ FIRST(α), then FOLLOW(A) ∩ FIRST(β) = 공집합

<왜 그래야 하는가?>

LL파서의 LL파싱테이블을 채울 때 FIRST가 null인 경우는 FOLLOW를 봐야 하기 때문이다. 

recall)

Let : 규칙 4 : S' -> ε

"규칙 4"에서 S'가 nullable임을 봤다. 그럼 FOLLOW(S')를 봐야 한다.

(문제에서) FOLLOW(S')={ e, $ }다.

그럼 M[S', e]와 M[S', $]에다가 "규칙 4를" 넣어주면 된다.

 

(관련 링크)

 

.

.

 

∨ 어렵게 생각하지 말고,

LL 조건은 결국 그냥 이거다.

 

임의의 생성규칙 A -> α | β에서, 

FIRST(α)랑 FIRST(β)의 원소가 a로 겹치면 LL파싱테이블 [A, a]에서 규칙 A->α를 선택해야할지 규칙 A->β를 선택해야 할 지 모르니까 FIRST(α)랑 FIRST(β)가 공집합이어야 한다는 거고, 

만약 임의의 생성규칙 A -> α | β에서 어느 하나(α)가 null이면 결국 FIRST 대신 FOLLOW를 봐야 하니까, FOLLOW(α)랑 FIRST(β)가 공집합이어야 한다는 거다.

 

 

 

---

LL 문법 (=LL(1)문법)이 절대 아닌 경우

 

1. 모호한 문법

2. 좌인수분해(left-factoring)될 수 있는 부분을 가지는 문법

(즉, 완전히 좌인수분해 되어야 LL(1)문법으로 한발짝 다가가는 것이다.)

(Top-down 특유의 역추적을 막기 위해 좌인수분해해야하는 것이다)

좌인수분해, left-factoring이란? 

: 접두사가 같은 기호인 2개 이상의 생성규칙이 존재할 떄, 그 공통된 접두사를 인수분해하는 것이다.

 

<예제1>

다음 문법을 좌인수분해 해보자. 

S -> cAd

A -> a | ab

 

두 생성규칙 A -> a | ab는 공통된 접두사 a를 가진다. 이것을 좌인수분해 해야 LL(1) 문법에 다다갈 수 있다.

S -> cAd

A -> aA'

A' -> ε | b

 

 

<예제2>

다음 문법을 좌인수분해 해보자.

S -> iEtS | iEtSeS | a

E -> b

 

두 생성규칙 S -> iEtS | iEtSeS에서 공통된 접두사는 iEtS이다.

이것을 좌인수분해하여 LL(1)문법에 다가가보자.

S -> iEtSS' | a

S' -> ε | eS

E -> b

 

쉽다!!

 

3. left-recursive한 문법

- 즉, 좌재귀를 제거해야 LL(1) 문법에 다가갈 수 있다.

- 좌재귀 문법이 있으면 Top-down 파싱시 '같은 생성 규칙이 순환 적용되어 무한 루프에 빠진다'

- 좌재귀는 '직접 좌재귀'와 '간접 좌재귀'가 있는데, Top-down 파싱시에 둘다 제거해주면 된다!

- 좌재귀가 있으면 안되는 이유 : LL조건인 'FIRST(α) ∩ FIRST(β) = 공집합'에 위배된다.

<예시>

left recursion이 존재하는 다음 문법을 보자.

E -> E + T

E -> T

T -> num

 

FIRST(E)를 보자.

규칙1 (E -> E + T)에서 보면 FIRST(E) = FIRST(E) = {num}

규칙2 (E -> T)에서 보면 FIRST(E) = FIRST(T) = {num}

두 FIRST가 공통된 원소를 가지고 있다.

LL문법에 위배된다.

- 어떻게 좌재귀를 제거하는가?

=> 우재귀로 바꾼다!!!!!!!

 

---

좌재귀 제거하는 방법 

LL(1) 조건에 맞기 위해서는 좌재귀를 우재귀로 바꿔야 한다고 방금 말했다.

아래는 '직접 좌재귀'를 우재귀로 바꾸는 방법이다.

 

 

<연습문제>

 

두번째로 '간접 좌재귀'를 제거하는 방법도 있는데,

이건 시험에 안 나오는 거 같아서 넘어가겠다.

 

---

[ 요약 ]

LL파싱을 위해서는 LL문법이어야 한다.

주어진 문법을 LL문법으로 변경하기 위해서는,

- 모호성 제거

- 완전히 left-factoring 하기

- 완전히 left-recursion 제거하기

그리고 LL조건을 만족하는지 체크한 후, LL문법이 맞으면 LL파싱을 진행하면 된다.

 

또한,

어떤 문법이 LL인지 확인하기 위해서,

모호성 제거하고 좌재귀 제거하고 좌인수분해 하고 조건에 맞으면 LL문법이다

 

---

Strong LL(1) 조건

 

LL(k)중에 LL(1)한정으로 LL(1)문법인지 쉽게 체크할 수 있는 방법이 있다.

 

+ 필요한 개념 : lookahead의 또 다른 의미

: 어떤 규칙이 적용되었을 때 맨 처음 나올 수 있는 terminal symbols

: LOOKAHEAD(A->X1X2...Xn) = FIRST(X1) ⊕ FIRST(X2) ⊕ ... ⊕ FIRST(Xn) ⊕ FOLLOW(A)

: 이미 배웠던 개념과 연관된다. 앞의 FIRST 다 봤는데 다 null이면 FOLLOW(A)를 고려하자는 거다.

 

 

Strong LL(1) 조건

: LOOKAHEAD(A->α) ∩ LOOKAHEAD(A->β) = 공집합

즉, 주어진 상황에서 LOOKAHEAD가 유일하게 결정되어야 한다는 것이다.

 

 

 

---

<예제> 그래서 어떤 문법이 LL문법인지 확인하려면 두가지 방법이 있다.

다음 문제를 두 가지 방법으로 풀어보자.

 

 

 

 

첫번째 풀이

 

 

 

 

두번째 풀이