유도 트리 (derivation tree)

좌단유도(leftmost derivation)
의미 : 유도과정의 각 단계에서 문장형태(sentantial form)의 가장 왼쪽에 있는 논터미널 기호를 계속해서 대체(replacement)하는 경우
표현 : =lm=>
이 때 나타나는 문장형태를 좌문장형태(left-sentential form)라 함
좌파스(left-parse) : 좌단유도에 의해 적용된 일련의 생성규칙의 순서. top-down구문분석에 의해 생성됨

우단유도(right derivation)
의미 : 가장 오른쪽에 있는 논터미널 기호를 계속해서 대체하는 경우
표현 : =rm=>
이 때 나타나는 문장형태를 우문장형태(right-sentential form)라 함
우파스(right-parse) : 우단유도에 의해 적용된 일련의 생성규칙의 순서. bottom-up구문분석에 의해 생성됨


Context-Free Grammer(CFG) G = (VN,VT,P,S)에 대한 유도트리 정의

1. 모든 노드(vertex,node)는 문법기호를 레이블(label)로 갖는다
2. 루트(root)의 레이블은 시작기호 S이다.
3. 만약 어떤 노드가 하나 이상의 자식노드(child node)를 갖는다면, 이 노드는 논터미널 기호를 레이블로 갖는다.
4. 왼쪽부터 순서적으로 n개의 자식노드를 갖는 어떤 노드 A가 존재한다면 생성규칙이 존재한다.
5. 만약 어떤 노드가 자식노드를 하나도 가지고 있지 않다면, 이 노드를 잎(leaf, terminal node)이라 하고, 잎은 터미널 기호를 레이블로 갖는다.

관련개념
분석 나무와 모호성 ( parse tree and ambiguity )
모호성 (Ambiguity), 모호한 문법 (Ambiguous Grammer)