[컴파일러] 문맥자유문법(CFG)에서 좌측유도와 우측유도

좌측유도와 우측유도

문맥자유문법에 대한 유도에서 nonterminal을 어느 순서로 대체해나갈 것인가에 따라 "좌측유도"와 "우측유도"가 있다.

좌측으로 유도하든지 우측으로 유도하든지 적용된 생성규칙은 동일하다.

다만 생성규칙들이 적용된 순서가 다를 뿐이다.

 

 

예시

아래 예제를 통해 좌측유도, 우측유도를 구해보고,

적용된 생성규칙을 살펴보자.

 

:: 문제 :: 

문자열  a + a * a  에 대해

아래와 같은 생성규칙들이 있다.

1. E -> E + T
2. E -> T
3. T -> T * F
4. T -> F
5. F -> ( E )
6. F -> a
좌측유도와 우측유도를 구하시오

 

:: 풀이 ::
- 좌측유도

E => E + T  (규칙1)

  => T + T  (규칙2)

  => F + T  (규칙4)

  => a + T  (규칙6)

  => a + T * F  (규칙3)

  => a + F * F  (규칙4)

  => a + a * F  (규칙6)

  => a + a * a  (규칙6)

 

- 우측유도

E => E + T  (규칙1)

  => E + T * F  (규칙3)

  => E + T * a  (규칙6)

  => E + F * a  (규칙4)

  => E + a * a  (규칙6)

  => T + a * a  (규칙2)

  => F + a * a  (규칙4)

  => a + a * a  (규칙6)

 

 

이때 '적용된 생성규칙 종류와 수'를 관찰해보자.

좌측유도일 경우 : 12463466

우측유도일 경우 : 13646246

 

규칙1 : 1

규칙2 : 1

규칙3 : 1

규칙4 : 2

규칙6 : 3

 

결론 : 좌측유도와 우측유도에서 적용된 생성규칙은 동일하다. 순서만 다르다. 

 

 

 

 

---

공부배경 : 

컴파일러개론 구문분석을 위한 "유도"를 공부중이다.

 

 

참고 : 

http://www.aistudy.co.kr/linguistics/free_linz.htm