Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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


Дерево складових

План:


Введення

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


1. Терміни

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

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

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

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

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

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

2.1. Висновок

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

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


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

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


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


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

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

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

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

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

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

Правила:

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

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Формальна семантика
Формальна логіка
Формальна система
Формальна верифікація
Формальна мова
Формальна верифікація
Формальна система
Ім'я (граматика)
Граматика
© Усі права захищені
написати до нас
Рейтинг@Mail.ru