15 - Grammar Translation

어제 유도 트리를 만들면서, 사용하지 않는 터미널을 제거하는 과정이다.

 

 

사용하지 않는 production Rules 제거

---

Non-Terminal 중에서, Terminal 로 갈 수 있는 것들을 Terminating Non-terminal 이라고 하고,

이 Termination Non-terminal을 제외하고 모두 제거해야한다.

그리고, 존재하지만 갈 수 없는 경우의 수가 있다.

접근 가능한 터미널들을 Accessible Symbol이라고 하고 해당하지 않는건 제거해야한다.

 

 

Termination Non-terminal

S -> A
S -> B
B -> a

이와 같은 식이 있다.

여기서 termination non-terminal은, 마무리가 terminal이 되야한다는 뜻이다.

S -> B -> a 이기 때문에 2,3 번째 줄은 의미가 있으나,

S -> A는 마지막이 non-terminal이기 때문에 완결나지 않는다.

따라서 S -> A는 제거해야한다.

 

Accessible Symbols

S -> aB
A -> aB
A -> aC
B -> C
C -> B

이와 같은 식이 있다.

Accessible Symbol이 아닌 것을 지워야 하기 때문에, A -> aB 와  A -> aC는 제거해야 한다.

왜냐하면, 이러한 A를 사용하는 식이 없기 때문에 단절되었기 때문이다.

 

다음은 식을 오토마타 그래프로 표현해 보았다.

그래프를 보면, A는 a를 통해 B와 C로 가긴 하지만 A로 가는 선택지는 없다.

A로 가는 경우가 없다는 것은, 있어도 사용이 되지 않는다는 소리다.

그러므로 제거해야한다.