Компактное представление конечного автомата
Подготовка исходного кода С для инициализации большой матрицы может оказаться довольно утомительной. Кроме того, если каждый элемент матрицы переходов будет содержать полную информацию о выполняемом действии и следующем состоянии, то для размещения матрицы потребуется большой объем памяти. Для обеспечения возможности создания небольшой матрицы переходов и упрощения ее инициализации в нашем коде применяется компактное представление конечного автомата. Считыватели с последовательным интерфейсом. Биометрические считыватели.
Фактически эти структуры данных позволяют программисту создать компактную структуру данных, которая представляет конечный автомат, а затем предусмотреть развертывание в программе соответствующей матрицы переходов во время выполнения. Файл tnfsm.h содержит объявление структуры fsm_trans, применяемой в компактном представлении.
/* Файл tnfsm.h */
/* Состояния конечного
define TSDATA
tdefine TSIAC
tdefine TSWOPT
tdefine TSDOPT
tdefine TSSUBNEG
tdefine TSSUBIAC
tdefine NTSTATES
автомата вывода в сокет TELNET: */
0 /* Обработка обычных данных */
1 /* Обнаружен символ IAC */
2 /* Обнаружены символы IAC-{WILL/WONT} */
3 /* Обнаружены символы IAC-{D0/D0NT} */
4 /* Обнаружены символы IAC-SB */
5 /* Обнаружены символы IAC-SB-...-IAC */
6 /* Число состояний TS* */
/* Состояния конечного автомата ввода с клавиатуры TELNET: */
tdefine tdefine
KSREMOTE KSLOCAL
tdefine KSCOLLECT
tdefine NKSTATES
0 /* Введенные данные передаются в сокет */
1 /* Введенные данные передаются в локальную */
/* функцию */
2 /* Введенные данные представляют собой имя */
/* файла протокола */
3 /* Число состояний KS* */
/* Состояния конечного автомата уточнения опции TELNET: */
Компактное представление конечного автомата состоит из одномерного массива структур fsm_trans. Каждый элемент определяет один переход. Поле ft_state задает состояние конечного автомата, с которого начинается переход. Поле ft_char указывает символ, который вызывает переход (или TCANY для обозначения всех символов, отличных от указанных явно в качестве причины перехода). Поле ftjiext определяет состояние, в котором завершается переход, а поле ft_action содержит адрес вызываемой процедуры, которая выполняет действие, связанное с переходом.
Форма компактного представления, применяемая во время выполнения
В рассматриваемом примере клиентской программы не предусмотрено копирование всей информации из компактного представления в матрицу переходов. Вместо этого в нем компактное представление остается неизменным и служит для хранения информации о переходах. Для этой цели в программном обеспечении предусмотрено хранение в каждом элементе матрицы переходов целого числа. Это целое число определяет индекс записи в компактном представлении, соответствующей переходу. Соответствующие структуры данных показаны на рис. 26.6.
Реализация компактного представления
Файл ttfsm.c содержит пример компактного представления для конечного автомата, принципиальная схема которого приведена на рис. 26.4.
Массив ttstab содержит 22 действительные записи, каждая из которых соответствует одному из переходов, показанных на рис. 26.4 (а также дополнительную запись, отмечающую конец массива). Каждая запись в массиве состоит из структуры fsm_trans, которая определяет один переход. Следует отметить, что массив ttstab является и компактным, и удобным в определении. Он является компактным, поскольку не содержит пустых записей; он является удобным в определении, поскольку каждая запись непосредственно соответствует одному из переходов конечного автомата.