10: Автоматное программирование: от таблицы к программе

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

Анализ состояния дел

Построение таблиц заканчивает этап спецификации нашей программы. Таблицы 9.1 и 9.2-другое формализованное представление рисунков9.6 и 9.7. Как всегда, разные формализмы отличаются по практической направленности. Граф в некоторых случаях может быть автоматизированно преобразован в прототип программы (попытайтесь сами проделать это со спецификацией на языке UML ), но получающиеся программы всегда требуют ручной доработки. Табличное же представление допустимо рассматривать как мини-язык программирования. Для него возможно построение транслятора или интерпретатора, которые в частных типах таблиц давно уже используются (их широкому применению мешает привязка к конкретным предметным областям и приложениям, поскольку профессиональные системные программисты свысока смотрели на столь простые задачи).

Обратимся к семантике вычислений на языке таблиц. Рассматривается контекст некоторой программы на языке C++ (или на другом языке традиционного типа). В этом контексте определяется значение переменной Entry (множество ее значений совпадает с множеством наименований состояний), далее выполняются следующие действия:

1. Выбрать вход в таблицу, соответствующий значению Entry (текущее состояние).
2. Если Условие отсутствует, то перейти к шагу 4.
3. Вычислить совместно все Условия срабатывания переходов (клетки второй колонки для данного входа):
4. • Если среди результатов есть значения True, то выбрать одну из строк, Условие которой истинно, и перейти к шагу 4 для выбранной строки¹ ;
   • Если все значения Условий ложны и есть строка failure, то выбрать эту строку и перейти к шагу 4 для нее;
   • Если все значения Условий ложны и нет строки failure, то завершить вычисления.
    
5. Выполнить Действие.
6. В качестве значения переменной Entry установить наименование состояния-преемника (из четвертой колонки таблицы). Перейти к шагу 1.

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

• start - указание действий, которые выполняются до основных действий и проверок условий перехода (здесь таким действием является чтение очередного символа из файла);
• finish -указание действий, которые выполняются после основных действий и проверок, но до перехода.

Можно также определять локальные данные для состояний (в примере такие данные определены только для начального состояния), но это должно быть согласовано с правилами локализации имен языка программирования и с общим стилем, в котором написана программа. Заметим, что локальные данные всех состояний конечного автомата должны быть помещены в общий контекст, а приписывание их к конкретным состояниям является ограничением видимости, подобным тому, которое используется в модульном программировании (если Вы уже программировали на Object Pascal Delphi, Java либо Oberon, то знакомы с модульностью). Это прагматически следует из того положения, что работа теоретического конечного автомата не требует привлечения памяти².

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

1. Оттранслировать вручную.
2. Отдать препроцессору для превращения в нормальную программу.
3. Использовать интерпретатор.

Рассмотрим последовательно эти три возможности.

Ручная трансляция таблиц переходов

В решениях 1 и 2 возникает следующий вопрос: во что транслировать таблицу переходов? Вариантов множество, ниже рассматриваются лишь некоторые из них.

Вариант 1.Можно считать St1 и St2 функциями, реализующими все действия состояний.При использовании верно подобранных стиля и инструментальных средств этот подход дает отличный результат. Рассмотрим, в частности, как может быть реализована наша задача (еще точнее, автомат таблицы 9.1) на языке Рефал.

ENTRY Go{=<Open 'r' 1 'input.txt'><Open 'w' 2 'output.txt'><Init<Get 1>>};
Letters {='abcdefghijklmnopqrstuvwxyz';};
Init{=;
    e.1=<St1 e.1>;};
St1 {
    s.1 e.3,<Letters>: e.A s.1 e.B =<St2 e.3 (s.1)>;
    = <Init<Get 1>>;
    s.1 e.3 =<St1 e.3>;
    };
St2 {(e.2)= <Outstr e.2> <Init<Get 1>>;
    s.1 e.3 (e.2),<Letters>: e.A s.1 e.B =<St2 e.3 (e.2 s.1)>;
    s.1 e.3 (e.2)=<Outstr e.2><St1 e.3 >;
    };
* St3 не нужно
Outstr {
    e.2, <Lenw e.2>: {s.1 e.2 = <Putout 2 e.2 " - " <Symb s.1>>;};
    };
*
* Вторая программа, чуть дальше от непосредственной автоматной модели
*
$ENTRY Go{=<Open 'r' 1 'input.txt'><Open 'w' 2 'output.txt'><Init <Get 1>>};
Letters {='abcdefghijklmnopqrstuvwxyz';};
Init {=;
    e.1=<Parse e.1()>;};
Parse {
    s.1 e.3 (e.2),<Letters>: e.A s.1 e.B =<Parse e.3 (e.2 s.1)>;
    (e.2)= <Outstr e.2> <Init<Get 1>>;
    s.1 e.3 (e.2)=<Outstr e.2><Parse e.3 ()>;
    };
Outstr { = ;
    e.2, <Lenw e.2>: {s.1 e.2 = <Putout 2 e.2 " - " <Symb s.1>>;};
    };

Эти программы настолько коротки и естественны, что практически не требуют комментариев. Единственная новая возможность, использованная здесь, в принципе излишняя, но делает программу красивее. Конструкции <Letters>: e.A s.1 e.B и e.2, <Lenw e.2>: являются, соответственно, вложенной проверкой условия на выражении, порождаемом вызовом <Letters>, и вызовом определяемой дальше анонимной функции на выражении, получившемся после запятой. Стандартная функция <Lenw e.2> добавляет первым символом к выражению его длину (количество термов в нем). При проверке и при вычислении вспомогательной функции переменные, уже получившие значения, не изменяются.

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

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

Формально функциональное представление состояний возможно как на языке традиционного типа, так и на LISP и Prolog. Но в этом случае мы проигрываем в выразительности и естественности программы, а также еще по одному важному критерию. Во всех этих случаях то, что выглядит как рекурсия, действительно ею является, а рекурсия в данном случае лишь мешает.

Вариант 2. Считать St1, St2, St3 значениями некоторого перечислимого типа State.

// Реализация автомата с табл. 9.1
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

char symbol;
int cnt;

enum States { St1, St2, St3 } State;
void main( void )
{fstream a,b;
    a.open("input.txt",ios::in);
    b.open("output.txt",ios::out);
    State = St1;
    while (true )
    {symbol=a.get();
        switch ( State )
        { case St1: if ('a'<=symbol && symbol <= 'z')
            { b<<symbol;
                cnt = 1;
                State = St2;
        }
        else if (symbol != '\n') {State = St1;}
        else if (symbol == '\n') State = St3;
        break;
    case St2: if ('a'<=symbol && symbol <= 'z')
            {b<< symbol;
            cnt++; // State = St2;
            }
        else if (symbol != '\n')
            { b<<" - "<<cnt<<endl;
                State = St1;
            }
    else if (symbol == '\n')
        { b<<" - "<<cnt<<endl;
            State=St3;
        };
        break;
    case St3: if ('a'<=symbol && symbol <= 'z')
            { b<< symbol;
                cnt = 1;
                State = St2;
        }
        else if (symbol != '\n') {State = St1;}
        else if (symbol == '\n')
            { a.close(); b.close(); return;};
    } }
}

Программа 10.2.2 хороша только в том случае, если ограничиться автоматными моделями в достаточно узком смысле. Программа точно соответствует табличному представлению автомата, почти все дублирования действий, связанные с таким представлением, остались. Возникает некоторая неудовлетворенность тем, что появилось лишнее действие: выбор выполняемого фрагмента по значению переменнойState. Если ограничиться управляющими средствами методологии структурного программирования, то это - наилучший выход. Попытки применить циклы внутри фрагментов, помеченных как case St1: и case St2:, приводят лишь к уменьшению наглядности по сравнению с табличным представлением.

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

Следующая программа 10.2.3 почти буквально реализует данную идею. В отличие от программы 10.2.2, тип States содержит четыре значения: St1, St2, St3 и Exit. Последнему из них не соответствует ни одна функция из-за тривиальности переходов и действий в данном состоянии.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

char symbol;
int cnt;
enum States { St1, St2, St3, Exit } State;

inline States f_St1 ()
{
    if ('a'<=symbol && symbol <= 'z')
        printf ("%c", symbol);
        cnt = 1;
        symbol = getchar (); return St2;
    }
    else if (symbol != '\n') {
            symbol = getchar (); return
        }
    else {symbol = getchar (); return
}

inline States f_St2 ()
{
    if ('a'<=symbol && symbol <= 'z')
        printf ("%c", symbol);
        cnt++;
        symbol = getchar (); return St2;
    }
    else if (symbol != '\n') {
        printf (" -%i\n", cnt);
        symbol = getchar (); return St1;
    }
    else {
        printf (" - %i\n", cnt);
        symbol = getchar (); return St3;
    }
}

inline States f_St3 ()
{
    if ('a'<=symbol && symbol <= 'z') {
        printf ("%c", symbol);
        cnt = 1;
        symbol = getchar (); return St2;
    }
    else if (symbol != '\n') {
            symbol = getchar (); return St1;
        }
    else return Exit;
}

void main( void )
{
    symbol = getchar ();
    State = St1;
    for (;;)
        { switch ( State ) {
            case St1: State = f_St1 ();
                break;
            case St2: State = f_St2 ();
                break;
            case St3: State = f_St3 ();
                break;
            default: return;
        }
    }
}

Следует обратить внимание на то, что программа наглядна, строго соответствует таблице автомата. Можно сказать, что граф автомата определяет распределенную по состояниям схему потоковой обработки. На самом деле она гораздо лучше подходит модели вычислений в состояниях, а не на переходах. Более того, эта программа при небольшом увеличении числа состояний быстро теряет наглядность, если программировать на переходах, поскольку следующие состояния упрятаны внутри соответствующих процедур, но сохранит ее, если программировать в состояниях.

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

Проанализировав граф автомата или таблицу, можно заметить, что в данном примере, наряду с циклом потоковой обработки, имеется еще один цикл: передача управления между состояниями. Это причина, из-за которой в двух предыдущих вариантах появились присваиваниепеременной State значения и выбор выполняемого фрагмента по этому значению.

Особенность последовательностей действий

State = <значение>;

switch ( State )

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

А нельзя ли использовать это явно для организации управления конечным автоматом? Можно, это демонстрирует четвертый вариант решения обсуждаемой задачи.

Вариант 4. Матрица переходов и вектор-функций, соответствующих состояниям⁴

program funcgoto;
{$APPTYPE CONSOLE} {$T+}
uses SysUtils;

type P=procedure;
type Pp= ^P;
const maxstate = 7;
const maxcond = 3;
type states = 1.. maxstate;
conds = 1.. maxcond;
type table = array [states, conds] of states;
type act = array [states] of P;
const gotos: table = ((2,2,2),(3,2,4),(3,5,6),(3,2,7),(3,2,4),(3,2,7),(1,1,1));
var Symbol: char;
var Cnt: integer;
var Inf, Outf: text;
var state: states;

procedure Start;
begin
    Cnt:=0;
    AssignFile(Inf, 'input.txt');
    Reset(Inf);
    AssignFile(Outf, 'output.txt');
    Rewrite(Outf);
end;

procedure Finish;
begin
    Closefile(Inf);
    Closefile(Outf);
    Abort;
end;

procedure St1;
begin
    {No actions}
end;

procedure St2;
begin
    write(outf,Symbol);
    Inc(Cnt);
end;

procedure St4;
begin
    writeln(outf,' - ',Cnt);
    Cnt:=0;
end;

const actions: act = (Start, St1,St2,St1,St4,St4,Finish);

begin
    state:=1;
    while true do begin
        actions[state];
        if (state <>1) and (state<>7) then begin read(inf,Symbol);
        if Ord(Symbol)=10 then read(inf,Symbol) end;
        if Symbol in ['a'..'z'] then state:= gotos[state,1];
        if not(Symbol in ['a'..'z']) and (Ord(Symbol)<>13)
            then state:=gotos[state,2];
        if Ord(Symbol)=13 then state:=gotos[state,3];
    end;
end.

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

Рассмотрим последний вариант.

Вариант 5. Использование статической информации о разветвлениях вычислений.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

char symbol;
int cnt;
void main( void )
{
    symbol = getchar ();
St1: if ('a'<=symbol && symbol <= 'z') {
                printf ("%c", symbol);
                cnt = 1;
                symbol = getchar (); goto St2;
            }
            else if (symbol != '\n') {
                symbol = getchar (); goto St1;
        }
        else /* (symbol == '\n') */ {symbol = getchar (); goto St3;};
St2: if ('a'<=symbol && symbol <= 'z') {
                printf ("%c", symbol);
                cnt++;
                symbol = getchar (); goto St2;
            }
            else if (symbol != '\n') {
                printf (" -%i\n", cnt);
                symbol = getchar (); goto St1;
            }
            else {
                printf (" -%i\n", cnt);
                symbol = getchar (); goto St3;
            };
St3: if ('a'<=symbol && symbol <= 'z') {
                printf ("%c", symbol);
                cnt = 1;
                symbol = getchar (); goto St2;
            }
            else if (symbol != '\n') {
                symbol = getchar (); goto St1;
            }
            else /* (symbol == '\n') */ return;
}

В данном варианте исчезает необходимость вычисляемого перехода (результат внедрения статической информации в текст программы), и, как следствие, становятся избыточными описания типа States и переменной State этого типа. В программе появляются операторы безусловного перехода, из-за этого структура управления программы полностью расходится с канонами структурного программирования, что дает повод догматически мыслящим программистам и теоретикам подвергать критике такой вариант программы. Но в данном случае отступление от канонов структурного программирования полностью оправдано, поскольку за счет специального расположения фрагментов текста вся программа оказалась похожа на таблицу конечного автомата, а структура передач управления копирует граф конечного автомата. Более того, такое представление нейтрально по отношению к моделям Мура и Мили. Таким образом, лишь после полного отхода от канонов структурности программа стала адекватна своей спецификации.

Автоматизированное преобразование таблиц переходов

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

_1         char symbol;                    // Чтение потока символов неявное
           int cnt;
               . . .                       // Инициализация          _4 St1 _5
_1 St1 _2  'a'<=symbol && symbol <= 'z' _3 printf ("%c", symbol);
           cnt = 1;                                                  _4 St2 _5
_1     _2  //symbol <'a' && 'z'< symbol && symbol != '\n'
                                        _3
           //Так как нужно печатать только слова,
           //действий нет                                            _4 St1 _5
_1     _2  failure                      _3
           // symbol == '\n' не нужно читать                         _4 St3 _5
_1 St2 _2  'a'<=symbol && symbol <= 'z' _3 printf ("%c", symbol);
                                           cnt++;                    _4 St2 _5
_1     _2  //(symbol <'a'||'z'< symbol)&&*/ symbol!='\n'
                                        _3 printf (" - %i\n", Cnt);  _4 St1 _5
_1     _2  failure _3 printf (" - %i\n", Cnt);                       _4 St3 _5
_1 St3 _2  'a'<=symbol && symbol <= 'z' _3 printf ("%c", symbol);
                                           cnt = 1;                  _4 St2 _5
_1     _2  //symbol <'a' && 'z'< symbol && symbol != '\n'
                                        _3
           //Так как нужно печатать только слова,
           //действий нет                                            _4 St1 _5
_1     _2  failure _3
           // symbol == '\n' не нужно читать                         _4 exit_5
_1 exit_2  // условие истина, но без неявного чтения потока
                                        _3 return 0;                 _4     _5

Здесь <_i>, i = 1, . . . , 5 обозначают позиции таблицы. Эти сочетания символов, нигде в обычной программе не встречающиеся, легко могут распознаваться препроцессором. Размещаемые между ними последовательности символов разносятся по соответствующим полям нужной структуры, которая, в зависимости от выбранной стратегии, интерпретируется либо транслируется. С помощью этих сочетаний осуществляется разметка текста, которая дает возможность распознавать и осмысливать его фрагменты. Стоит обратить внимание на то, что за счет специального взаимного расположения символов в данном тексте представляемая им таблица автомата вполне обозрима. Если нет более подходящего представления, то данную структуру можно рекомендовать для ввода.

Однако непосредственная интерпретация универсального текстового размеченного представления довольно затруднительна. Предпочтительнее, чтобы единицами интерпретации были бы сами поля таблицы. Вообще, этому противоречит наличие в таблице полей, значения которых - фрагменты исполняемого кода на языке программирования (такая запись удобна для человека, так как для заполнения таблицы не приходится прибегать ни к каким дополнительным соглашениям). На самом деле противоречие возникает только для поля действий, поскольку последовательности символов между <_2> и <_3> имеют ясно выраженную семантику: это проверка условия. Если всегда рассматривать условия как проверку того, чему равен входной символ, то вполне понятны, легко задаются, распознаются и интерпретируются специальные обозначения: перечисления значений, их диапазоны и т.д. Трактовка этих обозначений не вызывает осложнений, а потому подобные приемы кодирования применяются довольно часто.

Если говорить о полях действий, то их представление для большинства языков программирования плохо разработано. Данное обстоятельство препятствует использованию автоматного программирования: кодирование действий усложняет обработку. Но если в языке можно задавать подпрограммы как данные, то описание структуры таблицы, которое будет согласовано с дальнейшей трансляцией или интерпретацией, возможно, в частности, в языках функционального программирования (семейство LISP и ML) и в языке Prolog. Но функциональное и сентенциальное программирование хорошо интерпретируют лишь частные случаи таблиц.

Пусть тип T_StructTableLine описывает структуру одной строки таблицы, а вся таблица представлена в виде массива Table таких структур. Пусть далее iSt - переменная, используемая для индексирования массива Table, некоторые из ее значений представляют состояния конечного автомата (но не все, а только те, к которым определен переход!). Наконец, пусть

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;                
    // поле перехода: индекс строки таблицы,
    // которая будет обрабатываться следующей,
    // или признак завершения процесса
}

Сама таблица описывается следующим образом:

T_StructTableLine Table[]

или

T_StructTableLine Table [Размер таблицы]

если значения строк задаются вне этого описания.

Однако сразу же видно ограничивающее соглашение, которое пришлось принять в связи с особенностями языка реализации: все условия и все действия оформлены как функции, тогда как задача, по своей сути, этого не требует. Более того, отделенное от таблицы описание функций, предписываемое языком С++/C#, резко снижает выразительность представления:

int Cond_St1_1() - условие в Table[1]

и

void Act_St1_1() - действие в Table[1] (строка 1 состояния St1 );

int Cond_St1_2() - условие в Table[2]

и

void Act_St1_2() - действие в Table[2] (строка 2 состояния St1 );

и т. д.

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

Последний недостаток неустраним ни в каком языке, если проверки и действия трактовать как процедуры, которые работают в общем контексте, задаваемом в заголовке таблицы. Так что лучше сразу отказаться от описания этого контекста в рамках таблицы (задание инициализации в ней возможно). Что касается первого недостатка, то он носит почти синтаксический характер, и если бы можно было задавать тела процедур как значения полей структур, то наглядность представления можно было бы сохранить. В языковом оформлении, похожем на С/С++/C#, это выглядело бы как следующее присваивание значения Table в качестве инициализации.

Table[]= {
    {{return true;}, /* инициализация */, 1},
/*St1*/{{return 'a'<=symbol &&
    symbol <= 'z';}, {printf ("%c", symbol);
        cnt = 1;}, 4},
    {{return symbol != '\n';}, 
    /* Так как нужно печатать только слова,
       действия не заполняются */,
        1},
    {{return true}, 
    /* Переход не требует чтения, 
	   symbol == '\n' не нужно читать */, 0},
/*St2*/{{return 'a'<=symbol &&
    symbol <= 'z';}, {printf ("%c", symbol);
        cnt++;}, 4},
    {{return symbol!='\n';},
        {printf ("-%i\n",cnt);},
    1},
    {{return true }, 
	    {printf ("- %i\n",cnt);}, 0}
};

Но для С/С++/C#, а также для других языков, не ориентированных на работу с таблицами, говорить о естественности представления не приходится. По-видимому, наиболее разумно строить автоматический преобразователь (типа препроцессора, но не путать этот термин с С!), который составляет текст программы по таблице. В этом случае снимается много проблем:

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

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

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

Теперь почти все готово для составления программы 10.3.3, реализующей интерпретатор таблицы переходов. Осталось решить вопрос о неявном для таблицы, но с необходимостью явном для программы способе чтения потока символов. Этот вопрос имеет три аспекта:

• Когда читать? Поскольку прочитанный символ используется после его распознавания, естественно "не терять" его, пока выполняется действие. Следовательно, читать очередной символ целесообразно после отработки действия.
• Как поступать в начале процесса: должен ли быть прочитан символ перед первым вызовом функции handler? Понятно, что чтение символов является частью функциональности этой функции. Если в ней реализовать чтение до вызовов условия и действия, то это противоречит предыдущему соглашению, а противоположное решение делает нестандартным начало процесса. В предлагаемой программе принято решение об особой обработке нулевой строки. Поскольку, являясь инициализацией, она действительно особая, это соответствует сделанному соглашению.
• Как поступать в конце процесса? Чтение заключительного символа ('\n') должно прекращать возможные попытки последующего обращения к чтению. Следовательно, необходимо позаботиться о завершающих переходах. В предлагаемой программе принято решение о завершающем переходе к нулевой строке, которая, согласно предыдущему, является нестандартной.

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

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

#include <stdio.h>
char symbol;                   // переменная для чтения потока символов
int cnt;                       // переменная для счета длин слов

int c0(), c1(), c2();          // функции-условия
void a0(), a1(), a2(), a3();   // функции-действия
int handler ( int i );         // обработчик строк таблицы
struct T_StructTableLine
{                              // поле для имени состояния избыточно
    int (*condition)();        // поле условия
    void (*action)();          // поле действия
    int ref;                   // поле перехода: индекс строки таблицы,
                               // которая будет обрабатываться следующей,
                               // или признак завершения процесса
}
    T_StructTableLine
    Table[]={ {c0,a0,1},       // таблица инициализируется статически,
    {c1,a1,2},                 // альтернативное решение - специальная
    {c2,a0,1},                 // функция задания начальных значений.
    {c0,a0,3},                 // Оно более гибкое, но менее
    {c1,a2,2},                 // эффективно.
    {c2,a3,1},                 // О наглядности см. комментарий
    {c0,a3,3};                 // в тексте.
    {c1,a2,2},
    {c2,a3,1},
    {c0,a3,0}};
void main()
{
    int iSt=0;
    do {
        iSt = handler ( iSt );
        }
    while ( iSt);
}

int handler ( int i )
{
    if (Table[i].condition()) {
        Table[i].action();
        if (Table[i].ref) { symbol = getchar ();
        return Table[i].ref; }
    } else return ++i;
}

// Описания используемых функций:
int c0(){return symbol == '\n';}
int c1(){return 'a'<=symbol && symbol <= 'z';}
int c2(){return 'a'>symbol ||symbol > 'z';}

void a0(){}
void a1(){printf ("%c", symbol);cnt = 1;}
void a2(){printf ("%c", symbol);cnt++;}
void a3(){printf ("- %i\n", cnt);}

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

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.