문맥 자유 문법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

V \to w

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

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

정의[편집]

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

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

관련 파서[편집]

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

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