Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

10.2. ПОДСЧЕТ ДЛИН СЛОВ

575

влением.

Более технологичный вариант предыдущей программы можно постро-

ить, если каждый фрагмент программного кода, который отвечает за реализа-

цию действий, относящихся к разным состояниям, (разделы таблицы, поме-

ченные метками состояний), оформить в виде процедуры. Но чтобы не прий-

ти к варианту 1, необходимо помнить, что вызов такой процедуры не должен

приводить к выделению для нее собственной (локальной) области памяти —

конечный автомат работает с общей памятью!

При использовании многих языков (и систем программирования) выпол-

нения этого условия нельзя добиться, и остается только примиряться с тем,

что вызовы процедуры приводят к заниманию новой памяти.В качестве сред-

ства, пригодного для решения проблемы, обычно предлагается использовать

макрогенерацию (пример — препроцессор

). Для макрогенератора проце-

дуры, им обрабатываемые, становятся макросредствами:

— описание процедуры — определение макроса, или, что то же, тело ма-

кроса, а

— вызов процедуры — макровызов, или, что то же, использование макро-

са.

Обработка определения макроса — это создание из тела макроса текстовой

заготовки для последующего встраивания ее вместо макровызова (параме-

тризация макросредств, хотя и приводит к затруднениям для препроцессора,

также возможна).

Однако внешний для языка препроцессор приводит к большой проблеме,

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

препроцессор не в состоянии различать контексты вызова и описания проце-

дур. По этой причине в развитых языках предлагаются иные средства, пред-

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

цией. В

С++/C#

это встраиваемые (

inline

) функции. И именно они наиболее

точно применимы для решаемой задачи. Описывать что-либо внутри встра-

иваемых процедур можно, понимая, что при этом образуется лишь собствен-

ная область видимости имен, а не область памяти.

Есть еще один вопрос, который требуется решить при таком подходе, —

выбор типа результата функций-состояний и способа возвращения результа-

та. Естественный результат такой функции — это новое состояние, в которое

попадает автомат при переходе. Он может быть представлен, например, гло-

бальной переменной (такой как

State

в программе 10.2.2, которой присваива-

576

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

ется новое значение при выполнении функции-состояния). Но элегантнее не

трогать

State

в каждой из функций, а предоставить задачу фактического из-

менения состояния общему их контексту. Наиболее правильной реализацией

состояний при таком подходе являются функции, которые вырабатывают в

качестве результата значение типа, перечисляющего все состояния.

Следующая программа 10.2.3 практически буквально реализует данную

идею. В отличие от программы 10.2.2 тип

States

содержит три значения:

St1

St2

Exit

. Последнему из них не соответствует ни одна функция из-за три-

виальности переходов и действий в данном состоянии.

Вариант 3: использовать тип

State

в качестве типа результата функций-

состояний.

Программа 10.2.3 Длины слов: использование процедур для описания со-

стояний

#include <stdlib.h>

#include <stdio.h>

#include <time.h>

char symbol;

int cnt;

enum States { St1, St2, 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 St1;

}

else return Exit;

}

inline States f_St2 ()

{

10.2. ПОДСЧЕТ ДЛИН СЛОВ

577

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); return Exit;

}

void main( void )

{

symbol = getchar ();

State = St1;

for (;;)

{ switch ( State ) {

case St1: State = f_St1 ();

break;

case St2: State = f_St2 ();

break;

default: return;

}

Следует обратить внимание на то, что в данной программе явный цикл об-

работки потока исчез. Но стоит ли из-за этого считать вариант 3 ухудшени-

ем предыдущего? Конечно, нет. Программа наглядна, строго соответствует

таблице автомата. Можно сказать, что граф автомата определяет распреде-

ленную по состояниям схему потоковой обработки. И это нисколько не хуже

схем с явными циклами.

Проанализировав граф автомата или таблицу, можно заметить, что в дан-

ном примере наряду с циклом потоковой обработки имеется еще один цикл:

передачи управления между состояниями. Это причина, из-за которой в двух

578

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

предыдущих вариантах появились присваивание переменной

State

значения

и выбор выполняемого фрагмента по этому значению.

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

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

switch ( State )

которая выполняется всякий раз в конце действий, ассоциированных с состо-

яниями (точнее — реализаций действий в программах), в том, что в каждой

точке программы, где встречается данное присваивание, можно точно ука-

зать результат динамически следующего оператора переключения, причем

эта информация не зависит от обрабатываемого потока и может быть опре-

делена до вычислений, статически.

А нельзя ли использовать это явно для организации управления конечным

автоматом? Ответ: можно, что и демонстрирует четвертый вариант решения

обсуждаемой задачи. В нем исчезает необходимость вычисляемого перехо-

да (результат внедрения статической информации в текст программы), но,

как следствие, становятся избыточными описания типа

States

и переменной

State

этого типа. В программе появляются операторы безусловного перехода,

которые делают структуру управления программы полностью расходящейся

с канонами структурного программирования, из-за чего такой вариант про-

граммы может подвергаться критике догматически мыслящих программи-

стов и теоретиков. Но в данном случае отступление от канонов структурного

программирования полностью оправдано, поскольку за счет специального

расположения фрагментов текста вся программа оказалась очень похожей на

таблицу конечного автомата, а структура передач управления копирует граф

конечного автомата. Таким образом, лишь сейчас, после полного отхода от

канонов структурности, программа стала адекватна своей спецификации.

Вариант 4: использование статической информации о разветвлениях вы-

числений.

Программа 10.2.4 Длины слов: состояния — метки в программе

#include <stdlib.h>

#include <stdio.h>

#include <time.h>

char symbol;

int cnt;

10.2. ПОДСЧЕТ ДЛИН СЛОВ

579

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’) */ return;

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

return;

}

10.2.5. Представления,ориентированные на автоматические преобра-

зования диаграмм переходов

Принятие решения об автоматическом оперировании с табличным пред-

ставлением влечет за собой требование строгого определения структур дан-

ных, программно представляющих конечный автомат. Это справедливо как

для варианта автоматической трансляции, так и для интерпретации. Задание

диаграммы конечного автомата зависит от стратегии дальнейшей обработки.

В частности, если предполагается предварительное построение текстового

580

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

представления таблицы, которое в дальнейшем преобразуется к виду, при-

способленному к конкретной работе, то вполне приемлемо, к примеру, такое

(универсальное) текстовое представление:

Программа 10.2.5 Программа в виде размеченного текста

_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’

Так как нужно печатать только слова,

действий нет

_4 St1 _5

_1 _2 failure _3

// symbol == ’\n’

не нужно читать

_4 exit _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 exit _5

_1 exit _2 //

отсутствие условия — истина, но без неявного чтения потока

_3 return 0; _4 _5

Здесь “

”, i = 1, . . . , 5, обозначают позиции таблицы. Эти сочетания симво-

лов, нигде в нормальной программе не встречающиеся, легко могут распо-

знаваться препроцессором. Размещаемые между ними последовательности

символов разносятся по соответствующим полям нужной структуры,которая

в зависимости от выбранной стратегии интерпретируется либо транслирует-

ся. С помощью этих сочетаний осуществляется разметка текста, которая

дает возможность распознавать и осмысливать его фрагменты. Стоит обра-

тить внимание, что за счет специального взаимного расположения символов

в данном тексте представляемая им таблица автомата вполне просто усма-

тривается взглядом. Если нет более подходящего представления, то данную

структуру вполне можно рекомендовать для ввода.

Однако непосредственная интерпретация универсального текстового раз-

меченного представления довольно затруднительна. Предпочтительнее, что-

бы единицами интерпретации были бы сами поля таблицы. Вообще гово-

10.2. ПОДСЧЕТ ДЛИН СЛОВ

581

ря, этому противоречит наличие в таблице полей, значения которых — фраг-

менты исполняемого кода на языке программирования (такая запись удобна

для человека, т. к. для заполнения таблицы не приходится прибегать ни к ка-

ким дополнительным соглашениям). На самом деле противоречие возникает

только для поля действий, поскольку последовательности символов между

“

” и “

” имеют ясно выраженную семантику: это проверка условия. Если

всегда рассматривать условия как проверку того, чему равен входной сим-

вол, то вполне понятны, легко задаются, распознаются и интерпретируют-

ся специальные обозначения: перечисления значений, их диапазоны и т. д.

Трактовка этих обозначений не вызывает осложнений, а потому подобные

приемы кодирования применяются довольно часто.

Что касается полей действий, то их представление для большинства язы-

ков программирования данное обстоятельство является непреодолимым пре-

пятствием: кодирование действий очень усложняет обработку. Но если в язы-

ке можно задавать подпрограммы как данные, то описание структуры табли-

цы, которое будет согласовано с дальнейшей трансляцией или интерпрета-

цией, возможно. Обсуждение проблем одновременной интерпретации полей

данных и полей действий будет продолжено в контексте произвольной раз-

метки текстов (т. е. без привязки к данному представлению таблицы).

Пусть тип

T_StructTableLine

описывает структуру одной строки таблицы,

а вся таблица представлена в виде массива

Table

таких структур. Пусть далее

iSt

— переменная, используемая для индексирования массива

Table

, некото-

рые из ее значений представляют состояния конечного автомата (но не все, а

только те, к которым определен переход!). Наконец, пусть

int handler ( int );

обработчик строки (ее интерпретатор или транслятор),‘понимающий’ струк-

туру

T_StructTableLine

, который специфицируется как функция, при выпол-

нении которой должно быть определено очередное значение

iSt

. Когда значе-

ние

iSt

не указывает ни на какую строку таблицы, это служит сигналом для

завершения обработки (при желании можно заняться кодированием того, как

завершилась обработка с помощью задания различных таких значений).

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

handler

может быть задана следующим циклом:

iSt = 0;

do {

iSt = handler ( iSt );

}

582

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

while ( OUTSIDE ( iSt ) );

Понятно, что выбор массива в качестве представления автомата неприн-

ципиален. Допустимо, а иногда и предпочтительнее, работать со списком

строк. Также непринципиален способ вычисления предиката

OUTSIDE

, про-

веряющего условие окончания цикла, хотя он и зависит от выбранного пред-

ставления автомата. Возможность не рассматривать явно имена состояний,

напротив, принципиальна: тот факт, что строки таблицы сгруппированы во-

круг (поименованных) состояний, ничего не значит ни для обработки, ни для

интерпретации, поскольку у конечного автомата следующее состояние все-

гда определяется явно.

Логически функция

handler

,интерпретирующая таблицу,описывается до-

вольно просто. Для правильной таблицы, не содержащей состояний, в кото-

рых возможны неопределенные переходы (неверно, что дизъюнкция условий

истинна), она строится из следующих шагов:

1. Извлечь значение

Table[iSt]

;

2. Активизировать вычисление условия обрабатываемой строки табли-

цы;

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

(a) активизировать подпрограмму действий,

(b) читать очередной символ,

handler

со значением, извлекаемым из поля следую-

щего состояния;

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

(a)

iSt++;

(b) Перейти к 1.

Эту простую схему несколько утяжеляют детали, которые нужно предусмо-

треть для заключительных состояний (проделать самостоятельно!).

Таким образом, нужно научиться описывать структуру строки таблицы.

На языке

C/C++/С#

эта задача может решаться довольно просто:

10.2. ПОДСЧЕТ ДЛИН СЛОВ

583

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

);

и т. д.

Другим неприятным моментом данного представления является то, что

не удается единообразно с действиями представить их общий контекст (нуле-

вая строка таблицы),а поскольку инициализацию естественно рассматривать

как задание предварительных действий, готовящих собственно обработку, то

ее предпочтительнее соединять с контекстом, а не с функциями, реализую-

щими проверки и действия.

Последний недостаток неустраним ни в каком языке, если проверки и

действия трактовать как процедуры, которые работают в общем контексте,

584

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

задаваемом в заголовке таблицы. Так что, быть может лучше сразу отказать-

ся от описания этого контекста в рамках таблицы (задание инициализации

в ней возможно). Что касается первого недостатка, то он носит почти чисто

синтаксический характер, и, если бы можно было задавать тела процедур как

значения полей структур, то наглядность представления можно было бы со-

хранить. В стиле, похожем на язык

С/С++/C#

, это выглядело бы как следую-

щее присваивание значения

Table

в качестве инициализации:

Программа 10.2.6

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}

};

Несколько нагляднее и ближе к табличному заданию то же самое может быть

записано на

Алголе 68

(фактически представлен не точный перевод на этот

язык, а некий гибрид его с

С/С++

, к тому же избавленный от ряда специфич-

ных деталей):

Программа 10.2.7