구문 분석 및 문법 형식론

기계를 통해 문장의 문법 구조를 복구하는 과정: 합법적인 구조를 설명하는 문법 형식론과 이를 계산하는 알고리즘(구성 트리부터 의존성 그래프까지).

Definition

구문 분석은 문법에 따라 입력 문자열에 문법 구조를 계산적으로 할당하는 것이며, 문법 형식론은 어떤 구조가 합법적인지 명시하는 데 사용되는 시스템입니다.

Scope

전산 언어학에서의 통사론적 분석을 다룹니다. 여기에는 문맥 자유 구성 구문 분석(context-free constituency parsing)과 그 확률적 및 차트 기반 알고리즘, 의존성 구문 분석(dependency parsing), 단순 문맥 자유 문법을 넘어서는 주요 문법 형식론, 그리고 구문 분석에 필요한 순서 레이블링 작업(예: 품사 태깅)이 포함됩니다. 의미론적 해석(전산 의미론에서 다룸)과 기초 이론에서 다루는 근본적인 오토마타 이론은 제외됩니다.

Sub-topics

• Constituency and Context-Free Parsing
• Dependency Parsing
• Grammar Formalisms
• Part-of-Speech Tagging and Sequence Labeling

Core questions

• 문장에 통사 트리나 의존성 그래프를 효율적으로 할당하는 방법은 무엇인가요?
• 어떤 문법 형식론이 자연어 구문을 적절하게 포착하나요?
• 확률은 가능한 많은 구문 분석 중 모호성을 해소하는 데 어떻게 도움이 되나요?
• 태깅과 청킹은 전체 구문 분석을 어떻게 지원하나요?

Key concepts

• 구성 구문 분석
• 의존성 구문 분석
• 문맥 자유 문법
• 차트 구문 분석
• 확률 문법
• 품사 태깅
• 트리뱅크
• 구조적 모호성

Key theories

차트 구문 분석

CKY 및 Earley와 같은 동적 프로그래밍 알고리즘으로, 공유되는 하위 구문 분석을 재사용하여 다항 시간 내에 문장의 가능한 모든 분석을 계산합니다.

확률적 문맥 자유 문법

문법 규칙에 확률을 부여하여 가장 가능성 있는 구문 분석을 선택함으로써 자연어의 만연한 구조적 모호성을 해결합니다.

History

초기 구문 분석은 수작업으로 구축된 문법과 철저한 탐색에 의존했습니다. CKY 및 Earley 알고리즘은 문맥 자유 구문 분석을 효율적으로 만들었습니다. 1990년대 트리뱅크의 출현은 데이터 기반 확률적 구문 분석을 가능하게 했고, 2000년대에는 의존성 구문 분석이 언어 간 견고성으로 인해 중요성이 부각되었으며, 이후 신경망 파서에 의해 대체되었습니다.

Debates

구성 표현 대 의존성 표현

구문이 중첩된 구로 가장 잘 표현되는지 또는 레이블이 지정된 주어-종속 관계(head-dependent relations)로 가장 잘 표현되는지에 대한 논의입니다. 둘 다 널리 사용되며, 의존성은 자유 어순 언어와 후속 작업에 선호되는 경향이 있습니다.

Key figures

• Jay Earley
• Joakim Nivre
• Christopher Manning
• Mitchell Marcus

Seminal works

• manning1999
• kubler2009
• jurafsky2025

Frequently asked questions

문법 규칙을 알고 있다면 구문 분석이 왜 어려운가요?

자연어 문장은 매우 모호합니다. 단일 문자열이 여러 합법적인 구조를 가질 수 있습니다. 따라서 구문 분석은 구조를 찾는 것뿐만 아니라 순위를 매겨야 하므로 확률적 모델과 학습된 모델이 필수적입니다.