Formal Grammar of compiler컴파일러에서 형식언어:정의,문법,분류

   

   

   

 

2-1. 형식 언어의 정의

2-2. 형식 언어의 문법 (Formal Grammar)

2-3. 형식 언어의 문법의 분류

 

2-1. 형식언어의 정의

¦  정의

 

¦  몇 개의 수학적 구조와 함께 기호적 스트링

   (Symbolic string)들로 구성

 

¦  어떤 alphabet에서 Symbol들로 구성되는

    string의 집합

 

¦  정의 2.0

¦  Symbol : 언어에 있어서 가장 기본이 되는 요소

예 :   0, 1, ㄱ, A

 

¦  정의 2.1

¦  Alphabet : Symbol들의 유한 집합

 예 :   T₁ = {0, 1} ,     T₂ = {ㄱ,ㄴ,·····,ㅎ,ㅏ,ㅑ,····,ㅡ,ㅣ}

 

¦  정의 2.2

¦  String : Alphabet T에 속하는 Symbol이나 T에 속하는  하나이상의 Symbol 연결

 예 : T = {a, b}일 때, a, b, aa, ab, ba, bb, aaa, ····· 는

      모두 T에서 만들 수 있는 String이다.

 

¦  정의 2.3

¦   String 길이 : String을 이루는 Symbol의 개수

 

 예 :   w = 0110           || = 4

           u = dog            |u| = 3

            = house          || = 5

 

¦  정의 2.4

¦   String 접속(Concatenation) : String의 연속 연결 해 놓은 것

 

¦   u = a₁····· a_n,     = b₁·····b_n

¦   u·u = a₁·····a_nb₁·····b_n,       |u| = |u| + || = n + m

¦   u· u = u  u (교환법칙 성립 안 함)

  예 :  |u| = dog = 3      || = house = 5

             u·u = u = doghouse        |u| = 8

 

¦  정의 2.5

 

¦   empty string : 길이가 0인 string : 문자열이 없는 것

 

¦   e(epsilon), (lambda)로 표현  || = || = 0

 예 : u = u = u ,  u = u,  dog·e·house = doghouse

          l(l+d)^*    ===>    A·e = A

 

¦   aⁿ : a가 n개 연결된 string을 표시

    예 : a⁵ = aaaaa

 

¦   a⁰ : empty String

 

¦   ^R : String의 역순

    예 :  = abc                    ^R = cba

     = ₁u₂····u_n              ^R  = _n···· ₂u₁

 

¦  정의 2.6

 

¦   T^* : empty string을 포함한 T에 속하는 Symbol로 이루어

         질 수 있는 모든 string의 집합

     예 : T = {0, 1}      T^* = {e, 0, 1, 00, 01, 10, 11, 000, ···}

¦   T⁺ : T^* - {e}

     예 : T = {a, b}      T⁺ = {a, b, aa, ab, ba, bb, aaa, aab, ··· }

 

¦  정의 2.7

 

¦   Alphabet T에 대하여 언어 L은 T^*의 부분집합 이다.

    예 :  T = {a, b}

    L¹ = T^* = {e, a, b, ab, ba, ···}

    L² = { a, ba, aba}

    L³ = {a^p | p는 소수(prime number)}

    L⁴ = {aⁿbⁿ | n 1 }

 

¦   정의 2.8

 

¦  언어의 곱 (Product)

 

¦  L·L´ = LL´ = {xy | x Î L, y  L´}  L´L

     예 : L = {a, b}     L´ = { ab, bc, cc}

  LL´ = { a, b} ·{ab, bc, cc} = {aab, abc, acc, bab, bbc, bcc}

¦   정의 2.9

¦  L의 거듭제곱      (Power)

    예 : L = {a, ba, aab}

  L⁰ = {}

  L¹ = {a, ba, aab}

  L² = L·L = {a, ba, aab}·{a, ba, aab}

      = {aa, aba, aaab, baa, baba, baaab, aaba, aabba, aabaab}

^¦     Lⁿ = L·L^n-1

 

2-2.형식언어의 문법(Formal Grammar)

¦  정의 2.12

 

   G = ( V_N, V_T, P, S )

¦  V_N : non-terminal Symbol의 유한집합

¦  V_T : terminal Symbol의 유한집합

_¦     V_N  Ç V_T =            V(Vocabulary) = V_N  V_T

¦   P : 생성규칙의 유한집합

^¦     a    (유도)       V⁺     V^*

_¦      S : start Symbol  Î V_N

 

 ®예제

       V_N = {<sentence>,<subject>,<verb>,<object>,<noun>,<article>}

         V_T = {The, Boy, Girl, Loves, .}

         S = <sentence>

         P :  1. <sentence>  ® <subject><verb><object>.

               2. <subject>  <article><noun>

               3. <object>   <article><noun>

               4. <verb>    Loves

               5. <article>    The

               6. <noun>  Boy | Girl

 

                        derivation(replacement:유도)

        <sentence> => <subject><verb><object>.

                          => <article><noun><verb><object>.

                          => The <noun><verb><object>.

                          => The Boy <verb><object>.

                          => The Boy Loves <object>.

                          => The Boy Loves <article><noun>.

                          => The Boy Loves The <noun>.

                          => The Boy Loves The Girl.

 

¦  정의 2.13

 

¦  derivation(유도) :  한 String에서 생성 규칙을 한 번 적용

    해서 다른 Sting으로 바뀌어진다.

               

¦    => : 한 번 이상 유도                => : 0번 이상 유도

예제 1

       G = ({S, A},{a, b}, P, S)   

       P : S ® aAS     S a

            A SbA    A ba    A SS

 

         i)  S => a

         ii) S => aAS

               => abaa

 

  예제 2

       P : S ® aA | bB |

            A  bS

            B aS

       

         i) S => aA

               => abS

               => ab

 

¦  정의 2.14

¦   sentential form(문장형태) : S => w,   V^*

¦   sentence (문장) :    V_t

     문장 형태 중 nonterminal symbol을 포함하지 않은 것

 

¦  정의 2.15

¦   L(G) = { | S =>  w,   V_t }

    예제 3

    G₁ = ({S}, {a}, P, S)

  P : S ® a | aS

  i) S => a

  ii) S => aS

         => aa

  iii) S => aS

         => aaS

         => aaa

  L(G₁) = { aⁿ | n 1}

 

 

¦  문법 작성

 

¦   특정한 형태의 언어를 생성하는 문법을 만드는 일

 

예제 1

 L₁ = {aⁿbⁿ | n ³ 1}

 i) 같은 수의 terminal symbol을 생성해야 하므로 nonterminal

    symbol이 terminal symbol사이에 내장되어 있어야 한다.

    S  aSb    (embedded 생성규칙)

 

 ii) 최소한의 terminal symbol은 nonterminal symbol을 필요로

    하지 않기 때문에 따로 구분 지어 주어야 한다.

    S  ab

\ S  aSb | ab

                 

 

예제 2

 

 L2 = {0ⁱ1^j | i ¹j,  i, j  1}

•     i > j 일 때, 0이 많은 경우,

      같은 수의 0과 1을 생성하고, 남은 0을 생성을 하면 된다.

        S  0A1

        A  0A1 | 0A | 0

 

•     i < j 일 때, 1이 많은 경우,

      같은 수의 0과 1을 생성하고, 남은 1을 생성을 하면 된다.

        S  0B1

        B  0B1 | B1 | 1

 

     S  0A1 | 0B1

        A  0A1 | 0A | 0

        B  0B1 | B1 | 1

 

같은 언어를 생성하는 문법은 여러 형태가 될 수 있다.

주어진 문법으로부터 생성되는 언어는 유일하지만 주어진 언어를

생성하는 문법은 다양한 형태가 될 수 있다.

2-3. 형식 언어의 문법의 분류

¦   Chomsky 4 type Grammar

¦   생성 규칙의 형태에 따라 구분

 

¦   Type 0(Unrestricted Grammar)

¦  생성 규칙에 어떤 제한도 두지 않는다. (위축형 문법)

 예제 )    bc  ® b

 

¦    Type 1(Context-sensitive Grammar :csg)

¦  오른쪽이 왼쪽보다 같거나 긴 생성규칙

 

¦ |a| ≤  |b|

 예제)      P : A  ® abc      A  aABc

                Bb  BC            CB  cc            bc  c (X)

 

¦  Type 2 (Context-free Grammar:cfg)

¦   왼쪽은 하나의 nonterminal symbol만 가능

^¦                : nonterminal       V^*

예제 )    L(G₂) = {aⁿbaⁿ | n 1}

                G₂ = ({S, C}, {a, b}, P, S),

                P : S  aCa

                C  aCa

                C  b 

 

¦   Type 3(Regular Grammar : rg : 정규문법)

¦  왼쪽에 하나의 nonterminal symbol이 오고, 오른쪽도 최대한

    하나의 nonteminal symbol이거나 terminal symbol로 구성

 

¦  A  tB   A  t   t  V_t   A,B  V_N   (right linear regular grammar)

 

¦  A  Bt    A  t    t  V_t   A,B  V_N    (left linear regular grammar)

예제 )    L(G₃) = {aⁿba^m | n, m 1}

                G₃ =({S,B,C}, {a,b}, P, S),

                P : S  aS         S  aB

                B  bC             C  aC             C  a