Дерева виведення

Виведення в мовах, породжених контекстно вільними грама­тиками, можна зображати графічно з використанням кореневих дерев. У такому разі ці дерева називають деревами виведення, або деревами синтаксичного розбору.

Кореню дерева виведення відповідає початковий символ, внутрішнім вершинам - нетермінальні символи, що зустрічаються у виведенні, листкам - термінальні символи. Нехай γ - ланцюжок і А→ 𝛾 - продукція, використана у виведенні. Тоді вершина, яка відповідає нетермінальному символу А, має синами вершини, які відповідають кожному символу ланцюжка γ у порядку зліва направо.

Приклад 9.14.Визначимо, чи належить ланцюжок сbаb мові, породженій граматикоюG=(V, T, S, P), деV={а, b, с, А, В, С, S }, Т={ а, b, с}, S — початковий символ, а множина продукцій

.

Розв'язати цю задачу можна двома способами.

1. Розбір зверху вниз.

Оскільки є лише одна продукція з початковим символом S у лівій частині, то виведення починаємо з S ⇒ АВ. Далі використаємо продукціюА→ Са. Отже, маємоS⇒ АВ⇒ СаВ.

Оскільки сbаb починається з символів сb, то використаємо продукціюС→ сb, це дастьS⇒ АВ⇒ СаВ⇒ сbаВ.

Завершуємо виведення використанням продукціїВ→ Ь:

Отже, ланцюжок сbаb належить мовіL(G).

2. Розбір знизу вверх.

Починаємо з ланцюжка, який потрібно вивести: сbаb. Можна використати продукціюС→ сb, отже, Саb⇒ сbаb.

Далі застосуємо продукціюА→ Са, тоді матимемо Аb⇒ Саb⇒ сbаb. З використанням продукції В→ b, отримаємо АВ⇒ Аb⇒ Саb⇒ сbаb. Нарешті, використаємо продукціюS→ АВ:

Дерево виведення для рядка сbаb у граматиціG зображено на рис. 9.3. ▲

Виведення називають еквівалентними, якщо вони мають одна­кові дерева. Отже, в прикладі 9.14 наведені еквівалентні виведення. Перевагою дерева виведення порівняно з виведенням є компактність. Дерево на рис. 9.3 має вісім вершин, тоді як виведення - 18 або 16 символів.

Взаємно однозначної відповідності між ланцюжками даної мови L та деревами виведення в граматиці G, яка породжує L, може і не бути. Контекстно вільну граматикуG називають неоднозначною, якщо існує хоча б один ланцюжок в L (G), який має в L понад одне дерево виведення.

Приклад 9.15. Розглянемо граматику, яку отримують з граматики прикладу 9.13 ототожненням усіх нетермінальних символів і вилученням усіх тривіальних правилякі в цьому разівиникнуть. У результаті отримаємо граматику з такою множиною правил Р:

S→ S, S→ S+S, S→ S-S, S→ S*S, S→ S/S, S→ (S), S→ a, S→ b, S→ c.

Ця граматика еквівалентна до граматики прикладу 9.13; окрім того, виведення в ній суттєво коротші, а дерева мають суттєво меншу висоту. Проте ця граматика неоднозначна. Вираз а*b+с маєів ній два дерева виведення (рис 9.4, а та б). ▲

Рис. 9.4

Неоднозначність мови є незручністю в разі її використання. Річ у тому, що дерево виведення є головним засобом для інтерпретації ланцюжка; тому синтаксична неоднозначність (тобто наявність декількох дерев виведення) ланцюжка тягне за собою його семан­тичну неоднозначність - наявність різних інтерпретацій. Наприклад, для ланцюжка а*b+с з прикладу 9.15 різні дерева виведення інтерпретуються як різні способи розставлення дужок: (а*b)+с у першому випадку і а*(b+с) у другому. Це зумовлює різну послідовність операцій і, відповідно, різні результати обчислень. Зазначимо, що явне введення дужок після кожної неодномісної операції у мовах формул (логічних, арифметичних, алгебричних тощо) є достатнім засобом для забезпечення однозначності. Граматика з дужками (див. приклад 9.13) хоча й призводить до інадлишкових дужок у формулах, однак дає змогу зменшити кіль­кість нетермінальних символів і тим спростити синтаксичну струк­туру формули, що визначається її деревом.