14 - Derivation Tree (Parse Tree)

유도 과정을 통해 유도 트리를 만들어보자

먼저 유도 트리를 만들기 위해서는 유도에 관한 개념을 알아야한다.

 

Define Derivation

---

(a + a)에서 nonterminal E는 E -> E + E | E * E | (E) | a가 될 수 있다.

따라서 E 에서 (a + a)로 도출되려면 E -> (E) -> (E +E) -> (a + E) -> (a + a)가 된다.

위는 leftmost 유도할 경우이고, rightmost에서는 반대로 E -> (E) -> (E +E) -> (E + a) -> (a + a) 가 된다.

 

이제 a + a * a를 윧ㅎ해보자.

leftmost일 경우 E -> ( E ) -> E + E -> E + E * E 로, 맨 왼쪽 E부터 a로 바뀐다.

그렇게 되면 연산이 덧셈부터 시작하게 된다.

그래서 rightmost로 할 경우 트리가 * 표시가 더 위에 있어 * 먼저 연산하게 된다.

이렇게 한 문장으로 여러개의 의미를 가질 수 있는걸 모호성이라고 하고, 이걸 해결하기 위하여 

더 여러가지 방법들을 알아야한다.