Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 101
Текст из файла (страница 101)
Перебор элементов вектора естественным образом выражается циклом Тог: Гог 1 := 1 Во К до Н 'ТЕСТ(1) - 0 тлел роте а где и — некоторая метка оператора вне тела цикла. 362 Глава 8. Управление последовательностью действий Однако в языке Разса1 либо оператор доте следует использовать для выхода из оператора цикла до его завершения, либо цикл Еог яужно заменить циклом н)Ь)1е, который скрывает информацию о наличии индексной переменной 1 и диапазоне ее значений, содержащуюся в заголовке цикла Еог. Оператор ех1Ь языка Ах(а и оператор ЬгеаХ языка С представляют апьтернативную конструкцию для выражения способа такого преждевременного выхода из цикла без использования оператора доСЬ: Гог 1 Хп )..К 1оор ехга ньеп НЕСИ 1) = О епб 1оор: Конструкция бо-н)Ь)1е-бо.
Иногда проверять условие выхода из цикла удобно не в начале и не в конце цикла, а где-нибудь в середине, после того как выполнена некоторая обработка данных, например; 1оор геабХХ) )г епб ог г!1е тпеп доте и (а — ане цикла) ргосеаж Х ) епб 1оор. Эта форма иногда называется бо-)ХЬ) 1е-бо, потому что возможность выхода может определяться оператором нп) 1е, вставленным в середину цикла: бонП)1ебо геабХХ) яьп1е Хпот епб от ЕМ 1е) ргосееа(Х) епб боны )ебо К сожалению, ни один из стандартных языков не реализует зту структуру, хотя конструкция языка С 1( (услоеие) ЬгеаХ и оператор языка Ах)а ех)1 ипеп по смыслу близки к ней. Исключительные ситуации. Искл)очення (или исключительпыс ситуации) могут представлять собой различные ситуации, приводящие к возникновению ошибок, например, неожиданное достижение конца файла, ошибки, связанные с выходом индексов из диапазонов их значений, или обработка некорректных данных.
Операторы, обрабатывающие такие исключительные ситуации, часто группируются в определенном месте программы (например, в конце подпрограммы), в которой может возникнуть ошибка, а иногда даже в отдельную подпрограмму, занимающуюся только обработкой исключительных ситуаций. В языках, в которых не реализованы специальные операторы обработки исключительных ситуаций, лучше всего с помошью оператора дого передавать управление от места, где возникла исключительная ситуация, обработчику исключений (грухн)а операторов).
Однако в языках Ах)а и М(. существуют специальные языковые механизмы для определения обработчика исключений и передачи управления при обнаружении исключения. Типичным оператором в алгоритме обработки искл)очений в языке Ах(а является оператор гз)зе: гаазе ВАЬ СНЯВ НЯЕЬЕ Этот оператор передает управление операторам обработки исключительной ситуации, соответствующей исключению с именем ВАВ СНЯВ НАЕВЕ. Исключения и их обработка будут рассмотрены далее в разделе 11.1,1.
8.3. Управление последовательностью выполнения операторов 363 8.3.3. Первичные программы Хотя на первый взгляд совокупность управляющих структур, представленная в этой главе, кажется некоторым случайным набором операторов, для описания непротиворечивой теории структур управления можно использовать теорию первичных, или атомарных, програм и, Теория первичных программ была предложена Маддуксом (Маоопх) [761 в качестве обобщения методологии структурного программирования для определения однозначной иерархической декомпозиции блоксхем. Мы предполагаем, что графы программ могут содержать три класса узлов: Функциональные узлы представляют вычисления, производимые программой, и изображаются прямоугольниками с одной входящей в этот узел дугой и одной выходящей. Интуитивно понятно, что функциональные узлы представляют операторы присваивания, выполнение которых вызывает изменение состояния виртуальной машины.
Узлы принятия регаения изображаются в виде ромбов с одной входящей дугой и двумя выходящими, намечаемыми истина и ложь. Эти узлы представляют предикаты, и управление из узла принятия решения передается дальше либо по ветви истина, либо по ветви ложь. Узел соединения представляется в виде точки, в которой сходятся две дуги графа, чтобы сформировать одну выходную дугу. Любая блок-схема состоит их этих трех компонентов.
Определим правильную программу, являющуюся формальной моделью структуры управления, как блоксхему, которая: 1) имеет одну входящую дугу; 2) имеет одну выходящую дугу; 3) имеет путь от входящей дуги к любому узлу и из любого узла — к выходя- щей дуге. Нашей целью является определить различие между структурированной правильной программой и неструктурированной. Например, если посмотреть на рис. 8.7, то можно заметить очевидные различия между блок-схемами на рис. 8.7, а и 8.7, б. Левая блок-схема содержит большое количество казалось бы случайным образом построенных дуг графа, в то время как правый граф имеет упорядоченную вложенную структуру.
С помощью первичных программ можно обьяснить эти различия, Первичная программа является правильной программой, которую нельзя подразделить на более мелкие правильные программы. Если нельзя разрезать две дуги правильной программы таким образом, чтобы разделить ее на отдельные графы, то правильная программа является первичной. (Единственным исключением из этого правила является длинная последовательность функциональных 364 Глава 8. Управление последовательностью действий узлов, которая считается одной первичной программой.) Программа, изображенная на рис.
8.7, а, является первичной, а на рис. 8.7, б — нет. Пунктирные прямоугольники А, В и С представляют вложенные правильные программы внутри всей блок-схемы. йно. 8.7. Блок-схемы: а — первичная программа; б — составная программа Определим составную п)тограмму как правильную программу, которая не является первичной.
На рис. 8.7, б изображена как раз составная программа. Заменив каждый первичный компонент правильной программы функциональным узлом (например, первичные компоненты А и В на рис. 8.7, б заменим функциональнымии узлами), мы можем продолжить этот процесс (например, заменить теперь блок С как первичный компонент функциональным узлом) до тех пор, пока не получим представлениелюбой правильной программы в виде единственной первичной программы. Можно перечислить все первичныс программы. На рис.
8.8 изображены все первичные программы, которые включают в себя не более четырех узлов. Обратите внимание на то, что большинство из них либо неэффективны, либо являются стандартными структурами управления, описанными ранее в этой главе. Первичные программы а, б, д и к представляют собой последовательности функциональных узлов и соответствуют основному блоку большинства языков программирования. Первичная программае — конструкция1т-тлел,лс — бо-нйПе,з — герезГ -цпГП, л — тГ-гпеп-е1зе,м — бо-нвтЗе-бо.
Рассмотрим первичные программы в, г и с н по ль Все они состоят только из узлов принятия решения и соединения. В них нет функциональных узлов, значит, они не изменяют пространство состояний виртуальной машины. Поскольку эти первичные программы не изменяют значений никаких данных, все они вычисляют тождественную функцию. Однако из в и н всегда существует выход (то есть выпол пение завершается), и, следовательно, они являются тождественными функциями при любых входных данных, тогда как остальные первичные программы могут выполняться циклически. Однажды начавшись, эти циклы будут выполнять- 8.3.
Управление последовательностью выполнения операторов 365 ся и никогда не завершатся. Они представляют собой частично вычислимые функции, которые завершаются только при определенных значениях входных данных. Ни один из этих вариантов первичных программ не представляет эффективной структуры управления в программе. 3 узла Рис. 8.8. Виды первичных программ 366 Глава 8. Управление последовательностью действий Не удивительно, что в определения языков программирования были включены наборы управляющих структур, описанные в этой главе. Все они представляют собой первичные программы с небольшим количеством узлов. Такие первичные программы просты для понимания, и те изменения в пространстве состояний виртуальной машины, которые являются результатом их выполнения, поддаются управлению. Перечислив все первичные программы, мы приходим к очевидному выводу, что конструкция бо-ий1!е-бо является естественной структурой управления, хотя, к сожалению, она была проигнорирована разработчиками языков.
Структурная теорема. Когда в 70-е гг. разрабатывалась методология структурного программирования, обсуждался вопрос, не приведет ли использование только таких структур управления к ограничению возможностей программ. То есть можно ли написать программу, подобную приведенной на рис. 8.7, а, используя только структуры управления, представленные па рис. 8.8? На этот вопрос отвечает теорема Бема — Якобини (Во!пп — [асоЬ|п! Гйеогегп) [19]. Они показали, что любую первичную программу можно преобразовать в другую первичную программу, используя только операторы иМ!е и 11.
На рис. 8.9 приведен набросок процесса, похожий на конструкцию Бема-Якобини (ВоЬш — [асоЬ1п!), однако этодоказательство принадлежит Харлану Миллзу (Наг!ап М]!!з) [71]. 1. В любой заданной блок-схеме пометьте все узлы. Выходящую дугу пометьте числом О. 2. Определите новую переменную !. 3.
Для каждого узла блок-схемы примените преобразование, приведенное на рис. 8.9, а. 4. Перестройте программу, как показано на рис. 8.9, 6. Должно быть ясно, что переменная ! играет роль счетчика команд виртуальной машины, указывающего наследующий оператор, который необходимо выполнить, а вся программа является просто рядом вложенных в единственный цикл нШ!е операторов 11. Эта программа будет работать так же, как и исходная блок-схема, с единственным отличием — переменная ! будет изменяться в процессе ее выполнения. Результаты исследований Бема и Якобини иногда приводят в качестве причины, почему яе нужно избегать операторов уотс.
Можно написать программу как с использованием оператора уосо, так и бсэ него, а затем, пользуясь структурной теоремой, переделать программу в «хорошо структурированную». Доверчивым людям было продано много таких структурпрующих машин. Структурное программирование не является синонимом хорошего программирования. Оно обозначает только использование структур управления, которые являются первичными программами с небольшим количеством узлов. Если начп ~ шть с плохого кода «спагетти», то преобразование просто приведет к плохому структурированному коду Терема Бема — Якобини фактически доказывает лишь то, что любую программу можно написать, используя только стандартные структуры управления.
Приведенный алгоритм не обеспечивает наилуч|пее решение. Его разработка полностью за- 8.4. Последовательность вычисления неарифметических выражений 367 висит от программиста. Мы знаем лишь то, что существует некоторое решение не хуже, чем результат Бема и Якобини, а может быть, даже лучше. Исходный узел -Н- Модифицированный узел Рис. 8.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
