ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ. Звіт з Лiнгвiстичне забезпечення САПР. Робота № 531339

ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

ТГВ

Кафедра:

Кафедра САПР

Інформація про роботу

Рік:

2020

Тип роботи:

Звіт

Предмет:

Лiнгвiстичне забезпечення САПР

Група:

КН-413

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національний університет «Львівська політехніка» Кафедра САПР Звіт з виконання Лабораторної роботи №4 на тему: ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ з курсу: «Лінгвістичне забезпечення САПР» 1. МЕТА РОБОТИ Ознайомитись з автоматами і лінійними граматиками, проаналізувати їх розв’язок із скінченими автоматами. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ На перших порах наука про мову – лінгвістика зводилась до вивчення природних мов, їх класифікації виявлення різниці та подібності між ними. З виникненням ЕОМ і мов програмування поняття значно розширилось. Виникла потреба створення формального математичного апарату – формальних граматик як механізму описання мов програмування і проектування. Сформулюємо деякі визначення. Неформально визначити можна як підмножину множин всіх речень із слів або символів деякого основного словника. Алфавіт – це непуста скінчена множина елементів, які називаються символами. Ланцюжком називається будь-яка скінчена послідовність алфавіту . Довжина ланцюжка дорівнює кількості символів у ньому: , . За способом задання правильних ланцюжків формальні граматики поділяються на породжуючі і розпізнаючі. До породжуючих належать граматики, які встановлюють правила побудови будь-якого правильного ланцюжка і визначають структуру так, що не можна побудувати жодного неправильного ланцюжка. Розпізнаючі граматики дають змогу встановити, чи є правильним довільно вибраний ланцюжок, якщо він правильний, визначити його будову. Для побудови трансляторів використовують обидва ці способи: породжуючу граматику для описання синтаксису мови програмування і розпізнаючий пристрій – скінчений автомат як модель алгоритму розпізнавання речень мови. Породжуючою граматикою називається впорядкована четвірка: . де - основний термінальний алфавіт; - скінчений нетермінальний алфавіт; - початковий нетермінальний символ – аксіома; - скінчена множина підстановок (продукцій), ліві і праві частини – це ланцюжки та , які містять символи термінального і нетермінального алфавітів. Символи термінального алфавіту є елементарними одиницями мови. Символи нетермінального алфавіту є метазмінними, які використовують при виведені правильних ланцюжків. Початковий символ - це метазмінна з якої виводяться всі правильні ланцюжки. Множина – граматичні правила мови, яку визначають. Щоб відрізнити термінальні символи від нетермінальних, прийнято не термінальні символи поміщати в кутові дужки. ФОРМА БЕКУСА-НАУРА Таке подання граматики є нормальною формою Бекуса (БНФ) і є першою метамовою, яка використовувалась для описання синтаксису алгоритмічної мови «Алгол-60». Основним призначенням форми Безуса – Наура є представлення в стислому і компактному вигляді формальних і однозначних правил написання основних конструкцій мови програмування. У формі Бекуса описуються два класи об’єктів: 1. основні символи мови (термінальні символи); 2. мета лінгвістичні змінні (не термінальні символи). Кожна металінгвістика форма описує правила побудови конструкцій мови і складається з двох частин. Ліворуч мета лінгвістична змінна, яка визначає відповідну конструкцію. Далі металінгвістична зв’язка , що означає «визначається як». Праворуч – формули, що означають один або декілька варіантів побудови конструкції. Для побудови відповідної конструкції необхідно вибрати відповідний варіант з правої частини формули і підставити його замість відповідної металінгвістичної змінної. Такий процес називається і позначається символам . КЛАСИФІКАЦІЯ ФОРМАЛЬНИХ ГРАМАТИК Вирішальний вплив на властивості мови, складність породження і розпізнавання ланцюжків мають правила підстановки множини , тобто граматичні правила мови. Класифікація мов буда запропонована в 1959 році американським лінгвістом Н. Хомським. Він запропонував класифікувати формальні мови за типом правил породжуючих граматик. Клас 0. Правила виводу граматики мають таку форму , без будь-яких обмежень на ланцюжки та . Ці мови є моделлю природних мов. Клас 1. Контекстно-залежні мови або граматика безпосередніх складових (НС - граматики) з граматикою , де - довільні можливо і пусті ланцюжки з алфавіту ; - лівий; - правий контекст; - нетермінальний символ; - непустий ланцюжок з множини . Клас 2. Контекстно-вільні граматики (КВ - граматики). Мають правила виводи вигляду: , де - нетермінальний символ; - довільний непустий ланцюжок з множини . Мови породжені КВ – граматикою, називаються контекстно-вільними. Вони найчастіше використовуються для описання мов програмування в мов проектування. Клас 3. Лінійні (ЛН) і автоматні (А) граматика. Лінійні мають продукцію , де або : , . Автоматні , де , . Лінійні і автоматні мови мають скінчену кількість станів і можуть представлятися скінченими автоматами. Алгоритми розпізнавання лінійних і автоматних мов досить прості і використовуються для аналізу простих мов, найчастіше на етапі лексичного аналізу. ЗВ'ЯЗОК РЕГУЛЯРНИХ МОВ ІЗ СКІНЧЕННИМИ АВТОМАТОМ Граматики, які мають продукції вигляду або , де , , називаються регулярними і можуть описуватися скінченним автоматом. Правила переходу від скінченного автомата до формальної граматики: 1. Множиною термінальних символів зробити множину вхідного алфавіту. 2. Множиною нетермінальних символі зробити множину стані. 3. Початковим символом зробити початковий стан автомата. 4. Якщо в автоматі є перехід із стану в стан по входу , то в граматиці це відобразиться правилом: . 5. Якщо - допускаючий стан автомата, то в граматиці вводиться правила: , де - пуста множина. 3. ВИКОНАННЯ РОБОТИ ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Варіант №17 Скласти програму для розпізнавання ланцюжків, які породжуються конкретною формальною граматикою. Для розпізнавання використати скінченний автомат. SAB AaA|a BbB|b Бінарне дерево ПОСЛІДОВНІСТЬ КОНФІГУРАЦІЙ bbb…bbb aaa…aaa СКІНЧЕНИЙ АВТОМАТ b X X A F X B F X F ТЕКСТ ПРОГРАМИ НА МОВІ ПРОГРАМУВАННЯ С using System; namespace Lab04 { class endedAutomat { private string str; private char[] sl; private char[] tableOfStanes; private char[,] conf; private byte stan; public endedAutomat(string str) { this.str = str; sl = new char[3]; sl[0] = 'a'; sl[1] = 'b'; tableOfStanes = new char[5]; tableOfStanes[0] = 'S'; tableOfStanes[1] = 'A'; tableOfStanes[2] = 'B'; tableOfStanes[3] = 'X'; tableOfStanes[4] = 'F'; stan = 0; conf = new char[5, 2]; conf[0, 0] = tableOfStanes[1]; conf[0, 1] = tableOfStanes[3]; conf[1, 0] = tableOfStanes[2]; conf[1, 1] = tableOfStanes[3]; conf[2, 0] = tableOfStanes[3]; conf[2, 1] = tableOfStanes[4]; } public char getStan() { return tableOfStanes[this.stan]; } public void getAllowance() { byte first_second = 1; for (int i = 0; i < str.Length; i++) { if (stan == 3) { break; } else { switch (stan) { case 0: if (str[i] == sl[0]) { stan = 1; } else if (str[i] == sl[1]) { stan = 2; } break; case 1: if (str[i] == sl[0]) { stan = 1; } else if (str[i] == sl[1]) { stan = 3; } break; case 2: if (str[i] == sl[0]) { stan = 3; } else if (str[i] == sl[1]) { stan = 2; } break; }//End switch (stan) }//End else }//End for (int i = 0; i < str.Length; i++) }//End public void getAllowance() }//End class endedAutomat class Program { static void Main(string[] args) { string str; Console.WriteLine("Enter string:"); str = Console.ReadLine(); endedAutomat gr = new endedAutomat(str); gr.getAllowance(); if (gr.getStan() == 'A' || gr.getStan() == 'B') { Console.WriteLine("Strichka was allowed..."); } else { Console.WriteLine("Strichka was´nt allowed..."); } } } } Результати виконання програми Enter string: aaaaaaaaaa String was allowed... Enter string: aaabbb String wasn't allowed... 4. Висновок На цій лабораторній роботі, я ознайомився з автоматами і лінійними граматиками, проаналізував їх розв’язок із скінченими автоматами. Написав програму, яка допускає правильні рядки. Переконався, що вона працює і виводить коректний результат.

Звіт Лiнгвiстичне забезпечення САПР

horuktaras

17.07.2020 15:49

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись