문맥 자유 문법(Context-free grammar)

문맥 자유 문법은 기호를 다른 기호열로 바꾸는 규칙의 모음입니다. 대문자처럼 아직 풀어야 할 기호(비단말 기호⁠(nonterminal symbol)⁠. 예를 들어 문장 S, 명사구 NP, 동사구 VP)와 실제 글자나 단어(단말 기호⁠, terminal symbol⁠)가 있고, 규칙의 왼쪽에는 언제나 비단말 기호 하나만 옵니다. 그래서 그 기호가 어떤 기호들 사이에 있든 상관없이 규칙을 쓸 수 있고, '문맥 자유'라는 이름이 여기서 나왔습니다. 시작 기호 S에서 출발해 단말 기호만 남을 때까지 규칙을 적용하는 과정을 유도라 하고, 이 문법이 유도할 수 있는 문자열들의 집합⁠(set)⁠이 문법의 언어입니다. 촘스키 위계⁠(Chomsky hierarchy)⁠의 둘째 층(유형 2)입니다.

보기:

같은 영어 문장 I saw the man with the telescope에서 ①과 ②를 번갈아 보세요. 단어도 규칙도 같은데 트리⁠(tree)⁠가 다르고, 뜻도 다릅니다. 한 문자열에 트리가 둘 이상이면 문법이 중의적이라고 합니다. 한국어의 '예쁜 여자의 가방'도 '예쁜'이 '여자'에 붙느냐 '가방'에 붙느냐에 따라 트리가 둘입니다. 동사와 목적어 뒤에 전치사구가 1, 2, 3, 4개 이어지면 가능한 트리의 수는 2, 5, 14, 42로 불어납니다. 이것은 카탈랑 수⁠(Catalan number)⁠ $C_n = \tfrac{1}{n+1}\binom{2n}{n}$에서 n = 2, 3, 4, 5인 값인데, 이 수는 이항계수⁠(binomial coefficient)⁠로 적히고 짝 맞는 괄호열의 개수와도 같습니다. 괄호열과 이진 트리⁠(binary tree)⁠ 사이에 전단사⁠(bijective)⁠가 있기 때문입니다. 이진 트리는 '잎⁠(leaf)⁠이거나, 두 이진 트리의 쌍'이라는 정의, 곧 타입⁠(type)⁠의 등식 $T \cong 1 + T \times T$의 가장 작은 해(시작 대수)이고, 이 등식을 개수의 생성함수⁠(generating function)⁠ $T(x) = 1 + x\,T(x)^2$로 옮겨 풀면 카탈랑 수가 나옵니다(대수적 자료형⁠, algebraic data type⁠). 일반적으로 모호하지 않은 문맥 자유 문법이라면, 길이별 문장 수의 생성함수가 규칙을 그대로 옮긴 연립 다항 방정식을 만족합니다(1963년 촘스키와 쉬첸베르제).

aⁿbⁿ을 만드는 규칙 S → aSb는 자기 자신을 다시 품습니다. 이 되풀이(재귀⁠, recursion⁠) 덕분에 문맥 자유 문법은 '열린 것은 반드시 닫힌다'는 중첩을 얼마든지 깊이 적을 수 있고, 바로 이 점에서 정규 표현식⁠(regular expression)⁠과 유한 오토마톤⁠(finite automaton)⁠을 넘어섭니다. 유한한 상태로는 몇 겹 열렸는지를 셀 수 없기 때문입니다(비둘기집 원리⁠, pigeonhole principle⁠). 대신 스택⁠(stack)⁠ 하나를 가진 푸시다운 오토마톤⁠(pushdown automaton)⁠이 딱 맞습니다. 스택은 접시 더미처럼 맨 위에만 넣고 꺼낼 수 있는 기억 장치라서, a를 읽을 때마다 접시를 하나 얹고 b를 읽을 때마다 하나 꺼내면 개수가 맞는지 알 수 있습니다. 거꾸로 aⁿbⁿcⁿ처럼 세 덩어리를 맞추는 일은 문맥 자유 문법으로도 안 됩니다.

주어진 문장의 트리를 찾는 일(구문 분석⁠, parsing⁠)은 작은 문제의 답을 표에 적어 가며 큰 문제를 푸는 동적 계획법⁠(dynamic programming)⁠으로 풀 수 있습니다. 1960년대에 코크, 영거, 가사미가 따로 찾아내 세 사람의 머리글자를 딴 CYK 알고리즘⁠(CYK algorithm)⁠은 '구간 i..j를 기호 A로 묶을 수 있는가'를 짧은 구간부터 채워 나가, 문법을 정해 두면 길이 n인 문장을 $O(n^3)$ 시간에 분석합니다(문법을 먼저 규칙마다 오른쪽이 기호 둘이나 단말 하나인 표준 모양으로 바꿔 둡니다). 편집 거리⁠(edit distance)⁠의 표와 같은 생각입니다. 구문 트리는 순환 없이 이어진 그래프, 곧 그래프 이론⁠(graph theory)⁠에서 말하는 트리입니다. 한 기호에 규칙이 여럿일 수 있으니 문법은 기호를 기호열 하나로 보내는 함수⁠(function)⁠가 아니라 여러 선택지를 허락하는 관계이고, 그래서 한 문장에 트리가 여럿일 수도 있습니다.

이어지는 곳. 1960년 국제 위원회가 만든 프로그래밍 언어 ALGOL 60의 보고서는 구문을 배커스–나우르 표기법(BNF, 존 배커스와 페테르 나우르의 이름을 땄습니다)이라는 문맥 자유 문법으로 적었습니다. 그 뒤로 거의 모든 프로그래밍 언어와 JSON 같은 데이터 형식의 구문이 이렇게 정의됩니다. 규칙마다 확률⁠(probability)⁠을 붙이면 확률 문맥 자유 문법⁠(probabilistic context-free grammar)⁠이 되어, 중의적인 문장에서 가장 그럴듯한 트리를 고를 수 있습니다. 앞 단어 몇 개만 보는 n-그램⁠(n-gram)⁠ 모형은 트리를 보지 못하고, 이것이 촘스키가 유한 상태 모형을 비판한 핵심이었습니다. 규칙에 문맥을 허락하면 문맥 의존 문법⁠(context-sensitive grammar)⁠이 됩니다. αAβ → αγβ는 'A의 왼쪽에 α, 오른쪽에 β가 있을 때만 A를 γ로 바꿀 수 있다'는 규칙입니다(γ는 빈 문자열이 아니어야 합니다). 규칙에 어떤 제한도 두지 않으면 문법은 튜링 기계⁠(Turing machine)⁠와 같은 힘을 가집니다.