[Compiler] 8. Normal forms (정규 표현)

Why normal forms?

만약 모든 grammar의 productions이 같은 형식으로 표현된다면

• grammar를 사용하는 알고리즘 디자인 용이
• 증명 및 특성 표시 용이

대표적인 NF 2개

1. Chomsky Normal Form (CNF) (춈스키 정규 형태)
2. Greibach Normal Form (그레이바하 정규 형태)

 

Chomsky normal form (CNF)

context-free grammar G는 production이 아래와 같이 표현되는 경우 Chomsky normal form이다.

• A -> BC // 2개의 non-terminal로 이루어진 경우
• A -> a // 하나의 terminal로 이루어진 경우
• S -> ε // start symbol이 ε로 가는 경우

A, B, C ∈ VN, a ∈ VT, S -> ε이 P에 있을 때,  ε ∈ L(G)이라면 S는 어느 production에서도 right-hand side에 오지 않는다.

 

What is "Chomsky normal form" good for?

derivation 했을 때 나오는 Parse trees는 a binary tree가 된다.

• Simplicity of proofs
  • context-free grammar 증명시 많은 도움이 된다.
• Enables parsing
  • parsing 알고리즘을 쉽게 구현할 수 있다.
  • 대표적인 parsing 알고리즘
    Cocke-Younger-Kasami (CYK) algorithm

 

Convert the grammar to Chomsky normal form

어떤 context-free language가 Chomsky normal form으로 표현되어도 생성할 수 있다.

context-free grammar가 주어졌을 때, CNF로 변환

1. G' = (V'T, VN, P', S) -> ε-productions, single(unit) productions, useless symbols form G들을 제거한 grammar
2. • A -> x는 G'의 rule인데, |x| = 0이다.
     |ε| = 0인데 앞에서 제거했는데, |x| = 0? => A는 start symbol이라는 의미
     
     
   • A -> x는 G'의 rule인데, |x| = 1이다.
     x는 VT => A -> B와 같은 signle(unit) productions은 제거 되었기 때문
3. A -> X1X2...Xn (n >= 2)
   만약 A -> X1이라면 X1은 terminal symbol이고, n >= 2 이라면
   2단계 거쳐 CNF로 변환
   
   1. RHS(Right-hand side)는 오직 VN만으로 구성
   2. RHS 길이는 2로 변환

 

Make the RHS consist only of non-terminal symbols

A -> X1X2...Xn에서 Xi가 non-terminal과 terminal symbol로 되어있을 때, Xi는 non-terminal로만 변환

1. 새로운 변수 추가 ex) Xa -> 마음대로 정해라
2. 모든 rule에서 RHS에 terminal symbol이 있다면, 앞에서 추가한 변수로 대체
   ex) A -> aBCaB
   Xa -> a
   A -> XaBCXaB
3. 새로운 rule 추가 Xa -> a

 

Make the RHS be of length 2

모든 production rule이 A -> a || A -> B1B2...Bn으로 되어있을 때, n >= 2 인 RHS의 길이를 2로 변환

ex)

• A -> B1B2....Bn
• A -> B1B_(2,n)
• B_(2,n) -> B2...Bn
• B_(2,n) -> B2(B3,n)
• ....
• B(n-1, Bn) -> Bn-1Bn

 

Greibach Normal Form (그레이바하 정규형태, GNF)

context-free grammar G에서 production이 다음과 같은 형태라면, Greibach Normal form이다.

• A -> aBC
• A -> aB
• A -> a
  // RHS의 처음이 VT으로 시작
• S -> ε