Рассматривается решение задачи подсчета длин слов в строке на основе автоматного подхода. Описан ряд методов реализации автоматов.
В книге [1] в главе «Методы программирования от состояний» предлагается несколько процедурных способов реализации автоматов, а в главе «Объектно-ориентированный подход» предлагаются идеи по реализации автоматов с помощью объектов. К сожалению, описание предложенных в книге методов реализации автоматов является недостаточно четким, что может создать сложности при их применении на практике. Часть этих методов описана также и в книге [2], где появились главы по автоматному программированию, названные так со ссылкой на работу [3].
В данной статье рассматривается пять методов реализации автоматов: четыре процедурных и один объектно-ориентированный. Объектно-ориентированный метод в книге [1] представляет собой лишь набор идей, применение которых невозможно без дополнительной доработки.
Авторы попытались устранить указанные недостатки. В работе предложены шаблоны для реализации автоматов различными методами. Кроме этого сделана попытка выделить общую часть реализации автоматов, не зависящую от метода процедурной реализации. Применение методов, как и в книге [1], иллюстрируется на примере подсчета длин слов в тексте. Примеры написаны на языке C++ (листинги и полную версию статьи см. на «Мир ПК-диске»). Для изображения графа переходов автомата используется нотация, предложенная в работе [4].
Постановка задачи
На вход программы подается строка символов, состоящая из слов и разделителей. Она завершается символом перевода строки ? ?. Под словом понимается непустая последовательность букв латинского алфавита. Его символы будем называть символами слова. Разделителем считается любой символ, не являющийся символом слова или символом перевода строки.
Программа должна преобразовывать <строку символов> в последовательность строк вида: <слово> - <длина слова>
Например, если на вход программы подана строка
dasda fsdf2dfsfs
то программа формирует следующую выходную последовательность строк:
dasda - 5
fsdf - 4
dfsfs - 5
Как отмечалось выше, в работе строится пять программ, в каждой из которых используется автоматный подход, однако методы реализации автомата в этих программах различны.
Автомат. Описание и формализация
Приведем словесное описание алгоритма подсчета длин слов в тексте. При получении символа слова он записывается в выходной поток, счетчик символов в слове увеличивается на единицу. В случае разделителя, если перед ним поступил символ слова, в выходной поток записывается строка вида:
-<длина слова><перевод строки>
и счетчик длины слова сбрасывается в ноль.
При получении символа перевода строки автомат завершает работу и, если перед ним поступил символ слова, в выходной поток записывается строка вида:
-<длина слова><перевод строки>
Для решения поставленной задачи построим автомат, в котором переходы выполняются по событию e0 — «Приход символа из входного потока». Введем две булевы переменные x1 и x2. Переменная x1 принимает значение «истина», если по событию e0 пришел символ слова, а переменная x2 принимает то же значение, если по событию e0 пришел символ перевода строки. Заметим, что переменные x1 и x2 не могут принимать значение «истина» одновременно.
Построим автомат с тремя состояниями и опишем каждое из них.
- Ожидание начала слова — автомат начинает работу в этом состоянии и переходит в состояние 1, если x1 — «истина» (получен символ слова), и в состояние 2, если x2 — «истина» (получен символ перевода строки).
- Обработка слова — автомат переходит из этого состояния в состояние 0, если x1 — «ложь» и x2 — «ложь» (получен разделитель), и в состояние 2, если x2 — «истина» (получен символ перевода строки).
- Работа завершена — при попадании в это состояние автомат завершает работу. Переходы из этого состояния в другие невозможны.
Опишем действия, выполняемые на переходах:
- z1_0 (записать символ в выходной поток) — выполняется при переходе из состояния 0 в состояние 1, а также когда автомат остается в состоянии 1 при приходе нового символа;
- z1_1 (записать в выходной поток «длину слова») — выполняется при переходе из состояния 1 в состояния 0 и 2;
- z2_0 (установить счетчик символов в слове в 0) — выполняется при переходе из состояния 0 в состояние 1, а также в том случае, когда автомат остается в состоянии 1 при приходе нового символа;
- z2_1 (увеличить счетчик символов в слове на единицу) — выполняется при переходе из состояния 1 в то же состояние.
Схема связей автомата, описывающая его интерфейс, приведена на рис. 1, а граф переходов, описывающий поведение автомата, — на рис. 2.
Методы реализации автомата
Общие функции и переменные для процедурных способов реализации автомата
Во всех рассматриваемых реализациях автомата, выполненных с помощью процедурных методов, функции для входных переменных, выходных воздействий, внутренние переменные, а также функция, реализующая событие, не изменяются.
Реализация этих функций и определение переменных состоит из следующих частей:
- определение внутренних переменных;
- функции входных переменных;
- функции выходных воздействий;
- функции, реализующие событие.
Метод 1. Каждому состоянию сопоставляется рекурсивная функция
Для каждого состояния записывается функция, в которой реализуются все возможные действия в этом состоянии. Чтобы запустить автомат, в данном случае требуется вызвать функцию, соответствующую его начальному состоянию.
Недостаток данного метода состоит в том, что в нем используются рекурсивные функции. Поэтому количество переходов по дугам, которые может совершить такой автомат, ограничено размером стека.
Шаблон для функции, реализующей действия для состояния
Метод 2. Реализация автомата с помощью оператора switch
Чтобы избавиться от рекурсивных вызовов, используемых в методе 1, можно ввести переменную, в которой хранить текущее состояние автомата, а вместо вызова функции, соответствующей состоянию автомата, изменять значение этой переменной.
Шаблон для реализации автомата
Метод 3. Каждому состоянию сопоставляется нерекурсивная функция
Этот метод основан на двух предыдущих. Для каждого состояния реализуется функция (в данном случае нерекурсивная), которая определяет операции — выходные воздействия для этого состояния и состояний, в которые автомат может перейти. В отличие от первого метода переход в новое состояние осуществляется не внутри функции, а в операторе switch. Функция только возвращает следующее состояние. Как и во втором методе, для хранения текущего состояния вводится переменная, используемая в операторе switch.
Шаблон для функции, реализующей операции для состояния
Шаблон для реализации автомата
Метод 4. Реализация автомата с помощью безусловных переходов по меткам
В данном методе для управления состояниями автомата предлагается использовать метки и операторы безусловного перехода. При изменении состояния автомат переходит на метку, соответствующую новому состоянию. Такой подход позволяет избавиться от необходимости хранить состояние автомата в переменной.
Шаблон для реализации автомата
Метод 5. Объектно-ориентированный подход
Класс ставится в соответствие состоянию автомата
При применении данного метода предлагается описать все состояния автомата в виде потомков некоего базового класса состояния. При этом в базовом классе определяются функции входных переменных, выходных воздействий и указатель на объект данных автомата. Кроме того, в базовом классе объявляется абстрактный метод execute, возвращающий указатель на объект базового класса состояния. Этот метод предназначен для определения нового состояния автомата и должен быть переопределен в классах-потомках.
Для работы автомата требуется вызывать указанный метод у текущего объекта класса состояния, изменяя текущее состояние на результат выполнения метода до тех пор, пока не придем в конечное состояние.
В объекте данных автомата хранятся указатели на объекты классов состояний, внутренние данные автомата, методы, реализующие события. Объект данных отвечает за создание и разрушение объектов состояний.
Базовый класс автомата включает в себя следующие части:
- указатель на объект данных автомата (pMainData);
- функции входных переменных;
- функции выходных воздействий;
- конструктор и деструктор;
- объявление абстрактного метода, реализующего действия для состояния (execute).
Шаблон для базового класса состояния
Класс состояния включает в себя следующие части:
- конструктор;
- метод, реализующий действия для состояния (execute).
Класс данных включает в себя следующие части:
- конструктор и деструктор;
- указатели на объекты состояний;
- внутренние переменные;
- функции, реализующие события.
В работе предложены пять шаблонов для реализации автоматов, позволяющих формально преобразовать графы переходов автоматов в код программы. Поэтому достаточно просто осуществить и обратное преобразование. Предложенные шаблоны можно использовать для автоматизации указанного процесса. Метод реализации автомата с помощью рекурсивной функции является скорее учебным, так как количество переходов по дугам автомата ограничено размером стека.
Листинги и полную версию статьи см. на «Мир ПК-диске».
Литература
- Непейвода Н.Н., Скопин И.Н. Основания программирования. Москва — Ижевск: Институт компьютерных исследований, 2003. http://ulm.udsu.ru/~nnn/index.html
- Непейвода Н.Н. Стили и методы программирования. М.: Интернет-университет информационных технологий, 2005.
- Шалыто А.А. SWITCH-технология. Алгоритмизация программирования задач логического управления. СПб.: Наука, 1998.
- Шалыто А.А, Туккель Н.И. Программирование с явным выделением состояний // Мир ПК. 2001, № 8, c. 116; № 9, c. 132. http://is.ifmo.ru/works/mirk/
Павел Геннадьевич Лобанов — магистрант кафедры «Компьютерные технологии» С.-Петербургского государственного университета информационных технологий, механики и оптики (СПбГУ ИТМО); plobanov@rain.ifmo.ru.
Анатолий Абрамович Шалыто — доктор технических наук, профессор, заведующий кафедрой «Технологии программирования» СПбГУ ИТМО; shalyto@mail.ifmo.ru.
