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

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

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

585

[0: ] структ ( имя проц Condition = ()лог,

имя проц Action = ()ничто,

цел iRef

)= (

((истина), co

инициализация

co), 1),

( co St1: co

(‘a’<=symbol и symbol<=‘z’;), (печатать(symbol); cnt = 1;),

4),

((symbol <> ‘\n’;), co

пустые действия

co), 1),

((истина), (co

пустые действия

co), 0),

( co St2: co

(’a’<=symbol и symbol<=‘z’;), (печатать(symbol); cnt += 1;),

4),

(symbol <> ‘\n’;), (печатать(symbol+‘- \n’,cnt), 1),

((истина), (печатать(symbol+‘- \n’,cnt), 0)

);

Символ

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

Эта запись таблицы более наглядна за счет того, что:

• есть возможность описывать процедурный тип (вид, по терминологии

Алгола 68

);

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

• проще выглядит так называемое “

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

вающее значение

”.

Но и для

С/С++/C#

, и для

Алгола 68

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

рованных на работу с таблицами, говорить о естественности представления

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

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

этот термин с

!), который составляет текст программы по таблице. В этом

случае снимается много проблем:

a) для программиста сохраняется наглядность;

b) при исполнении достигается алгоритмичность;

c) легко разносить фрагменты таблицы по разным участкам программы;

586

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

d) можно жертвовать наглядностью результирующего текста,поскольку фак-

тически с ним никто, кроме транслятора не работает (пример: вставка но-

вых строк в таблицу — проблема для человека, но не для препроцессора);

e) по той же причине можно жертвовать даже структурностью результирую-

щего текста (в рассматриваемом примере, в частности, можно отказаться

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

Это решение часто является приемлемым, но недостатков оно не лишено.

Прежде всего, становится трудным делом поиск ошибок, допущенных в тек-

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

приходится понимать как исходное представление, так и внутренне). Так что

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

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

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

Из-за нестандартности работы с инициализацией (нулевая строка таблицы)

удобно пополнить этот набор еще двумя функциями: “условием” и “действи-

ем”, выполняемыми при переходе к этой строке, которая интерпретируется

как завершение работы автомата (таким образом, предикат

OUTSIDE (iSt)

можно представить как равенство аргумента нулю).

Теперь почти все готово для составления программы 10.2.8, реализую-

щей интерпретатор диаграммы переходов. Осталось решить вопрос о неяв-

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

символов. Этот вопрос имеет три аспекта:

• Когда читать? Поскольку, прочитанный символ используется после его

распознавания (например, он может выводиться на экране), естествен-

но “не терять” его, пока выполняется действие. Следовательно, читать

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

• Как поступать в начале процесса: должен ли быть прочитан символ пе-

ред первым вызовом функции

handler

? Понятно, что чтение символов

является часть функциональности этой функции, и, если в ней реализо-

вать чтение до вызовов условия и действия, то это противоречит преды-

дущему соглашению, а противоположное решение делает нестандарт-

ным начало процесса. В предлагаемой программе принято решение об

особой обработке нулевой строки. Поскольку, являясь инициализаци-

ей, она действительно особая, это соответствует сделанному соглаше-

нию.

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

587

• Как поступать в конце процесса? Чтение заключительного символа (

’\n’

)

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

чтению. Следовательно, нужно позаботиться о завершающих перехо-

дах. В предлагаемой программе принято решение о завершающем пе-

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

стандартной.

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

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

переход от табличного представления к программе.

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

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

щим образом.

Программа 10.2.8 Длины слов: интерпретатор конечного автомата

#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,4}, //

альтернативное решение — специальная

{c2,a0,1}, //

функция задания начальных значений.

{c0,a0,0}, //

Оно более гибкое, но менее

{c1,a2,4}, //

эффективно.

{c2,a3,1}, //

О наглядности см. комментарий

{c0,a3,0}}; //

в тексте.

588

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

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 true;}

int c1(){return ’a’<=symbol && symbol <= ’z’;}

int c2(){return symbol != ’\n’;}

void a0(){}

void a1(){printf ("%c", symbol);cnt = 1;}

void a2(){printf ("%c", symbol);cnt++;}

void a3(){printf ("- %i\n", cnt);}

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

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

следовательно, вызовы

Table[i].condition()

Table[i].action()

нарушают теоре-

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

память. Но фактически здесь нет никакого противоречия:

• Во-первых, теоретическое “не требуется” совсем не обязательно долж-

но буквально реализовываться. Напротив, на каждом уровне требуются

свои средства.

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

589

• Во-вторых, не исключается, что транслятор, проанализировав транс-

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

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

вы функций на прямые переходы к нужным фрагментам.

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

действий функциями, а вместо этого составить специальные “неиспол-

няемые” фрагменты и задать переходы к ним взамен вызовов. Послед-

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

время, реализация ранее указанного подхода (см. пункт e) на стр. 586).

На первый взгляд может показаться,что задача оптимизации вызовов в

С/С++/C#

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

вы

inline

. В самом деле, использование встраиваемых (

inline

) функции име-

ет целью подмену вызова размещением кода тела функции в точке вызова.

Однако в данном случае это не приведет к желаемому: компилятору просто

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

inline

будет проигнори-

рована.

Если только что отмеченные недостатки метода автоматического встраи-

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

дующая критика уже принципиальна. Более того, приводимые далее замеча-

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

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

универсального) метода.

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

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

ки зрения препроцессора (не препроцессора системы программирования, а

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

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

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

-компилятором. Интер-

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

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

условия и действия в таблице двойственны: они являются одновременно и

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

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

менее, их объединить с обычными данными (в рассматриваемом случае это

индексы строк переходов) в одной структуре.

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

языке, в котором есть возможность воспринимать данные как выполнимые

590

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

фрагменты. Пример такого рода — команда “Вычислить строку”. Эта коман-

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

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

ках скриптов, ориентированных на интерпретацию. А в языке

LISP

, в кото-

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

ность не возникает. Но опыт показывает, что столь общее решение чревато

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

его вариант, адекватный для данной задачи.

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

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

проверкам символов (как в обсуждаемой задаче). Достаточно закодировать

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

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

сти, в рассматриваемом примере, это решение можно оформить в виде пе-

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

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

в функции

handler

. Поэтому замечание о двойственности более точно от-

носить лишь к действиям, которые являются программными фрагментами

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

ее можно рассматривать в качестве стандартного приема программирования

(см., к примеру, синтаксические таблицы в § 10.3).

Метод решения задач с помощью построения конечных автоматов являет-

ся довольно удобным, когда речь идет об обработке потоков. Чтобы освоить

его, предлагаем самостоятельно решить этим методом ряд задач такого ро-

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

число действий, ассоциированных с переходами, требуется. Полезно опре-

делить различные конечные автоматы для одной и той же задачи и сравнить

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

которые вполне подходят для применения данного метода, мы рекомендуем:

• Подсчитать число вхождений нескольких заданных заранее слов во вход-

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

• Преобразовать входной текст,в котором неразличимы заглавные и строч-

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

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

кой перед ними символа подчеркивания).

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

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

591

выводящих решения за рамки данного метода. Это не страшно, нужно только

четко осознавать, где кончается использование конечного автомата и начина-

ется применение другого подходящего метода.

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

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

состояний. При сопоставлении вариантов,предложенных выше для подсчета

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

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

ям.

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

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

нив его описанием структуры перерабатываемых данных, и в терминах та-

кой структуры формулировать задание. Это осуществимо, например, можно

определить структурное понятие слова и способ вычисления его длины. Но

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

избыточной? Для сентенциального стиля характерно оставлять за рамками

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

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

щие расходы. Применительно к нашей задаче оказывается, что эти расходы

слишком обременительны по сравнению с основной задачей. Конечно же,

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

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

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

за собой экономию умственных усилий при многократном использовании

этой поддержки. Но в данной задаче использование сентенциального стиля

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

женного в библиотеку), не дает экономии и мыслительных ресурсов. Такой

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

лее сложными структурами данных.

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

по поводу сентенциального стиля можно перенести на функциональное ре-

шение. Здесь базовое соглашение становится совсем уж далеким от исход-

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

перехода и действия. Общим для двух стилей недостатком решения могут

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

знавания слов. Очень часто именно это преимущество метода конечных ав-

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

туации. Поэтому при разработке сентенциальных и функциональных систем

592

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

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

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

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

любых системах программирования.

Следующие два стиля (программирование от событий и от приоритетов)

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

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

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

чтобы отделить его функционирование от другой обработки. Применитель-

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

обсуждаемого метода, это обстоятельство решающей роли не играет, а пото-

му указанное преимущество не является принципиальным. Иными словами,

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

поддержки уже имеется.

Метод конечных автоматов вполне сочетается с объектно-ориентирован-

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

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

ций конечного автомата с потенциально неограниченным числом состояний,

представляемых объектами. При таком взгляде на объектную систему анало-

гом переходов между состояниями служат сообщения, передаваемые меж-

ду объектами. Конечно, это далеко не единственная трактовка, более того,

в задачах, которые неестественно решать данным методом, она оказывается

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

но активные единицы выполнения программы. И это обстоятельство следует

рассматривать в качестве границы сочетаемости объектно-ориентированно-

го стиля и метода конечных автоматов.

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

что объекты могут возникать (и уничтожаться) динамически, а число строк

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

вано до вычислений. Но эта разница и дает качественный рост мощности

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

ставлять таблицы состояний объектами.

Применительно к конкретной задаче о длинах слов объектно-ориентиро-

ванное задание автомата возможно, но для решения вопроса об автоматиза-

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

чего не дает. В схеме с функцией

handler

двойственность программ и данных

по-прежнему затрудняет построение и интерпретацию.

10.3. СИНТАКСИЧЕСКИЕ ТАБЛИЦЫ

593

§ 10.3. СИНТАКСИЧЕСКИЕ ТАБЛИЦЫ

10.3.1. Расширение сферы применения конечных автоматов: анали-

затор как система связанных конечных автоматов

Привлекательность метода конечных автоматов является побудительной

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

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

ций, связанный с построением систем объектов объектно-ориентированной

программы как автомата, был упомянут выше. Расширение сферы примене-

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

ограниченного множества объектов-состояний.

В данном параграфе мы обсуждаем другой путь расширения метода.Ключе-

вым свойством его является снабжение автомата памятью. Речь идет не о той

памяти, которая используется в действиях, сопутствующих переходам, —

она есть часть обработки и к вычислительной мощности автомата отноше-

ния не имеет. Расширение конечного автомата как алгоритма распознавания

за счет памяти связывается с модификацией команд перехода из состояния

в состояние: теперь при выполнении команды может запоминаться какая-

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

из входного потока, но и запомненные данные.

Если автомат снабжается стековой памятью, то говорят об автоматах со

стековой памятью

, вычислительная мощность которых больше обычных

конечных автоматов, но меньше мощности машины Тьюринга. Именно такие

автоматы служат теоретической основой разработок синтаксических анали-

заторов контекстно-свободных языков. По существу все анализаторы, осно-

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

стратегиями работы со стеком.

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

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

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

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

литературы понимании). В таком случае, стек — это память, для которой определены опе-

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

элементов. Доказано, что с помощью магазина можно промоделировать стек, а потому тео-

ретически достаточно только одного понятия, т. е. магазина, как наиболее простого. Вместе

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

ило бы использовать оба понятия. Однако вслед за англоязычной традицией сегодня чаще

всего используется термин стек.

594

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

Мы рассмотрим только одну из этих стратегий, которая допускает интер-

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

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

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

циплине: активизация нового экземпляра автомата приводит к приостанов-

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

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

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

татель тут же заметит, что эта трактовка повторяет то, что ранее мы называли

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

рые реализуют конечные автоматы.

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

успешно, и False в противном случае) используются для выбора очередно-

го состояния, в которое переходит автомат. Использование автоматов со сте-

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

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

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

ется локальной. Конечно же, регламентированный отход от стиля не является

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

рования как варианты базовых стилей. Но в настоящей главе нас в первую

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

стилю программирования от состояний. По этой причине мы и рассматрива-

ем системы конечных автоматов, связанных стеком.

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

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

Однако требование корректно определять вычисления системы неизбежно

приводит к тому, что потоки, которые перерабатываются вызываемыми в од-

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

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

общим, то чтение из него должно быть независимым для каждого из экзем-

пляров, а это противоречит дисциплине обработки потока. При успешном

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

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

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

экземпляру. Что же касается неуспешно завершившихся экземпляров, то их

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

расщепления потока и локализации его потомков по вызываемым экземпля-

рам автоматов является организация возвратов по обрабатываемой строке.