Тема 8. Виведення у різних класах породжуючих граматик. Дерева синтаксичного розбору (два заняття)

8.1 Мета занять за даною темою

Засвоїти основні прийоми виведення у різних типах породних граматик та побудови дерев синтаксичного розбору

7.2 Виведення у різних типах породних граматик

7.2.1 Мета заняття

7.2.2 Методичні вказівки з організації самостійної роботи студентів

При вивченні даної теми необхідно повторити основний теоретичний матеріал, звернувши увагу на такі основні моменти.

Різні граматики можуть породжувати одну й ту ж мову. Такі граматики називаються еквівалентними.

Граматика безпосередньо складових – граматика із правилами виведення: φΑψ → φωψ, або Α → ω, де нетермінальний символ Α ∊ VN, ω ∊ V – довільний непустий ланцюжок. Таким чином у НС-граматиках на кожному кроці виведення дозволяється заміняти тільки один символ.Граматики безпосередньо складових є нескорочуваними граматиками, тобто це граматики, в яких для будь-якого правила α→β справедливе співвідношення | ‌α ‌| ≤ ‌| β ‌|. Правила такого виду називаються нескорочуваними.

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

Серед БС-граматик розрізняють – лівоконтекстні та правоконтекстні граматики. Лівоконтекстною НС-граматикою називається граматика із правилами виду:

φ Α → φ ω,

Правоконтекстною БС-граматикою називається граматика із правилами виду:

Α φ → ω φ,

де А – нетермінальний символ А є VN,

φ, ψ – ланцюжка в алфавіті V= VT U VN.

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

Теорема 8: Клас лівоконтекстних мов не збігається з класом контекстно-вільних мов.

Теорема 9: Клас правоконтекстних мов не збігається з класом контекстно -вільних мов.

Граматика безпосередньо-складових називається НС-граматикою, відзначеною праворуч (НС-ОП-граматика), якщо кожне правило має вигляд:

φ Α ψ → φ ω ψ = φ ω’ ‌αψ,

де ‌α є V

НС-граматика називається НС-граматикою, відзначеною ліворуч (НС-ОЛ -граматика), якщо кожне її правило має вигляд:

φ Α ψ → φ ω ψ = φdω’ψ,

де ‌d є V

Мають місце теореми:

Теорема 10. Для будь-якої НС-ОП-граматики можна побудувати слабко еквівалентну КВ-граматику.

Теорема 11. Для будь-якої НС-ОЛ-граматики можна побудувати слабко еквівалентну КВ-граматику.

Виведення ланцюжка х у деякій мові LG називаються істотно різними, якщо структурні описи ланцюжка х, що відповідають цим виведенням, відрізняються один від одного.

Якщо заздалегідь відомо, що граматика не є неоднозначною, то очевидно, що по будь-якому породжуваному нею ланцюжку можна однозначно відновити виведення цього ланцюжка.

Якщо задано конкретну граматику G одного з типів і потрібно встановити, чи є вона неоднозначною, то алгоритмічна можливість розв'язання такого завдання встановлюється наступною теоремою.

Теорема 12. Для мов типу 3 існує алгоритм, що дозволяє по заданій граматиці визначити, чи є вона однозначною. Для інших типів мов це завдання алгоритмічно нерозв'язне.

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

Якщо змінити лише порядок застосування правил, а правила будуть використовуватися ті ж самі, то, очевидно, буде отримано інше виведення, але заключний термінальний ланцюжок і його обумовлена виведенням синтаксична структура залишиться незмінними. Зазвичай множина виведень КВ-граматики обмежується, і розглядаються не всі її можливі виведення, а лише так звані лівосторонні або правосторонні висновки.

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

7.2.3 Контрольні запитання і завдання

– Дайте характеристику відмінних рис щодо виведення у різних типах породних граматик;

–

–

–

–

7.2.4 Приклади аудиторних і домашніх задач

Приклад 1:

В якості нескорочуваної граматики розглянемо БС-граматику

G = (VT, VN, P, S), де VT={ a, b }, VN ={S}, P={S→aa, S→bb, S→aSa, S→bSb}. Нехай задано слово bSb. У результаті підстановки кожного з 4 правил одержуємо нове слово, довжина якого не менше довжини исходного слова: baab, bbbb, baSab, bbSbb.

Приклад 2:

Допустимо, що в нескорочуваній граматиці має місце правило виду АВ → ВА, де А і В – нетермінальні символи.

Таке правило може бути замінене чотирма правилами БС-граматики:

АВ → ВА:

АВ → А1 АВ → 1В; АВ → 1В АВ → 1В

А1 → В1. 1В → 12; 1 1В → 1А

В1 → ВА. 12 → В2; 1А → ВА.

В2 → ВА.

де 1, 2 – нові нетермінальні символи, які не зустрічаються в старих правилах. Послідовне застосування цих правил рівносильне застосуванню правила АВ → ВА.

Приклад 3:

Розглянемо КВ-граматику G=(VN,VT,P,S), у якої VN={E,R,F},

VT={ i, +, *, (,)}, S={E}, схема граматики Р ={ (1) E→E+R; (2) E→R;

(3) R→R*F; (4) R→F; (5) F→(E); (6) F→ i}. Дана КВ-граматика породжує арифметичні вирази, побудовані з ідентифікаторів (у граматиці ідентифікатору відповідає термінальний символ i), знаків арифметичних операцій + і *, дужок (і). Для термінального ланцюжка i+i*i побудуємо його лівостороннє та правостороннє виведення.

а) лівостороннє виведення:

(1) (2) (4) (6) (3) (4) (6) (6)

E => E+R => R+R => F+R => i+R => i+R*F => i+F*F => i+i*F => i+i*i.

б) правостороннє виведення:

(1) (3) (6) (4) (6) (2) (4) (6)

E => E+R => E+R*F => E+R*i => E+F*i => E+i*i => R+i*i => F+i*i => i+i*i.

7.3 Дерева синтаксичного розбору

7.3.1 Мета заняття

Засвоїти основні прийоми побудови дерев синтаксичного розбору для певних типів формальних граматик

7.3.2 Методичні вказівки з організації самостійної роботи студентів

При вивченні даної теми необхідно звернути увагу на такі основні теоретичні питання.

Одержання синтаксичної структури програми у формі кроків виведення не зовсім зручно - у виведенні не проглядається явно структура програми.

Більше зрозумілим є подання структури програми у вигляді дерева виведення (його називають також деревом синтаксичного розбору або деревом породження). Це поняття відіграє важливу роль у теорії трансляції. Синтаксичне дерево будується за породженням

S → N1, N2 … Nn → T1 T2 … Tk, Ni є VN, Tj є VT (j = 1,2,…,k)

(i=1,n)

Побудова синтаксичного дерева:

З кореня дерева, позначеного нетермінальним символом S, відходить n гілок (рос. – ветвей) по числу символів у рядку, безпосередньо породженого початковим нетермінальним символом. Кожна з гілок закінчується вершиною, позначеною символом Mi. Вершини помічаються зліва направо у порядку зростання номера та індексу.

Якщо в процесі породження до нетермінального символу Ni застосоване граматичне правило Ni →B1, B2, … Bt, то вершина Ni стає коренем піддерева. З цієї вершини виходить t гілок, кожна з яких закінчується вершиною, позначеною символом Br (r=1,2,...t). Така побудова виконується для всіх вершин, позначених термінальними символами.

Побудова дерева виведення закінчується, коли всі вершини зі ступенем по виходу, рівному нулю, виявляються позначеними термінальними символами T1 T2 … Tk... Сукупність цих міток при перегляді вершин зліва направо утворює термінальний рядок T1 T2 … Tk

Граматика G називається однозначною, якщо не існує ланцюжка α є L(G), що має більше одного дерева виведення. У противному випадку граматика називається неоднозначною.

Структурне дерево – це позначений граф (позначені ребра й вузли), де вузлам відповідають граматичні типи або синтаксичні одиниці, а ребра розрізняються своїм порядковим номером.

Ланцюг дерева – послідовність ребер, кожне з яких пов'язане з попереднім.

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

Кожний С-маркер містить у вигляді при кінцевих вузлах перелік слів, з яких складене дане речення.

У розглянутому реченні складовими є «м'яч», «гарний м'яч», «упустила гарний м'яч», Але! «упустила гарний» - не є складовою.

Кожна складова зводитися до деякого вузла дерева. Якщо цей вузол, припустимо, позначений С, то говорять, що складова належить до типу С.

Ті складові, з яких утворена конструкція, є безпосередніми складовими.

Очевидно, граматика не може складатися задовільно, якщо не даємо породжуваним реченням структурного опису - хоча б у вигляді розкладання на безпосередні складові.

Таким чином граматика повинна забезпечувати С-маркером кожне з безкінечного числа речень.

Два С-маркера (дерева) вважаються тотожними, якщо вони мають однакову структуру гілок і однакові мітки при відповідних вузлах.

Дерево С-маркера характеризується певним упорядкуванням гілок зліва направо відповідно до порядку елементів у ланцюжку.

Оскільки число правил скінченне, а число маркерів може бути безкінечним, то можуть знайтися такі символи граматичного словника, які повторюються в С-маркерах скільки завгодно раз. Більше того, можуть знайтися такі ланцюги дерева, які містять деякий символ більше ніж n разів для будь-якого фіксованого n.

Синтаксичний елемент називається рекурсивним елементом, якщо для деякого фіксованого n знайдеться деяке структурне дерево, ланцюг якого містить цей символ як найменування вузла більше ніж n раз.

Виділяють 3 види рекурсивних елементів:

Елемент А називається ліворекурсивним елементом, якщо підпорядковане йому дерево містить А тільки в самому лівому ланцюзі. (Дерево, підпорядковане А – це дерево, що може бути возведено з А).

Елемент А називається праворекурсивним, якщо підпорядковане йому дерево містить А тільки в крайньому правому ланцюзі.

А А

В С В С

А А

А

В С

А

Рисунок 7.1 – Три види рекурсивних элементів

Рекурсивний елемент А називається самовставленим, якщо підпорядковане йому дерево містить А в деякому внутрішньому ланцюзі.

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

Граматика G=(VT,VN,P,S) називається граматикою із самовставлянням, якщо для деякого А Є VN існує виведення А => *φ Α ψ, де φ і ψ не порожні слова в V(φ, ψ Є (VT U VN))

(Відношення виводимості =*> або => називається транзитивним замиканням)

Граматика G називається однозначною, якщо для кожного символу Х є L(G) всі його виведення мають одне й те ж дерево.

Добре відомо, що в природній мові можуть бути речення, що зводяться за написанням, але допускають неоднозначне синтаксичне трактування.

Приклад: «Пальто забруднило вікно».

У прикладах такого роду существенно (істотно?) не «статичне» окончательное начертание, а «динаміка» процесу граматичного виведення.

Подібного роду неоднозначність відіграє істотну роль для мов програмування.

Тому виникає питання про однозначність різних типів граматики та можливості знайти однозначну граматику певного типу.

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

При цьому під существенно різними виведеннями розуміється наступне:

Граматиці з правилами виду

поставимо у відповідність граматику у якої

тобто для кожного правила φi → ψi, системи Р до термінального словника додається рядок (φi (i=1,2,…...,k).

Система Р' получается (виходить?) із системи Р заміною кожного правила виду φi → ψi правилом φ1 → (φ1 ψ1).

Очевидно, що кожному виведенню ланцюжка х в LG однозначно відповідає виведення ланцюжка х' в LG '.

Цей ланцюжок х ' зводиться з х, якщо в ньому опустити всі рядки. Дужки, таким чином, зберігають «динаміку» виведення - їх розміщення, дозволяє відновити процес виведення.

Ланцюжок х ' називається структурним описом ланцюжка х.

У КC-граматиках під деревом синтаксичного розбору розуміють скінченний неорієнтований граф, що має наступні властивості:

− у нього є одна вершина, в яку не входить жодна дуга; цю вершину називають коренем дерева, корінь дерева відповідає початковому символу граматики - аксіомі;

− у кожну з інших вершин входить лише одна дуга; вершини, що не мають вихідних з них дуг, називаються заключними вершинами дерева або листами, у КВ-граматиці їм відповідають термінальні символи граматики; не заключним вершинам дерева відповідають нетермінальні символи граматики.

− він не містить контурів.

КВ-граматика називається однозначною, якщо у деякого ланцюжка w є (VT U VN)⁺ існує тільки одне дерево виведення. У противному випадку граматика називається неоднозначною.

Зауваження: однозначність або неоднозначність – це властивість граматики G, а не мови L(G). У загальному випадку ту ж саму мову можна описати за допомогою нескінченної множини граматик, що породжують її.

Для практичних цілей має сенс розглядати лише однозначні граматики, які забезпечують однозначну семантичну інтерпретацію програми та відповідно отримання програми машиною.

КВ - граматика називається:

лівосторонньою, якщо в ній є виведення виду

правосторонньою, якщо в ній є виведення виду

самовставляющей, якщо вона має виведення виду

КВ-граматика називається рекурсивною, якщо має місце хоча б один з випадків а) - в).

У загальному випадку КВ-граматика, що описує мову програмування, є рекурсивною.

Важливим є виявлення виду рекурсії при використанні того чи іншого методу синтаксичного розбору.

Розрізняють методи побудови дерева синтаксичного розбору допускають у граматиці, як правило, лише один вид рекурсії.

(Различают методы построения дерева синтаксического разбора допускают в грамматике, как правило, лишь один вид рекурсии.)

Задачу синтаксичного розбору можна сформулювати так: для заданого речення а1,а2,…,аn є VT і граматики G побудувати трикутник та спробувати заповнити його внутрішню частину деревом синтаксичного розбору [Кук ]

S

а1,а2,…,аn

В принципі, не має значення, яким чином буде заповнюватися внутрішня частина трикутника. На рис. 7.2 наведені три найбільше використовувані способи заповнення трикутника:

S S S

а1,а2,…,аn а1,а2,…,аn а1,а2,…,аn

а) б) в)

Рисунок 7.2 – Основні способи побудови синтаксичного дерева

Стратегія синтаксичного розбору, зображена на рис. 3 а) називається розбором зверху вниз. Так як програма може складатись з багатьох тисяч речень, то методи, що вимагають розміщення в оперативній пам'яті всього речення, у загальному випадку неприйнятні.

Тому на практиці застосовують методи заповнення трикутника, використовуючи частину речення.

Очевидно спосіб розбору речення по частинам – перебирати слова по одному зліва направо в їхній природній послідовності. При цьому використовується дві основні стратегії заповнення трикутника розбору: зверху вниз і зліва направо (рис. 3 б)), або знизу вверх та зліва направо (рис. 3 в)).

Вибір стратегії синтаксичного розбору для конкретної КВ-граматики, у загальному випадку, обумовлює швидкість його виконання.

На сьогоднішній день розроблена й використовується на практиці велика кількість алгоритмів розбору. Кожний з алгоритмів використовує певну стратегію розбору і в більшості випадків накладає різні обмеження на правила КВ-граматики, тобто вихідна КВ-граматика, перш ніж вона може бути використана як основа синтаксичного розбору, повинна бути піддана певним перетворенням.

Ці перетворення повинні забезпечувати:

− Однозначність, детермінованість граматичного розбору;

− Усувати зайві кроки в дереві розбору;

− Прості емпіричні критерії вибору продукції з множини альтернативних.

7.3.3 Контрольні запитання і завдання

1. Що таке дерево синтаксичного розбору?

2. Чому неоднозначна граматика не може бути взята за основу для виконання синтаксичного аналізу?

7.3.4 Приклади аудиторних і домашніх задач

Приклад 1:

Розглянемо граматику G4 = (VT, VN, Py, Sy).

P4 = {S → А, S → BEEF, E→BC, E → A}

Дерево виведення, що відображає породження

S → BEEF → BAEF → BABCF

Рисунок 7.3 – Приклад виведення для граматики G4

Коренем дерева є вершина, позначена початковим нетермінальним символом S, що безпосередньо породжує рядок BEEF. У цьому рядку нетермінальними є символи Е, які породжують ребра, що закінчуються вершинами А, В, С.

Вершини, позначені термінальними символами, мають ступінь по виходу, що дорівнює нулю. Сукупність цих міток при перегляді їх зліва направо утворює термінальний рядок ВАВСF.

Приклад 2

Для вивчення властивостей БС–граматики розглянемо маленький фрагмент граматики української мови, заданої наступними правилами:

~ ~ ~

F1: П → С Г;

~

F2: С → П С;

~ ~

F3: Г → Г С;

F4: П → маленький | пустотливий | гарний;

F5: C → м'яч | хлопчик | дівчинка;

F6: Г → упустив | ударив | кинув;

Правила F4 - F6 - це в дійсності група правил, оскільки вони вказують кілька можливостей (варіантів, альтернатив?) для кожного символу П, С, Г.

У розглянутій граматиці

VT = {маленький, пустотливий, гарний, м'яч, хлопчик, дівчинка, упустив, ударив, кинув}

~ ~ ~

VN = {Г, С, Г, С, П, П}

~

Г - група дієслова;

Г - дієслово;

~

С - група іменника;

С - іменник;

П - прикметник;

~

П - речення.

Початковим символом буде поняття речення. Виведені термінальні ланцюжки - правильні речення даної мови.

~

П S

~ ~

NP С Г VP

~

A П C N Г V С VP

П А С N

Пустотливий хлопчик упустив красивий м'яч

Гарна дівчинка вдарила пустотливого хлопчика

Рисунок 7.4 – Приклад дерева безпосередньо складових

У цій простій граматиці всі термінальні ланцюжки мають одну й ту ж синтаксичну структуру фраз, що може бути виражена за допомогою структурного дерева – маркера структури складових (С-маркера).

У даному прикладі, С и Г – безпосередні складові речення.

~ ~ ~

Є безпосередні складові для С і Г - це відповідно П і С, Г і С тощо.

Приклад 3:

G=({0,1}, S, S, P),

P={S → 0, S → S1S},

Тоді G’=({0,1(S)}, S, S, P);

P={S → (S0), S → (SS1S)}.

Ланцюжок 01010 мови LG може бути виведений різними способами:

1) S → S1S → 0 1S → 01 S1S → 0101S → 01010;

2) S → S1S → S1 0 → S1S 10 → 0 1S10 → 01 0 10.

Їм відповідають різні структурні описи, отримані в LG ’:

1) (S (S0)1 (S (S0) 1 (S0)));

2) (S (S (S0) 1 (S0)) 1 (S0)).

Приклад 4:

Розглянемо мову алгебраїчних виразів, словник якої складається з символів a, b, знаків +, -, /, *, а також символів (і). Можна запропонувати граматику типу 2 для породження ланцюжків цієї мови з початковим символом S і з наступними продукціями:

S→W+S,

S→W-S,

S→W,

W→W*W,

W→W/W,

W→(S),

W→α,

W→β.

Розглянемо виведення ланцюжка (a*b*b) – a/b з початкового символу даної граматики:

S=>W-S=>(S)-S=>(W+S)-S=>(a+S)-S=>(a+W)-S=>(a+W*W)-s=>(a+b*W)-S=>(a+b*b)-S=>(a+b*b)-W=>(a+b*b)-W/W=>(a+b*b)-a/W=>(a+b*b)-a/b.

Наведений спосіб опису виведення ланцюжка з початкового символу не зовсім зручний. Більше наглядним є використання так званого дерева виведення (виводу?). При цьому коренем дерева буде вершина, що має мітку початкового символу S. Всі підпорядковані їй вершини, позначені зліва направо A1…AN(n→1,Aiє VTUVN), відповідають символам продукції S→A1…An, яка першою використовувалася у виведенні S=>*α, де αєVT+. Аналогічно кожній вершині, позначеній нетермінальним символом, відповідає продукція, символи правої частини якої позначають вершини, безпосередньо підпорядковані даній вершині. На рис. 7.5 наведене дерево виведення для ланцюжка (a+b*b)-a/b.

Рисунок 7.5 – Дерево виведення ланцюжка мови алгебраїчного виразу (a+b*b)-a/b

Приклад 5:

На рис. 7.6 показане дерево синтаксичного розбору ланцюжка i+i*i для граматики з приклада 3 п. 7.2.4. Лівосторонньому виведенню ланцюжка відповідає обхід його дерева виведення зверху вниз і зліва направо. Аналогічно визначається й правостороннє виведення, тільки орієнтацію шляху обходу дерева необхідно поміняти на зворотну.

E

E + R

R R * F

F F

i i i

Рисунок 7.6 – Дерево синтаксичного розбору ланцюжка i+i*i

Приклад 6:

для мови арифметичних виражень з приклада 3 п. 7.2.4 граматика з правилами

E → E+E | E*E |i

неоднозначна, так як ланцюжок i+i*i має два дерева виведення:

E E

E + E E * E

E * E E + E

i i i i i i

Рисунок 7.7 – Неоднозначні дерева виведення

8.2 Методичні вказівки по організації самостійної роботи студентів

8.3 Контрольні питання і завдання

8.4 Приклади аудиторних і домашніх задач