Синтаксичні дерева

S

Синтаксичне дерево - дерево, корінь якого є аксіома, проміжні вершини позначені елементами з N, на кроні знаходяться елементи з множини E.

Контекстно-вільні граматики: Породжуюча граматика (за Хомським): G=<N,E,P,S>, де N - допоміжний алфавіт (алфавіт нетерміналів); E - основний алфавіт (алфавіт терміналів); N та E - скінченні множини; P - скінчена множина правил типу , де: , ( множина всіх слів у термінальному алфавіті), - аксіома (виділений нетермінал).

Впорядковане дерево D називається деревом виводу (або деревом розбору) в КВ-граматиці G(S)=(N,E,P,S), яцщо виконуютсья наступні умови:

1. корінь дерева D позначений S;

2. кожен лист позначений або , або e;

3. кожна внутрішня вершина помічена нетерміналом;

4. якщо N - нетермінал, яким позначена внутрішня вершина і X₁,...,X_n - мітки її прямих нащадків в у вказаному порядку, то N -> X₁...X_k - правило з множини P.