В разделе 2.1 проведена формализация отдельных задач. В данном разделе часть алгоритмов оформляется в виде конструкторов классов, часть - в виде отдельных методов. И те, и другие в контексте выполнения задачи теории автоматов и грамматик будут именоваться «решающими методами».

При программировании использовались рекомендации пособия [23].

3.2.1 Конечный автомат

Известно, что конечный автомат характеризуется, помимо прочего, набором правил функции переходов (д). К примеру, для задачи построения ДКА по КА возможно задать КА в виде:

s1: a -> s1, s1: a -> s2, s2: b -> s3, s3: -> a s1 (s1 - нач, s3- кон)

Каждое правило представляет собой тройку «начальное состояние», «условие перехода», «конечное состояние». Согласно принципам ООП, каждую такую тройку можно считать отдельным объектом. Для хранения троек предусмотрен класс TransRule.

TransRule (от англ. Transition Rule) - простой ненаследуемый класс для хранения тройки Current, Symbol, Next. Объект такого класса представляет собой основную единицу КА - правило.

Базовым классом конечного автомата является StateMachine. Конечный автомат A характеризуется пятеркой A = (Q, ?, д, q0, F). В табл. 3 приведено соответствие данных понятий и методов класса.

Таблица 3. Соответствие понятий ТА и данных класса

Понятие	StateMachine
Множество состояний Q	string[] SetOfStates { get; }
Множество входных символов ?	string Alphabet { get; set; }
Функция переходов д	List<TransRule> StateTable bool FindNextStates(string curr, char sym, out string[] result) bool FindNextStatesForSet(List<string> set, char sym, out List<string> nextStates)
Начальное состояние q0	string StartState { get; set; }
Множество конечных состояний F	List<string> FinalState

Функция состояний защищена от прямого доступа (ключ private), доступ к остальным данным реализован через открытые свойства и методы.

Класс обладает несколькими конструкторами (инициализирующими методами), наиболее значимые из которых - StateMachine(string TransitionRules) и StateMachine(Grammar G).

Первый позволяет задавать класс вводом пользовательской строки в формате следующего вида с допущением дополнительных пробельных символов:

<rules> | <start> <fin>

Где start - начальное состояние,

fin - перечень заключительных состояний (через пробел),

rules - список правил вида <current> : <symbol> -> <next>, где

current - текущее состояние,

symbol - входной символ (условие перехода),

next = д(<current>,<symbol>).

Допускается любое количество правил в части <rules>, разделённых запятой. Проверяется допустимость имён (для состояний - любая последовательность букв и цифр, для входных символов - одна буква/цифра) и существование указанных начального и конечных состояний. В случае выявления ошибки на любом этапе программа сообщает о ней пользователю и вырабатывает исключение.

Для разбора строки TransitionRules вызывается закрытый метод ParseOK, заполняющий таблицу переходов StateTable и возвращающий false в случае проблемы. ParseOK задействует встроенный в .Net Framework механизм регулярных выражений (System.Text.RegularExpressions) и метод string.Split для выделения подстрок.

Другой конструктор выполняет задачу преобразования регулярной грамматики в конечный автомат согласно алгоритму в подразделе 2.1.5.

Важным методом является также DFMFromNFM(), приводящий вызывающий конечный автомат к детерминированному виду согласно алгоритму в подразделе 2.1.1.

Вывод конфигурации автомата в табличном формате или в виде списка правил осуществляется методом Show.

Помимо упомянутых, добавлен класс TRuleComparer, наследующий интерфейс IComparer<TransRule>. Данный класс предназначен для сортировки правил таблицы переходов по возрастанию, что реализуется в методе StateMachine.SortStateTable().

Код, демонстрирующий описанные классы, расположен в Приложении Б.1.

3.2.2 Формальная грамматика

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

Для хранения отдельной продукции разработан класс GramRule. Левая часть правил (Left) имеет символьный тип для предотвращения нарушения условия составления продукций КС-грамматик.

Базовым классом конечного автомата является Grammar. Объект грамматики G задаётся четвёркой G = <N, T, P, S>. Соответствие между элементами грамматики и открытыми свойствами класса представлено в табл. 4.

Таблица 4. Соответствие понятий ФГ и данных класса

Понятие	StateMachine
Множество нетерминалов N	string N { get; set; }
Множество терминалов T	string T { get; set; }
Множество продукций P	List<GramRule> P { get; }
Начальное состояние S	char S { get; set; } = 'S';

Класс обладает различными конструкторами по аналогии с классом StateMachine. Как и у класса конечного автомата, существует возможность задать грамматику перечислением правил или объектом StateMachine.

В первом случае перечень должен быть задан в формате

<NT> -> <cons1> |<cons2> | … | <consn>

Где NT - нетерминал левой части правила,

consi - последовательность правых частей, i [1,n], n > 0.

Во втором случае в конструктор передаётся ссылка на объект StateMachine, преобразование проводится по алгоритму из подраздела 2.1.3

Для вывода грамматики также существует метод Show, который может объединять правила c одинаковыми левыми частями в виде: S > б | в | …, где б и в - правые части исходных правил.

Для сравнения GramRule и сортировки правил существует класс GRuleComparer.

Код, демонстрирующий описанные классы, расположен в Приложении Б.2.

3.2.3 Формирование файлов с решением

Класс Reporter (Приложение Б.3) применяется для автоматического отслеживания данных, появляющихся в ходе решения задачи, записи их в текстовый файл и очередь решения. Объект Reporter создаётся как статическая глобальная сущность, получая при инициализации путь и расширение для сохранения файлов.

Для создания каждого файла вызывается метод MakeReport(string name, Function operation, string userInput), в который следует передать ссылку на одну из задач и входные данные. Введены объекты:

· Интерфейс IShowable. Требует от реализующих его классов предоставлять метод Show() и событие Report, где Show() - способ вывести действующую конфигурацию автомата, Report позволяет из любой точки проекта определить некоторое сообщение как шаг решения задачи. Классы Grammar и StateMachine реализуют данный интерфейс.

· Делегат сигнатуры bool Function(string input). Представляет собой шаблон для сценариев решения отдельных задач.

В Reporter также существует метод CompleteLog, который дописывает передаваемый в качестве аргумента шаг в открытый файл и очередь шагов Q. Метод должен быть подписан на события Report для автоматического отслеживания полезной информации, но может быть вызван вручную. По умолчанию классы Grammar и StateMachine подписают CompleteLog на свои события Report.

В случае, когда требуется сохранять только раздельную последовательность шагов для вывода, должен использоваться метод CompleteStages.

3.2.4 Задачи

На основе разработанных классов возможно выполнять различные сценарии. Для хранения таких сценариев разработан статический класс Tasks (Приложение Б.4). Каждый сценарий («Задача») реализован в виде отдельного метода. При необходимости выполнить одну из них с записью процесса в файл, пользователь должен вызвать MakeReport, передав в него функцию задачи, к примеру, Tasks.MakeDFAFromNDFA(input). После этого происходит следующее:

1. MakeFile формирует поток записи в файл и вызывает задачу в Tasks.

2. Управление передаётся задаче. В нем создаются необходимые классы, выполняется подписка на их Report, вызываются решающие методы.

3. Каждый решающий метод в ходе работы вызывает событие Report, в параметрах которого передаёт сообщение. Поддерживается обратная связь.

4. Событие Report обращается к Reporter.CompleteLog, который записывает данные в привязанный файл.

Для удобства интеграции сценариев задач и графического интерфейса все задачи включаются в коллекцию Operation, также принадлежащую классу Tasks. Объекты коллекции автоматически загружаются в объект ListBox.

3.3 Разработка графического интерфейса

На предыдущих этапах разработки определено, что программа нуждается в отображении списка доступных задач, воспроизведении выбранной задачи и выдаче справочных сведений.

Визуальный пользовательский интерфейс разрабатывается средствами WinForms в составе .Net и при поддержке VS. Сетка формы решения задачи и реализация взаимодействия с пользователем частично вдохновлены интерфейсом COCO/R.

Для прототипа главного окна системы был создан простой интерфейс (рис. 6). Элементы реализации и задействованные компоненты приведены ниже:

· Стандартные элементы окна Windows: свернуть, развернуть, закрыть;

· Строка меню MenuStrip. Пункт «Файл» для работы с файлами задач и отчётов, «Задача» для отправки тестовых файлов на выполнение и «Справка» для получения сведений о программе;

· Область навигации TabControl (слева), где возможно переключение между вкладками (теория и практика), в каждой из которых выводится список доступных элементов в компоненте ListBox;

· Рабочая область RichTextBox (справа), куда выводятся генерируемые инструкции;

· Строка состояния StatusStrip (внизу), отображает режим пользования и прогресс просматриваемой задачи.

Рисунок 6. Прототип интерфейса программной системы.

3.4 Демонстрация работы системы

На ранних этапах работы над системой использовался консольный ввод-вывод, достаточный для подтверждения функциональности системы. В дальнейшем тестирование системы проводилось в автоматизированном пакетном режиме. Для тестирования задач применялись текстовые файлы со описаниями задач (рис. 7), которые преобразовывались программой в описания процесса решения (рис. 8, 9).

Рисунок 7. Входные данные тестирования на примере первой задачи

Рисунок 8. Автоматически сгенерированные файлы в указанной директории



Рисунок 9. Пример выполнения сценария решения задачи

В случае пользовательского интерфейса задачи выполняются похожим образом. Различие состоит в том, что данные могут выводиться пошагово благодаря занесению строк событий Report не в файл, а в очередь вывода на экран, и потому могут выводиться постепенно по нажатию кнопки.

3.5 Рекомендации по дальнейшей разработке

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

Исходный код был дублирован в удалённый репозитории на сайте Github и может быть скачан вручную или, при наличии установленной Git, в текущую папку командой: git clone https://github.com/pixelJedi/ATFL.git .

3.5.1 Добавление и модификация задач

1. Открыть файл Task.cs, найти класс Task.

2. Добавить метод, соответствующий делегату Function:

public delegate bool Function(string input);

В методе должны создаваться необходимые объекты (автоматы StateMachine, грамматики Grammar) и вызываться их решающие методы в требуемом порядке. Существующие решающие методы автоматически записывают важные этапы выполнения в класс Reporter; при необходимости добавления дополнительных записей следует обращаться напрямую к классу Reporter через метод CompleteLog, используя соответствующие флаги (см. рис. 10).

Program.R.CompleteLog(Program.R,new ReportEventArgs(SM.Show('t'),'s'));

Рисунок 10. Оформление решения задачи на примере «Детерминизация КА».

Рекомендуется придерживаться общих принципов программирования. Установленный порядок написания метода также включает принципы:

· название метода однозначно определяет цель задачи;

· в начале сценария указываются стартовые данные с ключом `s';

· в конце сценария указывается результат с ключом `r';

· метод возвращает true, если выполнен успешно.

3. Для отображения новой задачи в графическом интерфейсе в список инициализации массива Operation добавляется объект Task: имя задачи, формат входных данных, описание задачи и имя сценария (рис. 11).

Рисунок 11. Включение задачи в список на примере «Детерминизация КА».

3.5.2 Добавление и модификация решающих методов

Решающие методы (см. разд. 3.2) - непосредственные методы базовых классов (Grammar, StateMachine), реализующие тот или иной математический алгоритм (разд. 2.1).

При работе над методами следует придерживаться общих принципов программирования на языке C#. Кроме того, особенностью данного проекта является событийная отправка сообщений в Program.R для последующего пошагового вывода. Каждое событие Report записывает переносимое сообщение в очередь «шагов» R.Q как один элемент. Таким образом, при разработке своего метода следует аккумулировать записи, относящиеся к одному действию, в единую строку, которую затем отправлять посредством Report (рис. 12).



Рисунок 12. Фрагмент решающего метода с отправкой сообщений в Report: 1 - одиночная запись, 2 - создание строки-аккумулятора, 3,4 - накопление результата, 5 - запись созданного шага в R

При формировании записей может быть удобным применение интерполяции строк [24], упрощающей запись переменных данных и форматирования. В общем случае при интерполяции перед соответствующей строкой ставится знак доллара ($), а переменные в строке заключаются в фигурные скобки.

3.5.3 Добавление новых флагов события Report

В прототипе программы используются следующие флаги (рис. 13):

Рисунок 13. Определение флагов

e - «end», обязательный автоматический флаг, определяет конец решения;

i - «input», автоматический флаг, добавляет входные данные в общую очередь;

s - «start», помечает сообщение как стартовые данные;

r - «result», помечает сообщение как результат задачи;

u - «usual», флаг по умолчанию, выводит строку без комментариев.

Чтобы определить новый флаг, изменяется метод GetNextStep() в Reporter.cs:

1. Найти блок switch, определяющий действия в зависимости от флагов.

2. Добавить блок case. Новый флаг должен представлять константу символьного типа. Согласно правилам синтаксиса C#, блок case должен оканчиваться ключевым словом break.

3. Внутри блока должна быть дополнена строка Step по аналогии с имеющимися примерами. Step - строка, добавляемая в рабочую область при нажатии Шаг.

3.5.4 Решение задачи посредством графического интерфейса

1. Запустить программу.

2. Открыть вкладку «Практика» и выбрать задачу.

3. Выбрать источник данных в Файл Открыть. Можно создать собственный файл txt с шаблонными данными в любом текстовом редакторе и выбрать его.

4. Рассчитать решение в Задача Вывести.

5. При нажатии на Шаг в текстовом поле выводится следующий шаг решения. В прототипе программы данные также сохраняются в директории по умолчанию (изменить директорию можно в Файл Настроить).

3.5.5 Написание файлов с тестовыми конфигурациями

Наиболее простой способ получить решения задач - создание текстового файла с входными строками и запуск пакетной обработки.

Формат строк в файле зависит от выбранной задачи. Так, задача детерминизации конечного автомата требует перечисления правил перехода в формате <rules> | <start> <fin>. Пример такого ввода может быть найден в разделе 3.4 (рис. 7). Для уточнения формата входных данных можно обратиться к методу соответствующей задачи в исходном коде или выбрать Задача Показать формат.

После создания файла он открывается посредством Файл Открыть и запускается стандартным способом.

Выводы из раздела

На данном этапе проекта разработана программа, способная решать тестовые задачи, записанные в текстовом файле, и генерировать файлы с решениями, а также выводить решения пошагово в специальное окно. Основным результатом работы стал исходный код программной системы на языке C# .Net, наиболее значимой частью которого являются файлы классов конечного автомата (StateMachine) и грамматики (Grammar), вокруг которых выстраиваются все взаимодействия. Не менее важны классы задач (Task) и генератора письменных описаний (Reporter). Наконец, файлы пользовательского интерфейса представляют удобную оболочку для безопасного доступа к возможностям основных файлов. Основными модифицируемыми элементами являются сценарии задач Tasks.

В дальнейшем предполагается ряд модификаций, как косметических, так и архитектурных.

Планируемые общие изменения:

· добавление новых задач;

· расширение справочной системы комментариями в XML-формате.

Планируемые архитектурные модификации:

· наследование классов Grammar и StateMachine для разделения разных типов грамматик и машин состояний, обеспечение преобразований между классами;

· дополнение событийного механизма возможностью передачи текущей конфигурации обрабатываемого объекта (например, грамматики);

· качественная валидация входных файлов, предварительно определяющая их пригодность для решения конкретной задачи;

· модификация очереди Report.Q таким образом, чтобы при пакетной обработке оставалась возможность возврата к прочитанным решениям.

Модификации GUI:

· возможность вывода состояний объектов в отдельном окне или рабочей зоне;

· ввод данных в иных, более удобных формах (таблицы, диаграммы).



Заключение

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

Во-первых, проведён теоретический анализ предметной области, в рамках которого выделены существующие понятия, аналоги и их особенности. На основании полученной информации был составлен приблизительный образ программы и приобретено представление об удачных примерах реализации, таких, как COCO/R и JFLAP.

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

В-третьих, с учётом выявленных структур произведён выбор подходящих технологий и инструментов программирования, которые затем были применены на практике. Так, написан и протестирован код ПО и GUI.

Итак, основным результатом работы стал исходный код программной системы - классы Grammar, StateMachine и другие. С использованием данных сущностей возможно построение и решение различных типов задач. В случае необходимости расширения возможностей достаточно пополнить перечень методов соответствующего класса. Поскольку каждый файл имеет подробные комментарии, понимание структуры классов не является трудоёмкой задачей. В перспективе усовершенствование графического интерфейса, перенос на более современный графический движок WPF, добавление сетевых взаимодействий. Возможен также выпуск web-версии, основанной на существующем коде.



Приложение

UML

Диаграмма 1. Диаграмма прецедентов с точки зрения потребителя ПО



Диаграмма 2. Диаграмма последовательностей. Решения задачи в пакетном режиме



Диаграмма 3. Диаграмма последовательностей. Решения задачи для пошагового вывода

Диаграмма 4. Диаграмма классов. Общая структура



Диаграмма 5. Диаграмма состояний. Взаимодействие с системой

Размещено на Allbest.ru

...