Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 215

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 209 210 211 212 213 214 < 215 > 216 217 218 219 220 221 .. 316 >> Следующая

612
ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
возникает и в наих системах, формализуемх диаграммами переходов10. Тем не менее, как и многие другие математические модели первого порядка, автоматная аналогия диаграмм переходов дает много полезного для обращения с диаграммами и получаимися программами, если ее не абсол ти-зировать. В частности, методы преобразования и оптимизации автоматов часто могут прямо применяться для преобразования и оптимизации программ, описанных диаграммами переходов.
Мы уже рассмотрели один случай, когда структура, по виду совершенно аналогичная диаграммам переходов, на самом деле имеет другу интерпретацию .А именно, это — синтаксические таблицы. В синтаксических таблицах на самом деле мы имеем рекурси , замаскированну тем, что аргументы рекурсивного обращения к процедурам всегда вычисляются стандартно: это — текущее подвыражение. Здесь годятся методы преобразования автоматов, связанные с экономией состояний, но методы декомпозиции и композиции у е не идут, поскольку в данном случае автомат на самом деле не конечный, а магазинный, и прямо представить последовательности его состояний в виде полугрупп не удается.
Это лишь первый из отмеченных нами случаев, когда поверхностные аналогии, связанные с совпадением грубейих представлений и (иногда вдобавок ее и) грубейих математических моделей ведут в концептуальне тупики.
§ 10.5. ПРОГРАММНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФА СОСТОЯНИЙ
Отметим, что программные представления графа состояний очень сильно зависят от динамики данного графа. Стоит выделить четыре подслучая.
1. остояния и таблица переходов естко задан постановкой задачи (например, такова задача синтаксического анализа). Тогда практически всегда лучшее программное представление — goto, независимо от размера таблицы.
2. Состояния и таблица переходов пересматрива тся, но фиксированы меду двумя модификациями задачи. Тогда при небольих размерах таблицы по-прежнему предпочтительней всего реализация через переход , а при достаточно больих необходима ее декомпозиция, в связи
10 Диаграммы переходов можно считать моделями второго порядка. Хотя действия по-прежнему остаются неконкретизированными, условия переходов выписываются более детально.
10.5. ПРОГРАММНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФА СОСТОЯНИЙ
613
с чем часто целесообразно представление состояний объектами.
3. Состояния и таблица переходов динамически порождаются перед выполнением данного модуля, и фиксированы в момент его выполнения. Тогда лучий способ реализации — задание таблиц переходов в виде структуры данных и написание интерпретирующей программы для таких таблиц.
4. 'Живая таблица': модифицируется в ходе исполнения. Пока что дать методологические советы для таких таблиц мы не можем, хотя очевидно, что, несмотря на внен рискованность, такой путь явился бы чрезвчайно вигрыным для многих систем адаптивного реагирования.
В контексте этих ситуаций следует рассматривать и работу с табличным представлением конечнх автоматов, в частности, систему конечных автоматов как средство расирения их распознаих возмо ностей. риведенные в -ше примеры ручной трансформации таблиц в программный формат дают представление о том, каку цель мо но ставить, если реать задачу их автоматического перевода на язык программирования, а указанные ситуации слу ат ориентиром для выбора меду трансляционным и интерпретацион-нм подходом к реализации. В связи с этим далее м уточним постановку задачи перевода для конечного автомата и обозначим варианты ее решения применительно к конечному автомату, подсчитываему длины слов. Затем будет рассмотрена задача, которая по суеству является автоматной, но принципиально не может быть решена с помощью ручного построения таблиц конечного авома а.
10.5.1. Требования к автоматической трансляции таблиц
Серьезный недостаток предложенного в § 10.2.5 решения задачи автоматического преобразования диаграмм конечного автомата в программу связан с идеей препроцессорного построения, удобного для обработки представления диаграмм переходов. Игнорирование обратной связи между исход-нм представлением автомата и его интерпретируемым представлением поро дает проблемы. Если не рассматривать развитие программы, то отсле-ивать ее не ну но. о как только встает вопрос о хотя бы минимальных переделках, возникает проблема:
614
ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
• внесение изменений в диаграмму не влечет за собой автоматического изменения внутреннего представления, а возможные нарушения соглашений, связанных с исходным решением, могут сделать бессмысленным переиспользование. Это особенно заметно, если обратить внимание на то, что в результируей таблице отсутству т имена состояний;
• поиск и диагностика ошибок (речь идет не только о синтаксисе) воз-мо ны лиь на уровне интерпретируемого представления, что противоречит осмысливани программ в прених терминах;
• наличие программ , не зависяей от исходного представления, провоцирует на ее модификации, которые не будут перенесены в исходное представление. В результате концептуальная и реализационная модели расходятся между собой.
Предыдущая << 1 .. 209 210 211 212 213 214 < 215 > 216 217 218 219 220 221 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100