ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 403
Скачиваний: 1
Розв'язати цю задачу можна двома способами.
1. Розбір
зверху вниз.
Оскільки
є лише одна продукція з початковим
символом S
у лівій
частині, то почнемо виведення з S AB.
Далі
використаємо продукцію A Ca.Отже,
S AB CaB.
Позаяк
ланцюжок cbab
починається
із символів cb,
то,
використавши продукцію C cb,
одержимо
S AB CaB cbaB.
Завершуємо
виведення
застосуванням
продукції B
b:
S AB CaB cbaB cbab
Отже, ланцюжок cbab належить мові L(G).
2. Розбір знизу вверх. Почнемо з ланцюжка cbab, який потрібно вивести. Можна використати продукцію C cb; отже, Cab cbab. Застосувавши продукцію A Ca, отримаємо Ab Cab cbab. Тепер використаємо продукцію B b; отже, AB Ab Cab cbab. Нарешті, застосуємо продукцію S AB;
S AB Ab Cab cbab
Дерево виведення для рядка cbab в граматиці G зображено на рис. 37.3.
Рис 37.3.
Означення 37.6. Виведення називають еквівалентними, якщо їм відповідають однакові дерева.
Перевага дерева виведення порівняно з виведенням його компактність. Дерево на рис. 37.3 має вісім вершин, а відповідні виведення 18 або 16 символів.
Взаємно однозначної відповідності між ланцюжками мови L і деревами виведення в граматиці G, яка породжує L, може й не бути.
Означення 37.7. Контекстно вільну граматику G називають неоднозначною, якщо існує хоча б один ланцюжок у мові L(G), який має в G більше одного дерева виведення.
Розглянемо граматику G = (V, T, S, P), де V = {S, a, b, c, +, , *, /, (, )}, T = {a, b, c, +, , *, /, (, )}, P = {S S+S, S SS, S S*S, S S/S, S (S), S a, S b, S c}. Ця граматика породжує мову арифметичних виразів, але вона неоднозначна. Вираз a*b + c має в ній два дерева виведення (рис. 37.4).
Неоднозначність мови призводить до незручностей у її використанні. Річ у тому, що дерево виведення основний засіб інтерпретації ланцюжка; тому синтаксична неоднозначність (тобто наявність декількох дерев виведення) ланцюжка спричинює її семантичну неоднозначність наявність різних інтерпретацій. Наприклад, для ланцюжка a*b + c з попереднього прикладу різні дерева виведення інтерпретовано як різні способи розставлення дужок: (a*b) + c в першому випадку й a * (b + c) в другому. Це зумовлює різну послідовність операцій і, відповідно, різні результати обчислень. Щоб забезпечити однозначність, достатньо явно ввести дужки після кожної неодномісної операції в мовах формул (логічних, арифметичних, алгебричних тощо). Граматика з дужками хоча й призводить до надлишкових дужок у формулах, однак дає змогу зменшити кількість нетермінальних символів і тим самим спростити синтаксичну структуру формули, задану її деревом.
|
|
|
Рис. 37.4.
37.5 Форми Бекуса-Наура
Для граматик типу 2 (контекстно вільних), окрім звичайного, є й інший спосіб подання форми Бекуса-Наура. У лівій частині продукцій граматик типу 2 один символ (нетермінальний). Замість того щоб виписувати окремо всі продукції, можна об'єднати в один вираз продукції з однаковими символами в лівій частині. Тоді замість символу в продукціях використовують символ ::=. Усі нетермінали в цьому разі беруть у трикутні дужки . Праві частини продукцій в одному виразі відокремлюють одну від одної символом |.
Наприклад, три продукції A Aa, A a, A AB можна подати одним таким виразом у формі Бекуса-Наура: A ::= Aa | a | AB.
