문법 변환 : 단일 생성 규칙의 제거, 좌인수 분해, 좌재귀의 제거

단일 생성 규칙: 생성 규칙 중 A->B와 같이 생성 규칙의 오른쯕이 단 하나의 논터미널 기호로만 구성된 규칙이 존재하는 경우

A → B (단일 생성 규칙)을 제거하고,
A가 B가 만들 수 있는 모든 α를 직접 만들도록 바꾼다.
즉 A → α 를 새로 넣는다.

 

ex.

P:

E -> E + T | T

T -> T * F | F

F -> (E) | a

 

각 비단말마다 연결될 수 있는 비단말 집합을 만들어야 함

 

VNE = {T, F}    // E에 의해서 유도 가능한 논터미널

T -> T * F, F -> (E), F -> a가 존재

E -> E + T | T * F |  (E) | a 가 E 규칙이 됨

 

T의 경우

T -> T * F | (E) | a 

 

F의 경우 그대로

결국,

P':

E -> E + T | T * F |  (E) | a

T -> T * F | (E) | a 

F -> (E) | a

로 변환됨

 

proper한 문법

문맥 자유 문법 G가 어떤 논터미널 기호 A에 대하여 A=>+A 형태의 유도과정을 가지지 않으면 cycle-free (A가 사이클을 거쳐 다시 단일 A가 되는 경우)

Cycle-free하고 ε-free, 그리고 불필요한 생성 규칙을 가지지 않으면 그 문법은 proper하다고 함

 

좌인수분해(left-factoring)

- 같은 기호들을 접두사로 같은 2개 이상의 생성 규칙이 있을 때 주어진 문자열이 올바른 문장인가를 검사하기 위해 하향식 구문 분석기는 어떤 생성 규칙을 적용해야 할 지를 결정할 수 없음

- 만약 하나의 생성 규칙을 적용했다가 주어진 문자열이 생성되지 않으면 다시 돌아와서 다른 생성 규칙 적용 필요

- 하향식 구문분석의 전형적인 단점인 백트래킹 발생

- 이런 경우, 다음 기호를 볼 때까지 결정을 연기하여 구문 분석을 효율적으로 할 수 있음

- 좌인수분해 : 같은 기호를 접두사로 가진 2개 이상의 생성 규칙이 존재할 때 공통된 접두사를 인수분해 하는 것을 좌인수분해라고 함

 

예시

S -> cAd

A -> a | ab

A에서 a인지 ab인지... : 백트래킹 발생 -> 좌인수분해로 해결

S -> cAd

A -> aA'

A' -> ε | b

 

좌재귀(left-recursive)

- 문법이 어떤 문자열 α에 대해 A=>+Aα의 유도과정이 존재하는 경우 하향식 구문 분석기가 무한 루프에 빠짐

- 제거 필요

 

직접 좌재귀 :  A=>Aα

간접 좌재귀 :  A=>+Aα 의 유도 과정이 존재하는 경우

- 무한 루프에 빠지기 쉬운 좌재귀 대신에 A=>+αA의 형태와 같은 우재귀로 변환

 

직접 좌재귀의 제거

E -> E + T | T

T -> T * F | F

F -> (E) | id

일때

논 터미널 E에 대해서 좌재귀를 제거하면?

E + T가 좌재귀 부분(α1 == + T), T는 비좌재귀 부분(β1 == T) : A ->  βnA' ..., A' -> αnA' .... | ε 꼴로 변형

E -> TE'

E' -> + TE' | ε

 

T에 대해서는?

α1 : * F, β1 : F

T -> FT'

T' -> * FT' | ε

 

F는 좌재귀 존재 안함

 

결국,

E -> TE'

E' -> + TE' | ε

T -> FT'

T' -> * FT' | ε

F -> (E) | id

가 됨

 

간접 좌재귀의 제거

간접 좌재귀는 눈에 안보임. 정해진 순서로 정렬한 뒤 제거

S -> Aa | b

A -> Ac | Sd | e

S쪽에선 직접 좌재귀는 없지만, S -> Sda로 유도가 되어 간접 좌재귀는 존재

S를 먼저 놓는다고 할 때

A -> Sd에 생성 규칙을 모두 대입 (앞에서 뒤로 참조가 흐르게 함)

A -> Ac | Aad | bd | e

- A에 대한 직접 좌재귀가 새로 나타남

제거 시,

A -> bdA' | eA'

A' -> cA' | adA' | ε

 

최종적으로,

S -> Aa | b

A -> bdA' | eA'

A' -> cA' | adA' | ε