Page 32 - 4625

S  S  S | S * S | a.
Покажемо, що для ланцюжка   a  a  a існує щонай-
менше два варіанти виведення:
1. S  S  S  S  S  S  a  S  S  a  a  S  a  a  a
2. S  S  S  a  S  a  S  S  a  a  S  a  a  a
У теорії граматик розглядається декілька стратегій виве-
дення ланцюжка  в G. Визначимо дві стратегії, які будуть
використані в подальшому.
Лівостороння стратегія виведення ланцюжка  в G –
це послідовність кроків безпосереднього виведення, за якої на
кожному кроці до уваги береться перший зліва направлено
нетермінал.
Правостороння стратегія виведення  в G протилежна
лівосторонній стратегії. З виведенням  в G пов'язане синтак-
сичне дерево, яке визначає синтаксичну структуру програми.
Означення. Синтаксичне дерево виведення  в G – це
впорядковане дерево, корінь котрого позначено аксіомою, в
проміжних вершинах перебувають нетермінали, а на корені –
елементи з    . Побудова синтаксичного дерева виведен-
ня  в G виконується покроково з урахуванням стратегії ви-
воду  в G.
Алгоритм. Побудова синтаксичного дерева ланцюжка
 в граматиці G з урахуванням лівосторонньої стратегії
виведення:
 . Будуємо корінь дерева та позначимо його аксіомою
1
S.
 . У схемі P граматики G візьмемо правило виду
2
S  ...  , де   N    .
1 2 p i
Та побудуємо дерево висоти 1 (рис. 9).
 . На кроні дерева, побудованого на попередньому
i
кроку, візьмемо перший зліва направо нетермінал. Нехай це
буде  . Тоді в схемі P виберемо правило виду   
1 2
i
i
...  , де   N      та побудуємо таке дерево (рис. 10).
l i
31