CFG
Chomsky Hierarchy • Type 2 Grammar

문맥자유 문법 (Context Free Grammar)

수학적 정의 및 규칙 구문 트리(Parse Tree)와 모호성 CFG vs CSG 비교 대조 푸시다운 오토마타 (PDA) 최신 AI·LLM에서의 의미와 한계 강의 영상 관련 용어 및 논문
★ Chomsky Formal Language Hierarchy Type 2 Grammar & CFL

문맥자유 문법 (Context Free Grammar, CFG)

Context Free Grammar 에서 '배'라는 단어는 언제나 똑같이 치환되며 표현력이 중간 수준 (대부분의 프로그래밍 언어) ..... Context Sensitive Grammar 에서 '배'라는 단어는 앞뒤 문맥에 따라 '먹는 배(과일)', '타는 배(선박)', '사람의 배(신체)'로 다르게 치환되며 표현력이 매우 높음 (인간의 자연어에 더 가까움)

컴퓨터 프로그래밍 언어의 구문 설계와 컴파일러 파서의 이론적 근간이 되는 형식 문법입니다. 비단말 기호가 치환될 때 주변의 이웃 단어나 문맥과 무관하게(자유롭게) 단독으로 치환 규칙을 적용받습니다. 스택(Stack) 메모리 1개를 구비한 푸시다운 오토마타(Pushdown Automaton, PDA)에 의해 완벽히 인식되며, 현대 컴파일러와 LLM의 정형 출력 제어(Constrained Logit Masking)의 핵심 규격으로 기능합니다.

인식 계산 모델
푸시다운 오토마타 (PDA)
파싱 계산 복잡도
O(n³) / 선형 O(n) (LL/LR)
수학적 기초

1. Context Free Grammar 의 수학적 정의와 규칙

형식 언어학에서 문맥-자유 문법(Context Free Grammar, CFG)은 4개의 집합으로 이루어진 순서쌍(4-tuple)으로 정의됩니다.

【 CFG의 수학적 4조 표현 】
G = (V, T, S, P)   (또는 G = (VN, Σ, S, P))
  • V (또는 VN): 비단말 기호들의 유한 집합 (Non-terminal 변수, 예: S, Expr, Term)
  • T (또는 Σ): 단말 기호들의 유한 집합 (Terminal 알파벳/토큰, 예: a, b, +, *, 0~9). 단, V ∩ T = ∅
  • S ∈ V: 유도의 출발점이 되는 시작 기호 (Start symbol)
  • P: 문자열 치환을 관장하는 생성규칙(Production Rules)의 유한 집합
핵심 생성규칙 규격 (Production Rule)

단일 변수 치환 규칙: A → x

A → x      (여기서 A ∈ V 이고, x ∈ (V ∪ T)*)

💡 "문맥-자유(Context-Free)"란 이름이 붙은 이유:
생성규칙의 좌변에 오직 단 하나의 비단말 변수 A만이 허용되기 때문입니다. 비단말 기호 A의 앞뒤(좌우)에 어떤 기호나 문맥이 놓여 있든 상관없이, 언제 어디서나 A를 독립적으로(자유롭게) 우변 문자열 x로 치환할 수 있다는 사실에서 유래되었습니다. (Peter Linz 2001)

우변 x는 비단말과 단말 기호들이 섞인 임의의 유한 문자열이며, 아무것도 생성하지 않는 빈 문자열(ε, epsilon)이 되는 것도 허용됩니다 (즉, A → ε).

예제 1: 짝맞춤 언어 (aⁿbⁿ)
L = {anbn | n ≥ 0}
S → aSb | ε

정규 문법(유한 오토마타)으로는 개수 카운팅이 불가능하지만, CFG의 스택 재귀를 통해 완벽히 생성됩니다.

예제 2: 회문 언어 (Palindrome)
L = {w wR | w ∈ {a, b}*}
S → aSa | bSb | ε

앞뒤 대칭 구조를 중앙에서부터 바깥쪽으로 거울처럼 확장해 나가는 전형적인 문맥자유 구조입니다.

예제 3: 균형 괄호 언어 (Dyck)
L = 균형 잡힌 중첩 괄호쌍
S → (S) | SS | ε

프로그래밍 언어의 코드 블록 `{ { } }` 및 수식 `( ( ) )` 검증의 근간이 되는 딕 언어(Dyck Language)입니다.

문맥-자유 언어 (Context Free Language, CFL):
어떤 언어 L에 대하여 L = L(G)를 만족하는 문맥-자유 문법 G가 적어도 하나 존재할 때, 그 언어 L을 문맥-자유 언어라고 부릅니다. 모든 정규 언어는 자명하게 문맥-자유 언어에 포함되므로, 정규 언어군은 문맥-자유 언어군의 진부분 집합(Proper Subset)입니다.

파스 트리 & 파싱

2. 구문 유도 트리 (Parse Tree) 와 문법의 모호성 (Ambiguity)

CFG에서 문장이 생성되는 과정을 계층적 트리 구조로 시각화한 것을 파스 트리(Parse Tree, 또는 구문 트리 Derivation Tree)라고 합니다. 트리의 루트는 시작 기호 S이며, 내부 노드는 비단말 기호, 리프(잎) 노드는 단말 기호가 됩니다.

【 Peter Linz 교재 수록: CFG 유도 파스 트리 다이어그램 】
Peter Linz Parse Tree Diagram

시작 기호로부터 자식 노드로 생성규칙이 단계별로 확장되어 리프 노드에 최종 단말 문자열이 배치되는 구조

⚠️ 문법의 모호성 (Ambiguity) 이란?

동일한 문자열에 대해 두 개 이상의 서로 다른 파스 트리(또는 서로 다른 좌단 유도)가 존재하는 경우, 해당 문법을 모호한 문법(Ambiguous Grammar)이라고 합니다.

예시: Expr → Expr + Expr | Expr * Expr | id
문자열 id + id * id 계산 시, 덧셈을 먼저 묶는 트리와 곱셈을 먼저 묶는 트리가 모두 성립하여 연산자 우선순위 혼선 발생!

컴파일러 작성 시 이러한 모호성은 치명적이므로, 문법 규칙을 계층화하여 단 하나의 유일한 파스 트리만 생성되도록 명확한 문법(Unambiguous Grammar)으로 개정하거나 연산자 우선순위 규칙을 부여합니다.

대조 분석

3. 문맥자유 문법 (CFG) vs 문맥인식 문법 (CSG) 알기 쉬운 비교

문맥자유 문법(CFG)과 문맥인식 문법(CSG)은 촘스키 계층에서 2단계와 1단계를 차지하며, "주변 문맥의 구속 여부"와 "파싱 계산 복잡도"에서 극명한 차이를 보입니다.

비교 항목 문맥자유 문법 (CFG, Type 2) 문맥인식 문법 (CSG, Type 1)
생성 규칙의 구조 A → x
(좌변은 오직 단 하나의 비단말 변수) 		αAβ → αγβ 또는 x → y (|x| ≤ |y|)
(좌변에 좌우 이웃 문맥 α, β가 필수 결합)
문맥 의존성 문맥 완전 무관 (Context-Free)
주변에 어떤 단어가 있든 A는 어디서나 자유롭게 치환 		문맥 필수 구속 (Context-Sensitive)
좌우 특정 문맥이 일치해야만 비단말 기호 치환 가능
대응 계산 오토마타 푸시다운 오토마타 (PDA)
(단일 LIFO 스택 1개를 가진 유한 기계) 		선형 한계 오토마타 (LBA)
(입력 크기 k·n 한정 테이프를 쓰는 튜링 기계)
표현 가능 언어 anbn, 회문, 괄호쌍 (Dyck)
(세 기호 일치 aⁿbⁿcⁿ 불가) 		anbncn, 복사 언어 (ww), a2ⁿ
(CFG보다 표현력이 엄격히 큼)
파싱 계산 시간 다항 시간: O(n³) (CYK, Earley 알고리즘)
결정적 서브셋(LL, LR)은 선형 시간 O(n) 		PSPACE-완전 (일반적으로 지수 시간 O(cⁿ))
계산량이 폭증하여 실시간 직접 파싱 난해
컴퓨터 언어 및 자연어 적용 • 프로그래밍 언어의 구문(Syntax) 정의 (BNF)
• 컴파일러 구문 분석기 (Parser)
• HTML/XML 문서 계층 구조 		• 변수 선언과 호출의 타입 일치 (Type Check)
• 자연어의 단수/복수 수 일치, 시제 일치
• 스위스 독일어의 교차 의존 구조

🌳 CFG의 구조적 특징: 깔끔한 분할 정복

CFG는 하위 트리(Subtree)들이 상호 간섭 없이 부모 노드에만 종속되므로, 문맥을 따지지 않고 부분 문제를 독립적으로 풀 수 있는 동적 프로그래밍(CYK 파싱)이 가능합니다. 이로 인해 컴파일러 제작과 고속 파싱이 가능해집니다.

🕸️ CSG의 구조적 특징: 상호 교차 의존성

CSG는 트리의 가지들이 서로 옆의 이웃 가지들과 수평적 조건(Cross-dependency)을 주고받아야 하므로, 트리가 아닌 복잡한 그래프 구조를 띠게 되며 이로 인해 파싱 복잡도가 지수적으로 치솟습니다.

오토마타 & 컴파일러

4. 푸시다운 오토마타 (PDA) 와 프로그래밍 언어의 설계

형식언어 (Formal Language) 이론에서 문맥-자유 언어(CFL)는 푸시다운 오토마타(Pushdown Automaton, PDA)에 의해 정확히 수락됩니다. 유한 상태 제어기에 후입선출(LIFO) 스택 메모리 1개가 결합된 형태입니다.

🥞 스택 기반 작동 원리 (PDA)

문자열 aⁿbⁿ을 읽을 때, 입력에서 a를 만날 때마다 스택에 A를 PUSH하고, b를 만나면 스택에서 A를 POP하여 최종적으로 스택이 비었을 때 문자열을 수락합니다.

※ 결정론적 푸시다운 오토마타(DPDA)가 인식하는 언어를 DCFL이라 하며, 현대 프로그래밍 언어 파서의 모태가 됩니다.

📝 배커스-나우르 표기법 (BNF)

C, Java, Python 등 모든 주요 프로그래밍 언어의 문법 명세는 CFG의 또 다른 수학적 표현 방식인 BNF (Backus-Naur Form) 또는 EBNF로 작성됩니다.

<statement> ::= <if_stmt> | <while_stmt> | <assign>
<if_stmt> ::= "if" "(" <expr> ")" <block>

문맥-자유 언어에 관한 연구는 실제 컴파일러 파서 생성 도구(Yacc, Bison, ANTLR)의 설계에서부터 정적 분석 도구에 이르기까지 컴퓨터 과학의 가장 실용적이고 중요한 토대를 형성하고 있습니다.

Deep Research

5. 최신 AI 와 LLM 에서 Context Free Grammar 의 의미와 한계

트랜스포머 기반의 거대 언어모델(LLM) 시대에 이르러 Context Free Grammar(CFG)는 단순한 고전 컴파일러 이론을 넘어, 생성형 AI의 출력을 100% 제어하는 '제약 디코딩(Constrained Decoding)'과 신경망 내부의 계층적 추론 구조를 해석하는 핵심 열쇠로 재조명받고 있습니다.

⚡

CFG가 최신 AI·LLM에 주는 핵심 의미 (Significance)

① 정형화된 출력 제어 (Constrained Decoding & Structured Outputs)

최근 OpenAI Structured Outputs, llama.cpp GBNF, Outlines, Guidance, SGLang 등 핵심 LLM 엔진들은 JSON Schema나 SQL 문법을 CFG로 변환하여 토큰 생성 단계에서 로짓을 실시간 마스킹(Logit Masking)합니다. 매 스텝마다 CFG 기반 푸시다운 오토마타(PDA)를 실행하여 문법적으로 불가능한 토큰의 확률을 -∞로 강제 차단함으로써, LLM이 단 1개의 쉼표나 괄호 오차도 없는 100% 문법적 유효성을 보장합니다.

② 어텐션 메커니즘을 통한 계층적 구문 트리 암묵적 학습

스탠퍼드 Christopher Manning 연구팀(2019 "A Structural Probe for Finding Syntax in Word Representations")의 연구에 따르면, 트랜스포머의 Self-Attention 헤드들은 명시적 문법 규칙을 가르치지 않아도 문장의 명사구(NP), 동사구(VP)와 같은 CFG적 계층 구문 트리 구조를 자발적으로 유도해 냅니다. 고차원 연속 벡터 공간 속에서 CFG의 재귀적 트리 분할 구조를 완벽히 모사하고 있는 것입니다.

③ 코드 LLM과 AST(추상 구문 트리) 인터페이스

GitHub Copilot, Cursor 등 코드 특화 LLM은 프로그래밍 언어의 CFG 명세(ANTLR, Tree-sitter)와 연동되어 작동합니다. 생성된 코드가 CFG 파서를 즉각 통과하도록 유도하여 자동 완성 및 린팅(Linting) 정확도를 획기적으로 향상시킵니다.

④ 계층적 사고와 논리 분할 정복 (Divide-and-Conquer)

인간의 언어와 논리적 추론은 본질적으로 부분 문제를 해결해 상위 개념으로 병합하는 트리 형태를 띱니다. CFG의 재귀적 생성 규칙은 CoT(Chain-of-Thought) 추론의 구조적 뼈대를 제공합니다.

⚠️

최신 AI·LLM 관점에서 CFG의 본질적 한계 (Limitations)

① 원거리 문맥 의존성 및 수 일치 포착 실패 (No Context-Awareness)

CFG는 정의상 "문맥 자유"이기 때문에, 문장의 앞부분에 있는 주어와 수십 단어 뒤에 나오는 동사의 단수/복수 일치, 대명사 상호참조(Coreference), 프로그래밍 언어에서의 변수 스코프/타입 일치와 같은 문맥 의존적 제약(Context-Sensitive constraints)을 표현할 수 없습니다. 이는 순수 CFG만으로는 인간 언어와 고수준 코딩을 온전히 모델링할 수 없는 근본 이유입니다.

② 구문적 모호성(Ambiguity) 폭증과 확률적 선호도 결여

자연어를 순수 CFG로 작성하면 문장 길이가 길어질 때 수십~수백 개의 서로 다른 파스 트리가 성립하는 '구문적 폭발'이 발생합니다. CFG 자체는 어떤 트리가 인간 상식상 타당한지 가중치를 매기지 못하므로, 확률적 가중치를 주는 통계 모델(PCFG)이나 대규모 신경망 LLM의 도움이 없이는 올바른 의미 해석이 불가능합니다.

③ 토크나이저(BPE/WordPiece)와의 경계 불일치 (Token Mismatch)

CFG는 단어 또는 완성된 토큰 단위의 비단말/단말 기호를 전제하지만, 최신 LLM은 서브워드(Subword) 바이트 단위로 토큰을 쪼개어 생성합니다. 이로 인해 CFG 파서의 상태와 LLM 서브워드 토큰 간의 경계가 어긋나며, 정형 디코딩 시 어휘집 전체(128k+)를 실시간 역추적하는 상당한 연산 오버헤드가 발생합니다.

④ 의미론(Semantics) 및 사실성(Factuality) 검증 부재

CFG는 문장이 "문법적으로 올바른 형태인가"만을 따질 뿐, 촘스키의 유명한 예문 "Colorless green ideas sleep furiously (무색의 초록 아이디어가 맹렬히 잔다)"처럼 문법적으로는 완벽하지만 의미상 넌센스이거나, 그럴듯한 거짓 정보를 생성하는 LLM의 환각(Hallucination) 문제를 전혀 차단하지 못합니다.

결론: 최신 AI 환경에서 CFG는 자연어의 유연한 의미를 생성하는 주역이라기보다는, LLM의 거침없는 확률적 생성을 정형화된 틀(JSON, SQL, 코드 AST)에 안전하게 가두는 '신뢰성 가드레일(Reliability Guardrail)'로서 결정적인 현대적 역할을 수행하고 있습니다.

학술 색인

7. 관련 용어 사전 및 참고 자료 (Terms, Sites & Papers)

【 관련 주제 및 용어 링크 (Terms) 】

문맥자유 문법 (CFG) 문맥인식 문법 (CSG) 형식언어 (Formal Language) 언어학 (Linguistics) 인공지능 (AI) 촘스키 계층 (Hierarchy) 계산가능성 이론 문맥 (Context) 지식 (Knowledge)

【 외부 사이트 및 참고 문헌 (Sites & Papers) 】

🌐 웹 백과사전: Wikipedia : Context-free grammar ↗
영문 위키백과 공식 항목
📖 참고 교재: 문맥-자유 문법 (Free Linz Chapter) : Peter Linz 저서 『An Introduction to Formal Languages and Automata』
Peter Linz 교수 홈페이지 ↗