제 4 장 구문 분석
4.1 구문 분석 개념 그림 4.1 구문 분석기의 위치와 기능 어휘 분석기 구문 중간 코드 심볼 테이블 원시프로그램 토큰 파스트리 중간 코드 심볼 테이블 그림 4.1 구문 분석기의 위치와 기능
유도과정과 파스 트리 파스트리는 프로그램의 각 문장이 문법에서 만들어지는 언어인지를 검사하는 유도 과정이다. 이러한 유도 과정을 파스 트리라 한다. 문장 구조가 올바른지 아닌지를 알기 위해 입력 토큰 스트림과 문법을 비교한다.
신택스 트리와 중간코드 구문 분석에 의하여 생성되는 것은 중간 코드의 신택스 트리 중간 코드는 기계어 인스트럭션을 만들 수 있는 가장 작은 동작으로 컴퓨터의 주소로 되어 있는 피연산자를 포함한다. = x + * y 1.873 - 78 a 그림 4.2 x = (a - 78) * 1.873 + y; 의 신택스 트리
4.2 문법과 언어 컴파일러의 구문 분석 단계를 이해하기 위하여 형식 언어의 이론과 개념을 살펴보자!
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 이다.
예 4.1 문법 G1 = ({S, T}, {t, r}, P, S)을 살펴보자. 이 문법의 각 원소는 아래와 같다. 4. 생성 규칙 P : S →tTS S →t T →SrT T →rt T →SS
유도 정의 4.2 유도는 생성규칙에서 문장을 생성하는 과정으로 시작 심볼에서 생성규칙의 정의 기호(→)의 오른쪽에 있는 심볼들로 대치한다. S는 시작 넌터미널, α,β,γ는 터미널이나 넌터미널 스트링, x는 터미널 스트링이면 유도(⇒)는 아래와 같이 쓴다. S ⇒ α ⇒ β ⇒ γ ⇒ .... ⇒ x
예 아래의 문법이 있으면 스트링 baaa을 S ⇒ Sa ⇒ Saa ⇒ Saaa ⇒ baaa와 같이 유도한다. P : S → S a S → b S → ε 스트링 baaa을 S ⇒ Sa ⇒ Saa ⇒ Saaa ⇒ baaa와 같이 유도한다.
정의 4.3 언어는 시작 넌터미널 심볼 S로 시작하는 문법 G 에서 ⇒+를 적용하여 문법 G에서 생성되어지는 언어 L(G)로 표기한다. 언어 L(G)안에 있는 스트링은 아래와 같이 G의 터미널 심볼만으로 구성된다. L(G) = {ω| S ⇒+ω, ω∈VT*}
예 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) ......
예 4.3 문법 G3 = ({S}, {0,1}, P, S) 이고, 생성 규칙이 아래와 같을 때 이 문법에서 언어를 유도해 보자. P : S → 0S0 | 1S1 | 0 | 1 이 문법에서 한 언어를 유도하면 아래와 같다. S ⇒ 0S0 ⇒ 00S00 ⇒ 001S100 ⇒ 0010100
문장과 문장형식 정의 4.4 S ⇒* α이고 α ∈V * 이면 α를 문법 G 의 문장형식이라 하고, S ⇒* α이고 α ∈VT* 이면 α는 문법 G 의 문장이라 한다.
예 4.4 문법 G4 = ({S, A, B}, {0, 1, ε}, P, S) 이고, 생성 규칙이 아래와 같을 때 문장 0110를 유도하는 과정에서 문장 형식을 알아보자. P : S →0A|1B|ε A →1S B →0S
이 문법에서 0110를 유도하는 과정은 아래와 같다. S ⇒0A (생성규칙 S →0A) ⇒01S (생성규칙 A →1S) ⇒011B (생성규칙 S →1B) ⇒0110S (생성규칙 B →0S) ⇒0110 (생성규칙 S →ε) 유도 과정에서 생성되는 S, 0A, 01S, 011B, 0110S는 문장형식이고, 터미널 스트링만으로 구성된 0110 은 문장이다.
실습 4. 1 생성 규칙이 아래와 같은 문법 G5 = ({S}, {0,1}, P, S)가 있다 P : S → 0S0 S → 1S1 S → 0 S → 1
예 4.5 아래 생성 규칙이 있는 문법 G6 = ({S, A, B}, {a, b, ε}, P, S)에서 문장 aabb를 유도해 보자. P : S →ASB S →ε A →a B →b
이 문법은 문장 aabb를 유도할 수 있다. S ⇒ ASB (생성규칙 S →ASB) ⇒ AASBB (생성규칙 S →ASB) ⇒ AaSBB (생성규칙 A →a) ⇒ AaBb (생성규칙 S →ε) ⇒ Aabb (생성규칙 B →b) ⇒ aabb (생성규칙 A →a)
실습 4.2 문법 G = ({S, A, B}, {1,0}, P, S) 이고, 생성 규칙이 아래와 같을 때 이 문법에서 생성할 수 있는 여러 개의 유도과정을 보이시오. P : S → 1SA|BA A → 10 B → 0A 어떤 스트링을 생성하는데 두 개 이상 여러 개의 유도가 있을 수 있다는 것을 알 수 있다.
4.2.2 문법의 분류 무제한 문법 문맥-민감 문법 문맥-자유 문법 우-선형 문법 그림 4.3 문법의 분류 무제한 문법
촘스키의 문법 분류 타입 0 문법: 무제한 문법은 타입 0 문법이라고도 하며 생성규칙에 제한이 없는 문법이다. 각 생성규칙은 화살표 → 의 양쪽(왼쪽과 오른쪽)에 임의의 터미널과 넌터미널 스트링으로 구성된다. 단 ε 는 화살표의 오른쪽에만 올 수 있다. AaB → bA|ε
타입 1 문법: 문맥-민감 문법은 타입 1 문법이라고도 하며 아래와 같은 생성규칙으로 구성된다 타입 1 문법: 문맥-민감 문법은 타입 1 문법이라고도 하며 아래와 같은 생성규칙으로 구성된다. 문맥-민감 문법은 컴파일러에서 실제로는 사용할 수 없다. |α|≤|β|로 β의 길이가 α의 길이보다 더 길다. α → β 1. A → aABCc 2. A → ε 3. aB → ab 4. bB → bb 5. cB → cb 6. bC → ac 7. C → Cc
교재를 수정해야함 A → aABCc 를 A → aABC 로 문맥-민감 문법에서 생성한 언어의 예 A ⇒ aABC ⇒ aaABCBC ⇒ aaBCBC ⇒ aabCBC ⇒ aabCcBC ⇒ aabCcbC ⇒ aabCccbC ⇒ aabCccbCc ⇒ aaacccbCc ⇒ aaacccacc
타입 2 문법: 문맥-자유 문법은 타입 2 문법이라고도 하며, 문맥에 제한되지 않고 자유롭기 때문에 아래와 같은 생성규칙으로 구성된다. A → α, |A|=1, |A|≤| α | 생성한 언어 예 S →aAS S →a A →SbA A →ba A →SS
타입 3 문법: 우-선형 문법은 타입 3 문법이라고도 하며 아래와 같은 생성규칙으로 구성된다. A → aB 또는 A → a
실습 4.3 아래의 문법 생성 규칙에서 촘스키의 분류에 따라 무제한, 문맥-민감, 문맥-자유, 우-선형 문법을 고르시오. 1. aSb → aAbBc 2. A → bB 3. Ab → b 4. b → AB 5. S → aAbc 6. AB → BAC
실습 4. 4 어떤 언어 L(G) = {ε, abc, aabbcc, aaabbbccc, 실습 4.4 어떤 언어 L(G) = {ε, abc, aabbcc, aaabbbccc, ...} = {anbncn}, n≥0는 a뒤에는 b가, b뒤에는 c가 오지만, a, b, c 각각의 갯 수가 반드시 같은 스트링의 집합이다. 이 언어를 생성하는 문맥-민감 언어를 구성해 보자.
4.2.3 문맥-자유 문법과 표현 문맥-자유 문법은 반복 구조로 프로그래밍 언어의 문장이나 구조 조건 문장을 만드는 아래의 규칙을 정규 수식으로 표현할 수 있는지?? 「S1과 S2이 각각 문장이고 E 가 수식이면 "if (E ) S1 else S2;" 는 문장이다」 제한된 방법으로 표현하기 어려운 언어 구조도 문맥-자유 문법으로는 표현하기 쉽다. 정규 수식으로 이러한 조건 문장을 표현하기는 어렵다.
예 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 → +
이 생성 규칙에 의하여 아래와 같이 유도할 수 있다. 밑줄 친 넌터미널 심볼이 대치된다. 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
예 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 → /
이 생성 규칙에 의하여 아래와 같이 유도할 수 있다. 밑줄 친 넌터미널 심볼이 대치된다. 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
정의 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 이다.
예 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 → /
실습 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)
BNF(Backus-Naur Form) <S> ::= a <S> b | ε
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 의 순서로 구성한다.
S N1 N2 ... Nn 그림 4.4 유도 트리 구성하기
예 4.9 아래의 문맥-자유 문법 G8 이 있다. G8 = ({E, OP }, {a,+,-,*,/,(,)}, P, E ) P : E → E OP E |(E )|-E | a OP → +|-|*|/
E ⇒ E OP E a * E OP E + 그림 4.5 산술수식 a + a * a 의 유도 트리
우단 유도와 좌단유도 아래는 우단 유도 과정이다. 아래는 좌단 유도 과정이다. 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
4.3 문법의 불명확성 이와 같이 문맥-자유 문법에서 어느 스트링에 대하여 여러 개의 유도 트리를 만들 수 있으면 그 문법을 불명확하다고 한다. 예를 들어 그림 4.5의 유도 트리는 수식 a + a * a를 a + (a * a)와 같은 의미로 유도한 트리이다.
4.3.1 불명확한 문법을 명확한 문법으로 재구성하기 아래의 산술 연산 수식에 대한 문법을 살펴보자. G8 = ({E }, {+, *, (, ), a}, P, E ) P : E → E +E E → E * E E → (E ) E → a
재구성한 문법 G8' = ({E', T, F }, {+, *, (, ), a}, P', E' ) P' : E' → E' +T T → T * F T → F F → (E' ) F → a
E' T + T * F F a 그림 4.7 스트링 a + a * a 를 재구성한 명확한 문법(G8' )으로 유도한 유도트리
실습 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
실습 4.7 아래 문법 G9에서 스트링 a + a + a를 좌단 유도와 우단 유도 과정을 보이고 각 경우의 유도 트리를 그리시오. 또한 유도 트리에서 연산자 우선순위를 비교하시오. 이때 연산자 결합법칙을 비교한다. G = ({E }, {+, *, (, ), id}, P, E ) P : E → E +E E → E *E E → (E ) E → id
실습 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
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
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 의 유도 트리
그림 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 에 대한 두 개의 유도 트리
변환된 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
그림 4.12 블명확성을 제거한 if 문의 유도트리 Stmt Ifstmt Unmatched_Stmt if CondEp Stmt if CondEp Matched_stmt else Mached_Stmt OtherStmt OtherStmt 그림 4.12 블명확성을 제거한 if 문의 유도트리
4.4 푸쉬다운 기계와 번역기 푸쉬다운 기계는 문맥-자유 문법을 인식한다.
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
# 푸쉬다운 기계 구성과 전이함수 테이블 X2 X1 ai ai+1 … an ↲ 푸쉬다운기계 읽기헤드 입력 스트링 전이함수 (테이블) ai ai+1 … an ↲ # X1 X2 읽기헤드 s (상태) 입력 심볼 a1 a2 ... an ↲ 스택 심볼 X 내용 # 그림 4.13 스택을 사용하는 푸쉬다운 기계 구성과 전이함수 테이블
그림 4.14는 아래 문법의 푸시다운 기계의 동작을 테이블로 나타낸 예이다. S → ASB S → ε A → a B → b s1 a b ↲ X s1, 푸시(X) s2, 팝 거부 # 수락 s2 a b ↲ X 거부 s2, 팝 # 수락 그림 4.14 푸쉬다운 기계의 상태전이 테이블 예
그림 4.14의 상태 전이 테이블을 이용하여 입력 스트링 aabb을 인식 ____________________________________________ 스택 입력 액션 (# aabb↲) (s1, 푸시(X)) (#X abb↲) (s1, 푸시(X)) (#XX bb↲) (s2, 팝) (#X b↲) (s12, 팝) (# ↲) (수락)
실습 4. 9 수식에서는 왼쪽 괄호의 수와 오른쪽 괄호의 수가 같도록 한다. 즉, (a-b-c). ((d/4 s1 ( ) ↲ X s1, 푸시(X) s1, 팝 거부 # 수락
4.4.2 언어의 등급과 인식 기계 문 법 언 어 인식기 무제한 문법(타입 0) 반복 나열 집합 튜링 기계 언 어 인식기 무제한 문법(타입 0) 반복 나열 집합 튜링 기계 문맥-민감 문법(타입 1) 문맥-민감 언어 선형 기계 문맥-자유 문법(타입 2) 문맥-자유 언어 푸쉬다운 기계 정규 문법(타입 3) 정규 언어 유한 상태 기계
제 4 장 끝