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

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

В решениях 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. Матрица переходов и вектор-функций, соответствующих состояниямЭтот вариант сознательно запрограммирован на Object Pascal, поскольку разница между языками традиционного типа несущественна, а изменение языка заодно выделяет и тот факт, что данный вариант ориентирован на другую модель автоматного программирования.

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

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

Таким образом, нужно научиться описывать структуру строки таблицы. На языке 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, реализующей интерпретатор таблицы переходов. Осталось решить вопрос о неявном для таблицы, но с необходимостью явном для программы способе чтения потока символов. Этот вопрос имеет три аспекта:

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

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

#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);}

Обсуждение решения

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

На первый взгляд кажется, что ситуация существенно упростилась бы в языке, в котором есть возможность воспринимать данные как выполнимые фрагменты. Пример такого рода - команда <Вычислить строку>. Эта команда давала бы возможность интерпретатору понимать программы-данные, не оставляя их нераспознанными. Подобная команда порою встречается в языках скриптов, ориентированных на интерпретацию. А в языке LISP, в котором структуры данных и программы просто совпадают, указанная двойственность не возникает. Но по опыту известно, что столь общее решение чревато столь же общими и вездесущими неприятностями, и нужно искать частный его вариант, адекватный данной задаче.

Метод решения задач с помощью построения таблиц и графов состояний и переходов часто удобен для обработки потоков данных. В книгах [32], [33], а особенно в задачнике [2] и на сайте http://is.ifmo.ru, имеется ряд задач такого рода. Решения стоит оценить количественно и качественно: сколько требуется состояний и действий, как лучше получается в данном случае (в состояниях или на переходах). Может оказаться, что понадобятся средства, выходящие за рамки описанных методов. Это допустимо, следует только осознавать грань между использованием конечного автомата и применением другого подходящего метода, а также четко разделять внутри программы возможности, относящиеся к разным стилям программирования.

Подведем итоги

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

Таблицы и графы гораздо лучше самой программы с точки зрения модифицируемости и преобразований.

Таким образом, табличное и графовое представления автомата являются спецификациями №1, о которых нужно думать в первую очередь, когда составляется автоматная программа.

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

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