Построение распознавателя для заданной грамматики и реализация его в виде программы которая проверяет (стр. 3 из 4)

“Выбор 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--|--|	bahababbhh--|	QahAbBbbHhhÑ	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 Современные требования к программным продуктам

1. Лицензионная чистота (применение программного продукта допустимо только в рамках лицензионного соглашения).

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, программный продукт, позволяющий пользователю набирать, редактировать правила грамматик и получать соответствующие им МП-распознаватели.