[컴파일러] 02. 형식언어_문법의 분류

문법의 분류 (Chomsky Hierarchy)

α -> β ∈ P의 형태에 따라

Type 0 : No restrictions(unrestricted grammar, UG)

• 생성규칙에 제한이 없음. 다만 α 는 ε 가 될 수 없음.

 

Type 1 : Context-sensitive grammar(CSG)

• α -> β, | α | ≤ | β| 우측의 스트링 길이가 좌측보다 길다.

 

Type 2 : Context-free grammar(CFG).

• A -> α, where A : nonterminal, α ∈ V*.

좌측은 하나의 nonterminal이며, 우측은 terminal과 nonterminal로 이루어진 스트링이다.

 

Type 3 : Regular grammar(RG). 정규문법

1) A -> tB or A -> t, (right-linear)

2) A -> Bt or A -> t, (left-linear) where, A, B: nonterminal, t ∈ VT*