6. 구문 분석 (syntax analysis) 6-1. 구문분석 방법 6-2. 구문 분석기의 출력 6-3. Top-down방법 6-4. Botton-up방법
6-1. 구문분석방법 구문분석기 파스트리(parse tree) 구문분석기의 출력으로 생성되는 유도 트리와 같은 모양의 트리 스캐너 파서 중간코드 생성기 원시 프로그램 일련의 토큰 구문 분석 정보 중간 코드
Top-down방식 Bottom-up방식 루트노드로부터 시작하여 단말노드를 생성 좌측유도와 같은 생성규칙 단말 노드로부터 루트 노드를 향하여 위로 생성 우측유도의 역순의 생성규칙
예제 1. S XY 2. X aX 3. X b 4. Y aY 5. Y c S X Y a b c S XY aXY abY abaY abac 좌파스 = 12345 XaY Xac aXac 우파스 = 32541
6-2. 구문 분석기의 출력 구문분석 구문 분석기 주어진 스트링이 정의된 문법에 의해 생성될 수 있는지의 여부를 결정하는 과정으로 올바른 문장에 대해서는 일련의 생성 규칙 번호나 그 문장의 구조를 나타내는 파스 트리 또는 구문 트리를 출력으로 나타낸다. 올바른 문장 : 일련의 생성 규칙 번호, 또는 트리(파스 트리, 구문 트리) 틀린 문장 : 오류 메세지 입력 스트링 구문 분석기 구문분석기의 기능
파스(parse) 유도 과정에서 적용된 일련의 생성 규칙 번호 좌측유도과정에서 생성된 좌파스(left parse)와 우측유도과정에서 생성된 우파스(right parse) 예제 1. E E + T 2. E T 3. T T*F 4. T F 5. F ( E ) 6. F id (1) 좌측유도과정 (2) 우측 유도 과정 E E + T (1) E E + T (1) T + T (12) E + F (14) F + T (124) E + id (146) id + T (1246) T + id (1462) id + F (12464) F + id (14624) id + id (124646) id + id (146246) 좌파스 = 124646 우파스 = 642641
파스트리(parse tree) 올바른 문장에 대해 구문분석기가 그 문장의 구조를 트리 형태로 나타낸 것 루트노드 : 정의된 문법의 시작 심벌 중간노드 : 각 생성 규칙의 좌측 nonterminal 심벌 단말노드 : 주어진 스트링을 생성하는 terminal 심벌
예제 1. E E + E 2. E E * E 3. E ( E ) 4. E -E 5. E id 1) Top-down방식 E ( ) + id 2) Bottom-up방식
구문트리(Abstract Syntax Tree) 코드 생성 단계에서 꼭 필요한 의미정보만을 갖는 트리 비단말노드 : 의미있는 생성규칙의 이름 단말노드 : 의미있는 terminal 심벌 예제 1. E E + T add 2. E T 3. T T * F mul 4. T F 5. F ( E ) 6. F id add id mul E + T * F 1) 구문트리 2) 파스트리
6-3. Top-down 방법 구문분석과정 (Backtracking : 반복검조) 처음에 시작 심벌의 첫번째 생성 규칙을 적용하여 유도한다. 생성된 문장 형태의 스트링과 입력 스트링을 차례로 비교한다. 비교과정에서 nonterminal이 생성된 스트링에 나오면 이 nonterminal의 첫번째 생성규칙을 적용하여 유도한다. 유도된 스트링과 입력이 같으면 계속 비교해 나간다
비교한 두 심벌이 같지 않으면, 생성 규칙을 잘 못 적용한 것이므로 현재 적용된 생성 규칙을 제거하고 다른 생성규칙을 적용한다 비교한 두 심벌이 같지 않으면, 생성 규칙을 잘 못 적용한 것이므로 현재 적용된 생성 규칙을 제거하고 다른 생성규칙을 적용한다. 이때 입력 심벌의 위치는 제거한 생성규칙에서 보았던 심 벌의 개수 만큼 입력으로 되돌려 보낸다. 이상과 같은 과정을 반복하다가 더 이상 적용할 생성규칙이 없으면 주어진 스트링을 틀린 문장으로 인식하고, 문장 형태에 나 타난 스트링이 주어진 스트링과 같아지면 올바른 문장으로 인식 한다.
예제 S a B ccd A d b () 스트링 accd가 정의된 문법의 올바른 문장임을 확인 1. S aAd 2. S aB 3. A b 4. A c 5. B ccd 6. B ddc S a B ccd A d b ()
left-recursion 무한 loop의 가능성 => right-recursion으로 해결 예제 E + T => E E + T | T T T * F | F F ( E ) | id E + T =>
직접 left-recursion은 생성 규칙이 AA의 형태로 lhs의 nonterminal이 같은 생성 규칙의 rhs의 첫 심벌에 나타날 때 예제 A A | A A´ => A= (+ + ) => A = A + A´A´| = + + = * = (+ + ) = * A A A´ A => right-recursion A´ A A´ A A´
간접 left-recursion은 유도 과정 중 A => A의 형태를 갖는 경우로 예제 E E + T | T T T * F | F F ( E ) | id => E TE´ E´ +TE´ | T FT´ T´ *FT´ | 간접 left-recursion은 유도 과정 중 A => A의 형태를 갖는 경우로 두 번 이상 유도 과정이 있은 후에 순환이 나타나는 경우 +
간접 left-recursion을 직접 left-recursion으로 변환하는 방법 일정한 순서로 nonterminal을 순서화 생성 규칙에서 lhs보다 순서적으로 앞선nonterminal이 rhs의 첫번째로 나오는 생성 규칙에서 간접 순환이 발생한다. 따라서, 이와 같은 형태의 생성규칙을 대입기법을 통하여 제거한다. 대입 기법을 사용하여 간접 left-recursion을 제거하면 반드시 직접 left-recursion이 나타나게 된다. 예제 S Aa | b S Aa | b A Ac | Sd | e 간접 left-recursion제거 A Ac | Aad | bd | e A bdA´ | eA´ A´ cA´ | adA´ |
Left-factoring LL조건 공통 앞부분(common prefix)을 새로운 nonterminal을 도입하여 인수 분해 해야 한다. 예제 A | ==> A A´ A´ | S iCtS | iCtSeS | a C b ==> S iCtSS´ | a S´ eS | LL조건 형식적으로 전개하기 위해 FIRST, FOLLOW등을 이용 이 조건을 만족하는 문법을 LL문법
6-4. Bottom-up방법 Reduce S => 이고 AB의 생성규칙이 존재할 때, 문장 형태 예제 1. S aAcBe 2. A Ab 3. A b 4. B d (1) reduce sequence abbcde = aAbcde (reduce 3) = aAcde (reduce 2) = aAcBe (reduce 4) = S (reduce 1) (2) 파스트리 ====> * S A A B a b b c d e
Handle 한 문장 형태에서 reduce되는 부분 S => A => 의 과정이 있을 때, 을 문장형태 의 handle 예제 E E + E | E * E | ( E ) | id id + id * id E => E + E E => E * E => E + E * E E => E * id => E + E * id E => E + E * id => E + id * id E => E + id * id => id + id * id E => id + id * id 같은 sentential form에서 다른 handle이 존재할 때, 그 Grammar는 ambiguous하다. *
예제 1. E E + T 2. E T 3. T T * F 4. T F 5. F ( E ) 6. F a (1) 우측 유도 (2) reduce 과정 E => E + T (1) a + a * a = F + a * a (6) => E + T * F (13) = T + a * a (64) => E + T * a (136) = E + a * a (642) => E + F * a (1364) = E + F * a (6426) => E + a * a (13646) = E + T * a (64264) => T + a * a (136462) = E + T * F (642646) => F + a * a (1364624) = E + T (6426463) => a + a * a (13646246) = E (64264631) 우파스와 reduce sequence : 64264631
(2) 우파스와 reduce sequence : 64264631 Handle pruning S r0 r1 … rn-1 rn 의 우측 유도 과정이 있을 때 각 ri의 문장 형태에서 handle을 찾아 ri-1로 가면서 시작 심벌로 reduce되는 과정 예제 (1) id + id * id 분석과정 (2) 우파스와 reduce sequence : 64264631
Shift-reduce 구문분석 스택의 top부분에 handle이 나타날 때까지 계속해서 shift를 행하며, handle를 찾으면 이 handle에 해당되는 rhs를 갖는 생성 규칙을 결정하여 lhs로 reduce하여 문법의 시작 심벌에 이를 때 까지 반복, 수행하는 구문 분석 과정 123…I …n-1n$ Sn . : $ 출력 Shift-redude 파서 파싱 테이블 그림 6-3 shift-reduce
파싱 스택(parsing stack) Shift행동 Reduce행동 Accept행동 Error행동 문장 형태에서 handle을 찾을 때까지 필요한 문법 심벌들을 유지하고 입력 버퍼는 주어진 스트링을 간직 Shift행동 현재의 입력 심벌을 스택에 옮기는 것 입력포인터를 하나 증가하여 다음 심벌을 가리키도록 하고 현재의 입력 심벌은 스택에 push하는 작업을 의미 Reduce행동 스택 top부분에 있는 handle을 생성규칙의 lhs로 대치하는 것을 의미한다. Accept행동 주어진 스트링이 문법의 올바른 문장인 것을 나타낸다. Error행동 현재 보고 있는 입력 심벌이 그 상태에서 나타날 수 없기 때문에 틀린 문장 이라는 것을 의미
예제 1. E E + T 2. E T 3. T T * F 4. T F 5. F ( E ) 6. F a (1) reduce 과정 : a + a * a = F + a * a (6) = T + a * a (64) = E + a * a (642) = E + F * a (6426) = E + T * a (64264) = E + T * F (642646) = E + T (6426463) = E (64264631) reduce sequence : 64264631
(2) 구문 분석 과정 $는 end marker이며, 단계 0에서는 스택에 $, 그리고 입력 버퍼에는 파싱 하고자 하는 스트링과 입력의 끝을 나타내는 기호 $ 기호를 넣는다. 이 상태를 초기 상태라 한다. 그리고, 13단계에서, 스택 top에 시작 심벌이 있고 입력은 모두 본 상태를 accept상태라 말한다.
트리 생성 파스트리 구성하는 방법 shift 모든 shift되는 심벌에 대해 단말 노드를 만든다. reduce가 일어날 때마다 AX1X2…Xn A에 해당하는 비단말 노드를 만든다. X1X2…Xn을 A노드의 자노드로 연결한다. 생성규칙이 A인 경우, 단지 A노드만 만든다. accept 현재 구성된 트리를 파스트리로 복귀한다. error 이제까지 구성한 트리가 아무 의미가 없게 된다.
예제 1. LIST LIST, ELEMENT 2. LIST ELEMENT 3. ELEMENT a (1) 파싱 과정 (2) 파스 트리 7 LIST 3 LIST 2 ELEMENT 6 ELEMENT 1 4 5 a , a
구문트리 구성 방법 예제 (2) 구문트리 build node 의미있는 terminal 심벌을 shift할 때 호출한다. build tree 의미있는 생성 규칙으로 reduce할 때 호출한다. 예제 (1) 파싱과정 (2) 구문트리 8 Id_list a 5 a 1