Page 13 - 4761

1.7 Дерево виводу

Деревом виводу граматики G(VT,VN,P,S) називається граф, який відповідає
деякому ланцюгу виводу і задовольняє наступним умовам:
 кожна вершина графа позначається символом граматики А  (VT VN);
 коренем дерева є вершина, яка позначається початковим символом граматики S;
 кінцеві вершини позначаються термінальним символом граматики або λ;
Якщо деякий вузол позначено символом А  VN, а зв’язані з ним вузли –
символами b 1, b 2,…b n>0,  n i>0, b i ( VT VN {λ}), то в граматиці G існує правило
А b 1, b 2,…b n P.
З визначення видно, що по структурі правил дерево виводу можна побудувати
тільки для граматики типу 2 і 3.
Для того, щоб побудувати дерево виводу достатньо мати тільки ланцюг виводу.
Його можна побудувати двома способами: зверху вниз і навпаки. При побудові дерева
виводу зверху вниз побудова починається з цільового (початкового) символу, який
поміщається в корінь дерева. Потім в граматиці вибирається необхідне правило і на
першому кроці виводу кореневий символ розкривається на декілька символів першого
рівня. На другому кроці серед всіх кінцевих вершин вибирається крайня (ліва для
лівостороннього виводу; права для правостороннього виводу) вершина, позначена
нетермінальним символом, для неї вибирається потрібне правило і вона розкривається на
декілька вершин наступного рівня. Побудова дерева закінчується, коли всі кінцеві
вершини позначені термінальними символами, інакше повертається до другого кроку і
продовжується побудова.
Як правило для побудови зверху вниз використовується лівосторонній вивід, а для
побудови знизу вверх – правосторонній.
Приклад 1.4. Розглянемо деяку граматику для побудови арифметичних
виразів.
G ({+, -, *,/,(,),a, b,},{S},P,S)
P:
SS+S S  S *S S S/S (S) a b

Приклади речень мови, заданої даною граматикою: a*b+a, a*(a+b).

Розглянемо ланцюг a*b+a. Побудуємо для нього лівосторонній вивід (буде 2
варіанти):
S S+SS*S+Sa*S+S a*b+S a*b+a
S S*S a*Sa*S+S a*b+S a*b+a
Побудуємо дерево виводу для кожного варіанту:

Рисунок 1.1 – Два варіанта дерева виводу ланцюга «a*b+a»

11