Download presentation
Presentation is loading. Please wait.
1
제 4 장 구문 분석
2
4.1 구문 분석 개념 그림 4.1 구문 분석기의 위치와 기능 어휘 분석기 구문 중간 코드 심볼 테이블 원시프로그램 토큰
파스트리 중간 코드 심볼 테이블 그림 4.1 구문 분석기의 위치와 기능
3
유도과정과 파스 트리 파스트리는 프로그램의 각 문장이 문법에서 만들어지는 언어인지를 검사하는 유도 과정이다.
이러한 유도 과정을 파스 트리라 한다. 문장 구조가 올바른지 아닌지를 알기 위해 입력 토큰 스트림과 문법을 비교한다.
4
신택스 트리와 중간코드 구문 분석에 의하여 생성되는 것은 중간 코드의 신택스 트리
중간 코드는 기계어 인스트럭션을 만들 수 있는 가장 작은 동작으로 컴퓨터의 주소로 되어 있는 피연산자를 포함한다. = x + * y 1.873 - 78 a 그림 4.2 x = (a - 78) * y; 의 신택스 트리
5
4.2 문법과 언어 컴파일러의 구문 분석 단계를 이해하기 위하여 형식 언어의 이론과 개념을 살펴보자!
6
4.2.1 문법 정의 4.1 문법(G)은 알파벳, 입력 심볼, 터미널 심볼 문자의 유한 집합에 대하여, G = (VN, VT, P, S)와 같이 구성한다. 여기에서 각 구성요소는 아래와 같다. VN 은 넌터미널 심볼의 유한 집합이다. VT 은 터미널 심볼의 유한 집합으로 VN ∩VT =∅, VN∪VT = V 이다. V 는 알파벳 집합이다. P 는 생성규칙의 유한 집합으로 아래의 형식을 가지는데 α 는 널이 아니다. α →β (α ∈V+, β∈V* ) S 는 시작 심볼이나 문장 심볼로서 S ∈VN 이다.
7
예 4.1 문법 G1 = ({S, T}, {t, r}, P, S)을 살펴보자. 이 문법의 각 원소는 아래와 같다.
4. 생성 규칙 P : S →tTS S →t T →SrT T →rt T →SS
8
유도 정의 4.2 유도는 생성규칙에서 문장을 생성하는 과정으로 시작 심볼에서 생성규칙의 정의 기호(→)의 오른쪽에 있는 심볼들로 대치한다. S는 시작 넌터미널, α,β,γ는 터미널이나 넌터미널 스트링, x는 터미널 스트링이면 유도(⇒)는 아래와 같이 쓴다. S ⇒ α ⇒ β ⇒ γ ⇒ .... ⇒ x
9
예 아래의 문법이 있으면 스트링 baaa을 S ⇒ Sa ⇒ Saa ⇒ Saaa ⇒ baaa와 같이 유도한다.
P : S → S a S → b S → ε 스트링 baaa을 S ⇒ Sa ⇒ Saa ⇒ Saaa ⇒ baaa와 같이 유도한다.
10
정의 4.3 언어는 시작 넌터미널 심볼 S로 시작하는 문법 G 에서 ⇒+를 적용하여 문법 G에서 생성되어지는 언어 L(G)로 표기한다. 언어 L(G)안에 있는 스트링은 아래와 같이 G의 터미널 심볼만으로 구성된다. L(G) = {ω| S ⇒+ω, ω∈VT*}
11
예 4. 2 문법 G2 = ({S}, {t}, P, S)을 살펴보자
예 4.2 문법 G2 = ({S}, {t}, P, S)을 살펴보자. 이 문법의 생성 규칙이 P : S →tS |t이면 유도에 의하여 아래의 언어가 생성될 수 있다. S ⇒t t ∈L(G2) S ⇒tS ⇒tt tt∈L(G2) S ⇒tS⇒ttS⇒ttt ttt∈L(G2) ......
12
예 4.3 문법 G3 = ({S}, {0,1}, P, S) 이고, 생성 규칙이 아래와 같을 때 이 문법에서 언어를 유도해 보자.
P : S → 0S0 | 1S1 | 0 | 1 이 문법에서 한 언어를 유도하면 아래와 같다. S ⇒ 0S0 ⇒ 00S00 ⇒ 001S100 ⇒
13
문장과 문장형식 정의 4.4 S ⇒* α이고 α ∈V * 이면 α를 문법 G 의 문장형식이라 하고, S ⇒* α이고 α ∈VT* 이면 α는 문법 G 의 문장이라 한다.
14
예 4.4 문법 G4 = ({S, A, B}, {0, 1, ε}, P, S) 이고, 생성 규칙이 아래와 같을 때 문장 0110를 유도하는 과정에서 문장 형식을 알아보자.
P : S →0A|1B|ε A →1S B →0S
15
이 문법에서 0110를 유도하는 과정은 아래와 같다. S ⇒0A (생성규칙 S →0A) ⇒01S (생성규칙 A →1S) ⇒011B (생성규칙 S →1B) ⇒0110S (생성규칙 B →0S) ⇒0110 (생성규칙 S →ε) 유도 과정에서 생성되는 S, 0A, 01S, 011B, 0110S는 문장형식이고, 터미널 스트링만으로 구성된 0110 은 문장이다.
16
실습 4. 1 생성 규칙이 아래와 같은 문법 G5 = ({S}, {0,1}, P, S)가 있다
P : S → 0S0 S → 1S1 S → 0 S → 1
17
예 4.5 아래 생성 규칙이 있는 문법 G6 = ({S, A, B}, {a, b, ε}, P, S)에서 문장 aabb를 유도해 보자.
P : S →ASB S →ε A →a B →b
18
이 문법은 문장 aabb를 유도할 수 있다. S ⇒ ASB (생성규칙 S →ASB) ⇒ AASBB (생성규칙 S →ASB) ⇒ AaSBB (생성규칙 A →a) ⇒ AaBb (생성규칙 S →ε) ⇒ Aabb (생성규칙 B →b) ⇒ aabb (생성규칙 A →a)
19
실습 4.2 문법 G = ({S, A, B}, {1,0}, P, S) 이고, 생성 규칙이 아래와 같을 때 이 문법에서 생성할 수 있는 여러 개의 유도과정을 보이시오.
P : S → 1SA|BA A → 10 B → 0A 어떤 스트링을 생성하는데 두 개 이상 여러 개의 유도가 있을 수 있다는 것을 알 수 있다.
20
4.2.2 문법의 분류 무제한 문법 문맥-민감 문법 문맥-자유 문법 우-선형 문법 그림 4.3 문법의 분류 무제한 문법
21
촘스키의 문법 분류 타입 0 문법: 무제한 문법은 타입 0 문법이라고도 하며 생성규칙에 제한이 없는 문법이다. 각 생성규칙은 화살표 → 의 양쪽(왼쪽과 오른쪽)에 임의의 터미널과 넌터미널 스트링으로 구성된다. 단 ε 는 화살표의 오른쪽에만 올 수 있다. AaB → bA|ε
22
타입 1 문법: 문맥-민감 문법은 타입 1 문법이라고도 하며 아래와 같은 생성규칙으로 구성된다
타입 1 문법: 문맥-민감 문법은 타입 1 문법이라고도 하며 아래와 같은 생성규칙으로 구성된다. 문맥-민감 문법은 컴파일러에서 실제로는 사용할 수 없다. |α|≤|β|로 β의 길이가 α의 길이보다 더 길다. α → β 1. A → aABCc 2. A → ε 3. aB → ab 4. bB → bb 5. cB → cb 6. bC → ac 7. C → Cc
23
교재를 수정해야함 A → aABCc 를 A → aABC 로
문맥-민감 문법에서 생성한 언어의 예 A ⇒ aABC ⇒ aaABCBC ⇒ aaBCBC ⇒ aabCBC ⇒ aabCcBC ⇒ aabCcbC ⇒ aabCccbC ⇒ aabCccbCc ⇒ aaacccbCc ⇒ aaacccacc
24
타입 2 문법: 문맥-자유 문법은 타입 2 문법이라고도 하며, 문맥에 제한되지 않고 자유롭기 때문에 아래와 같은 생성규칙으로 구성된다.
A → α, |A|=1, |A|≤| α | 생성한 언어 예 S →aAS S →a A →SbA A →ba A →SS
25
타입 3 문법: 우-선형 문법은 타입 3 문법이라고도 하며 아래와 같은 생성규칙으로 구성된다.
A → aB 또는 A → a
26
실습 4.3 아래의 문법 생성 규칙에서 촘스키의 분류에 따라 무제한, 문맥-민감, 문맥-자유, 우-선형 문법을 고르시오.
1. aSb → aAbBc 2. A → bB 3. Ab → b 4. b → AB 5. S → aAbc 6. AB → BAC
27
실습 4. 4 어떤 언어 L(G) = {ε, abc, aabbcc, aaabbbccc,
실습 4.4 어떤 언어 L(G) = {ε, abc, aabbcc, aaabbbccc, ...} = {anbncn}, n≥0는 a뒤에는 b가, b뒤에는 c가 오지만, a, b, c 각각의 갯 수가 반드시 같은 스트링의 집합이다. 이 언어를 생성하는 문맥-민감 언어를 구성해 보자.
28
4.2.3 문맥-자유 문법과 표현 문맥-자유 문법은 반복 구조로 프로그래밍 언어의 문장이나 구조
조건 문장을 만드는 아래의 규칙을 정규 수식으로 표현할 수 있는지?? 「S1과 S2이 각각 문장이고 E 가 수식이면 "if (E ) S1 else S2;" 는 문장이다」 제한된 방법으로 표현하기 어려운 언어 구조도 문맥-자유 문법으로는 표현하기 쉽다. 정규 수식으로 이러한 조건 문장을 표현하기는 어렵다.
29
예 4.6 수식 a + a + a + a + a 와 같이 더하기 연산을 반복하는 문법 G = ({E, OP}, {a, +}, P, E)를 구성해 보자. 이 수식에서 터미널 심볼은 a와 연산자 + 이고 더하기 연산만 반복한다. 그러므로 이 수식을 표현하려면 터미널 심볼 a는 넌터미널 E에서 유도되고, 터미널 심볼 +는 넌터미널 OP에서 생성되도록 아래와 같이 반복하여 유도하도록 한다. E ⇒E OP E ⇒*E OP E OP E OP E OP E ⇒* a + a + a + a + a 다음과 같은 생성 규칙을 구성할 수 있다. P : E → E OP E E → a OP → +
30
이 생성 규칙에 의하여 아래와 같이 유도할 수 있다. 밑줄 친 넌터미널 심볼이 대치된다.
E ⇒ E OP E ⇒ E OP E OP E ⇒ E OP E OP E OP E ⇒ E OP E OP E OP E OP E ⇒ a OP E OP E OP E OP E ⇒ a + E OP E OP E OP E ⇒ a + a OP E OP E OP E ⇒ a + a + E OP E OP E ⇒ a + a + a OP E OP E ⇒ a + a + a + E OP E ⇒ a + a + a + a OP E ⇒ a + a + a + a + E ⇒ a + a + a + a +a
31
예 4. 7 수식 a + a - a. a / a 와 같이 사칙 연산을 하는 문법 G = ({E, OP}, {a, +, -,
예 4.7 수식 a + a - a * a / a 와 같이 사칙 연산을 하는 문법 G = ({E, OP}, {a, +, -, *, /}, P, E)를 구성해 보자. 이 수식에서 보듯이 터미널 심볼은 a와 연산자 +, -, *, / 이다. E ⇒ E OP E ⇒*E OP E OP E OP E OP E ⇒* a + a – a * a / a 다음과 같은 생성 규칙을 구성할 수 있다. P : E → E OP E E → a OP → + OP → - OP → * OP → /
32
이 생성 규칙에 의하여 아래와 같이 유도할 수 있다. 밑줄 친 넌터미널 심볼이 대치된다.
E ⇒ E OP E ⇒ E OP E OP E ⇒ E OP E OP E OP E ⇒ E OP E OP E OP E OP E ⇒ a OP E OP E OP E OP E ⇒ a + E OP E OP E OP E ⇒ a + a OP E OP E OP E ⇒ a + a - E OP E OP E ⇒ a + a - a OP E OP E ⇒ a + a - a * E OP E ⇒ a + a - a * a OP E ⇒ a + a - a * a / E ⇒ a + a - a * a / a
33
정의 4.6 문맥-자유 문법(CFG:Context-Free Grammar)은 CFG = (VN, VT, P, S)와 같이 구성한다.
VT 은 터미널 심볼의 유한 집합으로 VN∩VT =∅, VN ∪VT = V 이다 V 는 알파벳 집합이다. P 는 생성규칙의 유한 집합으로 아래의 형식을 가진다 A→ α, (A∈VN, α ∈V *, |A|=1 이고 |A|≤|α|) S 는 시작 심볼로서 S ∈VN 이다.
34
예 4. 8 문맥-자유 문법의 정의에 따라 괄호와 음수를 포함하는 산술 연산 수식을 생성하는 문법을 구성해 보자
예 4.8 문맥-자유 문법의 정의에 따라 괄호와 음수를 포함하는 산술 연산 수식을 생성하는 문법을 구성해 보자. 연산에 사용할 연산자 터미널 심볼은 VT = {a,+,-,*,/,(,)}이며, 넌터미널 심볼은 VN = {E, OP}이다. 그러므로 문맥-자유 문법 G6 = ({E, OP}, {a,+,-,*,/,(,)}, P, E)의 생성 규칙은 아래와 같다. P : E → E OP E E → (E ) E → -E E → a OP → + OP → - OP → * OP → /
35
실습 4. 5 문맥-자유 문법 G = ({E, OP}, {a,+,-,
실습 4.5 문맥-자유 문법 G = ({E, OP}, {a,+,-,*,/,(,)}, P, E)에서 아래의 각각을 생성하는 유도 과정을 보이시오. P : E → E OP E |(E )|-E | a OP → +|-|*|/ (a) a * a * a (b) a -(-a) - a (c) a + a * a (d) a * a - a (e) a - a / (a +a)
36
BNF(Backus-Naur Form)
<S> ::= a <S> b | ε
37
4.2.4 유도 트리 문맥-자유 문법 CFG = (VN, VT, P, S) 이고, ω∈VT* 일 때 유도 트리는 다음과 같이 그린다. 각 노드는 알파벳 V(VN∪VT)의 모든 심볼이다. 루트 노드는 시작 심볼 S 이다. N∈VN 이면, N 노드에는 서브 트리가 적어도 하나는 있다. N →N1N2 ... Nn ∈ P 이면, N 노드를 루트로 하고 N1, N2, ..., Nn를 N 노드의 서브 트리로 한다. 서브트리는 가장 왼쪽부터 N1, N2, ..., Nn 의 순서로 구성한다.
38
S N N Nn 그림 4.4 유도 트리 구성하기
39
예 4.9 아래의 문맥-자유 문법 G8 이 있다. G8 = ({E, OP }, {a,+,-,*,/,(,)}, P, E ) P : E → E OP E |(E )|-E | a OP → +|-|*|/
40
E ⇒ E OP E a * E OP E + 그림 4.5 산술수식 a + a * a 의 유도 트리
41
우단 유도와 좌단유도 아래는 우단 유도 과정이다. 아래는 좌단 유도 과정이다.
E ⇒ E OP E ⇒ E OP E OP E ⇒ E OP E OP a ⇒ E OP E * a ⇒ E OP a * a ⇒ E + a * a ⇒ a + a * a 아래는 좌단 유도 과정이다. E ⇒ E OP E ⇒ E OP E OP E ⇒ a OP E OP E ⇒ a +E OP E ⇒ a + a OP E ⇒ a + a * E ⇒ a + a * a
42
4.3 문법의 불명확성 이와 같이 문맥-자유 문법에서 어느 스트링에 대하여 여러 개의 유도 트리를 만들 수 있으면 그 문법을 불명확하다고 한다. 예를 들어 그림 4.5의 유도 트리는 수식 a + a * a를 a + (a * a)와 같은 의미로 유도한 트리이다.
43
4.3.1 불명확한 문법을 명확한 문법으로 재구성하기 아래의 산술 연산 수식에 대한 문법을 살펴보자.
G8 = ({E }, {+, *, (, ), a}, P, E ) P : E → E +E E → E * E E → (E ) E → a
44
재구성한 문법 G8' = ({E', T, F }, {+, *, (, ), a}, P', E' ) P' : E' → E' +T
T → T * F T → F F → (E' ) F → a
45
E' T + T * F F a 그림 4.7 스트링 a + a * a 를 재구성한 명확한 문법(G8' )으로 유도한 유도트리
46
실습 4.6 아래와 같은 G8' 문법에서 유도되는 트리는 오직 하나만 존재한다는 것과 이 문법이 명확한 문법이라는 것을 증명하시오.
G8' = ({E', T, F }, {+, *, (, ), a}, P', E' ) P' : E' → E' +T E' → T T → T * F T → F F → (E' ) F → a
47
실습 4.7 아래 문법 G9에서 스트링 a + a + a를 좌단 유도와 우단 유도 과정을 보이고 각 경우의 유도 트리를 그리시오. 또한 유도 트리에서 연산자 우선순위를 비교하시오. 이때 연산자 결합법칙을 비교한다. G = ({E }, {+, *, (, ), id}, P, E ) P : E → E +E E → E *E E → (E ) E → id
48
실습 4. 8 문법 G9에서 스트링 a + a. a를 유도하는 과정에서 E + E 를 먼저 선택하는 경우와 E
실습 4.8 문법 G9에서 스트링 a + a * a를 유도하는 과정에서 E + E 를 먼저 선택하는 경우와 E * E 를 먼저 선택하는 경우의 유도 트리를 그리시오. 그리고 연산자 우선순위를 비교하시오. G9 = ({E }, {+, *, (, ), id}, P, E ) P : E → E +E E → E * E E → (E ) E → id
49
4.3.2 불명확한 if 문 구조 연산 수식에 대한 문법 뿐 만 아니라, 조건 문장에서도 불명확성을 발견할 수 있다.
G10 = ({Stmt, Ifstmt, CondEp, Compstmt, Assignstmt },{if, else}, P, Stmt ) P : Stmt → Compstmt Stmt → Assignstmt Stmt → Ifstmt Ifstmt → if CondEp Stmt Ifstmt → if CondEp Stmt else Stmt
50
if E1 S1 else if E2 S2 else S3 의 유도 트리
Stmt if CondEp else E1 S1 E2 S2 S3 그림 4.10 문법 G10에서 유도한 조건문 if E1 S1 else if E2 S2 else S3 의 유도 트리
51
그림 4.11 조건문 if E1 if E2 S1 else S2 에 대한 두 개의 유도 트리
stmt if CondEp else E2 S1 S2 E1 stmt if CondEp else S2 S1 E1 E2 그림 4.11 조건문 if E1 if E2 S1 else S2 에 대한 두 개의 유도 트리
52
변환된 if 문의 문법 G9 = ({Stmt, Ifstmt, CondEp, Matched_Stmt, Unmatched_Stmt}, {if, else}, P, Stmt ) P : Stmt → Ifstmt Ifstmt → Matched_Stmt Ifstmt → Unmatched_Stmt Matched_Stmt → if CondEp Matched_Stmt else Matched_Stmt Matched_Stmt → OtherStmt Unmatched_Stmt → if CondEp Ifstmt Unmatched_Stmt → if CondEp Matched_Stmt else Unmatched_Stmt
53
그림 4.12 블명확성을 제거한 if 문의 유도트리 Stmt Ifstmt Unmatched_Stmt if CondEp Stmt
if CondEp Matched_stmt else Mached_Stmt OtherStmt OtherStmt 그림 4.12 블명확성을 제거한 if 문의 유도트리
54
4.4 푸쉬다운 기계와 번역기 푸쉬다운 기계는 문맥-자유 문법을 인식한다.
55
4.4.1 푸쉬다운 기계 정의 4.7 입력 심볼 T에 대한 푸쉬다운 기계(M)는 M=(S, T, z , q, s0, Q, F)와 같이 7 개의 요소로 구성되는 시스템이다. 여기에서 각 요소는 아래와 같다. S: 상태의 유한 집합(빈상태는 없음) T: 입력되는 알파벳의 유한 집합 z: 스택 알파벳의 유한 집합 q: 현재의 상태에서 입력된 새 알파벳에 따라 다른 상태로 전이하는 상태 전이 함수, S×(T∪{λ})×z →S×z*의 부분집합 Q ∈z : 스택의 시작 심볼 s0: 시작 상태로, s0∈S F : 수락 상태의 유한 집합으로, F⊆S
56
# 푸쉬다운 기계 구성과 전이함수 테이블 X2 X1 ai ai+1 … an ↲ 푸쉬다운기계 읽기헤드
입력 스트링 전이함수 (테이블) ai ai+1 … an ↲ # X1 X2 읽기헤드 s (상태) 입력 심볼 a1 a2 ... an ↲ 스택 심볼 X 내용 # 그림 4.13 스택을 사용하는 푸쉬다운 기계 구성과 전이함수 테이블
57
그림 4.14는 아래 문법의 푸시다운 기계의 동작을 테이블로 나타낸 예이다.
S → ASB S → ε A → a B → b s1 a b ↲ X s1, 푸시(X) s2, 팝 거부 # 수락 s2 a b ↲ X 거부 s2, 팝 # 수락 그림 4.14 푸쉬다운 기계의 상태전이 테이블 예
58
그림 4.14의 상태 전이 테이블을 이용하여 입력 스트링 aabb을 인식
____________________________________________ 스택 입력 액션 (# aabb↲) (s1, 푸시(X)) (#X abb↲) (s1, 푸시(X)) (#XX bb↲) (s2, 팝) (#X b↲) (s12, 팝) (# ↲) (수락)
59
실습 4. 9 수식에서는 왼쪽 괄호의 수와 오른쪽 괄호의 수가 같도록 한다. 즉, (a-b-c). ((d/4
s1 ( ) ↲ X s1, 푸시(X) s1, 팝 거부 # 수락
60
4.4.2 언어의 등급과 인식 기계 문 법 언 어 인식기 무제한 문법(타입 0) 반복 나열 집합 튜링 기계
언 어 인식기 무제한 문법(타입 0) 반복 나열 집합 튜링 기계 문맥-민감 문법(타입 1) 문맥-민감 언어 선형 기계 문맥-자유 문법(타입 2) 문맥-자유 언어 푸쉬다운 기계 정규 문법(타입 3) 정규 언어 유한 상태 기계
61
제 4 장 끝
Similar presentations