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

1. висновок [ правити | правити код ]
2. Типи граматик [ правити | правити код ]
3. застосування [ правити | правити код ]

open wikipedia design.

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

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

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

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

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

висновок [ правити | правити код ]

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

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

Типи граматик [ правити | правити код ]

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

Крім того, виділяють:

застосування [ правити | правити код ]

Приклад - арифметичні вираження [ правити | правити код ]

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

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

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

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

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

Правила:

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

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

ФОРМУЛА

висновок:

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

ФОРМУЛА → 3 {\ displaystyle {\ stackrel {3} {\ to}}} (ФОРМУЛА) (ФОРМУЛА) → 1 {\ displaystyle {\ stackrel {1} ​​{\ to}}} (ФОРМУЛА ЗНАК ФОРМУЛА) (ФОРМУЛА ЗНАК ФОРМУЛА) → 4 {\ displaystyle {\ stackrel {4} {\ to}}} (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА) → 2 {\ displaystyle {\ stackrel {2} {\ to}}} (ФОРМУЛА + ЧИСЛО) (ФОРМУЛА + ЧИСЛО) → 5 {\ displaystyle {\ stackrel {5} {\ to}}} (ФОРМУЛА + ЦИФРА) (ФОРМУЛА + ЦИФРА) → 7 {\ displaystyle {\ stackrel {7} {\ to}}} (ФОРМУЛА + 5) (ФОРМУЛА + 5) → 2 {\ displaystyle {\ stackrel {2} {\ to}}} (ЧИСЛО + 5) (ЧИСЛО + 5) → 6 {\ displaystyle {\ stackrel {6} {\ to}}} (ЧИСЛО ЦИФРА + 5) (ЧИСЛО ЦИФРА + 5) → 5 {\ displaystyle {\ stackrel {5} {\ to}}} (ЦИФРА ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) → 7 {\ displaystyle {\ stackrel {7} {\ to}}} (1 ЦИФРА + 5) (1 ЦИФРА + 5) → 7 {\ displaystyle {\ stackrel {7} {\ to}}} (1 2 + 5)

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

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