Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» (стр. 4 из 4)
Рис. 8. Типичный пример устранения недетерминированности
Недетерминированность устраняется склеиванием двух позиций Pl и Pk в одну (Pl, Pk). При этом позиции (Pl, Pk) инцидентны все исходящие дуги, ведущие в переходы tr, tq, ts, являющиеся исходящими дугами позиций Pl и Pk.
Применим этот способ к сети на рис. 7, получим сеть, показанную на рисунке 9.
Рис. 9. Минимизированная детерминированная сеть Петри
В данном случае можно установить взаимно однозначное соответствие между сетью рис. 9 и графом переходов минимального автомата – рис. 3. (В скобках на рис. 9 указаны соответствующие состояния минимального автомата).
Указание. Выполнение обоих способов построения минимальнного автомата обязательно, так как это обеспечивает контроль правильности выполнения этапов курсовой работы.
От рис. 9 можно перейти к графу переходов автомата, заменив переходы сети Петри дугами автомата, переименовав позиции сети соответствующими им состояниями автомата и взвесив дуги наименованиями этих переходов.
8. ПОРЯДОК ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ
Этап 1. Получение задания. Построение праволинейной грамматики. Переход от праволинейной грамматики к автоматной.
Результаты: праволинейная грамматика, ее граф, автоматная грамматика.
Этап 2. Построение недетерминированного распознающего автомата.
Результаты: таблица переходов и граф переходов недетерминированного автомата.
Этап 3. Переход от недетерминированного автомата к полностью определенному детерминированному автомату.
Результаты: таблица переходов и граф переходов детерминированного автомата.
Этап 4. Минимизация автомата.
Результаты: таблица переходов и граф переходов минимального автомата. Этап 5. Выполнение предыдущих этапов с использованием аппарата сетей Петри.
Результаты: исходная сеть Петри, сеть свободного выбора, детерминированная сеть Петри, сравнение полученной автоматной сети с графом минимального автомата.
Этап 6. Написание программы, реализующей распознающий автомат.
Результаты: текст программы и документация к ней.
Этап 7. Тестирование программы.
Результаты:
1. Примеры тестов (правильно построенные цепочки, порождаемые исходной грамматикой, и неправильные цепочки);
2. Результат проверки допустимости тестовых цепочек автоматом (построение соответствующих последовательностей переходов автомата);
3. Сравнение результатов работы программы с результатами работы автомата на тестовом множестве цепочек.
9. РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ
Ниже приведено типовое содержание пояснительной записки.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. Постановка задачи
2. Индивидуальное задание. Построение праволинейной грамматики
3. Построение автоматной грамматики по праволинейной
4. Построение недетерминированного конечного автомата
5. Сведение недетерминированного конечного автомата к детерминированному
6. Построение минимального автомата
7. Построение сети Петри, моделирующей работу распознающего автомата
8. Описание программы, реализующей распознающий автомат
8.1. Вводная часть
8.2. Функциональное назначение
8.3. Описание информации
8.4. Описание логики
9. Описание контрольного примера
9.1. Назначение
9.2. Исходные данные
9.3. Результаты расчета
9.4. Результаты испытания программы
Заключение
Список литературы
Приложения
Приложение 1. Текст программы
Приложение 2. Результаты расчета на ЭВМ контрольного примера
Во «Введении» показывается актуальность темы и формулируется цель курсовой работы.
Здесь можно показать значение формальных грамматик, конечных автоматов(распознавателей), сетей Петри для решения задач построения лингвистических процессоров.
Целью курсовой работы является изучение способов задания языков грамматиками, распознающими автоматами и сетями Петри, синтез и программная реализация конечного автомата, распознающего заданный язык.
В разделе 1 необходимо дать четкую формулировку задачи, описать подход к ее решению, отразить основные этапы разработки(синтеза) распознающего автомата, описать входную и выходную информацию.
В разделе 2 описывается формирование индивидуального задания, построение праволинейной грамматики на основе индивидуального задания, приводится граф этой грамматики.
В разделе 3 приводится процедура перевода праволинейной грамматики в автоматную, описывается построение автоматной грамматики.
В разделе 4 приводится процедура построения недетерминированного автомата по автоматной грамматике, описывается
построение таблицы переходов и графа переходов недетерминированного автомата.
В разделе 5 приводится процедура перевода недетерминированного автомата в детерминированный, описывается построение таблицы переходов и графа переходов детерминированного автомата.
В разделе 6 описывается метод минимизации автомата, приводится процедура минимизации автомата, описывается построение таблицы переходов и графа переходов минимального автомата.
В разделе 7 описывается процедура построения сети Петри по праволинейной грамматике. Описывается построение для заданной праволинейной грамматики исходной сети Петри, описывается минимизация сети Петри – построение сети с позициями свободного выбора (недетерминированной сети), описывается устранение недетерминированности – построение детерминированной сети Петри. Описывается построение по полученной детерминированной сети Петри графа переходов минимального автомата. Производится сравнение графа автомата, построенного на основе сети Петри, с графом минимального автомата, полученным ранее.
1. Льюис Ф., Розенкранц Д., Стирнз Р. «Теоретические основы проектирования компиляторов». – М.: Мир, 1979.
2. Компаниец Р. И., Маньяков Е. В., Филатов Н. Е., «Системное программирование. Основы построения трансляторов». – СПб.: КОРОНА принт, 2000.
3. Мозговой М. В. «Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход». – СПб.: Наука и Техника, 2006.
4. Молчанов А. Ю. «Системное программное обеспечение: Учебник для вузов». – СПб.: Питер, 2003.
5. Синтез распознающего автомата. Методические указания к курсовой работе. – Новочеркасск: издание НПИ, 1987.
Учебное издание
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к курсовой работе по дисциплине
«Теория языков программирования и методы трансляции»
Сенилов Михаил Андреевич
(составление)
В редакции составителя
Подписано в печать . Формат 60х84/16. Бумага офсетная.
Гарнитура Таймс. Усл. печ. л. 0,93. Уч.-изд. л. 1,12. Тираж 50 экз. Заказ №
Отпечатано и изготовлено в Издательстве ИжГТУ.
426069, Ижевск, Студенческая ул., 7