Обсуждение решения
Как уже отмечалось, фрагменты, описывающие условия и действия в таблице переходов и реализованные как процедурные вставки, с точки зрения препроцессора (не препроцессора системы программирования, а специального преобразователя, генерирующего представление таблицы для интерпретации), являются нераспознаваемыми данными, которые он просто пропускает без изменений для обработки компилятором. Интерпретатор же, наоборот, не в силах сам исполнять процедуры, а потому трактует ссылки на них (в соответствующих полях) как данные. Таким образом, условия и действия в таблице двойственны: они являются одновременно и данными, и программными фрагментами. Автоматический преобразователь таблицы, не понимая языка таких двойственных данных, пытается, тем не менее, их объединить с обычными данными (в рассматриваемом случае это индексы строк переходов) в одной структуре.
На первый взгляд кажется, что ситуация существенно упростилась бы в языке, в котором есть возможность воспринимать данные как выполнимые фрагменты. Пример такого рода - команда <Вычислить строку>. Эта команда давала бы возможность интерпретатору понимать программы-данные, не оставляя их нераспознанными. Подобная команда порою встречается в языках скриптов, ориентированных на интерпретацию. А в языке LISP, в котором структуры данных и программы просто совпадают, указанная двойственность не возникает. Но по опыту известно, что столь общее решение чревато столь же общими и вездесущими неприятностями, и нужно искать частный его вариант, адекватный данной задаче.
Метод решения задач с помощью построения таблиц и графов состояний и переходов часто удобен для обработки потоков данных. В книгах [32], [33], а особенно в задачнике [2] и на сайте http://is.ifmo.ru, имеется ряд задач такого рода. Решения стоит оценить количественно и качественно: сколько требуется состояний и действий, как лучше получается в данном случае (в состояниях или на переходах). Может оказаться, что понадобятся средства, выходящие за рамки описанных методов.
Это допустимо, следует только осознавать грань между использованием конечного автомата и применением другого подходящего метода, а также четко разделять внутри программы возможности, относящиеся к разным стилям программирования.
Подведем итоги
Таблица и граф - два теоретически эквивалентных (но практически разных) представления. Каждое из них имеет свои достоинства и недостатки (на графе информация беднее, но обозримость может быть лучше). Одна из этих спецификаций чаще всего делает ненужной другую.
Таблицы и графы гораздо лучше самой программы с точки зрения модифицируемости и преобразований.
Таким образом, табличное и графовое представления автомата являются спецификациями №1, о которых нужно думать в первую очередь, когда составляется автоматная программа.
Главный недостаток табличных и графовых методов представления автоматов в том, что их приходится дополнительно преобразовывать в программу. А в дальнейшем возникает соблазн модифицировать непосредственно программу, и спецификация перестает быть адекватной программе.
В связи с этим возникает вопрос об улучшении поддержки методов табличного и графового представления автоматных программ.
 |
|
|
В этом пункте заложено недетерминированное поведение получаемой программы. Как правило, при применении метода таблиц переходов возможность недетерминированного поведения игнорируется. Вместо этого задается какое-либо произвольное детерминированное правило, например, выбирается текстуально первое из действий, для которого условие истинно. Это похоже на то, как определяются условные выражения и оператор переключения в традиционных языках.
2)
Памятью можно считать номер текущего состояния (замечание проф. А. А.Шалыто).
3)
Это верно и для унификационного варианта.
4)
Этот вариант сознательно запрограммирован на Object Pascal, поскольку разница между языками традиционного типа несущественна, а изменение языка заодно выделяет и тот факт, что данный вариант ориентирован на другую модель автоматного программирования.
