문맥자유언어 (Context Free Grammar)

1. 촘스키의 언어위계론

[그림] 언어위계론

• 현 프로그래밍 언어들은 대부분 촘스키의 언어위계론에서 제안된 문맥자유문법을 기반으로 함
• 촘스키의 언어위계론은 정규언어, 문맥자유언어, 문맥의존언어, 귀납적 가산언어가 있음.
• 그러나 이 내용을 모두 다루기에는 프로그래밍 언어론 과목의 범위를 넘어감 (컴파일러/오토마타때 다룸)
• 여기에서는 문맥자유문법만 가볍게 짚고 더 자세한 내용은 컴파일러/오토마타 과목에서 공부하기로 함

 

2. 문맥자유 문법 (Context-Free Grammar : CFG)

• 문맥 자유문법 G는 (V, T, P, S)의 순서쌍으로 정의된다. 음.. 이렇게 말하면 너무 어려우니까 쉽게 가보자.
• 어떤 한 문맥 자유문법을 새로이 정의할때는, 기본적으로 반드시 4개의 요소가 포함되어야한다는 것이다.
• 저 4가지 순서쌍이 각각 뭔지, 어떤식으로 돌아가는지 알아보자.

 

1) Voca Non Terminal (비 단말기호 집합 : 유한개)

• 단말기호를 제외한 문법기호들의 집합을 의미하며 유한개의 원소를 가짐
• 언어안에서 다른 문자열을 만들때 중간 과정으로 쓰이며, 보통 대문자로 쓰임
• 다른 기호로 유도할 수 있음. (유도는 규칙을 한번 써서 변환하는것)
• 언어에서 직접 쓰이는 기호보다는 그들을 포괄하는 개념들이 비단말임 (Expression 등)

 

2) Terminal Voca (단말 기호 집합 : 유한개)

• 단말기호 집합으로, 위의 비단말 기호랑은 서로소 임 (교집합이 없다는 것임)
• 단말기호는 다른 기호로의 유도가 불가능함 (단말이라는 의미를 잘 생각해보자 : 마지막 유도)
• 모두 언어에서 직접쓰이는 기호로써 알파벳, 아라비아숫자, 연산자 등이 해당함

 

3) Production (생성 규칙)

• 위의 단말기호들과 비단말기호들을 이용해 문자열을 만들어내는 방법을 열거한 것임
• 보통 V → (V U T)와 같은 방식으로 쓰인다 ("비단말 → 단말 or 비단말"이라는 뜻)
• 모든 생성규칙에서는 왼쪽(좌항)에 오는 기호는 단 하나만 쓰인다. 그러니까 대충말해보면
• (V), (Z if Z==3) -> K 이런거 안된다는 것이다. 조건이나 상황 등 언제나 상관없이 좌항은
• 우항으로 유도될수 있다는 개념으로 "문맥 자유문법"이라고 부른다.
• 이 때 화살표로 특정 기호를 다른기호로 바꾸는 것을 유도한다고 한다.
• 생성규칙은 기호들 사이에 유도가 어떻게 일어나는지 잘 정의해놓은 표와 같은 것이다.

 

4) Starting (시작 기호)

• 한 개의 비단말기호 (Voca - Non Terminal)를 정의한다. 
• 이 비단말기호가 바로 "시작 기호"이며, 이 문법의 시작은 시작기호로부터 시작된다.