문법 변환 : 불필요한 생성 규칙의 제거, ε-생성규칙의 제거

모호한 문법 이외에도 어떤 문법들은 구문 분석을 하는데에 있어 효율을 상당히 떨어뜨리는 경우가 있음

효율적인 구문 분석이 이루어지도록 주어진 문법을 적당한 문법으로 바꾸어 주는게 문법 변환

 

변환 방법

- 불필요한 생성 규칙의 제거

- ε-생성규칙의 제거

- 단일 생성 규칙의 제거

- 좌인수분해(left-factoring)

- 좌재귀(left-recursion)의 제거 등

 

---

 

불필요한 생성 규칙의 제거(elimination of useless production)

- 한 문법이 생성하는 언어는 시작 기호로부터 유도할 수 있으며, 모두 터미널 기호로 이루어진 문장임. 따라서 시작 기호로부터 도달 불가능하거나 터미널 기호들을 생성하지 못하는 기호들은 가지고 있는 생성 구칙들을 모두 제거

- 불필요한 생성 규칙이란, 불필요한 기호를 갖고 있는 생성 규칙을 말함

 

불필요한 기호

- 유도과정이 존재하지 않는 기호

 

터미널 문자열을 생성하는 논터미널 기호, 시작 기호로부터 도달 가능한 기호

1. 생성 규칙 A -> α 에 대해서 α =>* w이고 w ∈ VT*일 때, A를 터미널 문자열을 생성하는 논터미널 기호라 함

    => 터미널 문자열을 만들어낼 수(generating) 있는가

2. 생성 규칙 A -> α 에 대해서 S =>* uXw, u, w ∈ V*일 때, X를 시작 기호로부터 도달 가능한 기호라 함

    => 실제로 도달 가능한가(reachable)

 

 

터미널 문자열을 생성할 수 없는 논터미널 기호를 가진 불필요한 생성 규칙의 제거

방법

VN' : 터미널 문자열을 생성하는 논터미널 기호들의 유한집합

P' : 터미널 기호를 생성할 수 없는 논터미널 기호를 가진 불필요한 생성규칙을 제거한 생성규칙의 집합

 

VN' = {A | A -> w ∈ P, w ∈ VT*}    // 일단 논터미널 만드는 거만 남긴다

repeat

    VN = VN' ∪ { A | A -> α, α ∈ ( VN ∪ VT )* }     // 논터미널 기호 추가될 거 있는지 체크

until no change

VN'' = VN - VN'

P' = P - { B -> γβγ' | γ, γ' ∈ ( VN ∪ VT )* , 모든 B, β ∈ VN'' }

 

설명

- 생성 규칙의 오른쪽이 모두 터미널 기호면 왼쪽 부분은 당연히 터미널 문자열을 유도하는 논터미널 기호

- 터미널 문자열을 유도하는 논터미널 기호와 터미널 기호가 오른쪽이면 왼쪽도 ~

- 더이상 새로운 논터미널이 생성되지 않을 때까지 반복해서 구한 논터미널 기호들의 집합을 구하면 이 논터미널 기호들은 터미널 기호들을 생성하는 기호

- 주어진 생성 규칙에서 위에 거 빼면, 나머진 터미널 기호들을 생성하지 못하는 논터미널 기호들

 

예시

G = (VN, VT, P, S)

VN = {S, A, B}

VT = {a}

P:

S -> AB | a

A -> a

 

VN' = {S, A}

VN'은 더 갱신 안됨, VN - VN' = {B}

B를 포함하는 S->AB는 불필요한 생성 규칙

P' = { S->a, A ->a }

 

 

시작 기호로부터 도달 불가능한 기호를 가진 불필요한 생성 규칙의 제거

VN' : 시작 기호 도달 가능 논터미널 유한집합

VT' : 시작 기호 도달 가능 터미널 유한집합

P' : 시작 기호 도달 불가능 기호 제거한 생성규칙 집합

 

V' = {S}

repeat

    V' = V' ∪ { X | if A ∈ V' , then A -> αXβ ∈ P}    // A가 이미 V' 안에 있고, A -> αXβ 생산식이 있으면 X를 추가

until no change

V'' =  V - V'

P' = P - {B → γβγ' | γ, γ' ∈ (VN ∪  VT)*,  B ∈ V',  β ∈ V''};

VN' = VN ∩ V'

VT' = VT ∩ V'

 

예시

P :S -> AB | aA -> a

 

V' = {S}V' = {S, A, B, a}V - V'은 공집합..P' = P

 

둘 다 적용 시?터미널 못만드는 거 없애면P' = {S->a, A->a}시작에서 도달 불가능한 거 없애면V' = {S}V' = {S, a}, 여기서 끝V'' = {A}

 

P' = {S->a}

 

터미널 못만드는 걸 없애고, 시작에서 도달 불가능한 거 없애야 됨(반대 순서 시 불필요한 생성 규칙이 완전 제거 안됨)

---

 

ε-생성규칙의 제거

- ε-생성규칙의 제거은 A -> ε 형태의 생성 규칙을 가진 것

 

ε-free 문법

1. P가 ε-생성규칙을 갖지 않는 경우

2. 시작기호 S만이 S -> ε 인 ε-생성규칙을 가질 때, 다른 생성 규칙의 오른쪽에 S가 나타나지 않는 경우

 

알고리즘 스킵, 예시로( ε-생성규칙이 존재하면 제거하고 제거된 ε-생성규칙들에 의해서 생성될 수 있는 것들을 보상)

 

S -> aSbS | bSaS | ε 일 때

 

P' = { S -> aSbS | bSaS }, VNε = {S}

다음은 VNε(앱실론 생성 논터미널)을 포함한 규칙에서 넣거나 빼서..

P'에 속하는 생성 규칙의 오른쪽 부분 중 논터미널 S가 있는 경우,S 대신 ε을 대체해서 생성될 수 있는 모든 생성 규칙을 P'에 첨가S -> aSbS | bSaS | aSb | abS | ab | bSa | baS | ba

 

다음은 시작기호가 그냥 ε 만들수도 있으니 S'을 추가P':S' -> S | ε

S -> aSbS | bSaS | aSb | abS | ab | bSa | baS | ba

시작기호는 이제 S'