7. LL 구문 분석 7-1. 결정적 구문 분석 7-2. Recursive-descent 파서 7-3. Predictive 파서 7-4. Predictive 파싱 테이블의 구성 7-5. Strong LL(k) 문법과 LL(k)문법
7-1. 결정적 구문 분석 LL 파싱 top-down 방식은 주어진 스트링을 파싱하는데 많은 시간 필요 실제적인 컴파일러의 파싱 알고리즘 으로 사용하기에는 부적당. 따라서 backtracking을 하지 않고 결정적으로 파싱할 수 있는 방법 요구 LL 파싱 LL은 왼쪽에서 오른쪽으로 읽어가며(Left to right scanning) 좌파스(Left Parse)를 생성하기 때문에 붙여진 이름
LL 방법 입력 심벌을 보고 적용될 생성 규칙을 결정적으로 선택하여 유도 현재의 입력 심벌과 생성된 terminal 심벌이 같지 않으면 주어진 스트링을 틀린 문장으로 간주하는 방법 정의 7.1 : FIRST FIRST(A) = {a VT∪ {} | A a, V*} nonterminal A로부터 유도되어 첫 번째로 나타날 수 있는 terminal의 집합 예1(p257|p271) *
정의 7.2 정의 7.3 정의 7.4 : FIRST(A1A2An) nonterminal A가 을 유도할 수 있으면, A를 nullable하다고 부른다. 즉, A ⇒ 이면 nullable하다. 정의 7.3 두 개의 집합에 대한 연산자인 ring sum, 은 다음과 같이 정의 if A then A B = A 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, } 정의 7.4 : FIRST(A1A2An) = FIRST(A1) FIRST(A2)... FIRST(An) *
FIRST(X)를 계산하는 방법(p258|p273) 1. X가 terminal이면 X의 FIRST는 자기 자신이 된다. FIRST(X) = { X | if X VT } 2. X → a의 생성 규칙이 존재하면 a가 FIRST(X)에 포함된다. FIRST(X) = FIRST(X) ∪ {a} if X→a P and a VT 또한, X가 -생성 규칙을 가지면 X의 FIRST에 이 포함된다. FIRST(X) = FIRST(X) ∪ {} if X → P 3. X→Y1Y2...Yk인 생성 규칙이 있을 때, FIRST(X) = FIRST(X) ∪ FIRST(Y1Y2...Yk)이다.
FIRST(A) = FIRST(1) ∪ FIRST(2) ∪ ... ∪ FIRST(n) <알고리즘 7.1> 초기에 모든 nonterminal의 FIRST는 공집합이 된다. rhs에 첫번째로 terminal이 나오는 생성 규칙(-생성 규칙 포함)에서 FIRST를 구한 후, 이 형태의 생성 규칙은 다시 고려할 필요가 없기 때문에 제거한다. 남은 생성 규칙의 형태는 모두 nonterminal로 시작하므로 ring sum연산을 이용하여 모든 nonterminal의 FIRST가 변하지 않을 때까지 반복한다. 일반적으로 A-생성 규칙이 A→ 1|2||n P와 같은 형태일 때 다음과 같이 된다. FIRST(A) = FIRST(1) ∪ FIRST(2) ∪ ... ∪ FIRST(n)
<예 3> 다음 문법의 FIRST 계산(p259|p274) S → ABe A → dB | aS | c B → AS | b FIRST(S) = FIRST(A) = {a, c, d} FIRST(B) = {b} 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(B) = {a, b, c, d}
<예 4> 다음 문법의 FIRST 계산 (p260|p275) E → TE′ E′ → +TE ′ | T → FT ′ T′ → *FT ′ | F → ( E ) | id FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E′) = {+, } FIRST(T′) = {*, } <연습 7.4> p307
정의 7.5 : FOLLOW Nonterminal A가 nullable하면 FIRST(A)에 이 속하게 할 수 없다. 즉, nonterminal A 다음에 나오는 심벌에 따라 어느 생성 규칙으로 유도할 것인가를 결정하게 된다. 따라서 -생성 규칙을 갖는 문법에서는 nonterminal 다음에 나오는 terminal 심벌이 의미를 갖게 되는데 이것을 FOLLOW라 부른다. FOLLOW(A) = {a VT ∪{$} | S ⇒ Aa, , V*} $는 입력 스트링의 끝을 표기하는 마커 심벌 *
nonterminal A의 FOLLOW란? 시작 심벌로부터 유도될 수 있는 모든 문장 형태에서 A 다음에 나오는 terminal 심벌의 집합이다. 따라서 FOLLOW를 계산하기 위해서는 모든 문장 형 태를 고려해야 하나 , 문장 형태는 생성 규칙의 rhs들로 이루어져 있다. 그러므로 생성 규칙의 rhs를 이용하여 FOLLOW를 구할 수 있다.
각 nonterminal에 대한 FOLLOW 구하는 방법 (p262|p277 ) 먼저 nullable 심벌을 구하고, 이것을 이용하여 <Alg 7.1>에 따라 FiRST 계산한다. First를 이용하여 FOLLOW를 구한다. First를 이용하여 FOLLOW를 계산하는 방법 <Alg 7.2>
FOLLOW를 계산하는 방법(p261~|p276~ , Alg 7.2) 1. 시작 심벌은 $를 초기값으로 갖는다. FOLLOW(S) = {$} 2. 생성 규칙의 형태가 A → B, 일 때, FIRST()에서 을 제외한 terminal 심벌을 B의 FOLLOW에 추가한다. if A → B, then FOLLOW(B) = FOLLOW(B) ∪( FIRST() -{} ) 3. A → B이거나 A → B에서 FIRST()에 이 속하는 경우 (즉, ⇒ ), A의 FOLLOW 전체를 B의 FOLLOW에 추가한다. if A → B P or (A → B and ⇒ ) then FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(A) * *
FOLLOW를 계산하는 방법 3. A → B이거나 A → B에서 FIRST()에 이 속하는 경우 (즉, ⇒ ), A의 FOLLOW 전체를 B의 FOLLOW에 추가한다. if A → B P or (A → B and ⇒ ) then FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(A) 3번의 의미 생성 규칙의 형태가 A → B인 경우, 가 이거나 을 유도할 수 있으면, A의 FOLLOW 전체를 B의 FOLLOW에 넣는다. S ⇒ 1A2 ⇒ 1 B 2 ⇒ 1 B 2 왜냐하면, 임의의 문장 형태에서 A 다음에 나올 수 있는 심볼은 모두 B다음에 나올 수 있기 때문이다 * * * *
<예 5> FOLLOW 계산 ( p263|p277) E → TE′ E′ → +TE′ | T → FT′ T′ → *FT′ | F → ( E ) | id FOLLOW(E) = {$} ∪ FIRST( ) ) = { $, ) } FOLLOW(T) = ∪ (FIRST(E′) – {} ) = { + } FOLLOW(F) = ∪ (FIRST(T′) – {} ) = { * } FOLLOW(E′) = FOLLOW(E) = { $ , ) } FOLLOW(T′) = FOLLOW(T) = { $ , ) , +} FOLLOW(F) = { $ , ) , + , *}
7.1.3 LL 조건(p263 ~ |p278~ ) <정의 7.6 > 임의의 생성 규칙 A → | P에 대하여 다음 조건을 만족해야 한다. 1. FIRST() ∩ FIRST() = ; 2. if FIRST() then FOLLOW(A) ∩ FIRST()= ; 생성 규칙의 FIRST가 서로 다르다는 것은 유도하는 스트링이 다르다는 것이므로, 문장 형태에서 적용할 생성 규칙을 결정적으로 선택할 수 있다. 그러나 FIRST가 같으면 유도하는 스트링이 같아서 생성 규칙 중 어느 것을 적용해야 올바른 것인지 알 수 없게 된다. 또한 생성 규칙이 을 유도할 수 있으면 FOLLOW심벌에 대하여 그 생성 규칙을 선택하게 된다. 따라서 FOLLOW 심벌과도 서로 분리된 집합이어야 한다.
ex) A aBc | Bc | dAa B bB | FIRST(A) = {a, b, c, d} FOLLOW(A) = {$, a} FIRST(B) = {b, } FOLLOW(B) = {c} 1) A aBc | Bc | dAa에서, FIRST(aBc) FIRST(Bc) FIRST(dAa) = {a} {b, c} {d} = 2) B bB | 에서, FIRST(bB) FOLLOW(B) = {b} {c} = 1), 2)에 의해 LL 조건을 만족한다.
7-2. Recursive-desent 파서 <정의> LL 파서의 일종으로 주어진 입력 스트링을 파싱하기 위하여 일련의 순환 프로시저(recursive procedure)를 사용한다. 각 순환 프로시저는 각 nonterminal에 해당하는 것으로 nonterminal에 대한 유도를 프로시저 호출로 처리하는 방법 <정의 7.7> LOOKAHEAD LOOKAHEAD(A → ) = FIRST( {| S ⇒ A ⇒ ⇒ VT*} ) LOOKAHEAD(A → X1X2...Xn) = FIRST(X1) FIRST(X2)... FIRST(Xn) FOLLOW(A) * *
ex) S aSA | A c Nullable Set = {S} FIRST(S) = {a, } FOLLOW(S) = {$,c} FIRST(A) = {c} FOLLOW(A) = {$,c} LOOKAHEAD(S aSA) = FIRST(aSA) FOLLOW(S) = {a} LOOKAHEAD(S ) = FIRST() FOLLOW(S) = {$,c} LOOKAHEAD(A c) = FIRST(c) FOLLOW(A) = {c} LOOKAHEAD를 구하는 순서 : Nullable => FIRST => FOLLOW => LOOKAHEAD
<정의 7.8> Strong LL 조건 정의 : A | ∈ P, LOOKAHEAD(A ) LOOKAHEAD(A ) = . 의미 : LOOKAHEAD가 다르면 생성하는 스트링이 다르고 적용할 생성 규칙이 유일하므로, 현재 입력 심볼에 따라 결정적 구문 분석할 수 있다. ex) G : S aSA | A c LOOKAHEAD(S aSA) = {a} LOOKAHEAD(S ) = FOLLOW(S) = {$, c} LOOKAHEAD(S aSA) LOOKAHEAD(S ) = G는 strong LL(1)이다.
7.3 Predictive 파서(p273~ |p289~) <정의> 생성 규칙이 바뀌더라도 구문 분석 루틴은 고치지 않고, 단지 구문 분석기의 행동을 제어하는 파싱 테이블만 고쳐서 구문 분석기를 구현할 수 있는 방법 X . $ 구문분석기 파싱테이블 a1 a2 ... an$ 출력 input stack Parsing table의 크기 : 항상 |VN| (|VT| + 1)
1. pop(제거) 2. Expand(확장) Parser Action<Alg 7.3> p275|p291 stack의 top = 입력 symbol stack의 top 심벌은 stack에서 제거하고 현재 입력 심벌은 입력 스트링에서 제거 2. Expand(확장) stack의 top이 nonterminal인 경우로 생성 규칙을 적용하여 확장한다. 예를 들어, M[A, a] = {A →XYZ}일 때, A를 스택에서 제거하고 ZYX를 차례로 스택에 넣는다. X가 stack의 top이 되게 한다.
3. accept(인식) 4. error(오류) stack의 top 심벌과 현재 입력 심벌 모두가 $인 경우로 주어진 입력 스트링이 올바른 스트링임을 알린다. 4. error(오류) stack의 top이 nonterminal 심벌인 경우로 그 심벌 로부터 현재 보고 있는 입력 심벌을 결코 유도할 수 없음을 나타낸다.
<예 13> aabccd에 대한 구문분석(p277|p292) 1. S → aS 2. S → bA 3. A → d 4. A → ccA (1) 유도 과정에 의한 구문분석 S ⇒ aS (1) ⇒ aaS (11) ⇒ aabA (112) ⇒ aabccA (1124) ⇒ aabccd (11243) aabccd는 정의된 문법의 올바른 문장이다.
(2) 파스트리의 표현 S a b A c d
$S aabccd$ expand 1 1 $Sa pop & advance abccd$ 11 bccd$ expand 2 112 $ (3) 파싱 테이블을 이용한 predictive 구문 분석 스택의 내용 입력 스트링 파싱 행동 파스 $S aabccd$ expand 1 1 $Sa pop & advance abccd$ 11 bccd$ expand 2 112 $ Ab $A ccd$ expand 4 1124 Acc $Ac cd$ $A d$ expand 3 11243 $d d$ pop & advance 11243 $ $ accept 11243
7.4 Predictive 파싱 테이블의 구성 Predictive 파싱 테이블의 구조 : 2차원 배열(p279|p295) M[X, a] = r 이면 Stack top : symbol X (Nonterminal) 입력 symbol : symbol a ( terminal) 일 때 r 번 생성규칙으로 확장하라는 의미 VT VN a $ r X
Predictive 파싱 테이블 구성 방법(p280|p296) 모든 a FIRST()에 대하여 M[A, a] := A → 로 채운다. 2. 만일 FIRST()이면, 모든 b FOLLOW(A)에 대하여 M[A, b] := A → 로 채운다. LL(1) 문법 임의의 생성 규칙 A → | 에 대하여 1. FIRST() ∩ FIRST() = 2. 만약 FIRST()이면, FOLLOW(A) ∩FIRST() =
<예 14> LL(1) 파싱 테이블 구성(p281|p297) 1. E → TE′ 2. E′ → +TE′ 3. E′ → 4. T → FT′ 5. T′ → *FT′ 6. T′ → 7. F → (E) 8. F → id (1) FIRST의 계산 FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E′) = { +, } FIRST(T′) = { *, } (2) FOLLOW의 계산 FOLLOW(E) = FOLLOW(E′) = { ), $ } FOLLOW(T) = FOLLOW(T′) = { +, ), $ } FOLLOW(F) = { +, *, ), $ } (3) 파싱 테이블 V T N Id + * ( ) $ E 1 ’ 2 3 4 6 5 F 8 7
ambiguous(모호성) (p283|p299) <예제> 1. S → iCtSS′ 2. S → a 3. S′ → eS 4. S′ → 5. C → b 파싱 테이블 구현 스택 top 심벌이 S'이고 현재의 입력 심벌이 e일 때 적용해야 될 생성 규칙을 결정적으로 선택할 수 없다. 따라서 위 문법은 LL(1) 문법이 아니다.
7-5. Strong LL(k) 문법과 LL(k) 문법 현재 보고 있는 symbol의 개수가 k개 LL은 이제까지 본 symbol과 현재 보고 있는 symbol에 따라 파싱 행동 결정 strong LL은 현재 보고 있는 symbol에만 관계하여 파싱 행동 결정 strong LL(1) ⇔ LL(1) k = 1인 경우, 두 문법이 나타내는 언어의 종류는 같다. 즉, LL(1) 문법과 strong LL(1) 문법이 동등하다.