LL 구문 분석

Intro

• FIRST , FOLLOW 정의와 LL조건의 이해

FIRST

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

FIRST(A₁A₂…A_n) = FIRST(A₁) ⊕ A₂ … ⊕ A_n

⊕ (ring sum) 이란

1. if ε ∉ A then A ⊕ B = A
2. if ε ∈ A then A ⊕ B = (A - {ε}) ⋃ B.

첫 번쨰 피자연산자 집합이 ε를 갖지않으면 자신이되며, ε가 있으면 ε를 제외한 첫 번째 피연산자 두 번째 피연산자의 합집합이 된다.

예제

{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,ε}

FIRST 예제

다음의 FIRST 계산

S -> ABe
A -> dB | aS | c
B -> AS | b

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

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

= {a,c,d}

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

= {a,b,c,d}

가 된다.

FOLLOW

ε-생성 규칙을 갖는 문법에서는 FIRST만 으로는 생성 규칙을 결정적으로 선택할 수 없다.

그러므로 Nontermianl A 다음에 나오는 심벌에 따라 어느 생성 규칙으로 유도할 것인지 결정하는 집합을 FOLLOW라 부른다.

FIRST를 이용하여 FOLLOW를 구할 수 있다.

예제

다음의 FOLLOW 계산

E  -> TE'
E' -> +TE' | ε
T  -> FT'
T' -> *FT' | ε
F  -> (E) | id

FOLLOW(E) 는 Start symbol 이므로 $이 들어간다.

E -> TE’의 마지막이 E’ 이므로 E의 FOLLOW는 E’에 속한다. (E => E’)

E’는 nullable 하기 때문에 E->T 꼴이 된다. 그러므로 E의 FOLLOW는 T의 FOLLOW에 속한다. (E => T)

F -> (E)에서 E다음 Terminal 심볼인 ‘)’ 가 나왔기 때문에 추가한다.

FOLLOW(E) = {$,')'}

E’ 뒤에는 없기때문에 E만 상속받게된다.

FOLLOW(E') = {$,')'}

E -> TE’에서 T뒤에 E’가 나오기 때문에 E’의 FIRST를 추가시키고 E => T 이기 때문에

FOLLOW(T) = {$,')','+'} 가 된다.

T는 T’로 끝나므로 T => T’이 되며 T’이 nullable하기 때문에 T => F도 된다.

FOLLOW(T') = {$,')','+'}

F는 T’ -> *FT’ 에서 F뒤에 T’이 나오므로 T’의 FIRST인 *를 추가하면

FOLLOW(T) = {$,')','+','*'}

이로써 모든 FOLLOW가 구해졌다.

LL 조건

Nonterminal을 대치하기 위한 생성 규칙을 결정적으로 선택하기 위한 조건

한 Nontermianl에 2개 이상의 생성 규칙이 있을 떄 
각 생성 규칙의 FIRST가 달라야 하며

한 생성 규칙이 ε을 유도할 수 있으면
그 생성 규칙의 FOLLOW와 다른 생성 규칙의 FIRST가 달라야 한다.

LL 방법을 실제로 파싱 알고리즘으로 사용하는 구문 분석기에는 recursive-descent 파서와 predictive 파서가 있다.

LL조건 테스트 예제

A -> aB=e
B -> CB | ε
C -> [eD] | .a
D -> eD | ε

1 NULLABLE = {B,D}

2 FIRST

FIRST(A) = {a}
FIRST(B) = {[, .,  ε}
FIRST(C) = {[, .}
FIRST(D) = {e, ε}

3 FOLLOW

FOLLOW(A) = {$}
FOLLOW(B) = {=}
FOLLOW(C) = {[, ., =}
FOLLOW(D) = {]}

4 LL조건 테스트

1) B -> CB | ε

FIRST(CB) ∩ FOLLOW(B) = {[,.} ∩ {=} = ∅

2) C -> [eD] | .a
FIRST([eD]) ∩ FIRST(.a) = {[} ∩ {.} = ∅


3) D -> eD | ε
FIRST(eD) ∩ FOLLOW(D) = {e} ∩ {]} = ∅

모든 생성 규칙에 대하여 교집합이 공집합 이므로 LL조건 만족

참고 저서

오세만, 컴파일러 입문, 정익사,2010, 271쪽

참고 블로그