8. Context Free Grammar

• Consist of CFG
• Ambiguous
• Grammar Transform
• Chonskey Normal Form

 

---

Consist of CFG

 

 

• Context Free Grammar ( CFG )

CFG 는 4가지로 구성되어 있는데 기호로 G = (Vn, Vt, P, S ) 로 정의한다. 

Vn : non terminal symbols

Vt : terminal symbols

P : Production , a -> B 

S : start symbol

 

Context free language 는 CFG 에 의해 생성되는 문자열이고, Regular Language 와 마찬가지로 , Derivaiton 을 통해 state 를 trainsition 하며 만들어진다.

Regular Language 와의 차이는 production 에 있는데, Regular language 는 a 가 non terminal symbol 중 하나이고 , b 가 tB | t | Bt 인데, 여기서 B 는 non terminal symbol 중 하나를 의미하고 , t는 terminal symbol 중 하나를 의미한다.

반면 CFG 는 a 는 non terminal symbol 중 하나로 동일하지만, B 는 V* 이다. 이 내용에 대해서는 Compiler 2번째 글에 Chomskey Hierarchy 를 참고하면 된다. 이렇게 a, b 에 대한 제한만 다를 뿐 문자열이 생성되는 방법은 동일하다.

 

• Parse Tree

CFG symbol 들로 구성된 트리로, 단말 노드는 terminal 기호나 입실론을 의미하고, 자식이 있는 노드는 terminal symbol 이 된다. root 노드는 start symbol 을 의미한다. Regular Language 에서는 이 역할을 Finite Automata, DFA, NFA 가 수행하였다.

 

• Left / Rightmost derivation

Regular 때와는 다르게, a->b 에서 b가 non terminal 이 2개 이상일 수 있다. 위에서 말했듯이 RL 의 경우에는 b에 non terminal 기호가 하나밖에 오지 못한다. 

따라서 b의 non terminal 을 어떻게 구분짓느냐에 따라서 Leftmost 와 Rightmost 로 나뉘게 된다. 대표적인 예가 프로그래밍 언어론에서 배우는 연산자의 parse tree 구조이다. E -> E+E | E*E .. 식으로 표현된 Production 의 경우 다음 2가지 경우로 Leftmost, rightmost derivation 이 나타난다.

 

 

 

---

Ambiguous

 

 

• Ambiguous (모호성)

CFG 에서 모호성이란, 하나의 string이 2개 이상의 parse tree 를 만드는 경우를 말한다. 이런 경우 2가지 이상으로 해석되기 때문에 프로그래밍 언어로는 쓸 수 없다. 대표적인 예시가 Dangling else 이다. if - if - else 의 구문이 있을 때 else 가 어떤 if 에 속하는지 판단하는 문제를 말한다. 만약 어떤 프로그래밍 언어가 if 문이 ambiguous 한 CFG 로 작성되었다면, if - else - else 는 2가지로 해석되면서 해석 오류가 일어난다.

 

• unambiguous / inherently ambiguous

모호하지 않다 ( unambiguous ) 는 것은 L(G) 에 속하는 모든 string 이 unique 한 derivation 을 갖는 것을 말한다. 본질적으로 모호하다 ( inherently ambiguous )는 뜻은 CFL L 의 모든 G가 모호성을 가지는 경우를 말한다.

CFL 의 모호성은 해결되지 못하는 경우도 있다. 그렇다면 어떤 CFL 가 모호성을 가지는 지를 왜 알아야 할까? 그것은 string 을 판단하는 시간복잡도에 있다. 모호성이 없는 CFL 가 모호한 CFL 보다 Automata 를 통해 분석했을 때 훨씬 더 빠른 시간안에 결과를 내놓는다.

 

 

---

Grammar Transform

 

• 문법 변환

문법 변환을 하는 이유는 어떤 특정 형태의 문법을 만듦으로써 parsing 하는 시간을 줄일 수 있기 때문이다. CFL 의 문법변환은 CFL -> Proper CFL -> Chomskey Normal Form / Greibach Normal Form 의 순서로 이루어진다.

 

• Proper CFL

Proper CFL 은 쓸모없는 production 을 전부 삭제하고 (  Reduced ) , 입실론 production 을 지우고 ( e-free ) , 싸이클을 전부 지운 ( cycle free ) 형태를 말한다.

 

Reduced 한 형태를 만들기 위해서는 다음과 같은 과정을 거친다.

1. non terminal symbol 을 derive 할 수 있는 terminal symbol 을 선택한다.

2. ( 1(이전)에서 선택한 terminal symbol  /  non terminal symbol 들의  *   ) 의 합집합으로 만들 수 있는 non terminal symbol 을 선택한다.

3. 더 이상 선택된 symbol 집합이 변화가 없을 때 까지 2를 반복한다.

4. 3의 집합에 속하지 않는 non Terminal symbol 과, Start symbol 에서 도달할 수 없는 non Terminal symbol 을 전부 지운다.

 

e-free 한 형태를 만들기 위해서는 다음과 같은 과정을 거친다.

1. 모든 e 심볼을 지운다.

2. e 심볼을 derive 하는 non terminal symbol 들을 e으로 대체해 가며 나올 수 있는 모든 경우를 다 써넣는다.

3. 처음에 start symbol 이 e을 derive 했었다면 s->e 를 써준다.

cycle-free 한 형태를 만들기 위해서는 다음과 같은 과정을 거친다.

솔직히 Proper Grammar 를 만드는 과정은 잘 이해못했다.. 뭔가 맞는거 같으면서도 막상 CFL 를 변형해보라고 하면 턱막힌다. 

 

---

Chomskey Normal Form

 

• Chomskey Normal Form

Normal Form 을 만드는 이유는 위에서 말했듯이, 알고리즘 설계를 쉽게하고 더 빠른 속도로 수행하기 위해서이다. CFL 에서는 대표적으로 CNF ( Chomskey Normal Form ) 와 GNF ( Greibach Normal Form ) 이 있는데, 수업에서는 CNF 만 다뤘다.

 

CNF 는 A -> BC | a  , S -> e 의 형태로 만드는 것인데, 쉽게 말해서 오른쪽에 2개의 non terminal symbol 또는 1개의 terminal 심볼만 남도록 다 변형하는 것이다. 이런 형태를 만드는 것은 binary tree 를 만들 수 있게 해주며, 더 쉬운 parsing 을 할 수 있게 한다.

 

CNF 로 바꾸는 방법은 간단하다.

1. CNF 형태가 안되는 production 에 대해 non terminal symbol 은 전부 Xn -> a 형태로 terminal symbol 로 바꿔준다. 예를들어 A -> aBC 라면 여기서 a 는 non terminal symbol 이므로X(a) -> a 를 만든 후, A -> X(a)BC  로 바꿔준다. 이 과정을 통해 모든 non terminal symbol 을 다 지울 수 있다. 

2. 오른쪽에 x ( x >= 3 ) 개 이상의 non Terminal symbol 에 대해  ( 1개 | x-1 개 ) 형태로 쪼갠다. 그리고 x-1 를 생성하는 문법 규칙을 추가한다. 예를 들어 A -> BCD 라면,  A -> B / CD 로 쪼갠 후 CD를 만드는 새로운 규칙 X -> CD 를 만든다. 이렇게 하면 A -> BX 로 오른쪽에 2개의 non terminal symbol 만 남기고 다 지울 수 있다. 

 

밑에 예시를 통해 더 쉽게 이해할 수 있다.