3.7. Формальні граматики

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

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

Граматична мова — скінченна множина правил побудови об’єктів, їх аналізу та перетворень. Теорія формальних граматик сформульована у 50-ті роки американським лінгвістом М. Хомським, хоча основи, на яких вони базуються, були винайдені значно раніше. У теорії алгоритмів це системи, що знаходяться між скінченними абстрактними автоматами та нескінченними машинами Тьюринга.

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

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

Кожна граматика — це впорядкована четвірка символів G={V_T,V_H,P,S}, де V_T та V_H — відповідно термінальний та нетермінальний словники.

Термінальний словник — сукупність елементів, з яких будуються ланцюжки, породжувальні граматикою, так би мовити, предметна область граматики G (термінальні символи).

Нетермінальний словник — сукупність символів, якими позначено класи або ланцюжки вхідних елементів, тобто словник синтаксичних типів граматики (нетермінальні символи).

V = V_T U V_H — словник граматики G, V_T  V_H = .

У процесі перетворення ланцюжок може містити термінальні та нетермінальні символи одночасно.

S — початковий, виділений нетермінальний символ, що означає клас усіх мовних об’єктів, для опису яких призначена граматика. Символ S називають метою граматики.

P — правила підстановок граматики G:  à , де ланцюжок  має хоча б один символ  V_H .

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

Синтаксис мови — правила побудови речень у мові, або правила побудови конструкцій мови.

Семантика — тлумачення або пояснення цих конструкцій, тобто правила використання синтаксису, або правила надання мовній конструкції певного смислу.

Вимоги до граматики:

1) приписування кожному реченню мови його структурного опису (з яких елементів побудовано речення, який порядок їх розміщення);

2) граматика повинна бути скінченною.

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

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

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

Класифікація формальних граматик.

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

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

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

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

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

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

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

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

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

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

Нехай маємо граматику

G = {V_T, V_H, P, S},

де V_H = {S, B, C, D, E, F, K} — нетермінальний словник, символи якого означають:

S — речення (виділений символ);

B — група підмета;

C — група присудка;

D — іменник;

E — прикметник;

F — дієслово;

K — прислівник.

Термінальний словник

V_T = {a, b, c, d, e, f, i, j, k, e, m, n, p, r, t}, символи якого означають:

а — пес в — сніг с — малюк d — комар

е — білий f — пухнастий i — веселий j — бігає

к — кусає е — стрибає m — сміється n — падає

p — швидко r — голосно t — тихенько

Правила підстановок:

P = {SàBC, BàED, CàKF, Eàe, Eàf, Eài, Dàa, Dàb,

Dàc, Dàd, Kàp, Kàr, Kàt, Fàj, Fàk, Fàl, Fàm,Fàn}.

Таку граматику можна представити у вигляді графа (рис. 3.5):

Рис. 3.5. Граф породжувальної граматики

Виконуючи підстановки з множини Р, можна отримати будь-які речення, складені з термінальних символів, наприклад:

— веселий пес швидко бігає;

— білий сніг тихенько падає;

— пухнастий комар голосно сміється

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