구문분석
Saltlux
목차 |
개요
언어학에서 구문 분석은 문장을 그것을 이루고 있는 구성 성분으로 분해하고 그들 사이의 위계 관계를 분석하여 문장의 구조를 결정하는 것을 말합니다. 특히 자연언어 처리 시스템에서는 일련의 문자열을 의미 있는 토큰(형태소)로 분해(형태소 분석)하고 이들로 이루어진 구 묶음을 만드는 과정을 의미 합니다. 이렇게 작성된 구 묶음을 통해 입력된 문장에 대한 구조를 해석하고 그 구조를 명백히 하는 것입니다.
예를 들어 “The post office will hold out discounts and service concessions as incentives” 라는 문장의 경우 아래와 같이 3가지의 구문으로 묶일 수 있으며, 구문 분석 과정은 구 묶음과 이 구 묶음을 통해 발생한 애매성을 해소합니다.
구문 분석 문법
구문 분석은 다음과 같은 과정을 거쳐 분석됩니다.
구문 분석을 위해서는 일반적으로 문맥자유문법(Context Free Grammar)을 사용하여 구문 분석 후 여러 개의 Parsing Tree를 반환합니다. 문맥 자유 문법은 다음과 같은 요소로 이루어져 있습니다.
G = <NT, T, P, S>
- Start Symbol (S) : Sentence
- Non-Terminal (NT) : syntactic constituents
- Terminals (T): lexical entities/words
- Productions ⊆ NT× (NT∪T)+ ≡ grammar rules
구문 분석 방법은 다음의 2가지 방법이 일반적입니다.
- Bottom – up(상향식): 문법규칙을 우변으로부터 좌변으로의 바꿔 쓰기 규칙이라고 간주하여 입력문(bottom)에서 S(개시 기호)를 만들어 가는 방향으로 해석하는 방법을 Bottom-Up 알고리즘입니다.
- Top-Down(하향식): 문법 규칙을 좌변에서 우변으로 바꿔 쓰기 규칙으로 간주하여 개시기호로부터 시작하여 입력문을 만들어 가는 알고리즘입니다.
구문 분석의 예
다음은 구문 분석의 예입니다.
주요 개념
Back tracking 문제
Top-Down 알고리즘을 수행 하는 도중 어떤 시점에서 해석이 실패 했음을 알면 그때까지의 바꿔 쓰기 규칙의 적용을 거슬러 올라가, 다른 규칙의 적용이 가능한 시점까지 되돌아가서 다시 수행 하는 것을 의미합니다.
차트 파싱
모든 Parsing 가능한 경우 Chart에 기록하는 방식으로 최적의 Path를 찾아 냅니다.
통계적 구문분석
모든 Parsing 가능한 경우 Chart에 기록하고 최적의 Path 검색하는 방식입니다.
