제 6 장 상향식 파싱
제 6 장 상향식 파싱 상향식 파싱 생성규칙 A → β에 대해 아래같이 문법규칙을 적용(⇒R은 환원을 의미) αβω ⇒R αAω ⇒R S
6.1 상향식 파싱의 개념 그림 6.1 하향식 파싱과 상향식 파싱 기법의 기본 개념
간단하게 아래 문법 G를 사용하여 입력 스트링 abbcd를 상향식으로 파싱하는 과정을 살펴보자. G : S → aAB A → Abc|b B → d 스트링 abbcde가 S로 환원하는 과정은 아래와 같다. abbcd (b 를 A→ b에 의해 A로 바꾼다) ⇒R aAbcd (Abc 를 A→ Abc에 의해 A로 바꾼다) ⇒R aAd (d 가를 B→ d에 의해 B로 바꾼다) ⇒R aAB (aAB 를 생성규칙 S→ aAB에 의해 S로 바꾼다) ⇒R S (S는 시작 심볼이다)
정의 6. 1 생성 규칙 A → β가 있고 우단유도 S ⇒. rm αAω⇒ 정의 6.1 생성 규칙 A → β가 있고 우단유도 S ⇒*rm αAω⇒*rm αβω가 있으면 문장형식 αβω에서 부분 스트링 심볼 α뒤에 있는 β를 핸들이라 하고, 생성 규칙 A → β에 의해 β는 A로 환원할 수 있다. 즉, 핸들은 생성 규칙의 오른쪽에 있는 심볼 스트링에서 입력 문장의 스트링과 일치하는 부분 스트링이다. 문장형식 abbcd 에서는 핸들이 b 이다. 문장형식 aAbcd 에서는 핸들이 Abc 이다. 문장형식 aAd 에서는 핸들이 d 이다. 문장형식 aAB 에서는 핸들이 aAB 이다. 시작심볼 S 환원 끝
파스트리의 핸들 그림 6.2 파스트리에서 αβω에 대한 핸들 A → β
핸들 가지치기 파싱을 위하여 터미널 스트링에서 시작하여 루트의 시작 심볼까지 가면서 우단유도를 거꾸로 수행하면 핸들 가지치기를 알 수 있다. ω = ζn⇒R ζn-1⇒R ζn-2 .... ⇒R ζ1 ⇒R ζ0 = S
파스트리의 가지치기 그림 6.3 파스트리에서의 가지치기 과정
예 6. 1 아래 문법을 사용하여 산술 수식 스트링 id1 + id2 예 6.1 아래 문법을 사용하여 산술 수식 스트링 id1 + id2 * id3을 시작 심볼 E 로 환원하는 과정에서 핸들을 찾아보자. id1, id2, id3 은 터미널 심볼 id의 왼쪽에서 오른쪽으로 나타나는 순서이다. G: E → E +E E → E * E E → id 오른쪽 문장형식 핸 들 환원에 적용된 생성규칙 (1) id1 + id2 * id3 (2) E + id2 * id3 (3) E +E * id3 (4) E +E * E (5) E +E (6) E id1 id2 id3 E * E E + E E → id E → E * E E → E + E
6.2 이동-환원 파싱 알고리즘 상향식 파싱을 하려면 이미 언급한 것과 같이 이동-환원 파싱 알고리즘을 사용한다. 기본적으로 두 개의 행위가 있는데 이동(shift)과 환원(reduce) 이동-환원 알고리즘은 핸들을 탐지하기 위해 스택을 사용하여 오른쪽 문장형식에서 핸들을 찾고 적용할 생성 규칙을 결정적으로 선택한다.
이동-환원 알고리즘의 수행 행위 이동 환원 수락 에러 현재의 입력 스트링의 맨 앞에 있는 터미널 심볼을 스택의 톱에 이동한다. 스택의 톱에 있는 핸들을 규칙에 따라 해당 생성규칙의 넌터미널로 대치(환원)한다. 수락 입력 스트링을 모두 읽어서 정상적인 파싱이 수행되었음을 알린다. 에러 파서는 구문 에러를 발견하고 에러 처리루틴을 호출한다.
이동-환원 알고리즘의 동작 단계 1: 맨 처음 상태에 스택은 비어있다. 단계 2: 비어있는 스택에 입력 스트링의 맨 처음에 있는 심볼을 이동한다. 단계 3: 스택의 톱에 있는 심볼과 입력 스트링의 맨 앞 터미널 심볼을 비교한다. 이 때 규칙에 따라 입력 스트링의 터미널 심볼을 스택으로 이동할 것인지, 아니면 스택에서 심볼 몇 개를 해당 생성 규칙의 넌터미널로 바꿀 것인지를 결정한다. 3.1 규칙이 이동이면, 터미널 심볼을 스택에 넣는다. 3.2 규칙이 환원이면, 스택의 톱에서부터 문장형식을 환원하려는 생성 규칙의 넌터미널로 바꾼다. 3.3 입력 스트링을 모두 읽고 스택의 톱에 시작 심볼만 남으면 파싱 을 종료한다(즉, 주어진 문법으로 입력 문장을 인식할 수 있다).
예 6.2 아래 문법을 이용하여 입력 스트링 caabaab에 대하여 이동-환원 알고리즘이 어떻게 작동하는가를 살펴보자. G: 1. S → S a B 2. S → c 3. B → a b 이 문법에서는 입력 스트링 caabaab에 대하여 아래와 같은 유도과정을 가진다. S ⇒ SaB ⇒ Saab ⇒ SaBaab ⇒ Saabaab ⇒ caabaab
이동-환원 (# : caabaab↲)⊢ 이동 (#c : aabaab↲)⊢ 생성 규칙2에 의하여 환원 (#S : aabaab↲)⊢ 이동 (#Sa : abaab↲)⊢ 이동 (#Saa : baab↲)⊢ 이동 (#Saab : aab↲)⊢ 생성 규칙3에 의하여 환원 (#SaB : aab↲)⊢ 생성 규칙1에 의하여 환원 (#S : aab↲)⊢ 이동 (#Sa : ab↲)⊢ 이동 (#Saa : b↲)⊢ 이동 (#Saab : ↲)⊢ 생성 규칙3에 의하여 환원 (#SaB : ↲)⊢ 생성 규칙1에 의하여 환원 (#S : ↲)⊢ 수락
실습 6.1 아래 문법 G 가 있다. 이동-환원 알고리즘으로 입력 스트링 caab를 파싱하는 과정의 스택 상태를 보이시오. G: 1. S → SaB 2. S → c 3. B → ab
실습 6.2 아래 문법 G 가 있다. 이동-환원 알고리즘으로 입력 스트링 ababccab를 파싱하는 과정의 스택 상태를 보이시오. G: 1. S → SaB 2. S → c 3. B → ab
6.3 LR 문법 어떤 문법이 이동-환원 알고리즘으로 파서를 정확하게 구현할 수 있으면 이 문법을 LR 문법이라 한다. LR 문법에서 LR의 의미는 입력 스트링을 왼쪽(Left)에서 오른쪽으로 읽어서 가장 오른쪽(Right) 넌터미널을 먼저 유도한다는 의미이다.
예 6.3 아래 문법에 대하여 입력 스트링 aaab를 파싱하여 보자. G: 1. S → SaB 2. S → a 3. B → ab 스택과 입력 상태는 아래와 같으며 파싱을 진행할 수 없다. (# : aaab↲)⊢ 이동 (#a : aab↲)⊢ 생성 규칙2에 의하여 환원 (#S : aab↲)⊢ 이동 (#Sa : ab↲)⊢ 이동 혹은 환원(충돌 발생함) (더 이상 파싱을 진행할 수 없음)
이동/환원 충돌 (#Sa : ab↲)⊢ 이동 혹은 환원(충돌 발생함) 이와 같이 두 행위를 동시 수행해야하는 상태가 되면 이동/환원 충돌이 발생한다고 한다. 아래와 같이 몇 개의 충돌이 있을 수 있다. 이동/환원 충돌 이동/이동 충돌 환원/환원 충돌
충돌시 이동 적용 위의 파싱 과정에서 파싱을 계속 진행하도록 이동 행위를 적용하여 보자. (# : aaab↲)⊢ 이동 (#S : aab↲)⊢ 이동 (#Sa : ab↲)⊢ 이동 (#Saa : b↲)⊢ 생성규칙2에 의하여 환원(문법에 있는 번호) (#SaS : b↲)⊢ 이동 (#SaSb : ↲)⊢ 에러(이동 환원 모두 수행할 수 없음) (더 이상 파싱을 진행할 수 없음)
환원/환원 충돌 예 환원/환원 충돌은 파싱 도중에 환원할 생성규칙이 여러 개 존재하는 경우이다. 아래 문법에 대하여 입력 스트링 aa 를 파싱하면서 환원/환원 충돌을 살펴보자. G: 1. S → SA 2. S → a 3. A → a
입력 스트링 aa 에 대한 파싱 과정은 아래와 같다. (환원/환원 충돌, 에러) (더 이상 파싱을 진행할 수 없음)
파싱을 계속하기 위하여 생성규칙2를 적용하면 아래와 같이 파싱이 정상적으로 이루어진다. (# : aa↲) ⊢ 이동 (#a : a↲)⊢ 생성규칙2에 의하여 환원 (#S : a↲)⊢ 이동 (#Sa : ↲)⊢ 생성규칙3에 의하여 환원 (#SA : ↲)⊢ 생성규칙1에 의하여 환원 (#S : ↲)⊢ 수락
실습 6.3 입력 스트링 ababab를 파싱하는 과정의 스택 상태를 아래 문법 G에 대하여 보이시오. G: 1. S → Sa 2. S → ab
예 6.4 아래의 배열 참조와 함수 호출 두 문장을 살펴보자. area(x, y); /* 배열 참조, 배열명 area 이고 인덱스가 x, y 이다. */ area(A, B); /* 함수 호출, 함수명 area 이고 인자가 A, B 이다. */ 두 경우에서 area(x, y); 는 배열이므로 배열 참조에 대한 생성 규칙으로 환원 area(A, B); 는 함수를 호출하는 생성 규칙으로 환원
a 는 변수나 인자인 경우에 이 문장을 파싱하는 스택은 아래와 같은데, 입력 스트링의 맨 앞에 있는 터미널 심볼 ; 에 대하여 배열 참조 생성 규칙과 함수 호출 생성 규칙 둘 다 환원할 수 있다. 그러므로 환원/환원 충돌이 발생한다. (#......area(a, a) : ; a = a + a * a ......↲)
아래 문장은 두 개의 유도트리를 만들 수 있기 때문에 명확하지 않으므로 LR 문법이 아니다. 예 6.5 if 문장에 대한 아래 문법은 명확하지 않기 때문에 LR이 될 수 없다. S 는 문장을 나타내는 생성규칙의 넌터미널이고 Cexpr은 조건수식을 나타내는 생성규칙의 넌터미널로 결과 값은 참과 거짓 중에서 하나이다. G: 1. S → if Cexpr then S 2. S → if Cexpr then S else S 3. S → id 아래 문장은 두 개의 유도트리를 만들 수 있기 때문에 명확하지 않으므로 LR 문법이 아니다. if Cexpr then if Cexpr then S else S
예 6.6 예 6.5의 문법으로 아래 문장을 이동-환원 알고리즘으로 파싱을 수행해 보자 if Cexpr then if Cexpr then S else S 스택과 입력 스트링의 구성은 아래와 같이 구성된다. (# ... if Cexpr then if Cexpr then S : else S ..... ↲)⊢ 이동 혹은 환원
생성규칙1을 적용하면 (# ... if Cexpr then if Cexpr then S : else S ..... ↲)⊢ 생성규칙1에 환원 (# ... if Cexpr then S : else S ..... ↲)⊢ 이동 (# ... if Cexpr then S else : S ..... ↲)⊢ 이동 (# ... if Cexpr then S else S : ..... ↲)⊢ 생성규칙2에 환원 (# ... S : ..... ↲)⊢ (파싱 계속 진행)
생성규칙2을 적용하면 (# ... if Cexpr then if Cexpr then S : else S ..... ↲)⊢ 이동
실습 6.4 아래 문법으로 산술 수식 입력 a + b * c을 이동-환원 알고리즘으로 파싱하는 스택 상태를 보이시오. G: 1. E → E + E 2. E → E * E 3. E → ( E ) 4. E → a 5. E → b 6. E → c
실습 6. 5 좀 더 복잡한 아래 문법에 대하여 산술 수식의 입력 스트링 a + b 실습 6.5 좀 더 복잡한 아래 문법에 대하여 산술 수식의 입력 스트링 a + b * c을 이동-환원 알고리즘으로 파싱하는 과정을 스택으로 보이시오. G: 1. E → E + E 2. E → T 3. T → T * F 4. T → F 5. F → ( E ) 6. F → a 7. F → b 8. F → c
제 6 장 끝