[Compiler] 문법의 분류

 

Compiler

Compiler

 

---

문법의 분류 : Chomsky Hierarchy

 

 

형식문법은 생성생성 규칙에 어떠한 제약이 있는가에 따라서 다음과 같이 나눌 수 있다.

 

 

• 무제한 문법
  : 자연언어처럼 표현을 제한하지 않는 방법
  : 각 생성 규칙의 화살표(->) 양쪽에는 임의의 넌터미널과 터미널 스트링이 있다. 단, ε는 화살표의 오른쪽에만 올 수 있다.
  : AaB -> bA | ε

• 문맥-민감 문법
  : a -> b
  : |a|<=|b|로 화살표 우측 스트링 b의 길이가 a의 길이와 같거나 더 길다.
  : A -> aABCc
  : A -> ε
  : aB -> ab
  : bB -> bb

• 문맥-자유 문법
  : 문맥에 제한되지 않고 자유롭다.
  : 오늘날 대부분의 프로그래밍 언어는 이 문맥-자유 문법 형식으로 정의한다.
  : A -> a: |A| = 1이고, |A|<=|a|이다.
  : A는 반드시 넌터미널로 한 개, a는 넌터미널과 터미널이 혼합된 스트링이다.
  : S -> aAS
  : S -> a
  : A -> SbA
  : A -> SS

• 정규 문법(우-선형 문법)
  : 제한이 많기 때문에 기계 언어 같은 제한된 언어를 표현한다.
  : A -> aB 또는 A ->a
  : 문법의 제한이 많기 때문에 식별자, 상수, 예약어 같은 단순한 어휘를 정의한다.

 

 

이들 간의 포함관계는 다음과 같다. (L = langage)

L(G0) ≥ L(G1) ≥ L(G2) ≥ L(G3)