Presentation is loading. Please wait.

Presentation is loading. Please wait.

제 4 장 구문 분석.

Similar presentations


Presentation on theme: "제 4 장 구문 분석."— Presentation transcript:

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 장 끝


Download ppt "제 4 장 구문 분석."

Similar presentations


Ads by Google