[컴파일러] 촘스키 언어 계층 정리 - 문법 정리

 

 

Chomsky Grammar Hierarchy

 

촘스키 계층구조

 

 

 

문법을 표현 능력(Grammar Power)과 제약(Restrictions)에 따라 네 가지 계층으로 나눈 구조로, 안쪽에서 바깥쪽으로 갈수록 제약이 줄고, 표현 능력이 강해진다. 

 

 

1. Type-3 Grammar (Regular Grammar, 정규 문법)

• 가장 단순한 문법
• 정규 표현식(Regular Expression)으로 표현 가능
• 유한 오토마타(FA, Finite Automaton)로 인식 가능
  • 예: 이메일 형식, 전화번호 패턴

 

2. Type-2 Grammar (Context-Free Grammar, 문맥 자유 문법)

• 정규 문법보다 강력
• 푸시다운 오토마타(PDA)로 인식 가능
• 프로그래밍 언어 문법 대부분이 여기에 속함 (if-else, 중첩 구조 등)
  • 예: 괄호가 올바르게 짝지어진 식

 

3. Type-1 Grammar (Context-Sensitive Grammar, 문맥 민감 문법)

• 문맥에 따라 문법 규칙이 달라지는 구조를 포함
• 선형 경계 오토마타(LBA)로 인식 가능
• 정규 언어나 문맥 자유 언어보다 훨씬 표현력이 강함
  • 예: aⁿ bⁿ cⁿ (동일 개수의 a, b, c가 순서대로 오는 언어)

 

4. Type-0 Grammar (Unrestricted Grammar, 무제한 문법)

• 가장 일반적이고 강력한 문법
• 튜링 기계(TM)로 인식 가능
• 재귀적으로 열거 가능한 모든 언어를 표현 가능
• 제약이 거의 없음
  • 예: 어떤 계산 가능한 함수든 표현 가능

 

 

🌟정리🌟

Type-3 (정규): 단순한 패턴 → FA
Type-2 (문맥 자유): 프로그래밍 언어 대부분 → PDA
Type-1 (문맥 민감): 더 복잡한 언어 → LBA
Type-0 (무제한): 가장 강력, 튜링 기계 수준