문맥 자유 문법

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

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

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

 정의 

문맥 자유 문법 는 의 순서쌍으로 정의되며, 이때 각 원소의 의미는 다음과 같다.
 는 비말단 기호의 유한집합이다.
 는 말단 기호의 유한집합으로, 와는 서로소이다.
 은 에서 로 연결되는 생성 규칙의 유한집합이다.
 는 의 원소로, 시작 기호를 가리킨다.

 관련 파서 

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

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

분류:형식 언어
분류:컴파일러 구성
분류:1956년 컴퓨팅