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

План:

1 Терміни
2 Породжують граматики
3 Аналітичні граматики

Введення

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

1. Терміни

Термінал (термінальний символ) - об'єкт, безпосередньо присутній у словах мови, відповідного граматиці, і має конкретне, незмінне значення (узагальнення поняття "букви"). У формальних мовами, що використовуються на комп'ютері, як терміналів зазвичай беруть всі або частину стандартних символів ASCII - латинські букви, цифри і спец. символи.
Нетермінал (нетермінальний символ) - об'єкт, що позначає будь-яку сутність мови (наприклад: формула, арифметичний вираз, команда) і не має конкретного символьного значення.

2. Породжують граматики

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

Щоб задати граматику, потрібно задати алфавіти терміналів і нетерміналів, набір правил виведення, а також виділити в безлічі нетерміналів початковий.

Отже, граматика визначається наступними характеристиками:

Σ - Набір ( алфавіт) термінальних символів
N - набір ( алфавіт) нетермінальних символів
P - набір правил виду: "ліва частина" "Права частина", де:
- "Ліва частина" - непорожній послідовність терміналів і нетерміналів, що містить хоча б один нетермінал
- "Права частина" - будь-яка послідовність терміналів і нетерміналів
S - стартовий (початковий) символ з набору нетерміналів.

2.1. Висновок

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

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

2.2. Типи граматик

За ієрархії Хомського, граматики діляться на 4 типи, кожний наступний є більш обмеженим підмножиною попереднього (але й легше піддається аналізу):

тип 0. необмежені граматики - можливі будь-які правила
тип 1. контекстно-залежні граматики - ліва частина може містити один нетермінал, оточений "контекстом" (послідовності символів, у тому ж вигляді присутні в правій частині); сам нетермінал замінюється непорожній послідовністю символів у правій частині.
тип 2. контекстно-вільні граматики - ліва частина складається з одного нетермінала.
тип 3. регулярні граматики - простіші, еквівалентні кінцевим автоматам.

2.3. Застосування

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

2.4. Приклад - арифметичні вираження

Розглянемо просту мову, що визначає обмежена підмножина арифметичних формул, що складаються з натуральних чисел, дужок і знаків арифметичних дій. Варто зауважити, що тут у кожному правилі з лівого боку від стрілки $\ Rightarrow$ варто тільки один нетермінальний символ. Такі граматики називаються контекстно-вільними.

Термінальний алфавіт:

 Σ  = {0 ", '1 ', '2', '3 ', '4', '5 ', '6', '7 ', '8', '9','+','-', '*','/','(',')'}.

Нетермінальний алфавіт:

 {ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА}

Правила:

 1. ФОРМУЛА  ФОРМУЛА ЗНАК ФОРМУЛА (формула є дві формули, з'єднані знаком) 2. ФОРМУЛА  ЧИСЛО (формула є число) 3. ФОРМУЛА  (ФОРМУЛА) (формула є формула в дужках) 4. ЗНАК  + | - | * | / (Знак є плюс або мінус або помножити або розділити) 5. ЧИСЛО  ЦИФРА (число є цифра) 6. ЧИСЛО  ЧИСЛО ЦИФРА (число є число і цифра) 7. ЦИФРА  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра є 0 або 1 або ... 9)

Початковий нетермінал:

 ФОРМУЛА

Висновок:

Виведемо формулу (12 +5) за допомогою перерахованих правил виводу. Для наочності, сторони кожної заміни показані попарно, в кожній парі замінна частина підкреслена.

ФОРМУЛА $\ Rightarrow_3 \! \,$ (ФОРМУЛА)

(ФОРМУЛА) $\ Rightarrow_1 \! \,$ (ФОРМУЛА ЗНАК ФОРМУЛА)

(ФОРМУЛА ЗНАК ФОРМУЛА) ${\ Rightarrow_4 \! \,}$ (ФОРМУЛА + ФОРМУЛА)

(ФОРМУЛА + ФОРМУЛА) ${\ Rightarrow_2 \! \,}$ (ФОРМУЛА + ЧИСЛО)

(ФОРМУЛА + ЧИСЛО) ${\ Rightarrow_5 \! \,}$ (ФОРМУЛА + ЦИФРА)

(ФОРМУЛА + ЦИФРА) ${\ Rightarrow_7 \! \,}$ (ФОРМУЛА + 5)

(ФОРМУЛА + 5) ${\ Rightarrow_2 \! \,}$ (ЧИСЛО + 5)

(ЧИСЛО + 5) ${\ Rightarrow_6 \! \,}$ (ЧИСЛО ЦИФРА + 5)

(ЧИСЛО ЦИФРА + 5) ${\ Rightarrow_5 \! \,}$ (ЦИФРА ЦИФРА + 5)

(ЦИФРА ЦИФРА + 5) ${\ Rightarrow_7 \! \,}$ (1 ЦИФРА + 5)

(1 ЦИФРА + 5) ${\ Rightarrow_7 \! \,}$ (1 2 + 5)

3. Аналітичні граматики

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

Джерела

Гладкий А. В. Формальні граматики і мови - М .: Наука, 1973.
Касьянов В. Н. Лекції з теорії формальних мов, автоматів і складності обчислень. - К.: НГУ. - 1995. - 112 с.
Хомський Н., Міллер Дж. Введення в формальний аналіз природних мов / / Кібернетичний збірник / За ред. А. А. Ляпунова та О. Б. Лупанова - М .: Світ, 1965.