МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ ВАСИЛЯ СТУСА
ФАКУЛЬТЕТ ІНФОРМАЦІЙНИХ ТА ПРИКЛАДНИХ ТЕХНОЛОГІЙ
Реферат
З дисципліни «Теорія формальних мов»
Виконав ст. гр. КНІТ-Б18-В
Мисак М. П.
Перевірив:
Римар П. В.
Вінниця 2021
Варіант 4
Контекстно-вільні граматики
Контекстно-вільною, або КВ-граматикою, називається граматика, в якій ліві частини всіх продукцій є нетерміналами. Зміст терміну "контекстно-вільна" полягає в тім, що застосування продукції A w до ланцюжка uAv не залежить, тобто є вільним від сусідніх з A символів, які утворюють контекст uv.
Зазначимо, що БНФ вигляду A::=w цілком аналогічна продукції A w. Отже, сукупності БНФ є просто іншою формою КВ-граматик.
Контекстно-вільною мовою (КВ-мовою) називається мова, що може бути задана КВ-граматикою.
КВ-граматики відіграють особливу роль у програмуванні, оскільки ними описується синтаксис практично всіх конструкцій мов програмування. Більше того, він описується КВ-граматиками, продукції яких задовольняють певні структурні обмеження. З використанням цих обмежень було побудовано алгоритми синтаксичного аналізу, час виконання яких прямо пропорційний довжині аналізованого слова. А лінійна складність цих алгоритмів великою мірою зумовила ефективність сучасних систем програмування.
Визначення формальних мов і граматик
Для побудови компілятора необхідне однозначне та точне задання вхідної та вихідної мов. Таке задання потребує визначення правил побудови допустимих конструкцій мови. Множину таких правил називають синтаксисом мови. Крім того, таке задання повинно включати визначення змісту кожної мовної конструкції. Таке визначення називають семантикою мови. Для побудови точних і недвозначних описів використовують метод абстракцій. При цьому вхідний тест розглядається як послідовність символів, яка побудована згідно з правилами граматики. Математичні моделі, що використовують подання текстів у вигляді послідовності символів, називають формальними мовами і граматиками.
Визначення.Кінцева множина символів, неподільних у даному розгляді, називається словником чи алфавітом, а символи, що входять у множину, – буквами алфавіту.
Наприклад, алфавіт A = {2, b, c, - , ?} містить 5 букв, а алфавіт B = {00, 01, 10, 11} містить 4 букви, кожна з яких складається з двох символів.
Визначення. Послідовність букв алфавіту називається словом чи ланцюжком у цьому алфавіті. Число букв, що входять у слово, називається його довжиною.
Наприклад, слово а = bbbc в алфавіті A має довжину l(a) = 4, а слово b = 0000110010 в алфавіті B має довжину l(b) = 5.
Якщо заданий алфавіт A, то позначимо A* множину всяких ланцюжків, що можуть бути побудовані з букв алфавіту A. При цьому передбачається, що порожній ланцюжок, який позначимо знаком $, також входить у множину A*.
Визначення. Формальною граматикою Г, що породжує ланцюжок символів, називається така сукупність чотирьох об'єктів:
Г = { I, Vт ,Va, R},
де Vт – термінальний алфавіт (словник); букви цього алфавіту називаються термінальними символами; з них будуються ланцюжки, породжувані граматикою; Vа – нетермінальний, допоміжний алфавіт (словник); букви цього алфавіту використовуються при побудові ланцюжків; вони можуть входити в проміжні ланцюжки, але не повинні входити в результат породження; I – початковий символ граматики, I Vа; R – множина правил граматики чи правил виведення вигляду , де і – ланцюжки, побудовані з букв алфавіту Vт Vа, що називають повним алфавітом (словником) граматики Г.
До множини правил граматики можуть також входити правила з порожньою правою частиною вигляду Е . Щоб уникнути невизначеності через відсутність символу в правій частині правила, умовимося використовувати символ порожнього ланцюжка, записуючи таке правило у вигляді Е $.
Щоб встановити закономірності побудови правил граматики, введемо наступні поняття.
Визначення. Нехай τ g– правило граматики Г і '" – ланцюжок символів, причому ', " (VтVа). Тоді ланцюжок ' може бути отриманий з ланцюжка шляхом застосування правила . У цьому випадку говорять, що ланцюжок безпосередньо виведений з ланцюжка і позначають .
Визначення. Якщо задана сукупність ланцюжків = (0, 1, ..., n), дляякоїіснує послідовність безпосередніх виведень
01, 12, ..., n-1n ,
то таку послідовність називають виведенням n з 0 у граматиці Г і позначають:
0* n.
Визначення. Множина кінцевих ланцюжків термінального алфавіту Vт граматики Г, виведених з початкового символу I, називається мовою, породжуваною граматикоюГ, і позначається L(Г).
L(Г) = {Vт | I *}.
Типи формальних мов і граматик
У теорії формальних мов виділяють 4 типи граматик, яким відповідають 4 типи мов. Такий розподіл зветься «граматична структура Хомського». Ці граматики виділяються шляхом накладення обмежень на правила граматики.
10.4.1. Граматики типу 0. Граматики типу 0, що називаються граматиками загального вигляду, не мають ніяких обмежень на правила породження. Будь-яке правило
R = {}
може бути побудоване з використанням довільних ланцюжків (Vт Va). Наприклад, RLW FWT x Ab xrtHVD.
10.4.2. Граматики типу 1. Граматики типу 1, що називаються також контекстно-залежними граматиками, не допускають використання будь-яких правил. Правила виведення в таких граматиках повинні мати вигляд:
1A212,
де 1,2 – ланцюжки, можливо порожні, з множини (Vт Va), символ А Va і ланцюжок (Vт Va). Ланцюжки 1 і2 залишаються незмінними при застосуванні правила, тому їх називають контекстом (відповідно лівим і правим), а граматику – контекстно залежною.
Граматики типу 1 значно зручніші на практиці, ніж граматики типу 0, оскільки в лівій частині правила замінюється завжди один нетермінальний символ, який можна зв'язати з деяким синтаксичним поняттям, у той час як у граматиці типу 0 можна заміняти відразу кілька символів, у тому числі й термінальних.
Наприклад, граматика: Г10.4: Vт= {a, b, c, d}, Va = {I, A, B},
R = { I aAI (1)
AI AAI (2)
AA ABA (3)
A b (4)
bBA bcdA (5)
bI ba} (6)
є контекстно залежною, оскільки друге і шосте правила мають непорожній лівий контекст, а третє і п'яте правила містять обидва контексти. Виведення у такій граматиці може мати вигляд:
I aAI aAAI abAI abbI abba.
10.4.3. Граматики типу 2. Граматики типу 2 називають контекстно вільними (КВ) граматиками, або безконтекстними граматиками.
Правила виведення таких граматик мають вигляд:
A,
де A Va і (Vт Va).
Очевидно, що ці правила випливають із правил граматики типу 1 за умови, що 1 = 2= $. Оскільки контекстні умови відсутні, то правила КВ–граматик виходять простіші, ніж правила граматик типу 1. Саме такі граматики використовують для опису мов програмування. Прикладом КВ–граматики може служити така граматика.
Г10.5: Vт= {a, b}, Va = {I},
R = {I aIa (1)
I bIb (2)
I aа (3)
I bb}. (4)
Ця граматика породжує мову, що складається з ланцюжків, кожний з яких у свою чергу складається з двох частин: ланцюжка Vт і дзеркального відображення цього ланцюжка '.
За допомогою правил цієї граматики може бути побудований, наприклад, ланцюжок:
IaIaabIbaabaIabaababbaba.
10.4.4. Граматики типу 3. Граматики типу 3 називають автоматними граматиками (А-граматиками). Правила виведення в таких граматиках мають вигляд:
Aa,або AaB,абоABa,
де aVт,і A, BVa, причому граматика може мати тільки правила вигляду A aB – правосторонні правила, або тільки вигляду ABa – лівосторонні правила. Прикладами автоматних граматик можуть бути правостороння граматика Г10.6 і лівостороння граматика Г10.7.
Г10.6: Vт= {a, b}, Va= {I, A, Z},
R = {I aI (1)
I aA (2)
AbA (3)
A aZ (4)
A bZ (5)
Z $}. (6)
Г10.7: Vт= {a, b}, Va= {I, A, Z},
R = {I Ab (1)
A Ab (2)
A Za (3)
Z Za (4)
Z $}. (5)
Ці граматики є еквівалентними і породжують мову
L(Г7) = {a...ab...b | n, m 0}.
Між множинами мов різних типів існує відношення включення:
{L типу 3} {L типу 2} {Lтипу 1} {L типу 0}.
Доведено, що існують: мови типу 0, що не є мовами типу 1; мови типу 2, що не є мовами типу 1; мови типу 3, які не є мовами типу 2.
З огляду на те, що найбільш практично застосовуються граматики типу 2 і типу 3, подальший виклад присвячується розгляду саме цих типів граматик.
Виведення ланцюжків
Формальні граматики дозволяють задавати мови, що являють собою множину ланцюжків, побудованих за визначеними правилами. Використовуваний спосіб завдання дозволяє будь-як побудувати ланцюжок, що належить мові. Щоб зробити процес побудови, що називається наочним виведенням, його зображають у вигляді графа, точніше, у вигляді дерева, яке називають синтаксичним деревом, або деревом виведення. З огляду на те, що виведення будь-якого ланцюжка, який належить мові, породжуваній заданою граматикою, повинно починатися з початкового символу, правила побудови дерева можна сформулювати так:
1) як початок чи вершину кореня дерева візьмемо вершину, яку позначимо початковим символом граматики I; ця вершина утворить нульовий ярус дерева;
2) якщо при виведенні ланцюжка, на черговому кроці використовується правило граматики A, і вершина, позначена нетермінальним символом A, розташована на ярусі з номером k – 1, то до побудованого дерева потрібно додати стільки вершин, скільки міститься символів у ланцюжку ; треба розташувати ці вершини на ярусі k , позначити їх символами ланцюжка і з'єднати ці вершини дугами з вершиною A.
Результатом виведення по дереву є множина кінцевих вузлів – листів, що виписуються при обході дерева ліворуч – униз і праворуч – нагору.
Розглянемо, наприклад, граматику Г10.10.
Г10.8: Vт= {a, b}, Va= {I},
R = {I aIb (1)
I ab},(2)
яка породжує мову L(Г8) = {aa...abb...b}, де а і b повторюються по n разів (n = 1, 2, ...).
Виведення ланцюжка за допомогою правил цієї граматики має вигляд дерева, відображеного на Рис. 10.1.
Рисунок 10.1 – Виведення ланцюжка aaabbb
10.5.1. Синтаксичний розбір. Виведення ланцюжка за допомогою правил граматики може бути задане не тільки у вигляді синтаксичного дерева. Якщо пронумерувати правила граматики, то послідовність номерів правил, які використані, також задає виведення.
Визначення. Послідовність номерів правил граматики Г, застосування яких дозволяє побудувати виведення заданого ланцюжка з початкового символу граматики, називається синтаксичним розбором ланцюжка.
Наприклад, у граматиці Г10.9:
Г10.9: Vт= {i, +, *, (, )}, Va= {E, T, P}
R = {E E + T (1)
E T (2)
T T * P (3)
T P (4)
P (E)(5)
P i},(6)
правила якої пронумеровані, виведенняланцюжка i * i + i буде таким:
E E + T T + T T * P + T P * P + T i * P + T i * i + T
i * i +P i * i + i
Отже послідовністьвикористання правил є такою – 1, 2, 3, 4, 6, 6, 4, 6.
Якщо в процесі побудови виведення з'являються проміжні ланцюжки, що містять кілька нетермінальних символів, то можна продовжувати виведення, заміняючи кожний з ланцюжків. Таким чином, ті самі правила можуть бути використані при виведенні ланцюжка у будь-якому порядку.
Наприклад, виведення ланцюжка i + i в граматиці Г10.9 може бути отримане декількома різними способами.
10.5.2. Ліве і праве виведення. Серед різних типів виведення найбільший інтерес становлять наступні два типи виведення.
Визначення. Якщо під час побудови виведення ланцюжка при застосуванні кожного правила заміняється самий лівий нетермінальний символ, то таке виведення називається лівим, або лівостороннім виведенням . Але, якщо при побудові виведення завжди заміняється самий правий нетермінальний символ проміжного ланцюжка, то таке виведення називається правим, або правостороннім виведенням .
Наприклад, вище наведене виведення ланцюжка i * i + i в граматиці Г10.9 є лівостороннім виведенням. Слід зазначити, що різним виведенням ланцюжка i + i в граматиці Г10.9 відповідає те ж саме синтаксичне дерево. Аналогічна ситуація має місце і при виведенні ланцюжка i * i + i.
Виключення ланцюгових правил
Правило граматики вигляду A B, де A, B Va, називається ланцюговим. ДляКВ-граматики Г, яка містить ланцюгові правила, можна побудувати еквівалентну їй граматику Г′, яка не містить ланцюгових правил.
Ідея доведення полягає в наступному. Якщо схема граматики має вигляд
R = {..., A B, ..., B C, ..., C aX},
то така граматика еквівалентна граматиці зі схемою
R' = {..., A aX, ...},
оскільки виведення у граматиці зі схемою R ланцюжка aX:
A B C aХ
може бути отримано у граматиці зі схемою R' за допомогою правила A aX.