Основні поняття теорії мов та граматик

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

Форма́льна мо́ва — це множина скінчених послідовностей символів (“слів” і “речень”), спосіб побудови яких описується правилами певного виду.

Будь-яка формальна мова характеризується:

• алфавітом - набором знаків (символів) з яких можна складати слова і фрази даної мови;

§ синтаксисом (граматикою) - правилами побудови із символів алфавіту таких мовних конструкцій, як “слова”, “речення” і “тексти”;

• семантикою - набором правил використання мовних конструкцій, які встановлюють відповідність між структурними одиницями тексту і правилами їх інтерпретації.

Якщо Т — алфавіт мови, то як Т* позначають множину рядків (послідовностей символів), які можуть бути побудовані з символів алфавіту Т. При цьому передбачається, що порожній рядок (позначається як ε) також входить у множину Т*:

,

де Т⁺ — множина усіх можливих рядків, складених з символів алфавіту Т, окрім порожнього рядка ε.

Кожна мова в алфавіті Т - це підмножина множини Т*. Наприклад, якщо алфавіт заданий як { a, b }, а мова L включає в себе всі слова над ним, то слово ababba належить L.

Для задання формальної мови підходить будь-яке математично коректне визначення множини слів в заданому алфавіті. Так формальна мова може бути визначена

- простим перерахуванням слів, що входять в дану мову (цей спосіб, в основному, прийнятний для визначення мов простої структури).

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

- словами, породженими регулярним виразом,

- словами, породженими БНФ-конструкцією, тощо.

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

Формальна граматика (граматика формальної мови) — це множина правил породження слів, виразів і речень формальної мови. Ці правила називають ще синтаксисом мови.

Формальною граматикою G для породження формальної мови в алфавіті T є набір

G ={ T, N, P, S },

де

· T – множина символів алфавіту (термінальних символів[1]) або термінальний словник мови (її алфавіт). Термін "алфавіт" щодо формальних мов майже повністю відповідає його неформальному визначенню в розмовних мовах і відрізняється лише тим, що включає всі можливі символи, в той час як, наприклад, крапка, кома, знак переносу, знак оклику і т.п. при неформальному визначенні розмовних мов в алфавіт не включаються. З точки зору мов програмування, це - імена змінних, службові слова, знаки операцій тощо.

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

· P – множина правил граматики за допомогою яких будується нетермінальний словник (синтаксичні конструкції). Множину правил граматики ще називають синтаксисом мови.

· S - мета граматики (аксіома) - старший нетермінальний символ (), що визначає клас мовних об’єктів, для опису яких призначена граматика G. По аналогії з розмовною мовою це, наприклад, текст; в мовах програмування це - програма.

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

Правила граматики описують відношення між нетерміналами і терміналами шляхом визначення нетермінального символа через комбінацію термінальних і нетермінальних символів. Кожне таке правило P має вигляд , де , — елементи із словника граматики V = T È N, причому елемент містить принаймні один нетермінал. Таке правило означає, що послідовність символів у процесі виводу можна замінити на рядок .

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

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

У формальних граматиках послідовності символів інтерпретуються як мовні об’єкти різних рівнів. На рівні граматики визначаються поняття (нетермінали), послідовне розкриття яких (їх виведення), в кінці кінців дає їх представлення у вигляді послідовностей термінальних символів. Поняття бувають

§ осмислені – мовні конструкції, для яких визначена та або інша дія,

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

Мінімальні осмислені поняття відповідають лексемам; мінімальні допоміжні поняття подібні до знаків пунктуації.

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

Для прикладу опишемо формальну граматику, яка породжує математичні вирази (суми):

1. Сума → Цифра

2. Сума → Сума + Цифра

3. Сума → Сума - Цифра

4. Цифра → 1.. 9

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

Виходячи із даної аксіоми та застосовуючи наведені вище правила, можна отримати наступні вирази (рядки):

	Сума	Аксіома
	Сума − Цифра	Застосовано правило 3
	Сума + Цифра − Цифра	Застосовано правило 2
	Цифра + Цифра − Цифра	Застосовано правило 1
	1+ Цифра − Цифра	Застосовано правило 4
	1+2− Цифра	Застосовано правило 4
	1+2−9	Застосовано правило 4

Порядок застосування правил довільний. Граматика визначає лише правила, які дозволяється використовувати у поточній ситуації, і не дає вказівок, які правила мають бути застосовані. Наприклад, до першого речення (аксіоми) можна застосувати лише правила 1—3, та не можна застосувати правило 4. Починаючи з 4 речення можливе застосування лише правила 4.

Процес виводу слова в формальній граматиці може бути графічно представлений у вигляді синтаксичногодерева, кореневою вершиною якого є мета граматики, в проміжних вершинах знаходяться нетермінали, а «листям» є термінали. Розглянемо наступну граматику:

Виведенню відповідає наступне синтаксичнедерево:

Крона цього дерева виводу - ababab.

З математичної точки зору формальна мова - це множина рядків символів в алфавіті T, які можуть бути отримані із аксіоми шляхом кінцевого числа застосувань правил P граматики G.

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

Теорія формальних граматик сформульована у 50-ті роки американським лінгвістом Хомським (Чомскі).

Дата добавления: 2014-01-13