문맥 자유 문법 문서 원본 보기

{{위키데이터 속성 추적}}
'''문맥 자유 문법'''(文脈自由文法, Context-free grammar, '''CFG'''), '''문맥 무관 문법'''은 [[형식 문법]]의 한 종류로, 생성 규칙이 다음과 같은 문법을 의미한다.
:<math>V \to w</math>
여기에서 <math>V</math>는 비말단(비종결자) 기호이고, <math>w</math>는 비말단과 말단 기호들로 구성된 문자열이다. 즉, 문맥 자유 문법의 각 생성 규칙의 좌측에는 단 하나의 비말단 기호만 관계한다.

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

== 정의 ==

문맥 자유 문법 <math>G</math>는 <math>G = (V, \Sigma, R, S)</math>의 순서쌍으로 정의되며, 이때 각 원소의 의미는 다음과 같다.
* <math>V</math>는 비말단 기호의 유한집합이다.
* <math>\Sigma</math>는 말단 기호의 유한집합으로, <math>V</math>와는 [[서로소 집합|서로소]]이다.
* <math>R</math>은 <math>V</math>에서 <math>(V \cup \Sigma)^*</math>로 연결되는 생성 규칙의 유한집합이다.
* <math>S</math>는 <math>V</math>의 원소로, 시작 기호를 가리킨다.

== 관련 파서 ==

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

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

{{형식 언어 및 형식 문법}}

{{전거 통제}}

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