Смекни!
smekni.com

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

1.2.4 Удаление или добавление бесполезных (непродуктивных и недостижимых) нетерминалов

В множестве Р правил грамматики G непродуктивным называют нетерминал, из которого нельзя получить цепочку терминалов. Для поиска в множестве правил непродуктивных нетерминалов используется следующее свойство.

Свойство А: Если все символы правой части правила продуктивны, то продуктивен и символ, стоящий в его левой части.

Алгоритм поиска непродуктивных нетерминалов в множестве правил P грамматики G:

– составить список нетерминалов для которых найдется хотя бы одно правило, правая часть которого состоит только из терминалов;

– если найдется такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал стоящий в его левой части;

– если на предыдущем шаге список не пополняется, то получен исчерпывающий список всех продуктивных нетерминалов.

Hетерминалы грамматики не попавшие в список, построенный по приведенному выше алгоритму, являются непродуктивными и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.

В множестве правил грамматики недостижимым называют нетерминал, который не участвует в процессе вывода. цепочек. Для поиска недостижимых нетерминалов используется следующее свойство.

Свойство Б: Если нетерминал в левой части правила является достижимым, то достижимы все нетерминалы, стоящие в правой части этого правила.

Алгоритм поиска недостижимых нетерминалов в множестве правил P грамматики G:

– образовать одноэлементный список из начального нетерминала грамматики;

– если в множестве Р найдено правило, левая часть которого уже в списке, то включить в список все нетерминалы из его правой части;

– если на предыдущем шаге список не пополняется, то получен исчерпывающий список всех достижимых нетерминалов.

Hетерминалы грамматики не попавшие в список, построенный по приведенному выше алгоритму, являются недостижимыми и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.

Не нарушая эквивалентности, можно также исключить правила такого вида: A - A или A - B, B - C, C - A (циклический блок правил).

1.2.5 Построение грамматик для заданного КА

Любое регулярное множество, которое распознается КА, можно описать с помощью автоматной грамматики. Алгоритм построения грамматики следующий:

– Начальное состояние КА - начальный символ грамматики.

– Алфавит КА (без символа конец цепочки–"┤") - терминальные символы грамматики.

– Множество состояний КА - нетерминальные символы грамматики.

– Если в таблице переходов КА есть переход из состояния А в состояние В при воздействии входного символа х – ввести правило следующего вида: А - xB.

– Если D– допускающее состояние КА, то ввести правило следующего вида: D-*,где *– пустая цепочка(для отвергающих состояний правил нет).

– Закончить составление правил, когда будут обработаны все непустые клетки управляющей таблицы ("0" – пустая клетка).


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

2.1 Современные требования к программным продуктам

– Удобный, легкий в обращении интерфейс.

– В программе необходимо предусмотреть неквалифицированные действия пользователя.

– К программе должна прилагаться специально разработанная справочная система.

– Программа должна работать в разных операционных системах.

– Надёжность работы программы.

2.2 Область прикладного применения ПП

Представленный мною ПП является наглядным пособием для всех желающих изучить такую тему дискретной математики, как «Построение грамматики для заданного пользователем конечного автомата».

2.3 Обоснование выбора средств реализации

Программа написана в среде программирования Delphi 7.0 под Windows.

Основные характеристики среды разработки Delphi.

Delphi - это комбинация нескольких важнейших технологий:

–Высокопроизводительный компилятор в машинный код

– Объектно-ориентированная модель компонент

– Визуальное (а, следовательно, и скоростное) построение приложений из программных прототипов

– Масштабируемые средства для построения баз данных

Компилятор в машинный код. Компилятор, встроенный в Delphi, обеспечивает высокую производительность, необходимую для построения приложений в архитектуре “клиент-сервер”. Этот компилятор в настоящее время является самым быстрым в мире, его скорость компиляции составляет свыше 120 тысяч строк в минуту на компьютере 486DX33. Он предлагает легкость разработки и быстрое время проверки готового программного блока, характерного для языков четвертого поколения (4GL) и в то же время обеспечивает качество кода, характерного для компилятора 3GL. Кроме того, Delphi обеспечивает быструю разработку без необходимости писать вставки на Си или ручного написания кода (хотя это возможно).

В процессе построения приложения разработчик выбирает из палитры компонент готовые компоненты как художник, делающий крупные мазки кистью. Еще до компиляции он видит результаты своей работы - после подключения к источнику данных их можно видеть отображенными на форме, можно перемещаться по данным, представлять их в том или ином виде. В этом смысле проектирование в Delphi мало чем отличается от проектирования в интерпретирующей среде, однако после выполнения компиляции мы получаем код, который исполняется в 10-20 раз быстрее, чем то же самое, сделанное при помощи интерпретатора. Кроме того, компилятор компилятору рознь, в Delphi компиляция производится непосредственно в родной машинный код, в то время как существуют компиляторы, превращающие программу в так называемый p-код, который затем интерпретируется виртуальной p-машиной. Это не может не сказаться на фактическом быстродействии готового приложения.

Объектно-ориентированная модель программных компонент. Основной упор этой модели в Delphi делается на максимальном реиспользовании кода. Это позволяет разработчикам строить приложения весьма быстро из заранее подготовленных объектов, а также дает им возможность создавать свои собственные объекты для среды Delphi. Никаких ограничений по типам объектов, которые могут создавать разработчики, не существует. Действительно, все в Delphi написано на нем же, поэтому разработчики имеют доступ к тем же объектам и инструментам, которые использовались для создания среды разработки. В результате нет никакой разницы между объектами, поставляемыми Borland или третьими фирмами, и объектами, которые вы можете создать. В стандартную поставку Delphi входят основные объекты, которые образуют удачно подобранную иерархию из 270 базовых классов.

2.4 Структура разрабатываемого программного продукта.

Рисунок 2 – Структура разрабатываемого программного продукта

Рассматриваемая структура изображена на рисунке 2.

2.5 Блок-схема

Функциональная схема разработанного программного продукта приведена на рисунке 3.


нет

да


Рисунок 3 – Функциональная схема программного продукта

2.6 Работа с ПП, справочной системой

Справочная система представлена в виде Web-страницы, что вызывается gри нажатии F7. Ссылка на адрес её расположения указана в листинге программы: WinExec('C:\Program Files\Internet Explorer\Iexplore.exe F:\Моя курсовая работа\Моя Web-страница\Справка.mht',1);

Запустите Primer4. Всплывает окно (рисунок 4):

Рисунок 4 – Главная форма

Вводим состояния и алфавит (рисунок 5):

Рисунок 5 – Главная форма с заполненными строками

Нажимаем на кнопку «Конечный Автомат». Заполняем управляющую таблицу. Проверим конечный автомат (рисунок 6):


Таблица 1 – Компоненты программы

Имя компонента в модуле Назначение компонента События компонента Назначение обработчиков событий Примечания
MainMenu Самая главная форма, где расположены все компоненты
BitBtn1 Кнопка для создания конечного автомата OnClick Создание управляющей таблицы.
BitBtn2 Кнопка выхода OnClick Закрытие программы.
BitBtn3 Кнопка для создания граматики. OnClick Создания првил грмматики.
BitBtn4 Кнопка для вызова правил ввода. OnClick Открывается форма с правилами ввода.
BitBtn5 Кнопка проверки конечного автомата. OnClick Проверка конечного автомата на недостижимые символы.
BitBtn6 Кнопка очистки поля OnClick Очищает поле, где расположены правила найденной грамматики.
BitBtn7 Кнопка вызова справки о программном продукте. OnClick
Edit Cтрока для ввода символов состояния и алфавита. Ввод символов состоянии и алфавита конечного автомата.
StringGrid Компонент для управляющей таблицы
ListBox Поле для правил грамматики

В таком случае, невозможно построить грамматику. Строим конечный автомат, в котором все состояния достижимы. И только тогда строим грамматику. В таблице 1 предоставлена информация о компонентах программы.