문맥 자유 문법 (context-free grammar (CFG))

한 줄 정의: 하나의 비단말 기호를 그 주변 문맥과 무관하게 다른 기호열로 치환하는 생성 규칙들로 이루어진 문법 체계로, 프로그래밍 언어의 구문 구조를 정의하는 데 널리 쓰인다.

쉽게 풀면

문맥 자유 문법은 '이 기호는 이런 다른 기호들의 나열로 바꿀 수 있다'는 규칙들의 모음으로 언어의 문장 구조를 정의한다. '문맥 자유'라는 이름은 어떤 기호를 치환할 때 그 기호 앞뒤에 무엇이 있는지와 무관하게 항상 같은 규칙을 적용할 수 있다는 뜻이다. 프로그래밍 언어의 문법(예: '표현식은 항 더하기 항으로 이루어질 수 있다')이 대부분 이런 형태로 정의되며, 컴파일러의 구문 분석기가 소스 코드를 파스 트리로 변환할 때 이 문법을 기준으로 삼는다.

왜 중요한가

문맥 자유 문법은 컴파일러·인터프리터 설계에서 구문 분석기를 체계적으로 만들 수 있게 해 주는 이론적 토대이며, 프로그래밍 언어뿐 아니라 자연어 처리에서 문장의 구성 구조를 분석하는 파싱 연구와도 밀접하게 연결된다. 또한 촘스키 위계 안에서 정규 문법보다 표현력이 크고 문맥 의존 문법보다는 다루기 쉬운 위치에 있어, 언어의 표현력과 처리 효율성 사이의 균형을 논의할 때 자주 기준점으로 등장한다. 이 때문에 새로운 프로그래밍 언어나 데이터 교환 형식을 설계하는 논문, 파싱 알고리즘의 효율성을 개선하는 논문 모두에서 기본 개념으로 다뤄진다.

논문에서는 이렇게 쓰입니다

"본 프로그래밍 언어의 구문은 문맥 자유 문법으로 정의되며, LALR 파서 생성기를 통해 구문 분석기를 자동 생성하였다."

프로그래밍 언어나 데이터 형식의 구문 구조를 형식적으로 정의할 때 표준적으로 사용된다.

"자연어 문장의 구성 성분 구조를 표현하기 위해 확률적 문맥 자유 문법(PCFG)을 학습시키고, 각 생성 규칙에 확률을 부여하여 가장 가능성 높은 파스 트리를 선택하도록 하였다."

자연어 처리 분야에서는 문장의 통사 구조를 분석하는 구문 분석기(parser)를 설계할 때 문맥 자유 문법에 확률 개념을 결합한 형태로 확장하여 활용한다.

"질의 언어의 구문을 문맥 자유 문법으로 명세하고, 이를 바탕으로 오류 복구 기능을 갖춘 재귀 하강 파서를 구현하였다."

데이터베이스 질의어나 설정 파일 형식처럼 도메인 특화 언어(DSL)를 새로 설계할 때도 문법을 문맥 자유 문법으로 명세하는 방식이 흔히 쓰인다.

조금 더 깊게 보면

문맥 자유 문법은 촘스키 위계에서 유형 2 문법에 해당하며, 이를 인식하는 계산 모델은 푸시다운 오토마타(pushdown automaton)로, 문법과 오토마타 사이의 대응 관계가 파서 구현의 이론적 근거가 된다. 실제 논문에서는 순수한 문맥 자유 문법 외에도, 각 생성 규칙에 확률을 부여한 확률적 문맥 자유 문법(PCFG)이 자연어의 모호성을 다루는 데 널리 쓰이며, LL·LR·LALR 등은 문맥 자유 문법을 실제로 효율적으로 파싱하기 위한 알고리즘 계열을 가리키는 용어다. 또한 어떤 문법이 문맥 자유 문법으로 표현 가능한지 여부는 펌핑 렘마(pumping lemma) 같은 도구로 이론적으로 판별할 수 있다.

주의할 점

문맥 자유 문법으로 표현 가능한 것과 실제로 유효한 프로그램인 것은 다를 수 있다. 예를 들어 변수가 선언 전에 사용되지 않아야 한다는 규칙 같은 문맥 의존적 제약은 문법이 아닌 별도의 의미 분석 단계에서 검사해야 한다.