컴파일러 입문 제 7 장 LL 구문 분석.

Presentation on theme: "컴파일러 입문 제 7 장 LL 구문 분석."— Presentation transcript:

1 컴파일러 입문 제 7 장 LL 구문 분석

2 목 차 7.1 결정적 구문 분석 7.2 Recursive-descent 파서 7.3 Predictive 파서
목 차 7.1 결정적 구문 분석 7.2 Recursive-descent 파서 7.3 Predictive 파서 7.4 Predictive 파싱 테이블의 구성 7.5 Strong LL(k) 문법과 LL(k)문법 Syntax Analysis

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

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

5 정의 nonterminal A가 가 유도할 수 있으며 A를 nullable하다고 부른다.
두개의 집합에 대한 연산자인 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, } FIRST(A1A2 An ) = FIRST(A1)FIRST(A2)FIRST(An) * Syntax Analysis

6 FIRST(X)를 계산하는 방법 X가 terminal이면 X의 FIRST는 자기 자신이 된다.
FIRST(X) = { X | if X VT} 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 XY1Y2Yk인 생성규칙이 있을 때, FIRST(X) = FIRST(X) FIRST(Y1Y2Yk)이다. Syntax Analysis

7 초기에 모든 nonternal은 FIRST는 공집합이 된다.
rhs에 첫번째로 terminal이 나오는 생성 규칙(-생성 규칙 포함)에서 FIRST를 구한 후, 이 형태의 생성 규칙은 다시 고려할 필요가 없기 때문에 제거한다. 남은 생성 규칙의 형태는 모두 nonterminal로 시작하므로 ring sum 연산을 이용하여 모든 nonterminal의 FIRST가 변하지 않을 때까지 반복한다. 일반적으로 A-생성 규칙이 A1|2||nP와 같은 형태일 때 다음과 같이 된다. FIRST(A) = FIRST(1)  FIRST(2)  FIRST(n) Syntax Analysis

8 FIRST(S) = FIRST(S)(FIRST(A)FIRST(B) FIRST(e))
 예제 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} Syntax Analysis

9 FIRST(E) = FIRST(T) = FIRST(F) = {(,id} FIRST(E’) = {+, }
예제 E  TE’ E’  +TE’ |  T  FT’ T’  *FT’ |  F  ( E ) | id FIRST(E) = FIRST(T) = FIRST(F) = {(,id} FIRST(E’) = {+, } FIRST(T’) = {*, } Syntax Analysis

10 FOLLOW Nonterminal A가 nullable하면 FIRST(A)에 이 속하게 되지만
유도할 것인가를 결정하게 된다. 따라서 -생성 규칙을 갖는 문법에서 는 nonterminal 다음에 나오는 terminal심벌이 의미를 갖게 되는데 이것을 FOLLOW라 부른다. FOLLOW(A) = {aVT{$} | S Aa, , V*} $는 입력 스트링의 끝을 표기하는 마커 심벌 nonterminal A의 FOLLOW란 시작 심벌로 부터 유도될 수 있는 모든 문장 형태에서 A 다음에 나오는terminal심벌의 집합이다. 따라서 FOLLOW를 계산하기 위해서는 모든 문장형태를 고려해야 하나 문장 형태는 생성 규칙의 rhs들로 이루어져 있다. 그러므로 생성 규칙의 rhs를 이용하여 FOLLOW를 구할 수 있다. Syntax Analysis

11 FOLLOW를 계산하는 방법 시작심벌은 $를 초기값을 갖는다. FOLLOW(S) = {$}
생성 규칙의 형태가 AB,   일 때, FIRST()에서 을 제외 한 terminal 심벌을 B의 FOLLOW에 추가 한다. if A  B,  then FOLLOW(B) = FOLLOW(B)(FIRST()-{}) AB이거나 AB에서 FIRST()에 이 속하는 경우 (즉, ), A의 FOLLOW 전체를 B의 FOLLOW에 추가한다. if A  B  P or (A  B and   ) then FOLLOW(B) = FOLLOW(B)FOLLOW(A) Syntax Analysis

12 생성규칙 형태가 AB인 경우, 가 이거나 또는 을 유도
할 수 있으면, A의 FOLLOW전체를 B의 FOLLOW에 넣는다는 것이다. 왜냐하면 임의의 문장 형태에서 A 다음에 나올 수 있는 심벌은 모두 B 다음에 나올 수 있기 때문이다. S1A21B21B2 FOLLOW속성으로 인하여 AB, BA와 같은 형태의 생성 규칙을 갖고 있으면, FOLLOW(A) = FOLLOW(B)이다. 왜냐하면, 첫번째 형태의 생성 규칙으로부터 FOLLOW(A)  FOLLOW(B) 이고 두 번째 형태의 생성 규칙 으로부터 FOLLOW(A)FOLLOW(B)가 되기 때문이다. * * Syntax Analysis

13 *  예제 E  TE’ E’ +TE’ |  T  FT’ T’  FT’ |  F  ( E ) | id
FOLLOW(E) = {$} FOLLOW(E)  FIRST()) = {)} FOLLOW(F)  FIRST(T’) = {*} (은 제외) FOLLOW(T)  FIRST(E’) = {+} (은 제외) FOLLOW(E)  FOLLOW(E’) FOLLOW(T)  FOLLOW(T’) FOLLOW(E)  FOLLOW(T) FOLLOW(T)  FOLLOW(F) FOLLOW(E)  FOLLOW(T)  FOLLOW(F) FOLLOW(E) = {$, )} FOLLOW(T) = {$, ), +} FOLLOW(F) = {$, ), +, *} FOLLOW(E’) = FOLLOW(E) = {$, )} FOLLOW(T’) = FOLLOW(T) = {$, ), +} * Syntax Analysis

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

15 FIRST(A) = {a,b,c,d} FOLLOW(A) = {$,a}
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 조건을 만족한다. Syntax Analysis

16 7.2 Recursive-descent파서 정의 LOOKAHEAD LL파서의 일종으로 주어진 이력 스트링을 파싱하기 위하여
일련의 순환 프로시저를 사용한다. 각 순환 프로시저는 각 nonterminal에 해당하는 것으로 nonterminal에 대한 유도를 프로시저 호출로 처리하는 방법 LOOKAHEAD LOOKAHEAD(A) = FIRST({ | S  A      VT*} LOOKAHEAD(AX1X2Xn) = FIRST(X1) FIRST(X2)…FIRST(Xn)FOLLOW(A) * Syntax Analysis

17 FIRST(S) = {a, } FOLLOW(S) = {$,c} FIRST(A) = {c} FOLLOW(A) = {$,c}
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 Syntax Analysis

18 LOOKAHEAD(A  )  LOOKAHEAD(A  ) = .
▶ Strong LL 조건 정의 : A   |  ∈ P, LOOKAHEAD(A  )  LOOKAHEAD(A  ) = . 의미 : LOOKHEAD가 다르면 생성하는 스트링이 다르고 적용할 생성 규칙이 유일하므로 현재 입력 심볼에 따라 결정적 구문 분석 할 수 있다. ex) G : S  aSA |  A  c  LOOKAHEAD(S  aSA) = {a}  LOOKAHEAD(S  ) = FOLLOW(S) = {$, c} LOOKAHEAD(S  aSA)  LOOKAHEAD(S  ) =   G는 strong LL(1)이다. Syntax Analysis

19 7.3 Predictive 파서 입력 a1 a2 … an$ X 구문분석기 . 출력 $ 파싱테이블 스택 정의
생성 규칙이 바뀌더라도 구문 분석기는 고치지 않고 단지 구문 분석기의 행동을 나타내는 파싱 테이블만 고쳐서 구문 분석기를 구현 할 수 있는 방법 입력 a1 a … an$ X . $ 구문분석기 출력 파싱테이블 스택 Syntax Analysis

20 Parser Action pop(제거) extend(확장) stack의 top = 입력 symbol
stack의 top심벌은 stackt에서 제거하고 현재 입력 심벌은 입력 스트링 에서 제거 extend(확장) stack의 top이 nonterminal인 경우로 생성 규칙을 적용하여 확장한다. 예를 들어, M[A, a] = {AXYZ}일때, A를 스택에서 제거하고 ZYX를 차례로 스택에 넣는다. Syntax Analysis

21  aabccd는 정의된 문법의 올바른 문장이다.
accept(인식) stack의 top심벌과 현재 입력 심벌 모두가 $인 경우로 주어진 입력 스트링이 올바른 스트링임을 알린다. error(오류) stack의 top이 nonterminal 심벌인 경우로 그 심벌로부터 현재 보고 있는 입력 심벌을 결코 유도할 수 없음을 나타낸다.  예제 1. S  aS 2. S  bA 3. A  d A  ccA (1) 유도과정에 의한 구문분석 S  aS (1)  aaS (11)  aabA (112)  aabccA (1124)  aabccd (11243)  aabccd는 정의된 문법의 올바른 문장이다. Syntax Analysis

22 S a S a S b A A c d (2) 파스트리의 표현 (3) 스택을 이용한 predictive 구문 분석
Syntax Analysis

23 7.4 Predictive 파싱 테이블의 구성 파싱테이블 구성 방법 LL(1)문법
모든 aFIRST()에 대하여, M[A, a] := A로 채운다. 만일 FIRST()이면, 모든 bFOLLOW(A)에 대하여, M[A,b]:=A로 채운다. LL(1)문법 임의의 생성 규칙 A|에 대하여 FIRST()FIRST() =  만약 FIRST()이면, FOLLOW(A)FIRST() =  Syntax Analysis

24 예제 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) 파싱테이블 Syntax Analysis

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

26 7-5. Strong LL(k)문법과 LL(k) 문법
strong LL(1)  LL(1) k = 1인 경우, 두 문법이 나타내는 언어의 종류는 같다. 즉, LL(1)문법과 strong LL(1)문법이 동등하다는 것이다. Syntax Analysis

27 Syntax Analysis