제  2 장  어휘 분석

내용 어휘 분석을 구현하기 위한 기초 이론과 배경 토큰 속성, 식별 번호와 해당하는 값 심볼 테이블과 상수 테이블 정규 수식, 유한 오토마타, 형식 언어, 오토마타 이론

2.1 형식 언어 형식 언어는 언어의 구조와 특성을 수학 표현             A boy is a girl.

2.1.1 언어를 표현하는 용어 정의 정의 2.1 집합이란? A= {학교, 집, 산, 강} B={school, house, mountain, river}

정의 2.2 알파벳이란? T1 = {ㄱ,ㄴ,ㄷ,...,ㅎ,ㅏ,ㅑ, … ,ㅡ,ㅣ} T2 = {A,B,C, … ,Z } 한글 자음과 모음 기호의 유한 집합 T1 = {ㄱ,ㄴ,ㄷ,...,ㅎ,ㅏ,ㅑ, … ,ㅡ,ㅣ} 영어 자음의 유한 집합 T2 = {A,B,C, … ,Z }

정의 2.3 스트링이란? "abc“, "cba“ "a", "aa", "aaa", "aab“

정의 2.4 스트링의 길이? |0| 혹은 |1|는 길이 1 |01|은 길이 2 |1010011|은 길이 7

정의 2.5 언어란? 알파벳 T의 원소로 만들어지는 언어 L은 T*의 부분집합으로 L ⊆ T* T*는 알파벳 T의 심볼로 만들어지는 스트링의 모든 집합으로 빈스트링도 포함한다. T+는 알파벳 T의 심볼로 만들어지는 스트링의 모든 집합에서 빈스트링은 포함하지 않는다.

예 2. 1 0과 1을 원소로 가지는 알파벳, T = {0, 1}로 몇 개의 언어를 만들어 보자                    0 1 01 10 00

예 2.3 빈스트링을 포함하는 언어의 무한 집합을 아래와 같이 수학적이지 않고 자연 언어로 기술할 수 있다. 수학적으로 표현한 {ε, 0011, 111100, ...} 는 “0과 1로 구성되지만 0이 짝수 개, 1 이 짝수 개 있는 스트링의 집합” 수학적으로 표현한 {ε, 11100, 001110, ...}는 “0과 1로 구성되고 1이 홀수 개 있는 스트링의 집합”

예 2.4 영어 문자의 집합 L = { A, B,…,Z, a, b, .., z }, 수의 집합 D = {0, 1, …, 9}라 하자. 이 때 아래와 같은 관계가 성립한다. (1) L∪D 은 영어 문자와 수로 구성되는 모든 스트링의 집합이다. (2) L․D 는 영어 문자 뒤에 반드시 숫자가 붙는 스트링이다. (3) L*  는 빈스트링 ε을 포함하는 모든 문자 스트링의 집합이다. (4) L+ 는 반드시 하나 이상의 숫자로 구성되는 모든 스트링의 집합이다(빈스트링은 없다) (5) L(L∪D) 는 맨 앞에는 반드시 문자로 시작하고, 그 뒤에는 문자와 숫자가 섞여서 구성되는 모든 스트링의 집합이다.

2.1.2 정규 수식 (1) 결합 결합 연산은 ‘+’ 로 표기 공집합이 있는 언어의 결합도 언어(L = L + { })

(2) 접속 두 언어의 접속 연산은 한 언어에 있는 스트링을 다른 언어에 있는 스트링과 결합하여 새로운 언어를 구성한다.     ∀u, v ∈ T*, uv ∈ T* 이며, |uv| = |u| + |v|이다. 또한, uε= u = εu 이다. 그러므로 u = a1a2a3...an,  v = b1b2b3...bm 이면,  u․v = a1a2a3...anb1b2b3...bm 아래는 접속 연산의 예           {a} ․ {b} = {ab}            {a} ․ { } = {a}

(3) 반복              L0 = {ε}                Ln = LLn-1, n ≥ 1 주의할 것은 ∅* = {ε}

L* 와 L+ 연산 U U L L L* = L0 + L1 + L2 + L3 + L4 + L5 + ......           = L0 ∪ L1 ∪ L2 ∪...∪ Ln ∪… =      L+ = L1 ∪ L2 ∪...∪ Ln ∪…      = L* - L0          i L U ¥ = i L U ¥ = 1

예 2.5 L 이 언어이면 반복 연산 L0, L1, L2 는 아래와 같이 계산한다.

예 2.6 정규 수식 (a*b)1와 (a*b)2은 아래와 같이 스트링을 생성한다.               (a0b)1 는 b               (a1b)1 는 ab               (a2b)1 는 aab               (a3b)1 는 aaab .... (a*b)1 는 εaaab

예 2. 7 정규 수식 (a +b). 에서 만들어지는 스트링을 살펴보자. 이 정규수식은 {a, b} 예 2.7 정규 수식 (a +b)*에서 만들어지는 스트링을 살펴보자! 이 정규수식은 {a, b}* 와 같이 집합으로 표현할 수 있다. 그러므로 L = {a, b}라 하면 L*를 구하는 것과 같다.       L* = {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, ....}

예 2. 8 정규 수식 a ․ ( a +b). ․ b에서 만들어지는 스트링을 살펴보자. 이 정규수식은 L = {a}{a,b} 예 2.8 정규 수식 a ․ ( a +b)* ․ b에서 만들어지는 스트링을 살펴보자! 이 정규수식은 L = {a}{a,b}*{b}와 같이 집합으로 표현할 수 있다.      L = {a}{a,b}*{b}        = {a}{ε,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,aaaa,....}{b}        = {ab, aab, abb, aaab, aabb, abab, abbb, ...}

실습 2.1 어떤 언어를 아래의 각 정규 수식으로 표현할 때, 생성할 수 있는 스트링을 보이시오. 1. (0 (1 +0))*1       2. (0 +1)* ․ (0 +1)       3. (0*1*)*

실습 2.2 아래 기술한 각 언어에 대하여 정규수식을 기술하시오.        "0과 1로 이루어진 스트링으로 1이 연속으로 세 개 있다(1 이 세 개 씩 여러번 있을 수 있다)“

실습 2.3 아래 기술한 각 언어에 대하여 정규수식을 기술하시오. “a와 b로 구성되며 a 가 반드시 세 개만 있는 스트링”

예 2.9 {A, B,…, Z, a, b, ..,z }는 영어의 알파벳 집합이고, {0, 1, 2, …, 9 }는 숫자의 집합이면 다음 정규 수식의 표현을 살펴보자!     {A, B,…, Z, a, b, ..,z }({A, B,…, Z, a, b, ..,z }+{0, 1, 2, …, 9 })*     KNU, Knu, K007, WorldCup2006, T01, Uni921, sky 011

정의 2.6 정규 수식이 긴 경우에 수식에 이름을 부여하는 것이 정규 정의 이다. letter = {A, B,…, Z, a, b, ..,z } digit = {0, 1, 2, …, 9 } letter(letter + digit)*    {A, B,…, Z, a, b, ..,z }({A, B,…, Z, a, b, ..,z } +{0, 1, 2, …, 9 })*

2.1.3 유한 상태 기계

2.1.3.1 유한 상태 기계의 정의 정의 2.7 알파벳 T에 대한 유한 상태 기계(M)는 M=(S, T, q, s0, F)와 같이 다섯 개의 요소로 구성되는 시스템이다. 여기에서 각 요소는 아래와 같다.          S: 상태의 유한 집합(빈상태는 없음)          T: 입력되는 알파벳의 유한 집합          q: 현재의 상태에서 입력된 새 알파벳에 따라 다른 상태로 전이하 는 상태 전이 함수,               q : S×T→ 2S          s0: 시작 상태로, s0∈S          F: 수락 상태의 유한 집합으로, F⊆S

(a) 시작상태 (b) 상태전이 (c) 상태 (d) 수락상태 2.1.3.2 상태 전이 다이어그램  (a) 시작상태       (b) 상태전이      (c) 상태    (d) 수락상태 그림 2.1 상태 다이어그램을 구성하는 기본 요소

간단한 유한 상태 기계 예 그림 2.2 는 알파벳이 {0, 1}인 경우에 입력으로 0이나 1이 들어오는 경우의 유한 상태기계의 동작이다. “0과 1로 구성되며 1이 반드시 짝수 개 있는 모든 스트링” 만 수락 스트링 집합은 {ε, 011, 001100, 10111, 1110111} 그림 2.2 간단한 유한 상태 기계의 예

실습 2.5 입력 알파벳이 {0, 1} 인 경우에 아래의 언어에 대한 유한 상태 기계를 상태 전이 다이어그램으로 나타내시오.     "0과 1로 이루어진 스트링에서 0이 반드시 홀수 개만 있는 스트링"

실습 2.6 입력 알파벳이 {0, 1} 인 경우에 “0과 1로 이루어진 스트링에서 1이 반드시 짝수 개 있는 스트링” 에 대한 유한 상태 기계를 그림 2.2와 다른 상태 전이 다이어그램으로 나타내시오.

전이 다이어그램으로 유한 상태 기계를 나타내는 다른 예 전이 다이어그램으로 유한 상태 기계를 나타내는 다른 예 그림 2.5는 입력 알파벳은 {0, 1}, 시작 상태는 A, 수락 상태는 C 이다. 수락 상태로 가려면 시작과 끝이 반드시 0인 스트링이어야 한다. 수락 가능한 스트링의 예     010, 0100, 01010, 01110, 010110 그림 2.5 0과 1로 이루어진 스트링으로 반드시 0으로 시작하고 반드시 0으로 끝나는 스트링을 수락하는 상태 전이 다이어그램

정의 2.8 어떤 유한 상태 기계가 임의의 입력 스트링을 수락하면 그 유한 상태 기계는 그 스트링을 생성하는 한 언어를 정의(인식)한다고 한다.

실습 2.7 입력 알파벳이 {0, 1} 인 경우에 아래의 언어에 대한 유한 상태 기계를 상태 전이 다이어그램으로  나타내시오.        "스트링이 0과 1로 이루어지며 1 세 개가 연속으로 나타나는 스트 링(1 세 개가 연속으로 여러 번 나올 수 있다)"

실습 2.8 입력 알파벳이 {0, 1} 인 경우에 아래의 언어에 대한 유한 상태 기계를 상태 전이 다이어그램으로  나타내시오.     “0과 1로 이루어지며 1이 반드시 세 개만 있는 스트링”

2.1.3.3 상태전이 테이블 유한 상태 기계를 테이블로 나타내 보자! 어떤 상태에서 입력 심볼 하나에 대하여 이동할 상태가 반드시 하나만 존재하는 경우를 결정적이라 한다. 테이블을 살펴보면 유한 상태 기계가 결정적이라는 것을 알 수 있다. 그림 2.8 그림 2.2와 그림 2.5에 있는 상태 전이 다이어그램의 상태 전이 테이블   1 A B D C C*   1 A* A B

실습 2.9 실습 2.5의 상태 전이 다이어그램을 테이블로 나타내시오.

실습 2.10 실습 2.6의 상태 전이 다이어그램을 테이블로 나타내시오.

실습 2.11 실습 2.7의 상태 전이 다이어그램을 테이블로 나타내시오.

실습 2.12 실습 2.8의 상태 전이 다이어그램을 테이블로 나타내시오.

2.1.3.4 결정형 유한 상태 기계 정의 2.9 결정형 유한 상태 기계는 어떤 상태에서 입력 심볼에 대하여 다른 상태로의 전이가 반드시 한개만 존재하는 유한 상태 기계이다.

2.2 토큰 어휘 분석 단계에서는 하나씩 읽은 문자를 속성별로 분리하여 토큰이라는 하나의 단어를 구성

2.2.1 예약어 main, function, for, while, if, array, int, float, do, case, switch, ...

아래 C 프로그램에서 예약어를 분리해 보자. #include <stdio.h> main() {           {            int x, y, z, loop;   /* 정수형 변수 x, y, z 를 선언 */            x = 10;            y = 20;            z = 40;            x = x + y * z + 5;            if ( x > x + y) printf ("%d",x);            y = (x + y) - (x - y) * 34;            printf ("%d \n", x);  /*  y 값 출력   */            x = 190;            z = y + 1;            for (loop = 1; loop < 100; loop++)           y = y + z;           }

분리한 예약어 include, stdio.h, main, int, if, printf, for

2.2.2 식별자 프로그램에서 어떤 값 float f, g, h=3.14; int knu[][]; function f1( ); int a, b, c;           float f, g, h=3.14;          int knu[][];          function f1(  );          vector::vector()           a = b + c;

2.2.3 연산자 산술연산자, 문자연산자, 관계연산자, 논리연산자 등 산술연산자: +, -, *, /, % 등 관계연산자: ==, <=, >=,  !=,  >,  < 등 논리연산자: ||(or), &&(and), !(not) 등

2.2.4 숫자 상수 정수, 실수 등 컴퓨터 내부에서 의미있는 수로 사용되는 수 1534, -35, 0, 0.64E4, 13.16, -3.4 등

2.2.5 문자 상수 단일 문자(‘ ‘)나 따옴표(“ ”) 안의 문자 스트링 단일 문자: 'KNU‘ 등 단일 문자(‘ ‘)나  따옴표(“ ”) 안의 문자 스트링 단일 문자: 'KNU‘ 등 문자열(스트링)"This is the first program.“, "Pass" 등

예 2.10에서 토큰을 분리하여 보자! #include <stdio.h> main() {           {            int x, y, z, loop;   /* 정수형 변수 x, y, z 를 선언 */            x = 10;            y = 20;            z = 40;            x = x + y * z + 5;            if ( x > x + y) printf ("%d",x);            y = (x + y) - (x - y) * 34;            printf ("%d \n", x);  /*  y 값 출력   */            x = 190;            z = y + 1;            for (loop = 1; loop < 100; loop++)           y = y + z;           }

분리한 토큰 (1) 예약어: include, stdio.h, main, int, if, printf, for (2) 식별자: x, y, z, loop (3) 연산자: +, -, *, >, ++ (4) 숫자형 상수: 1, 10, 20, 40, 5, 34, 190 (5) 문자형 상수: "%d", "%d \n“ (6) 특수 문자: <, >, {, 콤마(,), ;, (, ), } (7) 할당 기호: = (8) 주석: /* 정수형 변수 x, y, z 를 선언 */,  /*  y 값 출력  */

2.3 심볼 테이블 식별자에 대해서는 심볼 테이블을 구성한다. 원시 프로그램에서 어떤 식별자는 여러 번 사용되더라도 심볼 테이블에는 한번 씩만 저장한다.

실습 2.13 만약 for (loop = 1; loop >= x + y; loop++)  y = y + z; 의 문장에서 loop >= 부분이나  loop++부분을 loop >  = 와 loop  +  + 처럼 >, = 사이와  loop, +, + 사이에 빈칸을 넣으면 어휘 분석기는 토큰을 어떻게  생성하는지 설명하시오. 또, 이유를 설명하시오.

2.3 유한 상태 기계의 구현 a0 a1 a2 ... ai ai+1 ai+2 ... an 그림 2.9 유한 상태 기계의 구현 입력 원소 읽기 헤드 저장 장치 유한 상태 기계

유한 상태 기계의 구현 예 function FSM( ) { int State = 100; SymbolCh = 100;         {           int State = 100;  SymbolCh = 100;           int MapFn[StateNo][SymbolCh];  /*  상태 전이 테이블, 상태수, 심볼문자  */           int inchar, startSt, state;         /* 입력 심볼, 시작 상태, 다음 상태  */           scanf(&inchar);           state = startSt;           while ( !eof()) {                  state = MapFn[state][inchar];    /* 상태 전이 테이블의 비교  */                  scanf(&inchar);                  }          }

2.3.1 어휘 분석을 위한 유한 상태 기계 정규 수식 정규 정의 letter(letter + digit)* {A, B,…, Z, a, b, ..,z }({A, B,…, Z, a, b, ..,z } +{0, 1, 2, …, 9 })* 정규 정의 letter = {A, B,…, Z, a, b, ..,z}로, digit = {0, 1, 2, …, 9}로 정의                           letter(letter + digit)*

이 정규 정의에 대한 유한 상태 기계 아래는 식별자 KNU, K007, WorldCup2006를 인식할 수 있다. 1 1 letter 혹은 digit letter

그림 2.10 식별자와 자연수를 인식하는 유한 상태 기계 그림 2.10의 유한 상태 기계는 자연수 123나 654를 인식할 수 있다. 그러나 -912 와 같은 수는 인식할 수 없다. 2 1 letter letter, digit digit 그림 2.10 식별자와 자연수를 인식하는 유한 상태 기계

예 2.11 부호와 지수가 없으며 소수점으로 시작하고 소수 이하에만 수가 있는 실수형 상수를 인식하는 유한 상태 기계를 구성하자.

실습 2.14 부호와 지수 부분이 없고 소수점 앞과 뒤에 수가 있는 실수형 상수를 인식하는 유한 상태 기계를 구성하시오.            0.1     35.6        36.12305

실습 2.15 자연수 앞에 +/- 부호가 잇을 수도 있고, 없을 수도 있는 수를 인식하는 유한 상태 기계를 구성하시오.            517         +8783         -120

모든 실수형 상수를 인식하는 유한 상태 그림 2.14 +/- 부호가 없는 실수형 상수를 인식하는 유한 상태 기계

관계 연산자를 인식하는 유한상태기계

예약어를 인식하는 유한 상태 기계

2.4.2 유한 상태 기계의 동작 구현

+/- 부호와 지수가 없는 실수형 상수를 인식하는 유한상태기계 구현 예 function FSM_of_Realnumber( ) { char inchar; int state; state = 0;                           while (inchar == !eof( )) { switch(state)      {      case 0:     /* 시작 상태 0  */             { if (inchar ∈ {0,1,2,3,4,5,6,7,8,9}) {                             scanf(&inchar);                             state = 1;                            }                            else printf("error");      /*  다른 문자 혹은 에러 */             }

case 1:   /* 상태 1  */             {                 if (inchar ∈ {0,1,2,3,4,5,6,7,8,9}) {                             scanf(&inchar);                             state = 1 ;                            }                             elseif (inchar == " ․ ") {                                       scanf(&inchar);                                       state = 2;                                      }                            else printf("error");      /*  다른 문자 혹은 에러 */             } case 2:   /* 상태 2  */                             state = 3;

case 3:  /* 상태 3  */             {                 if (inchar ∈ {0,1,2,3,4,5,6,7,8,9}) {                             scanf(&inchar);                             state = 3 ;                            }                            else printf("error");      /*  다른 문자 혹은 에러 */             }    } }     if (inchar == eof( ) && state == 3)  printf("accept")     /*  수락 상태  */                    else printf("error");

실습 2.16 +/- 부호가 있는 일반 형식의 실수형 상수를 인식하는 유한 상태 기계를 간단하게 구현하시오.

자연수를 인식하는 유한 상태 기계에 액션을 추가

제 2 장 끝