SoftCraft
разноликое программирование

Top.Mail.Ru

Настраиваемые автоматные программы

© Б.П. Кузнецов ( Санкт-Петербург, 2006г.)

Благодаря публикациям А.А.Шалыто и В.С.Любченко применительно к кодированию программ в решении разнообразных задач возродилась и начала активно использоваться парадигма так называемого автоматного программирования. При этом решаемая задача, согласно теории конечных автоматов, разделяется на управляющую и операционную части, что применительно к программам ЦВМ соответствует управляющей программе и набору вычислительных процедур. Управляющая программа анализирует условия задачи и осуществляет выбор необходимых решающих процедур - действий. При этом алгоритм управления наиболее рационально задавать в виде диаграммы состояний (графа переходов) конечного автомата и последующим ее кодированием параллельно с кодированием решающих процедур. Основные публикации по данному вопросу сосредоточены на сайте www.SoftCraft.ru и в журналах «Мир ПК».

Подходы к кодированию автоматных программ названы: А.А.Шалыто SWITCH-технологией, а В.С.Любченко – КА-технологией. Общим для обоих подходов является по сути код списка дуг переходов, а основным различием – компиляция списка у А.А.Шалыто и интерпретация списка у В.С.Любченко. Общим недостатком обоих подходов является возможная неполнота кодируемых переходов вследствие неиспользования табличного представления функционирования конечного автомата, которое является основным, а графическое задание автомата лишь добавляет наглядность задачи управления, сродни сетевым графикам.

Во избежание этого недостатка предлагается проверенный временем вариант кодирования управляющей программы посредством оперирования непосредственно с таблицей переходов, совмещенной с таблицей выходов. Новизна предлагаемого подхода состоит в использовании шаблонного представления кода программы в ориентации на определенное максимальное число состояний конечного автомата и настройки ее на конкретный автомат. При этом существенно повышается вероятность избегания ошибок как в задании автомата так и в коде программы на выбранном языке. Рассмотрим подробно данную технологию, которую назовем IfTableSwitch–технологией (ITST).

Основу ITST составляет конечный С-автомат в качестве управляющей части проектируемой программы. Автомат может быть задан первично либо вне компьютера, либо в некоторой текстографической (см. ниже) среде как граф переходов и выходов. При этом реализация автомата и вызываемых им процедурных компонент осуществляется в программе посредством настройки шаблона, имеющего следующую структуру:

  1. Блок настроек, включающий:
    • описания констант;
    • описания внешних переменных;
    • заголовок автоматной программы;
    • описание внутренних переменных;
    • настраиваемую таблицу переходов и выходов типа 1;
    • настраиваемую таблицу выходов типа 2.
  2. Блок-заготовка для выбора буквы входного алфавита.
  3. Блок функционирования конечного автомата, включающий:
    • стандартный оператор определения выхода типа 1,
    • стандартный оператор определения нового состояния,
    • стандартный оператор определения выхода типа 2.
  4. Блок реализации выходов, включающий:
    • оператор трансляции номера состояния,
    • заготовку для реализации выхода типа 1 (вызова подпрограммы);
    • заготовку для реализации выхода типа 2 (вызова подпрограммы);

В отличие от принятого в школах А.А.Шалыто и В.С.Любченко процедурной реализации таблицы переходов и выходов (компиляцией и интерпретацией соответственно) в ITST явно используется настраиваемая таблица переходов и выходов в виде двухмерного массива и 3 стандартных оператора его обработки, реализуемых в большинстве компиляторов разнообразных языков. Кроме того, переменная состояния реализуемого автомата не доступна другим программам для исключения ее нечаянного искажения, но доступна из других программ специальная выделенная переменная – копия переменной состояния. Таблица переходов и выходов настраивается шестнадцатиричными (десятичными, восьмиричными) двухразрядными переменными с целью совмещения обозначений как состояния перехода, так и пометки выхода ( соответствующего автомату Мили) на переходе. Такое кодирование позволяет иметь шаблон для настройки на автомат с числом состояний от 2-х до 15-ти (девяти, семи).

В листинге 1 представлен обсуждаемый шаблон настраиваемого максимум на 15 состояний конечного автомата.

ЛИСТИНГ 1

// Шаблон автоматной программы A1
//
#include "A.h" // Подключение внешних переменных и констант
// Константы
#define MAXS_A1  15   // Число состояний автомата A1
#define MAXX_A1  15   // Число букв входного алфавита
#define MAXY1_A1 15   // Число букв выходного алфавита типа 1 (автомат Мили)
#define MAXY2_A1 MAXS // Число букв выходного алфавита типа 2 (автомат Мура)
// Внешние переменные
// Входные сигналы
extern int x0;
//...
extern int xN;
// Номера состояний автоматов других подпрограмм
extern int s_A2;
//...
extern int s_AK;
// Выходные сигналы
extern int z0;
//...
extern int zM;
// Вызываемые подпрограммы
void fault(int); // cообщение об ошибке
void y0_A1();
//...
void yl_A1();
// Копия номера состояния автомата А1
int s_A1 = 0;
//
void A1() // Программная реализация автомата А1
{
// Декларативная часть
// Внутренние переменные
static char s = 0; // номер состояния КА
int a;            // номер буквы входного алфавита
char y1;           // номер буквы выходного алфавита типа 1 (КА Мили)
static char y2;    // номер буквы выходного алфавита типа 2 (КА Мура)
// Таблица переходов и выходов типа 1
static unsigned char T1[MAXX_A1+1][MAXS_A1+1] = {
// s = 0    1    2    3    4    5    6    7    8    9    A    B    C    D    E    F |a=
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//0
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//1
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//2
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//3
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//4
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//5
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//6
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//7
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//8
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//9
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//10
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//11
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//12
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//13
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//14
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF} //15
                                                };
  // Таблица выходов типа 2
static unsigned char T2[MAXS_A1+1] =
// s = 0    1    2    3    4    5    6    7    8    9    A    B    C    D    E    F
  { 0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F};
//======================================================================================
// Процедурная часть
// Проверка номера состояния
  if(s == 0x0F || s >= MAXS_A1)
  { fault(-1); // Сообщение об ошибке кодирования состояния
    return ;
  }
//
// Выбор буквы входного алфавита
  a = (     )? 0:
      (     )? 1:
      (     )? 2:
      (     )? 3:
      (     )? 4:
      (     )? 5:
      (     )? 6:
      (     )? 7:
      (     )? 8:
      (     )? 9:
      (     )? 10:
      (     )? 11:
      (     )? 12:
      (     )? 13:
      (     )? 14:
               -1;
//////// Блок функционирования автомата
  if(a < 0 || a >= MAXX_A1)
  { fault(0); // Сообщение об ошибке кодирования входа
    return ;
  }
// Определение выхода типа 1
  y1 = T1[a][s] & 0x0F;
  if(y1 == 0x0F || y1 >= MAXY1_A1)
  { fault(1); // Сообщение об ошибке кодирования выхода типа 1
    return ;
  }
// Определение нового состояния
  s = T1[a][s] >> 4;
  if(s == 0x0F || s >= MAXS_A1)
  { fault(-1); // Сообщение об ошибке кодирования состояния
    return ;
  }
// Определение выхода типа 2
  y2 = T2[s];
  if(y2 == 0x0F || y2 >= MAXY2_A1 )
  { fault(2); // Сообщение об ошибке кодирования выхода типа 2
    return ;
  }
///////// Конец Блока функционирования автомата
//
//// Блок реализации выходов
  s_A1 = s;
  switch(y1)
  { case  0:            ; break;
    case  1:            ; break;
    case  2:            ; break;
    case  3:            ; break;
    case  4:            ; break;
    case  5:            ; break;
    case  6:            ; break;
    case  7:            ; break;
    case  8:            ; break;
    case  9:            ; break;
    case 10:            ; break;
    case 11:            ; break;
    case 12:            ; break;
    case 13:            ; break;
    case 14:            ; break;
    default:            ;
  }
  switch(y2)
  { case  0:            ; break;
    case  1:            ; break;
    case  2:            ; break;
    case  3:            ; break;
    case  4:            ; break;
    case  5:            ; break;
    case  6:            ; break;
    case  7:            ; break;
    case  8:            ; break;
    case  9:            ; break;
    case 10:            ; break;
    case 11:            ; break;
    case 12:            ; break;
    case 13:            ; break;
    case 14:            ; break;
    default:            ;
  }
  return;
} // end A1
// Головная программа
void main()
{
  while(1)
    A1();
} // end main.

КОНЕЦ ЛИСТИНГА 1

Рассмотрим процесс настройки шаблона на реализацию конечного автомата, представленного на рисунке 1. Автомат, назовем его А1, включает шесть состояний S0-S6, две буквы входного алфавита, определяемые как x0 и ~x0, две буквы выходного алфавита w1 и w2 типа 1 и три буквы выходного алфавита u0-u2 типа 2. Для иллюстрации полагаем, что w1 и w2 – вызываемые функции, а буквы u0-u2 кодируют операторы присваивания u = 0, u = 1, u = 2;

Рисунок 1

Настройка шаблона выполняется следующим образом. Сначала переопределяются константы МАХ, затем указывается входная переменная х0 и выходная u, перечисляются выходные функции w1 и w2. Далее в двухмерной таблице Т1 справа отсекаются столбцы, начиная с 7-й, и строки внизу таблицы, начиная с 4-ой (см. листинг 2). Затем настраивается оставшаяся часть таблицы Т1 на переходы и выходы типа 1. Столбцу таблицы Т1 соответствует текущее состояние s автомата, строке – буква входного алфавита а. Изначально каждая клетка таблицы Т1 заполнена шестнадцатиричным представлением числа «минус единица». Рассмотрим настройку первого столбца таблицы Т1. Префикс 0х шестнадцатиричного числа сохраняется во всех клетках. В столбце 0, соответствующему текущему состоянию S0 автомата выставляем два перехода: в первой строке вместо FF указываем 50, что означает переход в состояние S5, помеченный буквой 0 выхода типа 1 (w0); во второй строке этого столбца вместо FF указываем 31, то есть переход в состояние 3, помеченный буквой 1 выхода типа 1 (w1). Таким же образом кодируются переходы из состояний 1 – 5, соответственно в столбцах 1 – 5. Столбец 6 и строка 3 сохраняют шаблонную кодировку для ошибочных вычислений входа и состояния перехода.

ЛИСТИНГ 2

// Пример автоматной программы A1
//
// Константы
#define MAXS_A1  6   // Число состояний автомата A1
#define MAXX_A1  2   // Число букв входного алфавита
#define MAXY1_A1 2   // Число букв выходного алфавита типа 1 (автомат Мили)
#define MAXY2_A1 3   // Число букв выходного алфавита типа 2 (автомат Мура)
// Внешние переменные
// Входные сигналы
extern int x0;
// Выходные сигналы
extern int u;
// Вызываемые подпрограммы
void fault(int); // cообщение об ошибке
void w1_A1();
void w2_A1();
// Копия номера состояния автомата А1
int s_A1 = 0;
//
void A1() // Программная реализация автомата А1
{
// Декларативная часть
// Внутренние переменные
static char s = 0; // номер состояния КА
int a;            // номер буквы входного алфавита
char y1;           // номер буквы выходного алфавита типа 1 (КА Мили)
static char y2;    // номер буквы выходного алфавита типа 2 (КА Мура)
// Таблица переходов и выходов типа 1
static unsigned char T1[MAXX_A1+1][MAXS_A1+1] = {
// s = 0    1    2    3    4    5    - |a=
  { 0x50,0x50,0x31,0x20,0x31,0x01,0xFF},//0
  { 0x31,0x20,0x40,0x41,0x40,0x10,0xFF},//1
  { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},//-
                                                };
  // Таблица выходов типа 2
static unsigned char T2[MAXS_A1+1] =
// s = 0    1    2    3    4    5    -
  { 0x00,0x00,0x02,0x02,0x01,0x01,0x0F};
//======================================================================================
// Процедурная часть
// Проверка номера состояния
  if(s == 0x0F || s >= MAXS_A1)
  { fault(-1); // Сообщение об ошибке кодирования состояния
    return ;
  }
//
// Выбор буквы входного алфавита
  a = ( !x0  )? 0:
      (  x0  )? 1:
               -1;
//////// Блок функционирования автомата
  if(a < 0 || a >= MAXX_A1)
  { fault(0); // Сообщение об ошибке кодирования входа
    return ;
  }
// Определение выхода типа 1
  y1 = T1[a][s] & 0x0F;
  if(y1 == 0x0F || y1 >= MAXY1_A1)
  { fault(1); // Сообщение об ошибке кодирования выхода типа 1
    return ;
  }
// Определение нового состояния
  s = T1[a][s] >> 4;
  if(s == 0x0F || s >= MAXS_A1)
  { fault(-1); // Сообщение об ошибке кодирования состояния
    return ;
  }
// Определение выхода типа 2
  y2 = T2[s];
  if(y2 == 0x0F || y2 >= MAXY2_A1 )
  { fault(2); // Сообщение об ошибке кодирования выхода типа 2
    return ;
  }
///////// Конец Блока функционирования автомата
//
//// Блок реализации выходов
  s_A1 = s;
  switch(y1)
  { case  0: w1_A1(); break;
    case  1: w2_A1(); break;
    default:            ;
  }
  switch(y2)
  { case  0:    u = 0; break;
    case  1:    u = 1; break;
    case  2:    u = 2; break;
    default:            ;
  }
  return;
} // end A1
КОНЕЦ ЛИСТИНГА 2

Одномерная таблица Т2 настраивается номерами выходов типа 2 подстановкой номера выхода в последний разряд шестнадцатиричного числа с учетом того, что клетке соотвествует номер состояния автомата также как и столцам таблицы Т1. На этом декларативная часть программы завершается.

Далее следует информация текста программы, описывающая процедурную часть). Оставляем неизменным блок проверки номера состояния. Затем следует настроить выбор буквы входного алфавита то есть определение значения буквы а входного алфавита автомата. Далее сохраняем из шаблона Блок функционирования автомата и переходим к блоку реализации выходов из двух операторов switch, не требующему пояснений.

Использование таблицы Т1 позволяет избежать отсутствующих дуг переходов: если в таблице остается клетка, помеченная 0хFF – это свидетельство отсутствующего перехода, и надо очень хорошо позаботиться, чтобы клетка никогда не была задействована. Автор склонен к использованию полного входного алфавита, для чего и предусмотрен блок его настройки в виде цепочки if-else if-else if-...-else (см. оператор выбора буквы входного алфавита в листингах). При этом все комбинации входных сигналов, указываемые в звеньях этой цепочки должны быть ортогональны, требование чего снято в школах А.А.Шалыто и В.С.Любченко.

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

Рассмотрим особенности шаблона с восьмиричным кодированием таблиц. При этом вместо заполнения шаблона в каждой клетке величиной 0хFF применяется код 377. Число столбцов при этом равно восьми. При кодировании конкретного автомата в каждой клетке указывается трехразрядное число, первый разряд которого всегда установлен в 0. Остальные два разряда, как и при шестнадцатиричном кодировании обозначают номер состояния после перехода и номер выхода типа 1, помечающий переход. В рассматриваемом примере таблица 1 принимает вид: 

static unsigned char T1[MAXX_A1+1][MAXS_A1+1] = {
// s = 0     1    2    3    4    5    - | a=
   { 050,  050, 031, 020, 031, 001,0377},//0
   { 031,  020, 040, 041, 040, 010,0377},//1
   { 0377,0377,0377,0377,0377,0377,0377},//-
                                                };

Операторы типовой процедуры при этом принимают вид: 

// Определение выхода типа 1
  y1 = T1[a][s] & 007;
  if(y1 == 007 || y1 >= MAXY1_A1)
  { fault(1); // Сообщение об ошибке кодирования выхода типа 1
    return ;
  }
// Определение нового состояния
  s = T1[a][s] >> 3;
  if(s == 007 || s >= MAXS_A1)
  { fault(-1); // Сообщение об ошибке кодирования состояния
    return ;
  }
// Определение выхода типа 2
  y2 = T2[s];
  if(y2 == 007 || y2 >= MAXY2_A1 )
  { fault(2); // Сообщение об ошибке кодирования выхода типа 2
    return ;
  }

Наиболее просто осуществляется кодирование шаблона при использовании десятичной системы. При этом вместо кода 0xFF (377) в клетки таблиц Т1 и Т2 записывается число 99. При настройке на конкретный автомат используются только двухразрядное число, первый разряд которого – номер нового состояния, а второй – номер выхода типа 1, помечающий переход. Для рассматриваемого примера таблица 1 имеет вид: 

static unsigned char T1[MAXX_A1+1][MAXS_A1+1] = {
// s = 0  1  2  3  4  5  - |a=
    { 50,50,31,20,31, 1,99},//0
    { 31,20,40,41,40,10,99},//1
    { 99,99,99,99,99,99,99},//-

Следует иметь в виду, что при нулевом значении номера состояния перехода первый разряд опускается (см. 5-й столбец первой строки) Таблица 2 упрощается к виду: 

// Таблица выходов типа 2
static unsigned char T2[MAXS_A1+1] =
// s = 0 1 2 3 4 5 -
     { 0,0,2,2,1,1,9};

При этом операторы типовой процедуры при этом принимают вид: 

// Определение выхода типа 1
  y1 = T1[a][s] % 10;
  if(y1 == 9 || y1 >= MAXY1_A1)
  { fault(1); // Сообщение об ошибке кодирования выхода типа 1
    return ;
  }
// Определение нового состояния
  s = T1[a][s] / 10;
  if(s == 9 || s >= MAXS_A1)
  { fault(-1); // Сообщение об ошибке кодирования состояния
    return ;
  }
// Определение выхода типа 2
  y2 = T2[s];
  if(y2 == 9 || y2 >= MAXY2_A1 )
  { fault(2); // Сообщение об ошибке кодирования выхода типа 2
    return ;
  }

С использованием приведенных возможностей рекомендуется создать ряд шаблонов, например, на 3, 4, 6,... 11, 15 состояний и использовать их при настройке на конкретные реализации. Ортогонализация по входному алфавиту и прозрачность всех клеток таблицы 1 дают по сравнению со списком переходов в упомянутых школах больше оснований во избежание забытых переходов.

Школа А.А.Шалыто за основу программы, реализующей конечный автомат, берет графический рисунок (диаграмму состояний), в том числе подготовленный в графической среде (система UniMod), и практически игнорирует таблицы переходов и выходов. Поэтому для проверки правильности кодирования автомата применяет протоколирование. Школа В.С.Любченко также за основу принимает диаграмму состояний и тоже игнорирует таблицу переходов и выходов и проверка правильности реализуется только при функционировании программы. Для использования его подхода требуется специализированный модуль – интерпретатор списка переходов. Таким образом, проверка правильности кодирования в обеих школах переносится на отладочный этап кодирования.

Автор настоящей работы настоятельно рекомендует сверять диаграмму состояний с таблицей переходов и выходов, а также моделировать работу автомата до его кодирования в текст программы. В статье о моделировании автоматов электронными таблицами показана такая воможность. Более того, электронная таблица EXCEL позволяет использовать предложенный подход путем настройки шаблона и моделирования автомата до кодирования, которое можно осуществлять автоматически. На рисунке 2 показан таблично-графический шаблон автомата на 4 состояния в процессе его настройки на конкретную реализацию. Пример включает рисунок диаграммы состояний для С-автомата с 4-мя состояниями, изображенные цветными прямоугольниками в обеспечение планарности и исключения путаницы при пометке дуг переходов. Шаблон содержит также два варианта таблицы переходов, подлежащие тщательной проверки каждой их клетки. Данному представлению модели конечного автомата будет посвящена отдельная публикация.

Рисунок 2 (в натуральную величину)