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

목 차 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

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

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

정의 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

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

초기에 모든 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

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

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

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

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

생성규칙 형태가 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

*  예제 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

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

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

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

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

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

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

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

 aabccd는 정의된 문법의 올바른 문장이다. accept(인식) stack의 top심벌과 현재 입력 심벌 모두가 $인 경우로 주어진 입력 스트링이 올바른 스트링임을 알린다. error(오류) stack의 top이 nonterminal 심벌인 경우로 그 심벌로부터 현재 보고 있는 입력 심벌을 결코 유도할 수 없음을 나타낸다.  예제 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는 정의된 문법의 올바른 문장이다. Syntax Analysis

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

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

예제 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

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

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

Syntax Analysis