МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
КАФЕДРА
КОМПЬЮТЕРНЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
Курсовая работа
по дисциплине
"Основы дискретной математики"
Тема: "Построение распознавателя для заданной грамматики и реализация его в виде программы, которая проверяет вводимые пользователем цепочки"
2006
Задание на курсовую работу
по дисциплине "Основы дискретной математики"
Задание на выполнение работы:
1. Роль информационных технологий в быту современного человека.
2.Подробная справка по теоретическим аспектам формальных грамматик и их преобразованию.
3.Выполнить исследование и преобразование исходной грамматики:
G [Q] = (VT = {a, b,h}; VN = { Q, A, B, H }; P = { Q-aQH;
Q - b a h A; A - a b B h; H - bB; B - a b b H h; H -e }) (e - пустая цепочка).
Построить распознаватель для преобразованной грамматики и реализовать его в виде программы, которая проверяет текстовые файлы и вводимые пользователем цепочки.
Работу необходимо выполнить в соответствии с графиком и требованиями к выполнению курсовой работы по основам дискретной математики;
Изменение и уточнение темы с согласия преподавателя возможно только на первом этапе работы;
Готовая работа сдается на проверку не позже, чем за день до защиты.
Реферат
Курсовая работа по дисциплине "Основы дискретной математики" на тему: "Построение М П-распознавателя для задаваемой пользователем произвольной грамматики" содержит 21 страницу машинописного текста, 5 рисунков, 3 таблицы, страниц приложения.
В работе рассмотрен один из разделов дискретной математики - "Классификация грамматик; эквивалентные преобразования КС-грамматик", разработан программный продукт, с помощью которого можно проверить задаваемую пользователем грамматику и упростить ее с помощью эквивалентных преобразований правил.
Ключевые слова:
дискретная математика, КС-грамматика, S-грамматика, правило грамматики; терминальный символ; нетерминальный символ; дерево вывода; эквивалентные преобразования; сентенциальная форма.
Введение
Роль информационных технологий в быту современного человека.
За последние несколько лет человечество совершило удивительный рывок в области развития компьютерных, и вследствие этого, информационных технологий. Всего каких-то десять лет назад среднестатистический гражданин не мог и мечтать о собственном персональном компьютере. В середине 80-х годов ЭВМ были прерогативой крупных предприятий, обслуживание этих машин осуществлялось через разветвленную сеть специализированных сервисных центров. Зачастую многие предприятия не имели достаточно квалифицированных кадров для монтажа и обслуживания своих ЭВМ. Соответственно и проблемы связи между вычислительными комплексами вставали в узком кругу специалистов. Несмотря на то, что первые экспериментальные сети передачи пакетов данных были созданы в 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аука об осмысленных знаковых системах называется семиотикой. 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 Классификация грамматик
Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик (см. рис. на следующей странице):
Каждый тип грамматик включает грамматики более высоких типов, как частные случаи.
Построение грамматики - это процесс структурирования знаний в некоторой предметной области, другими словами - создание порождающего алгоритма некоторого множества, обработка которого удобна с помощью вычислительной машины. Построение распознавателя грамматики - создание алгоритма для проверки (контроля) правильности созданного конкретного множества. Оба алгоритма могут быть реализованы в виде программ на любом языке программирования. Примером такой взаимосвязи грамматика - распознаватель может служить язык программирования (любой) - компилятор.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 Q H (1);
Q - b a h A (2); A - a b B h (3); H - b B (4); B - a b b 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-aQ H (1);
Q - b a h A (2);
A - a b B h (3);
H - b B (4);
B - a b b 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 }
Управляющая таблица имеет вид:
| a | b | h | --| | ||||||
| Ñ | E | E | E | Доп. | |||||
Q |
Зам. QH |
П |
Зам. ahA |
П |
E |
Отв. |
|||
A |
Зам. bBh |
П |
E |
E |
Отв. |
||||
В |
Зам. bbHh |
П |
E |
E |
Отв. |
||||
Н |
E |
Зам. B |
П |
Выт. H |
Д |
Выт. H |
Д |
||
a |
Выт. a |
П |
E |
E |
Отв. |
||||
b |
E |
Выт. b |
П |
E |
Отв. |
||||
h |
E |
E |
Выт. h |
П |
Отв. |
||||
4 Для проверки правильности работы МП-распознавателя выведем, применяя правила грамматики, правильную цепочку:
(2) (3) (5) (5)
Q Þ b a h A Þ b a h b B h Þ b a h b a b b H h h Þ b a h b a b b h h
| Необработ. цепочка | Обраб. симв. |
Верхн. маг. симв | Содерж. магазина | Действия с маг. |
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 Ñ a h AÑ h AÑ A Ñ bBh Ñ bbHhh Ñ bHhh Ñ HhhÑ hhÑ hÑ Ñ |
Зам. ahA Выт. a Выт. h Зам. bBh Выт. 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 Современные требования к программным продуктам
<
2. Возможность консультации с разработчиком и другие формы сопровождения.
3. Соответствие характеристикам, комплектации, классу и типу компьютеров, а также архитектуре применяемой вычислительной техники.
4. Надежность и работоспособность в любом из предусмотренных режимов работы, как минимум, в русскоязычной языковой среде.
5. Наличие дружественного интерфейса, поддерживающего работу с использованием русского языка (для системного и инструментального программного обеспечения допустимо наличие интерфейса на английском языке).
6. Наличие документации, необходимой для практического применения и освоения работы с программным продуктом, на русском языке.
7. Развитая система интерактивной помощи при работе с программным продуктом.
8. Наличие спецификации, оговаривающей все требования к аппаратным и программным средствам, необходимым для функционирования данного программного продукта.
2.3 Обоснование выбора средств реализации
Наиболее популярны средства разработки WINDOWS, сочетающие в себе средства разработки интерфейса с мощными компиляторами и отладчиками. Одним из таких инструментов является язык программирования BORLANDDELPHI. Возможность проектирования пользовательского интерфейса с помощью редактора форм, а также простота использования функций WindowsAPI и мощные собственные средства отображения графических объектов явились главными критериями в выборе средств разработки предлагаемого продукта.
DELPHI- сложная современная система программирования. Диапазон возможностей Delphi поистине неисчерпаем. Среда DELPHI- это сложный механизм, обеспечивающий высоко эффективную работу программиста.
Программирование на DELPHI строится на тесном взаимодействии двух процессов: процесса конструирования визуального проявления программы (т.е. ее Windows-окон) и процесса написания программного кода, придающего элементам этого окна и программе в целом необходимую функциональность. Написание программы облегчено визуализацией разработки интерфейса. Сначала разработчик конструирует форму (внешний вид программы). Среда разработки автоматически вносит изменения в написанный код программы (тем самым значительно облегчает работу разработчику). DELPHI основан на объектном программировании языка программирования высокого уровня TURBOPASCAL. Именно Delphiстал тем продуктом, на примере которого стало ясно, что один продукт может столь удачно сочетать несколько передовых технологий:
• высокопроизводительный компилятор;
• объектно-ориентированная модель компонент.
• визуальное (а, следовательно, и быстрое) построение приложений из программных прототипов.
Таким образом, Delphi обеспечивает удобство и быстроту написания приложений, отвечающим самым высоким стандартам качества; поэтому он и выбран для реализации данного программного продукта.
2.4 Описание алгоритма реализации основной функции программного продукта
Основная функция разрабатываемого программного продукта (ПП) определена в названии темы: построение МП-распознавателя для заданной пользователем грамматики.
В основу алгоритма реализации положены формальные процедуры эквивалентных преобразований правил, проверки грамматики на принадлежность к классу S-грамматик, и построения МП-распознавателя (результат работы представлен в виде интерактивной управляющей таблицы).
Функциональная схема программного продукта:
Для анализа задаваемой пользователем грамматики в разрабатываемой программе необходимо предусмотреть:
ввод пользователем грамматики в виде множества правил с использованием латинского алфавита символов (нетерминальные символы - прописные, для терминальных - строчные, при вводе эпсилон-правила пустая цепочка будет обозначена символом е;
проверку введенных правил (контроль символов, отсутствие символов не входящих в алфавит;
в случае неправильного ввода множества правил - возможность их корректировки;
в случае правильного ввода - анализ нетерминалов на достижимость (левая часть первого правила - начальный символ грамматики) и продуктивность;
удаление правил с недостижимыми и непродуктивными нетерминалами;
обработка исключительных ситуаций.
Примечание. При создании программного продукта кроме основной функции предполагается реализация вспомогательных функций: создание тестовых примеров для проверки правильности функционирования программного продукта после переноса на другой компьютер, создание контекстной подсказки.
2.5 Экранные формы
Основная экранная форма представлена на рисунке 1. Для ввода очередного правила необходимо в поле 2 выбрать нетерминал левой части правила, а затем набрать правую его часть. После набора правила - нажать кнопку 3 "Добавить правило". Введенное правило будет добавлено к множеству правил в поле 7. Любое правило можно удалить, выделив его в поле 7 и нажав кнопку "Удалить правило". После набора всех правил выполняется проверка грамматики: нажать кнопку 5 ("Преобразования грамматики"). В результате процесса преобразований грамматика будет минимизирована и станет доступной кнопка 6 ("Построение распознавателя") на основной форме. После ее нажатия будет выполнено построение и на экране появится форма с МП-распознавателем, с помощью которой можно разобрать введенную пользователем цепочку (см. рис.2). Разбор цепочки выполняется посимвольно при последовательном нажатии соответствующей кнопки и при успешном разборе будет выдано сообщение об этом.
Дополнительные возможности можно получить с помощью функций горизонтального меню на основной форме: сохранить в файле правила грамматики; загрузить из файла сохраненные правила; получить помощь по теоретическому материалу и функционированию программы.
Общий вид папок в справочной системе показан на рисунке 3.
3. Руководство пользователя; инструкция по инсталляции
3.1 Требования к аппаратным и программным платформам Windows 95, WindowsNT 4.0 и выше
420 Kb дискового пространства для минимальной конфигурации (только выполняемые файлы, файлы справки)
650 Кb дискового пространства для нормальной конфигурации (выполняемые файлы, файлы справки, языковые модули, исходные тексты)
процессор Pentium 200 MMX
8 MbRAM
Приложение было тестировано на следующих конфигурациях:
Intel Pentium Pentium 4 2000, 512 Mb RAM, Windows 2000
Intel Pentium Celeron 430, 256 Mb RAM, Windows 98
3.2 Особенности запуска и работы с программой
Для установки программы на Ваш компьютер, необходимо скопировать с дискеты папку с файлами проекта на жесткий диск и запустить на выполнение exe-файл, или запустить этот же файл прямо с дискеты.
Программа предназначена для построения МП-распознавателей для грамматик, вводимых пользователем. Перед построением проводится минимизация грамматики и проверка ее на принадлежность к q -грамматикам. Программа снабжена достаточно мощной и подробной системой помощи как по использованию программного продукта, так и по теоретическим вопросам.
Неподготовленному пользователю рекомендуется перед началом работы непосредственно с программой изучить справочный материал и запустить на выполнение несколько примеров правил с последующим их редактированием.
Выводы
В рамках курсовой работы, в соответствии с полученным индивидуальным заданием был разработан программный продукт, реализующий построение МП-распознавателя для вводимых пользователем грамматики. Для успешного выполнения курсовой работы был изучен раздел дискретной математики - "Грамматики и МП-распознаватели". На основе полученных знаний был спроектирован и реализован, с использованием интегральной среды разработчика DELPHI6.0, программный продукт, позволяющий пользователю набирать, редактировать правила грамматик и получать соответствующие им МП-распознаватели.
Список литературы
1. Новиков Ф.А. Дискретная математика для программистов. - СПб: Питер, 2005. - 304с.
2. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. - М.: Лаборатория Базовых Знаний, 2002. - 288с.
3. Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов. - 2-е изд., перераб. и доп. - М.: Наука, 1996 - 384с.
4. Бардачов Ю.М. та ін. Дискретна математика: Підручник / За ред.В. Є. Ходакова. - К.: Вища шк., 2002. -287с.
5. Системное программное обеспечение / А.В. Гордеев, А.Ю. Молчанов. - СПб.: Питер, 2004. - 736с.
6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М: Энергоатомиздат, 1998. - 480 с.
7. Горбатов В.А. Основы дискретной математики. - М.: Высш. школа, 2001. - 324с.
Приложение
unitUnit2;
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.