Побудова розпізнавача для заданої граматики і реалізація його у вигляді програми яка перевіряє

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
КАФЕДРА
КОМП'ЮТЕРНИХ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
Курсова робота
з дисципліни
"Основи дискретної математики"
Тема: "Побудова розпізнавача для заданої граматики і реалізація його у вигляді програми, яка перевіряє вводяться користувачем ланцюжка"
2006

Завдання на курсову роботу

з дисципліни "Основи дискретної математики"

Завдання на виконання роботи:
1. Роль інформаційних технологій в побуті сучасної людини.
2. Докладна довідка щодо теоретичних аспектів формальних граматик та їх перетворення.
3. Виконати дослідження і перетворення вихідної граматики:
G [Q] = (VT = {a, b, h}; VN = {Q, A, B, H}; P = {Q è a QH;
Q è bah A; A è ab B h; H è bB; B è abb H h; H è e}) (e - порожня ланцюжок).
Побудувати распознаватель для перетвореної граматики і реалізувати його у вигляді програми, яка перевіряє текстові файли і вводяться користувачем ланцюжка.
Роботу необхідно виконати відповідно до графіка і вимогами до виконання курсової роботи з основ дискретної математики;
Зміна та уточнення теми за згодою викладача можливо тільки на першому етапі роботи;
Готова робота здається на перевірку не пізніше, ніж за день до захисту.

Реферат

Курсова робота з дисципліни "Основи дискретної математики" на тему: "Побудова М П-розпізнавача для задається користувачем довільній граматики" містить 21 сторінку машинописного тексту, 5 рисунків, 3 таблиці, сторінок додатку.
У роботі розглянуто один з розділів дискретної математики - "Класифікація граматик; еквівалентні перетворення КС-граматик", розроблений програмний продукт, з допомогою якого можна перевірити задається користувачем граматику і спростити її за допомогою еквівалентних перетворень правил.
Ключові слова:
дискретна математика, КС-граматика, S-граматика, правило граматики; термінальний символ; нетермінальний символ; дерево виводу; еквівалентні перетворення; сентенціальная форма.

Введення

Роль інформаційних технологій в побуті сучасної людини.
За останні кілька років людство зробило дивовижний ривок у області розвитку комп'ютерних, і внаслідок цього, інформаційних технологій. Всього якихось десять років тому середньостатистичний громадянин не міг і мріяти про власний персональному комп'ютері. У середині 80-х рокiв ЕОМ були прерогативою великих підприємств, обслуговування цих машин здійснювалося через розгалужену мережу спеціалізованих сервісних центрів. Найчастіше багато підприємств не мали достатньо кваліфікованих кадрів для монтажу та обслуговування своїх ЕОМ. Відповідно і проблеми зв'язку між обчислювальними комплексами вставали у вузькому колі фахівців. Незважаючи на те, що перші експериментальні мережі передачі пакетів даних було створено в 1961 році Defence Advanced Research Agency (DARPA) за завданням міністерства оборони США, в нашій країні вони застосовувалися лише в окремих галузях народного господарства та у військовій області.
Технологічний стрибок останнього десятиліття, особливо показовий у галузі комп'ютерних технологій, дозволив розробити серію сучасних персональних комп'ютерів. Мікро ЕОМ поступово почали входити в наше повсякденне життя. Згідно з журналом "Світ Internet" в Росії в приватному користуванні знаходиться більше 50 тис. персональних комп'ютерів. Новітні технології компаній IBM, Intel зробили можливою розробку потужних, багатофункціональних персональних ЕОМ, економічно доступних середньому та нижньо-середнього класу громадян. Комп'ютерні та інформаційні технології впевнено входять в наше життя. Зараз персональні ЕОМ можна зустріти не тільки в офісах великих і дрібних фірм, на виробництві та в навчальних закладах, комп'ютери все частіше можна зустріти вдома у інженерів і школярів, науковців та бізнесменів.
Персональна ЕОМ давно перетворилася на предмет праці, жодне підприємство не обходиться без електронної бази даних, без сучасних засобів комунікацій, потужних обчислювальних засобів. Не менш важливу роль відіграють ЕОМ і в побуті сучасного росіянина. Функції домашнього комп'ютера різноманітні. Він дозволяє здійснювати не тільки виробничий процес на дому, але і цілий ряд різноманітних процесів. Сучасні розробки дозволяють здійснювати управління електричними побутовими приладами, приймати радіо і телепередачі, комп'ютер у сполученні зі сканером і принтером є фактично домашнім офісом, що дозволяє виконувати обробку будь текстової чи графічної інформації. Рекреаційна роль персональних домашніх комп'ютерів не може бути обділена стороною. Численні комп'ютерні ігри дозволяють організувати дозвілля відповідно до інтересів конкретної людини. Мультимедійні програми можуть набагато полегшити засвоєння навчального матеріалу як студентам і школярам, ​​так і всі спраглим самоосвіти.
Окремої згадки заслуговує інформаційна складова комп'ютерних технологій. За даними ЮНЕСКО до 1950 р. кількість інформації, якої оперувало суспільство, подвоювалося за десять років, до 70 р. - за п'ять років, до 1980 - за два роки, з початку 90-х кількість інформації подвоюється за рік. В даний час до 80% працездатного населення тим чи іншим чином професійно задіяні у сфері отримання, розповсюдження або обробки інформації. Засоби поширення інформаційних потоків так само зазнали значної еволюції. Засоби теле та радіо зв'язку увійшли в кожний дім, друковані видання доступні передплатникам по всьому світу. Проте нові реалії часу представляють нові вимоги і до способів поширення та обробки інформації. Візьмемо на себе сміливість стверджувати, що засоби електронного зв'язку з використанням новітньої обчислювальної техніки представляють на сьогоднішній день найкращі можливості в області поширення й обробки інформаційних потоків. Всесвітня комп'ютерна мережа Internet є найбільш відомим носієм інформації. Internet - глобальна комп'ютерна мережа, що охоплює весь світ. Сьогодні Internet має близько 15 мільйонів абонентів у більш ніж 150 країнах світу. Щомісяця розмір мережі збільшується на 7-10%. Все більше людей звертаються до послуг електронної пошти, що дає можливість пересилки текстової, графічної, практично будь-якого виду інформації чи даних в будь-яку точку світу за лічені хвилини. Бази даних, сервера спеціалізованої інформації, телеконференції, файлові сервера, в даний час вже важко уявити життя сучасного спеціаліста або вченого без цих нововведень. Вже є розробки, які обіцяють безліч нових можливостей, серед них Internet-телефонія, передача відео та графічної інформації.
Стрімкий розвиток науково-технічного прогресу висуває нові вимоги і до якості інформатизації суспільства. Ми вважаємо особливо важливим розвиток саме інформаційної складової комп'ютерних технологій. На сьогоднішній день це найбільш важлива і найбільш динамічно розвивається галузь народного господарства Росії і промисловості всього світу. Особливо важливим, безсумнівно, є вдосконалення інфраструктури систем зв'язку. Якщо раніше глобальну мережу Internet в основному підтримували великі університети та промислові підприємства, то сьогодні все більше людей хочуть отримувати інформацію прямо з дому, а не лише зі свого робочого місця.

1. Теоретичні основи розроблюваної теми

1.1 Загальні відомості про граматиках

У розширеному виставі під терміном "мова" розуміють всякий засіб спілкування, яке складається з:
- Знакової системи, тобто безлічі допустимих послідовностей знаків;
- Безлічі смислів цієї системи;
- Відповідності між послідовностями знаків і смислами, що роблять осмисленими допустимі послідовності знаків.
Знаками можуть бути букви алфавіту, математичні позначення, звуки, ритуальні дії і т.д. Hаука про осмислені знакових системах називається семіотикою. Найбільш дослідженими є знакові системи, у яких знаками є символи алфавіту. Правила, що визначають безліч текстів (допустимих послідовностей знаків), утворюють синтаксис мови; опис безлічі смислів і відповідності між текстами та змістами - семантику мови. До таких знакових систем відносяться природні мови, мови різних галузей науки, мови програмування.
Семантика мови істотно залежить від призначення мови, в той час, як для синтаксису можна сформулювати поняття і методи, які не залежать від призначення і цілей мови. Для дослідження синтаксису склався спеціальний математичний апарат - теорія формальних граматик, в якому мова розуміється вже не як засіб спілкування, а як безліч формальних об'єктів - послідовностей символів алфавіту. Ці послідовності називають ланцюжками і мову розуміють як безліч ланцюжків.
Нехай заданий алфавіт V, в якому можна побудувати безліч V * (читається - ітерація алфавіту V) ланцюжків. Формальна мова L в алфавіті V - це підмножина ланцюжків з V * (L Ì V *). Опис формальних мов здійснюється за допомогою формальних граматик, що породжують (формальних граматик).
Формальна породжує граматика G (надалі - граматика G) - це формальна система, обумовлена ​​четвіркою об'єктів:
G [Z] = (VN, VT, Z, P),
де VN - алфавіт нетерміналів (допоміжних символів);
VT - алфавіт терміналів (основних символів);
Z - початковий символ (аксіома) граматики;
P - кінцеве безліч правил.
Hетермінали прийнято позначати великими літерами латинського алфавіту, термінали - малими буквами. У алфавіт нетерміналів обов'язково входить початковий символ граматики.
Кожне правило з безлічі P має вигляд x à y, - де x, y ланцюжки, що складаються з термінальних і нетермінальних символів. Надалі будемо розглядати граматики, що містять тільки правила, ліві частини яких складаються з одного нетермінального символу (контекстно-вільні граматики). При цьому має бути хоча б одне правило, ліва частина якого - початковий символ граматики.
Граматика описує нескінченний мову, якщо хоча б одне з правил рекурсивно, тобто у правій частині міститься його ліва частина в явному або неявному вигляді.
Приклад: Задано граматика G [Z]: VN = {Z, A, B}; VT = {a, b, c}; Z-початковий символ.
P = {Z à ABc; (1)
A à aB; (2)
B à b}. (3)
За допомогою граматики G можна продукувати (отримувати) ланцюжка в алфавіті терміналів.
Порядок виводу можна записати в наступному вигляді:
(1) (2) (3) (3) (номери застосованих правил)
Z à AВc à aBВc à aBbc à abbc.
Висновок продовжується до тих пір, поки на черговому кроці не вийде ланцюжок, що складається тільки з термінальних символів (тобто не можна застосувати ні одне з правил виводу).
Скорочено висновок можна записати, пропустивши проміжні результати, так Z + à abbc (ланцюжок abbc виведена з початкового символу Z в заданій граматиці).
Сентенціальная форма - будь-яка ланцюжок термінальних і нетермінальних символів, яка виходить на будь-якому кроці процесу виведення. Безліч сентенціальних форм можна отримати з дерева виведення, обходячи його по вузлах і дотримуючись таких правил:
- Починати обхід з самого лівого вузла;
- Обхід треба здійснювати так, щоб при переході до наступного вузла утворене піддерево не включало, як елемент, попереднє піддерево.
Фраза - частина сентенціальной форми, виведена з одного нетермінала за кілька кроків. Для простої фрази крок виведення дорівнює 1.
Одну й ту ж ланцюжок можна отримати, застосовуючи правила в різних послідовностях (дерева висновків різні). Якщо для однозначності в
процесі виведення на кожному кроці застосовувати правило до самого лівому (правому) нетерміналу в сентенціальной формі, то отримаємо лівобічний (правобічний) висновок. Таким чином:
1. Кожній ланцюжку виведеної в заданій граматиці відповідає одне або кілька дерев виводу.
2. Кожному дереву відповідає один або більше висновків.
3. Кожному дереву відповідає єдиний правий і єдиний лівий висновки.
4. Якщо кожній ланцюжку, що виводиться в даній граматиці, відповідає єдине дерево виведення, то така граматика називається однозначною (у правій частині кожного правила такої граматики міститься не більше одного нетермінала).
Мовою L (G), породжуваним граматикою G, називається безліч всіх ланцюжків в алфавіті термінальних символів VT, що виводяться з початкового символу граматики.
У процесі функціонування граматики можливі два варіанти:
1. Перевіряти ланцюжка на приналежність їх до мови, породжуваному заданої граматикою. Варіанти цього процесу можуть бути наступними:
а) виведення ланцюжки з початкового символу граматики (побудувати дерево виводу або висновок починаючи з кореня) - спадний висновок;
б) висновок можна також робити починаючи з крони дерева (готового пропозиції); якщо вдається прийти до початкового символу, то пропозиція належить заданої граматики - висхідний висновок.
В обох варіантах будується дерево виводу.
2. Отримувати ланцюжка, які належать до мови, породжуваному заданої граматикою.

1.2 Класифікація граматик

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

0-й тип - граматики з фразовой структурою. Правила мають вигляд: x à y, де x і y - будь-які ланцюжка терміналів і нетерміналів. 1-й тип - контекстно-залежні (КЗ) граматики. Правила мають вигляд x à y, де | x | <= | y | (права ланцюжок не коротше лівої). 2-й тип - контекстно-вільні (КС) граматики (вид правил A à y, де A - нетермінал, y - будь-яка ланцюжок). 3-й тип - автоматні граматики (вид правил A à aB або A à b, де a, b-термінали; A, B - нетерміналу).

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

1.3 Еквівалентні перетворення граматик

Для побудови розпізнавачів граматик, інших цілей часто необхідно перетворювати правила вихідної граматики до відповідного виду. При цьому мова, породжуваний вихідної і отриманими після перетворення граматиками, не повинен змінюватися.
Дві граматики еквівалентні, якщо вони породжують один і той же мова (одні й ті ж ланцюжка термінальних символів). Розглянемо ряд процедур, які завжди приводять до еквівалентних перетворень.
1 Видалення або додавання непотрібних (непродуктивних і недосяжних) нетерміналів
У безлічі Р правил граматики G непродуктивним називають нетермінал, з якого не можна отримати ланцюжок терміналів. Для пошуку в множині правил непродуктивних нетерміналів використовується наступне властивість.
Властивість А. Якщо всі символи правій частині правила продуктивні, то продуктивний і символ, що стоїть в його лівій частині.
Алгоритм пошуку непродуктивних нетерміналів в множині правил P граматики G:
- Скласти список нетерміналів, для яких знайдеться хоча б одне правило, права частина якого складається тільки з терміналів;
- Якщо знайдеться таке правило, що всі нетерміналу, що стоять в його правій частині вже занесені в список, то додати до списку нетермінал, що стоїть в його лівій частині;
- Якщо на попередньому кроці список не поповнюється, то отриманий вичерпний список всіх продуктивних нетерміналів.
Hетермінали граматики, що не потрапили в список, побудований за наведеним вище алгоритмом, є непродуктивними і, не порушуючи еквівалентності, з безлічі правил Р можна видалити всі правила, що містять такі нетерміналу.
У безлічі правил граматики недосяжним називають нетермінал, який не бере участь у процесі виведення. ланцюжків. Для пошуку недосяжних нетерміналів використовується наступне властивість.

Властивість Б. Якщо нетермінал в лівій частині правила є досяжним, то досяжні всі нетерміналу, що стоять у правій частині цього правила.
Алгоритм пошуку недосяжних нетерміналів в множині правил P граматики G:
- Утворити одноелементні список з початкового нетермінала граматики;
- Якщо в множині Р знайдено правило, ліва частина якого вже в списку, то включити до списку всі нетерміналу з його правій частині;
- Якщо на попередньому кроці список не поповнюється, то отриманий вичерпний список всіх досяжних нетерміналів.
Hетермінали граматики не потрапили в список, побудований за наведеним вище алгоритмом, є недосяжними і, не порушуючи еквівалентності, з безлічі правил Р можна видалити всі правила, що містять такі нетерміналу.
Приклад перевірки нетерміналів граматики:
G [S]: VN = {S, A, B, C, D}; VT = {a, b, c, d}; P = {S à aS (1), S à aA (2), A à bB (3),
A à bC (4), B à d (5) D à c (6)}.
1. Перевірка нетерміналів на продуктивність.
У правих частинах правил (5) і (6) тільки термінали. Внесемо в створюваний список продуктивних нетерміналу B і, D. Потім відповідно до правила (3) - A (у правій частині термінал і продуктивний нетермінал); відповідно до правила (2) - S; аналіз інших правил список не поповнює. Отримано вичерпний список продуктивних нетерміналів - {B, D, A, S}. У списку відсутня нетермінал С (непродуктивний, правило (4) для мінімізації вихідної граматики виключимо з безлічі P).
2. Перевірка нетерміналів на досяжність.
Внесемо на першому кроці у створюваний список досяжних нетерміналів початковий символ граматики S, потім на підставі правила (2) доповнимо список нетерміналом A; правило (3) дає підстави внести до списку нетермінал В. Подальший аналіз правил відповідно до алгоритму пошуку досяжних нетерміналів список не поповнює. Отримано вичерпний список продуктивних нетерміналів - {S, A, B}. У списку відсутня нетермінал D (недосяжний, правило (6) для мінімізації вихідної граматики виключимо з безлічі P).
У результаті цих перетворень одержимо мінімальну граматику G1 [S], еквівалентну вихідної.
G1 [S]: VN = {S, A, B}; VT = {a, b, d}; початковий символ S;
P = {S à aS (1), S à aA (2), A à bB (3), B à d (4)}.

2. Розробка програмного продукту

2.1 Побудова розпізнавача для граматики

Для заданої у варіанті граматики побудувати распознаватель.
Варіант 10:
G [Q] = (VT = {a, b, h}; VN = {Q, A, B, H}; P = {Q è a QH (1);
Q è bah A (2); A è ab B h (3); H è b B (4); B è abb H h (5); H è e (6)})
Рішення:
1 Перевірка нетермінальні символів вихідної граматики на досяжність (всі правила, в які входять недосяжні нетерміналу, не порушуючи еквівалентності, можна виключити).
(2) (3) (5) ç (номери правил)
{Q} è {Q, A} è {Q, A, B} è {Q, A, B, H}
(Недосяжних нетерміналів немає)
2 Перевірка нетермінальних символів отриманої після виконання п.1 граматики на продуктивність (всі правила, в які входять непродуктивні нетермінальні символи, не порушуючи еквівалентності, можна виключити).
(6) (5) (3) (2) ç (номери правил)
è {Н} è {Н, B} è {Н, B, A} è {Н, B, A, Q}
(Непродуктивних нетерміналів немає).
3. Визначення типу отриманої після виконання попередніх пунктів граматики.
Після еквівалентних перетворень нову граматику не змінилася:
G [Q] = (VT = {a, b, h}; VN = {Q, A, B, H};
P = {Q è a QH (1);
Q è bah A (2);
A è ab B h (3);
H è b B (4);
B è abb H h (5);
H è e (6)})
4. Визначимо тип отриманої граматики: з вигляду правил можна сказати, що це контекстно-вільна граматика (неправосторонняя - невідповідність у правилах (1), (3) і не є S-граматикою-є епсилон-правило (6)).
Отримана граматика може бути q-граматикою-(за визначенням для такої граматики безлічі "Вибір" для правил з однаковими лівими частинами попарно не перетинаються).
Для такої граматики безлічі "Вибір" для правил з однаковими лівими частинами попарно не перетинаються (перетинання пусто).
"Вибір Q (1)" = {a}; "Вибір Q (2)" = b
"Вибір Q (1)" Ç "Вибір Q (2)" = {(пусто)};
"Вибір H (4)" = {b}; "Вибір H (6)" = "СледH" = {h, ​​- |}
"Вибір H (4)" Ç "Вибір H (6)" = {(пусто)};
Досліджувана граматика є q - граматикою.
5. У відповідності з відомим алгоритмом будуємо для цієї граматики МП-распознаватель:
Алфавіт магазинних символів Vмаг = {Q, H, A, B, a, b, h}
Керуюча таблиця має вигляд:
4 Для перевірки правильності роботи МП-розпізнавача виведемо, застосовуючи правила граматики, правильну ланцюжок:
(2) (3) (5) (5)
Q Þ bah A Þ bahb B h Þ bahbabb H hh Þ bahbabbhh

Необработ. ланцюжок	Оброб. симв.	Верхн. маг. симв	Утримуючі. магазину	Дії з маг.
bahababbhh - | ahababbhh - | hababbhh-| ababbhh - | babbhh - | abbhh - | bbhh - | bhh - | hh - | h - | - |	b a h a b a b b h h - |	Q a h A b B b b H h h Ñ	Q Ñ ah A Ñ h A Ñ A Ñ bB h Ñ bbHhh Ñ bHhh Ñ HhhÑ hhÑ hÑ Ñ	Заст. ahA Вит. a Вит. h Заст. b Bh Вит. b Заст. bbHh Вит. b Вит. b Вит. H Вит. h Вит. h Доп.

5. Повний опис МП - розпізнавача:
Вхідний алфавіт {a, b, h - |}
Алфавіт магазинних символів {Q, A, B, H, a, b, h, Ñ}
Безліч станів {S 1}
Початкова конфігурація (S 1, Q, Ñ)
Допускає конфігурація (S 1, Ñ)
Керуюча таблиця наведена вище.
6. Програма, що реалізує МП - распознаватель, наведена у додатку.

2.2 Сучасні вимоги до програмних продуктів

1. Ліцензійна чистота (застосування програмного продукту допустимо тільки в рамках ліцензійної угоди).
2. Можливість консультації з розробником та інші форми супроводу.
3. Відповідність характеристикам, комплектації, класу і типу комп'ютерів, а також архітектурі застосовуваної обчислювальної техніки.
4. Надійність і працездатність в будь-якому з передбачених режимів роботи, як мінімум, в російськомовній мовному середовищі.
5. Наявність дружнього інтерфейсу, що підтримує роботу з використанням російської мови (для системного та інструментального програмного забезпечення допустима наявність інтерфейсу на англійській мові).
6. Наявність документації, необхідної для практичного застосування та освоєння роботи з програмним продуктом, російською мовою.
7. Розвинена система інтерактивної допомоги при роботі з програмним продуктом.
8. Наявність специфікації, враховував усі вимоги до апаратних і програмних засобів, необхідних для функціонування даного програмного продукту.

2.3 Обгрунтування вибору засобів реалізації

Найбільш популярні засоби розробки WINDOWS, що поєднують в собі засоби розробки інтерфейсу з потужними компіляторами і відладчиками. Одним з таких інструментів є мова програмування BORLAND DELPHI. Можливість проектування користувальницького інтерфейсу за допомогою редактора форм, а також простота використання функцій Windows API і потужні власні засоби відображення графічних об'єктів з'явилися головними критеріями у виборі засобів розробки пропонованого продукту.
DELPHI - складна сучасна система програмування. Діапазон можливостей Delphi воістину невичерпний. Середа DELPHI - це складний механізм, що забезпечує високо ефективну роботу програміста.
Програмування на DELPHI будується на тісній взаємодії двох процесів: процесу конструювання візуального прояву програми (тобто її Windows-вікон) і процесу написання програмного коду, що додає елементам цього вікна і програмі в цілому необхідну функціональність. Написання програми полегшено візуалізацією розробки інтерфейсу. Спочатку розробник конструює форму (зовнішній вигляд програми). Середовище розробки автоматично вносить зміни до написаний код програми (тим самим значно полегшує роботу розробнику). DELPHI заснований на об'єктному програмуванні мови програмування високого рівня TURBO PASCAL. Саме Delphi став тим продуктом, на прикладі якого стало ясно, що один продукт може настільки вдало поєднувати кілька передових технологій:
• високопродуктивний компілятор;
• об'єктно-орієнтована модель компонент.
• візуальне (а, отже, і швидке) побудова додатків з програмних прототипів.
Таким чином, Delphi забезпечує зручність і швидкість написання додатків, що відповідає найвищим стандартам якості, тому він і обраний для реалізації даного програмного продукту.

2.4 Опис алгоритму реалізації основної функції програмного продукту

Основна функція розроблюваного програмного продукту (ПП) визначена в назві теми: побудова МП-розпізнавача для заданої користувачем граматики.

1. Введення безлічі правил

2. Перевірка типу граматики

3. Генерація інтерактивної керуючої таблиці МП-розпізнавача

4. Візуалізація розбору задається користувачем ланцюжка

В основу алгоритму реалізації покладені формальні процедури еквівалентних перетворень правил, перевірки граматики на приналежність до класу S-граматик, і побудови МП-розпізнавача (результат роботи представлений у вигляді інтерактивної керуючої таблиці).
Функціональна схема програмного продукту:
Для аналізу задається користувачем граматики в розробляється програмі необхідно передбачити:
введення користувачем граматики у вигляді безлічі правил з використанням латинського алфавіту символів (нетермінальні символи - прописні, для термінальних - рядкові, при введенні епсилон-правила порожня ланцюжок буде позначена символом е;
перевірку запроваджених правил (контроль символів, відсутність символів не входять в алфавіт;
у разі неправильного введення безлічі правил - можливість їх коригування;
у разі правильного введення - аналіз нетерміналів на досяжність (ліва частина першого правила - початковий символ граматики) і продуктивність;
видалення правил з недосяжними і непродуктивними нетерміналом;
обробка виняткових ситуацій.
Примітка. При створенні програмного продукту крім основної функції передбачається реалізація допоміжних функцій: створення тестових прикладів для перевірки правильності функціонування програмного продукту після перенесення на інший комп'ютер, створення контекстної підказки.

2.5 Екранні форми

Рис.1 Основна екранна форма

7

6

5

4

3

2

1

Основна екранна форма представлена ​​на малюнку 1. Для введення чергового правила необхідно в поле 2 вибрати нетермінал лівій частині правила, а потім набрати праву його частину. Після набору правила - натиснути кнопку 3 "Додати правило". Введене правило буде додано до безлічі правил у полі 7. Будь-яке правило можна видалити, виділивши його на полі 7 і натиснувши кнопку "Видалити правило". Після набору всіх правил виконується перевірка граматики: натиснути кнопку 5 ("Перетворення граматики"). У результаті процесу перетворень граматика буде мінімізована і стане доступною кнопка 6 ("Побудова розпізнавача") на основній формі. Після її натискання буде виконано побудову і на екрані з'явиться форма з МП-розпізнавачем, за допомогою якої можна розібрати введену користувачем ланцюжок (див. рис.2). Розбір ланцюжка виконується посимвольний при послідовному натисканні відповідної кнопки і при успішному розборі буде видане повідомлення про це.

Рис. 2 Екранна форма МП-розпізнавача

Додаткові можливості можна отримати за допомогою функцій горизонтального меню на основній формі: зберегти в файлі правила граматики; завантажити з файлу збережені правила; отримати допомогу з теоретичного матеріалу та функціонування програми.
Загальний вигляд папок в довідковій системі показаний на малюнку 3.
SHAPE \ * MERGEFORMAT

Рис. 3 Зміст довідкової системи

3. Керівництво користувача; Інструкції з інсталяції

3.1 Вимоги до апаратних і програмних платформ Windows 95, Windows NT 4.0 і вище

420 Kb дискового простору для мінімальної конфігурації (тільки виконувані файли, файли довідки)
650 Кb дискового простору для нормальної конфігурації (виконувані файли, файли довідки, мовні модулі, вихідні тексти)
процесор Pentium 200 MMX
8 Mb RAM
Додаток було тестовано на наступних конфігураціях:
Intel Pentium Pentium квітня 2000, 512 Mb RAM, Windows 2000
Intel Pentium Celeron 430, 256 Mb RAM, Windows 98

3.2 Особливості запуску і роботи з програмою

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

Висновки

У рамках курсової роботи, у відповідності з отриманим індивідуальним завданням був розроблений програмний продукт, який реалізує побудову МП-розпізнавача для вводяться користувачем граматики. Для успішного виконання курсової роботи був вивчений розділ дискретної математики - "Граматики та МП-розпізнавачі". На основі отриманих знань був спроектований і реалізований, з використанням інтегральної середовища розробника DELPHI 6.0, програмний продукт, що дозволяє користувачеві набирати, редагувати правила граматик і отримувати відповідні їм МП-розпізнавачі.

Список літератури

1. Новіков Ф.А. Дискретна математика для програмістів. - СПб: Питер, 2005. - 304с.
2. Іванов Б.М. Дискретна математика. Алгоритми та програми: Учеб. посібник. - М.: Лабораторія Базових Знань, 2002. - 288с.
3. Яблонський С.В. Введення в дискретну математику: Учеб. посібник для вузів. - 2-е вид., Перераб. і доп. - М.: Наука, 1996 - 384с.
4. Бардачов Ю.М. та ін. Дискретна математика: Підручник / За ред.В. Є. Ходакова. - К.: Вища шк., 2002. -287с.
5. Системне програмне забезпечення / О.В. Гордєєв, О.Ю. Молчанов. - СПб.: Пітер, 2004. - 736с.
6. Кузнецов О.П., Адельсон-Бєльський Г.М. Дискретна математика для інженера. - М: Вища школа, 1998. - 480 с.
7. Горбатов В.А. Основи дискретної математики. - М.: Вищ. школа, 2001. - 324с.

Додаток

unit Unit2;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, Buttons, ExtCtrls, Menus;
type
TForm2 = class (TForm)
ListBox1: TListBox;
Label1: TLabel;
Bevel1: TBevel;
Label2: TLabel;
Edit2: TEdit;
BitBtn1: TBitBtn;
BitBtn2: TBitBtn;
BitBtn3: TBitBtn;
ComboBox1: TComboBox;
MainMenu1: TMainMenu;
N1: TMenuItem;
N2: TMenuItem;
N3: TMenuItem;
N4: TMenuItem;
Bevel2: TBevel;
BitBtn4: TBitBtn;
OpenDialog1: TOpenDialog;
SaveDialog1: TSaveDialog;
Bevel3: TBevel;
Label3: TLabel;
procedure BitBtn3Click (Sender: TObject);
procedure BitBtn1Click (Sender: TObject);
procedure BitBtn2Click (Sender: TObject);
procedure N3Click (Sender: TObject);
procedure N4Click (Sender: TObject);
procedure N1Click (Sender: TObject);
procedure N2Click (Sender: TObject);
procedure BitBtn4Click (Sender: TObject);
procedure FormActivate (Sender: TObject);
private
{Private declarations}
public
{Public declarations}
end;
var
Form2: TForm2;
var
i_max, j_max: byte;
const
Neterminal: set of byte = [65. .90];
Terminal: set of byte = [97. .122];
implementation
uses Unit1, Unit3, Unit4;
{$ R *. DFM}
Function DigitToCode (i: integer; osn: byte): String;
var
s, ss, last: string;
j: integer;
Begin
ss: ='';
while i div osn> 0 do
begin
str ((i mod osn), s);
ss: = ss + s;
i: = i div osn;
end;
str (i, s);
ss: = ss + s;
for j: = length (ss) downto 1 do last: = last + ss [j];
DigitToCode: = last;
End;
procedure TForm2. BitBtn3Click (Sender: TObject);
label Again, Again1, Again2, Again3, Return;
var
i: byte;
kol: byte;
i_tmp, j_tmp: byte;
s: string;
j, k, l: longint;
code: integer;
osn, num, p_ins: byte;
posled, chain, tmp: string;
let: char;
mn: set of char;
flag: boolean;
kk, kol_op: longword;
f: byte;
begin
if ListBox1. Items. Count = 0 then
begin
MessageDlg ('Не введені правила граматики.' + # 13 + 'Введіть правила.', MtError, [mbOk], 0);
exit;
end;
mn: = [];
for i: = 0 to ListBox1. Items. Count-1 do
begin
flag: = True;
for j: = 5 to length (ListBox1. Items. Strings [i]) do
if not (ord (ListBox1. Items. Strings [i] [j]) in Terminal) then flag: = False;
if flag then mn: = mn + [ListBox1. Items. Strings [i] [1]];
end;
Again:
for i: = 0 to ListBox1. Items. Count-1 do
begin
flag: = False;
for j: = 5 to length (ListBox1. Items. Strings [i]) do
begin
if (ord (ListBox1. Items. Strings [i] [j]) in Neterminal) and
(ListBox1. Items. Strings [i] [j] in mn) and
(Not (ListBox1. Items. Strings [i] [1] in mn)) then flag: = True;
end;
if flag then
begin
mn: = mn + [ListBox1. Items. Strings [i] [1]];
goto Again;
end;
end;
s: ='';
for i: = 0 to ListBox1. Items. Count-1 do
if (not (ListBox1. Items. Strings [i] [1] in mn)) and
(Pos (ListBox1. Items. Strings [i] [1], s) = 0) then s: = s + ListBox1. Items. Strings [i] [1] + '';
if s <>''then
begin
if length (s)> 2 then MessageDlg ('нетерміналу' + s + 'непродуктивні.' + # 13 + 'Всі правила, що їх містять, будуть видалені з граматики.', mtInformation, [mbOk], 0)
else MessageDlg ('нетермінала' + s + 'непродуктивний.' + # 13 + 'Всі правила, його містять, будуть видалені з граматики.', mtInformation, [mbOk], 0);
Again1:
if ListBox1. Items. Count <> 0 then
begin
for i: = 0 to ListBox1. Items. Count-1 do
for j: = 1 to length (ListBox1. Items. Strings [i]) do
if (ord (ListBox1. Items. Strings [i] [j]) in Neterminal) and
(Not (ListBox1. Items. Strings [i] [j] in mn)) then
begin
ListBox1. Items. Delete (i);
goto Again1;
end;
end
else
begin
MessageDlg ('Всі правила були видалені з граматики.' + # 13 + 'Введіть нові правила.', MtInformation, [mbOk], 0);
BitBtn2. Enabled: = False;
exit;
end
end;
flag: = False;
for i: = 0 to ListBox1. Items. Count-1 do
begin
if ListBox1. Items. Strings [i] [1] = 'S' then flag: = True;
end;
if not flag then
begin
MessageDlg ('Під введеної граматиці немає правила, що містить' + # 13 + 'в лівій частині початковий символ граматики S.' + # 13 + 'Необхідно додати таке правило.', MtError, [mbOk], 0);
ComboBox1. SetFocus;
exit;
end;
mn: = ['S'];
Again2:
for i: = 0 to ListBox1. Items. Count-1 do
begin
if ListBox1. Items. Strings [i] [1] in mn then
begin
for j: = 5 to length (ListBox1. Items. Strings [i]) do
begin
if (ord (ListBox1. Items. Strings [i] [j]) in Neterminal) and
(Not (ListBox1. Items. Strings [i] [j] in mn)) then
begin
mn: = mn + [ListBox1. Items. Strings [i] [j]];
goto Again2;
end;
end;
end;
end;
s: ='';
for i: = 0 to ListBox1. Items. Count-1 do
if (not (ListBox1. Items. Strings [i] [1] in mn)) and
(Pos (ListBox1. Items. Strings [i] [1], s) = 0) then s: = s + ListBox1. Items. Strings [i] [1] + '';
if s <>''then
begin
if length (s)> 2 then MessageDlg ('нетерміналу' + s + 'недосяжні.' + # 13 + 'Всі правила, що їх містять, будуть видалені з граматики.', mtInformation, [mbOk], 0)
else MessageDlg ('нетермінала' + s + 'недосяжний.' + # 13 + 'Всі правила, його містять, будуть видалені з граматики.', mtInformation, [mbOk], 0);
Again3:
if ListBox1. Items. Count <> 0 then
begin
for i: = 0 to ListBox1. Items. Count-1 do
for j: = 1 to length (ListBox1. Items. Strings [i]) do
if (ord (ListBox1. Items. Strings [i] [j]) in Neterminal) and
(Not (ListBox1. Items. Strings [i] [j] in mn)) then
begin
ListBox1. Items. Delete (i);
goto Again3;
end;
end
else
begin
MessageDlg ('Всі правила були видалені з граматики.' + # 13 + 'Введіть нові правила.', MtInformation, [mbOk], 0);
BitBtn2. Enabled: = False;
exit;
end
end;
alfavit: = [];
end;
for i: = 1 to length (Right) do
begin
if not (ord (Right [i]) in Neterminal) and not (ord (Right [i]) in Terminal) then
begin
ErrFlag: = True;
goto ErrorMsgRight;
end;
end;
if length (Right) <> 1 then
begin
for i: = 1 to length (Right) do
if Right [i] = 'e' then Delete (Right, i, 1);
end;
ErrorMsgRight:
if ErrFlag then
begin
MessageDlg ('Помилка в правій частині правила', mtError, [mbOk], 0);
Edit2. SetFocus;
exit;
end;
if not (ord (Right [1]) in Terminal) then
begin
ErrFlag: = True;
goto ErrorQGram;
end;
if ListBox1. Items. Count> 0 then
begin
for i: = 0 to ListBox1. Items. Count-1 do
begin
if (ListBox1. Items. Strings [i] [1] = Left) and
(ListBox1. Items. Strings [i] [5] = Right [1]) then
begin
ErrFlag: = True;
break;
end;
end;
end;
ErrorQGram:
if ErrFlag then
begin
MessageDlg ('Це правило не може міститися в q-граматиці', mtError, [mbOk], 0);
Edit2. SetFocus;
exit;
end;
Rule: = Left +'-->'+ Right;
ListBox1. Items. Add (Rule);
BitBtn4. Enabled: = True;
BitBtn3. Enabled: = False;
end;
procedure TForm2. BitBtn2Click (Sender: TObject);
var
i: byte;
begin
for i: = 0 to ListBox1. Items. Count-1 do
begin
if ListBox1. Selected [i] then
begin
ListBox1. Items. Delete (i);
break;
end;
end;
if ListBox1. Items. Count = 0 then BitBtn2. Enabled: = False;
end;
procedure TForm2. N3Click (Sender: TObject);
begin
/ / Winexec ('. \ Help.html', 4);
Application. Helpcontext (10);
end;
procedure TForm2. N4Click (Sender: TObject);
begin
Form2. Close;
Form1. Close;
end;
procedure TForm2. N1Click (Sender: TObject);
begin
if OpenDialog1. Execute then
begin
ListBox1. Items. LoadFromFile (OpenDialog1. FileName);
end;
BitBtn4. Enabled: = True;
BitBtn3. Enabled: = False;
end;
procedure TForm2. N2Click (Sender: TObject);
begin
if SaveDialog1. Execute then
begin
ListBox1. Items. SaveToFile (SaveDialog1. FileName);
end;
end;
procedure TForm2. BitBtn4Click (Sender: TObject);
Label Next, Again, Again1, Again2, Again3;
var
i, j: byte;
s: string;
mn: set of char;
flag: boolean;
begin
Next:
for i: = 0 to ListBox1. Items. Count-2 do
begin
for j: = i +1 to ListBox1. Items. Count-1 do
begin
if (ListBox1. Items. Strings [i] [1] = ListBox1. Items. Strings [j] [1]) and
(ListBox1. Items. Strings [i] [5] = ListBox1. Items. Strings [j] [5]) then
begin
MessageDlg ('Правило' + ListBox1. Items. Strings [j] + 'не може міститися в q-граматиці. Воно буде вилучено.', MtInformation, [mbOk], 0);
ListBox1. Items. Delete (j);
goto Next;
end;
end;
end;
mn: = [];
for i: = 0 to ListBox1. Items. Count-1 do
begin
flag: = True;
for j: = 5 to length (ListBox1. Items. Strings [i]) do
if not (ord (ListBox1. Items. Strings [i] [j]) in Terminal) then flag: = False;
if flag then mn: = mn + [ListBox1. Items. Strings [i] [1]];
end;
Again:
for i: = 0 to ListBox1. Items. Count-1 do
begin
flag: = False;
for j: = 5 to length (ListBox1. Items. Strings [i]) do
begin
if (ord (ListBox1. Items. Strings [i] [j]) in Neterminal) and
(ListBox1. Items. Strings [i] [j] in mn) and
(Not (ListBox1. Items. Strings [i] [1] in mn)) then flag: = True;
end;
if flag then
begin
mn: = mn + [ListBox1. Items. Strings [i] [1]];
goto Again;
end;
end;
s: ='';
for i: = 0 to ListBox1. Items. Count-1 do
if (not (ListBox1. Items. Strings [i] [1] in mn)) and
(Pos (ListBox1. Items. Strings [i] [1], s) = 0) then s: = s + ListBox1. Items. Strings [i] [1] + '';
if s <>''then
begin
if length (s)> 2 then MessageDlg ('нетерміналу' + s + 'непродуктивні.' + # 13 + 'Всі правила, що їх містять, будуть видалені з граматики.', mtInformation, [mbOk], 0)
else MessageDlg ('нетермінала' + s + 'непродуктивний.' + # 13 + 'Всі правила, його містять, будуть видалені з граматики.', mtInformation, [mbOk], 0);
Again1:
if ListBox1. Items. Count <> 0 then
begin
for i: = 0 to ListBox1. Items. Count-1 do
for j: = 1 to length (ListBox1. Items. Strings [i]) do
if (ord (ListBox1. Items. Strings [i] [j]) in Neterminal) and
(Not (ListBox1. Items. Strings [i] [j] in mn)) then
begin
ListBox1. Items. Delete (i);
goto Again1;
end;
end
else
begin
MessageDlg ('Всі правила були видалені з граматики.' + # 13 + 'Введіть нові правила.', MtInformation, [mbOk], 0);
BitBtn2. Enabled: = False;
exit;
end
end;
flag: = False;
for i: = 0 to ListBox1. Items. Count-1 do
begin
if ListBox1. Items. Strings [i] [1] = 'S' then flag: = True;
end;
if not flag then
begin
MessageDlg ('Під введеної граматиці немає правила, що містить' + # 13 + 'в лівій частині початковий символ граматики S.' + # 13 + 'Необхідно додати таке правило.', MtError, [mbOk], 0);
ComboBox1. SetFocus;
exit;
end;
mn: = ['S'];
Again2:
for i: = 0 to ListBox1. Items. Count-1 do
begin
if ListBox1. Items. Strings [i] [1] in mn then
begin
for j: = 5 to length (ListBox1. Items. Strings [i]) do
begin
if (ord (ListBox1. Items. Strings [i] [j]) in Neterminal) and
(Not (ListBox1. Items. Strings [i] [j] in mn)) then
begin
mn: = mn + [ListBox1. Items. Strings [i] [j]];
goto Again2;
end;
end;
end;
end;
s: ='';
for i: = 0 to ListBox1. Items. Count-1 do
if (not (ListBox1. Items. Strings [i] [1] in mn)) and
(Pos (ListBox1. Items. Strings [i] [1], s) = 0) then s: = s + ListBox1. Items. Strings [i] [1] + '';
if s <>''then
begin
if length (s)> 2 then MessageDlg ('нетерміналу' + s + 'недосяжні.' + # 13 + 'Всі правила, що їх містять, будуть видалені з граматики.', mtInformation, [mbOk], 0)
else MessageDlg ('нетермінала' + s + 'недосяжний.' + # 13 + 'Всі правила, його містять, будуть видалені з граматики.', mtInformation, [mbOk], 0);
Again3:
if ListBox1. Items. Count <> 0 then
begin
for i: = 0 to ListBox1. Items. Count-1 do
for j: = 1 to length (ListBox1. Items. Strings [i]) do
if (ord (ListBox1. Items. Strings [i] [j]) in Neterminal) and
(Not (ListBox1. Items. Strings [i] [j] in mn)) then
begin
ListBox1. Items. Delete (i);
goto Again3;
end;
end
else
begin
MessageDlg ('Всі правила були видалені з граматики.' + # 13 + 'Введіть нові правила.', MtInformation, [mbOk], 0);
BitBtn2. Enabled: = False;
exit;
end
end;
MessageDlg ('Еквівалентні перетворення граматики завершені', mtInformation, [mbOk], 0);
BitBtn3. Enabled: = True;
BitBtn4. Enabled: = False;
end;
procedure TForm2. FormActivate (Sender: TObject);
begin
BitBtn3. Enabled: = False;
end;
end.