Стили и методы программирования




Автоматизированное преобразование таблиц переходов - часть 3


Наконец, пусть

int handler ( int );

-обработчик строки (ее интерпретатор или транслятор), <понимающий> структуру T_StructTableLine, специфицируемый как функция, при выполнении которой должно быть определено очередное значение iSt. Значение iSt, не указывающее ни на какую строку таблицы, служит сигналом для завершения обработки (при желании можно заняться кодированием того, как завершилась обработка с помощью задания различных таких значений).

Тогда схема программы, которая оперирует с таблицей с помощью функции handler, может быть задана следующим циклом:

iSt = 0; do { iSt = handler ( iSt ); } while ( OUTSIDE ( iSt ) );

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

Логика функции handler, интерпретирующей таблицу, проста. Для правильной таблицы, не содержащей состояний, в которых возможны неопределенные переходы, она строится следующим образом:

  1. Извлечь значение Table[iSt];
  2. Активизировать вычисление условия обрабатываемой строки таблицы;
  3. Если условие истинно, то

    • активизировать подпрограмму действий;
    • читать очередной символ;
    • завершить handler со значением, извлекаемым из поля следующего состояния;

  4. Если условие ложно, то

    • iSt++;
    • Перейти к 1;

Осталось предусмотреть детали для заключительных состояний, но это сделать уже легко.

Таким образом, нужно научиться описывать структуру строки таблицы. На языке C++/С# эта задача может решаться довольно просто:

struct T_StructTableLine { // поле для имени состояния избыточно int (*condition)(); // поле условия void (*action)(); // поле действия int ref; // поле перехода: индекс строки таблицы, // которая будет обрабатываться следующей, // или признак завершения процесса }




Содержание  Назад  Вперед