문맥 자유 문법

문맥 자유 문법(文脈自由文法, Context-free grammar, CFG), 문맥 무관 문법은 형식 문법의 한 종류로, 생성 규칙이 다음과 같은 문법을 의미한다.

V\to w

여기에서 $V$ 는 비말단(비종결자) 기호이고, $w$ 는 비말단과 말단 기호들로 구성된 문자열이다. 즉, 문맥 자유 문법의 각 생성 규칙의 좌측에는 단 하나의 비말단 기호만 관계한다.

많은 프로그래밍 언어 문법은 문맥 자유 문법에 속하며^{[출처 필요]}, 따라서 이 문법은 컴파일러 등의 이론에 중요한 역할을 차지한다.

정의

문맥 자유 문법 $G$ 는 $G=(V,\Sigma ,R,S)$ 의 순서쌍으로 정의되며, 이때 각 원소의 의미는 다음과 같다.

$V$ 는 비말단 기호의 유한집합이다.
$\Sigma$ 는 말단 기호의 유한집합으로, $V$ 와는 서로소이다.
$R$ 은 $V$ 에서 $(V\cup \Sigma )^{*}$ 로 연결되는 생성 규칙의 유한집합이다.
$S$ 는 $V$ 의 원소로, 시작 기호를 가리킨다.

관련 파서

LL 문법은 문맥 자유 문법의 일부분으로, LL 파서를 이용해 효율적인 방법으로 구문적 분석(構文的分析,(syntactic) parsing)할 수 있는 문법을 가리킨다. 여기에서 LL은 문장을 왼쪽부터(Left-to-right) 읽어들이며, 좌측유도(左側誘導, Leftmost derivation) 방식으로 동작한다는 것을 가리킨다.

비슷하게, LR 문법은 문장을 오른쪽부터, 우측유도(右側誘導, Rightmost derivation) 방식으로 동작하는 파서 문법을 가리킨다.