자연어처리(NLP; Natural Language Processing) - 구문 분석 (2)

1.3 구문 분석(syntactic analysis)

    구문 분석(syntactic analysis)은 형태소 분석의 결과를 이용해서 주어진 문장이 어떤 구조로 이루어졌는지를 조사합니다. 구문 분석을 위해서는 문장 구조에 관한 지식인 문법(grammar) 지식이 필요합니다. 

 

1) 문법표현: 구(句) 구조문법(phrase structure grammar)

    문법표현에는 다양한 방법이 있지만 여기에서는 언어학자 촘스키(Noam Chomsky)가 제창한 구(句) 구조문법(phrase structure grammar)의 표현 방법을 공부해 봅니다.

    구(句) 구조문법(phrase structure grammar)은 다음의 4가지 요소로 구성됩니다.    

        (1) 바꿔 쓰기 규칙

        (2) 단말 기호

        (3) 비단말 기호

        (4) 시작기호

 

위 요소 중에서 (1)의 바꿔 쓰기 규칙(rewrite rule)이 구 구조문법의 중심 구성요소입니다. (2) ~ (4)의 단말 기호(terminal symbol), 비단말 기호(non-terminal symbol) 및 시작 기호(start symbol)는 바꿔 쓰기 규칙 내에서 나타나는 기호입니다. 바꿔 쓰기 규칙의 간단한 예는 아래 (그림 2)와 같습니다.

 

(그림 2) 바꿔 쓰기 규칙의 예

1)  <S>  ----> <NP>  <VP> 2)  <NP> ----> <ADJ>  <NP> 3)  <NP> ----> <N>  <PAR> 4)  <VP> ----> <ADV>  <VP> 5)  <VP> ----> <V> 6)  <N>  ----> 꽃 7)  <ADJ> ---->  이쁜 8)  <PAR>  ---->  이 9)  <V>  ----> 피다 10) <ADV>  ----> 화려하게

    (그림 2)를 보면 10개의 바꿔 쓰기 규칙의 집합으로 하나의 문법 규칙을 나타내고 있습니다. 각 규칙에서 화살표 왼쪽에 있는 기호가 규칙의 적용에 따라 오른쪽에 있는 기호로 바뀌어 써진 것입니다.

    예를 들면 규칙 1)은 <S>라는 기호가 <NP> <VP>라는 기호로 바뀌어 작성된 것입니다. 여기에서 괄호 <> 안에  들어 있는 기호가 비단말 기호입니다. 비단말 기호는 바꿔 쓰기 규칙을 구성하기 위한 기호이고 다시 쓰기 도중에 나타나는 기호입니다. 바꿔 쓰기 규칙 6)에서는 <N>이라는 비단말 기호가 화살표 왼쪽에 있고, 화살표 오른쪽에는 문장을 구성하는 구체적인 단어인 '꽃'이 있습니다. '꽃'처럼 실제 문장 구성요소인 기호를 단말 기호라고 합니다.

 

** 바꿔 쓰기 규칙을 적용하여 문장을 생성하는 방법

     바꿔 쓰기 규칙을 적용하기 위해서는 바꿔 쓰기를 시작하기 위한 기호를 정해야 하는데, (그림 2)에서의 <S>가 시작 기호입니다. 

    시작 기호 <S>부터 바꿔 쓰기를 하려면, 화살표 왼쪽에 <S>가 나타나는 규칙을 찾아야 합니다. 그러면 규칙 1)이 나타나고, 규칙에 따라 <S>를 두 개의 비단말 기호의 배열인 <NP> <VP>로 바꾸어 씁니다.

 

        <S>   ---->  <NP> <VP>       규칙 1)

 

    그다음 <NP>를 바꾸어 씁니다. 비단말 기호 <NP>의 바꿔 쓰기 규칙 여러 가지 중 규칙 3)을 적용해서 <NP>를 <N> <PAR>로 바꾸어 씁니다.

 

        <NP> <VP>  ---->  <N> <PAR> <VP>     규칙 3)

 

    계속해서 규칙 5)를 적용하여 <VP>를 <V>로 바꾸어 줍니다.

 

        <N> <PAR> <VP>  ----->  <N> <PAR> <V>     규칙 5)

        

    마지막으로 규칙 6), 8), 9)를 적용하여 모든 비단말 기호를 단말 기호로 바꾸어 씁니다. 

 

        ----> 꽃 이 피다    (규칙 6), 8), 9))

 

    이렇게 바꾸어 쓰는 과정을 트리(tree) 구조로 표현한 것이 아래 (그림 3)입니다.

  

    (그림 3)                            

                                                     

                                           <S>

                                    ↙              ↘

                            <NP>                             <VP>

                          ↙          ↘                          ↓                 

                   <N>                <PAR>              <P>

                    ↓                        ↓                      ↓   

                    꽃                     이                   피다

       

(그림 3)은 바꿔 쓰기 과정을 위에서 아래로 트리구조의 가지로 나타내고 마지막 단에는 단말 기호 배열로 문장이 기재되어 있습니다. 그림과 같은 데이터 구조를 구문 트리(syntax tree)라고 합니다. 구문 트리는 문장의 구조, 즉 구문을 표현한 데이터 구조입니다. 

    지금까지 구(句) 구조문법(phrase structure grammar)을 이용한 문법 생성에 대해 알아보았습니다.

 

2) 구문 분석

    이번에는 구(phrase) 구조 문법을 이용한 구문 분석 방법을 살펴보겠습니다. 구문 분석에서는 형태소 배열의 정보를 받아서 구문 트리를 구축하는데, 크게 나누어 톱다운(Top Down) 방식과 보텀업(Bottom Up) 방식이 있습니다.

    톱다운 방식은 시작 기호부터 바꾸어 쓰기를 시작하여 입력문과 일치하는 과정을 탐색하는 방식입니다.  보텀업 방식은 입력된 형태소를 정리하여 전체적으로 모순이 없도록 통합해 가는 방식입니다. 톱다운 방식으로 아래의 예를 들어 구문 분석을 해봅니다.

 

    <톱다운(top down) 방식으로 '꽃  이  화려하게  피다'라는 형태소의 배열을 분석해 보기>

    분석을 하려면 (그림 2)의  바꿔 쓰기 규칙에 따라 순서대로 문장을 생성하고, 생성한 문장의 일부가 입력과 일치하지 않으면 다른 규칙을 사용하여 문장을 다시 생성하는 작업을 반복합니다. 

 

    우선 시작 기호 <S>부터 바꿔 쓰기를 합니다. 시작 기호의 바꿔 쓰기 규칙은 규칙 1)뿐이므로 규칙 1)을 적용합니다.

        <S> 

        ---->  <NP> <VP>           규칙 1)

 

    이어서 비단말 기호 <NP>를 바꿔 씁니다. <NP>의 바꿔 쓰기는 규칙 2) 또는 규칙 3)을  적용할 수 있으므로, 먼저 규칙 2)를 적용해 봅니다.

        <S>

        ---->  <NP> <VP>            규칙 1)

        ---->  <ADJ> <NP> <VP>          규칙 2)

 

이번에는 앞의 <ADJ>를 바꿔 쓰기 위해 규칙 7)을 적용합니다.

        <S>

        ---->  <NP><VP>              규칙 1)

 

        ---->  <ADJ><NP><VP>            규칙 2)

        ---->  <예쁜><NP><VP>            규칙 7)

                 (구문 해석 실패)

 

    규칙 7)이 적용되어 생성된 '예쁜 <NP><VP>'이 입력문인 '꽃 이 화려하게 피다'와 일치하지 않는 것을 알 수 있습니다. 그 원인은 <NP>의 바꿔 쓰기에 규칙 2)를 도입했기 때문입니다. 따라서 규칙 2) 대신 규칙 3)을 도입해 <NP>를 <N><PAR>로  바꿔 쓰기를 시도합니다. 

        <S>

        ---->  <NP><VP>            규칙 1)

        ---->  <N><PAR><VP>            규칙 3)

        ---->  꽃 이 <VP>            규칙 6), 규칙 8)

 

    다음에는 <VP>를 바꿔 씁니다. <VP>는 규칙 4) 또는 규칙 5)를 쓸 수 있으므로 우선 규칙 4)를 적용해 봅니다.

        <S>

        ----> <NP><VP>

        ---->  <N><PAR><VP>

        ---->  꽃  이  <VP>

        ---->  꽃  이  <ADV><VP>            규칙 4)

 

    그다음 <ADV>에 규칙 10)을 적용하면 <ADV>가 '화려하게'로, 그리고 <VP>에 규칙 5), 규칙 9)를 적용하면 아래와 같습니다.

        <S>

        ---->  <NP><VP>            규칙 1)

        ---->  <N><PAR><VP>            규칙 3)

        ---->   꽃    이     <VP>            규칙 6), 8)

        ---->   꽃   이   <ADV><VP>            규칙 4)

        ---->   꽃   이   화려하게 <VP>           규칙 10)

        ---->   꽃   이   화려하게  <V>             규칙 5)   

        ---->   꽃   이   화려하게   피다            규칙 9)

        

위와 같이 바꿔 쓰기를 반복하여 바꿔 쓰기 계열을 얻게 됩니다. 이와 같은 바꿔 쓰기 과정을 아래 (그림 4) 구문 트리(tree)로 표현하여 구문 분석을 마치게 됩니다.

 

 (그림 4) 구문 트리(tree)                      <S> 

                                                        ↙            ↘

                                             <NP>                         <VP>

                                          ↙            ↘              ↙            ↘ 

                                   <N>              <PAR>   <ADV>        <VP>

                                    ↓                      ↓              ↓                ↓

                                   꽃                    이         화려하게      <V>                 

                                                                                              ↓

                                                                                             피다

                             

    (다음 편에 '의미 분석'이 이어집니다)

 

2023.05.31 - [인공지능(AI; Artificial Intelligence)] - 자연어처리(NLP; Natural Language Processing) (1)