7. LL 구문 분석 7-1. 결정적 구문 분석 7-2. Recursive-descent 파서 7-3. Predictive 파서 7-4. Predictive 파싱 테이블의 구성 7-5. Strong LL(k) 문법과 LL(k)문법.

Presentation on theme: "7. LL 구문 분석 7-1. 결정적 구문 분석 7-2. Recursive-descent 파서 7-3. Predictive 파서 7-4. Predictive 파싱 테이블의 구성 7-5. Strong LL(k) 문법과 LL(k)문법."— Presentation transcript:

1 7. LL 구문 분석 7-1. 결정적 구문 분석 7-2. Recursive-descent 파서 7-3. Predictive 파서 7-4. Predictive 파싱 테이블의 구성 7-5. Strong LL(k) 문법과 LL(k)문법

2 7-1. 결정적 구문 분석 LL 파싱 top-down 방식은 주어진 스트링을 파싱하는데 많은 시간 필요  실제적인 컴파일러의 파싱 알고리즘 으로 사용하기에는 부적당. 따라서 backtracking을 하지 않고 결정적으로 파싱할 수 있는 방법 요구  LL 파싱 LL은 왼쪽에서 오른쪽으로 읽어가며(Left to right scanning) 좌파스(Left Parse)를 생성하기 때문에 붙여진 이름

3 LL 방법 입력 심벌을 보고 적용될 생성 규칙을 결정적으로 선택하여 유도
현재의 입력 심벌과 생성된 terminal 심벌이 같지 않으면 주어진 스트링을 틀린 문장으로 간주하는 방법 정의 7.1 : FIRST FIRST(A) = {a  VT∪ {} | A  a,   V*} nonterminal A로부터 유도되어 첫 번째로 나타날 수 있는 terminal의 집합 예1(p257|p271) *

4 정의 7.2 정의 7.3 정의 7.4 : FIRST(A1A2An) 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(A1A2An) = FIRST(A1)  FIRST(A2)...  FIRST(An) *

5 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)이다.

6 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)

7 <예 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}

8 <예 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

9 정의 7.5 : FOLLOW Nonterminal A가 nullable하면 FIRST(A)에 이 속하게
할 수 없다. 즉, nonterminal A 다음에 나오는 심벌에 따라 어느 생성 규칙으로 유도할 것인가를 결정하게 된다. 따라서 -생성 규칙을 갖는 문법에서는 nonterminal 다음에 나오는 terminal 심벌이 의미를 갖게 되는데 이것을 FOLLOW라 부른다. FOLLOW(A) = {a  VT ∪{$} | S ⇒ Aa, , V*} $는 입력 스트링의 끝을 표기하는 마커 심벌 *

10 nonterminal A의 FOLLOW란?
시작 심벌로부터 유도될 수 있는 모든 문장 형태에서 A 다음에 나오는 terminal 심벌의 집합이다. 따라서 FOLLOW를 계산하기 위해서는 모든 문장 형 태를 고려해야 하나 , 문장 형태는 생성 규칙의 rhs들로 이루어져 있다. 그러므로 생성 규칙의 rhs를 이용하여 FOLLOW를 구할 수 있다.

11 각 nonterminal에 대한 FOLLOW 구하는 방법 (p262|p277 )
먼저 nullable 심벌을 구하고, 이것을 이용하여 <Alg 7.1>에 따라 FiRST 계산한다. First를 이용하여 FOLLOW를 구한다. First를 이용하여 FOLLOW를 계산하는 방법 <Alg 7.2>

12 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) * *

13 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 ⇒ 1A2 ⇒ 1 B 2 ⇒ 1 B 2 왜냐하면, 임의의 문장 형태에서 A 다음에 나올 수 있는 심볼은 모두 B다음에 나올 수 있기 때문이다 * * * *

14 <예 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) = { $ , ) , + , *}

15 7.1.3 LL 조건(p263 ~ |p278~ ) <정의 7.6 > 임의의 생성 규칙 A →  |   P에 대하여 다음 조건을 만족해야 한다. 1. FIRST() ∩ FIRST() =  ; 2. if   FIRST() then FOLLOW(A) ∩ FIRST()=  ; 생성 규칙의 FIRST가 서로 다르다는 것은 유도하는 스트링이 다르다는 것이므로, 문장 형태에서 적용할 생성 규칙을 결정적으로 선택할 수 있다. 그러나 FIRST가 같으면 유도하는 스트링이 같아서 생성 규칙 중 어느 것을 적용해야 올바른 것인지 알 수 없게 된다. 또한 생성 규칙이 을 유도할 수 있으면 FOLLOW심벌에 대하여 그 생성 규칙을 선택하게 된다. 따라서 FOLLOW 심벌과도 서로 분리된 집합이어야 한다.

16 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 조건을 만족한다.

17 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) * *

18 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

19 <정의 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)이다.

20 7.3 Predictive 파서(p273~ |p289~) <정의> 생성 규칙이 바뀌더라도 구문 분석 루틴은 고치지 않고, 단지 구문 분석기의 행동을 제어하는 파싱 테이블만 고쳐서 구문 분석기를 구현할 수 있는 방법 X . $ 구문분석기 파싱테이블 a1 a an$ 출력 input stack Parsing table의 크기 : 항상 |VN|  (|VT| + 1)

21 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이 되게 한다.

22 3. accept(인식) 4. error(오류) stack의 top 심벌과 현재 입력 심벌 모두가 $인 경우로
주어진 입력 스트링이 올바른 스트링임을 알린다. 4. error(오류) stack의 top이 nonterminal 심벌인 경우로 그 심벌 로부터 현재 보고 있는 입력 심벌을 결코 유도할 수 없음을 나타낸다.

23 <예 13> aabccd에 대한 구문분석(p277|p292)
1. S → aS S → bA 3. A → d 4. A → ccA (1) 유도 과정에 의한 구문분석 S ⇒ aS (1) ⇒ aaS (11) ⇒ aabA (112) ⇒ aabccA (1124) ⇒ aabccd (11243)  aabccd는 정의된 문법의 올바른 문장이다.

24 (2) 파스트리의 표현 S a b A c d

25 $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

26 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

27 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() = 

28 <예 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

29 ambiguous(모호성) (p283|p299) <예제>
1. S → iCtSS′ 2. S → a 3. S′ → eS 4. S′ →  5. C → b 파싱 테이블 구현 스택 top 심벌이 S'이고 현재의 입력 심벌이 e일 때 적용해야 될 생성 규칙을 결정적으로 선택할 수 없다. 따라서 위 문법은 LL(1) 문법이 아니다.

30 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) 문법이 동등하다.