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

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

5.3. ПРИОРИТЕТ ОПЕРАЦИЙ

265

<выражение вида равенство> ::=<выражение вида отношения> |

<выражение вида равенство> [“==” | “!=”] <выражение вида сложения>

<поразрядное AND-выражение> ::=<выражение вида равенство> |

<поразрядное AND-выражение> “&”<выражение вида равенство>

<поразрядное исключающее OR-выражение>::=<поразрядное AND-выражение>

<поразрядное исключающее OR-выражение>“^”<поразрядное AND-выражение>

<поразрядное OR-выражение>::=<поразрядное исключающее OR-выражение>

<поразрядное OR-выражение> “|

”<поразрядное исключающее OR-выражение>

<логическое AND-выражение> ::=<поразрядное OR-выражение>|

<логическое AND-выражение> “&&”<поразрядное OR-выражение>

<логическое OR-выражение> ::=<логическое AND-выражение> |

< логическое OR-выражение> “|”<логическое AND-выражение>

<условное выражение> ::= <логическое OR-выражение> |

<логическое OR-выражение> “?” <выражение>“:”<выражение вида присва-

ивания>

<выражение вида присваивания> ::= <условное выражение> |

<условное выражение> [ “=” | “*=” | “/=” | “%=” | “+=” | “-=” | “>>=” | “<<=” |

“&=” | “^=” | “|=”] <выражение вида присваивания>

<выражение> ::=<выражение вида присваивания> |

<выражение>“,”<выражение вида присваивания>

Заметим, что в языках

С/С++

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

вов функций также формально помещены в категорию постфиксных выра-

жений. В самом деле, то, что предшествует скобкам вокруг индексов массива

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

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

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

не на-

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

соответствуют функциям. Так что выражения вида

a[i]

a(i)

можно считать

приведением адреса массива (функции) к типу значения элемента массива

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

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

В развитых машинно-ориентированных языках программирования (та-

ких, как

BLISS

ЯРМО

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

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

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

266

ГЛАВА 5. ВЫРАЖЕНИЯ

(пока что на уровне конкретных систем программирования). Например, рас-

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

property

языка

Object-Pascal

и языка системы

Visual C

). После описаний типа

property a

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

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

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

данному — как вызов функции изменения.

Пример 5.3.1. Цепочка вывода x∗x + y ∗y <= 4 из <выражения> выглядит

следующим образом:

<выражение> →

<выражение вида присваивания> →

<условное выражение> →

<логическое OR-выражение> →

... → <выражение вида отношения> →

<выражение вида отношения> <= <выражение вида отношения> →

...→ <выражение вида отношения> <= 4 →

...→ <выражение вида сложения> <= 4 →

<выражение вида сложения> + <выражение вида умножения> <= 4 →

<выражение вида умножения > + <выражение вида умножения> <= 4 →

<выражение вида умножения > + <выражение вида умножения> *<унарное

выражение> <= 4 →

...→ <унарное выражение> * <унарное выражение> + <унарное

выражение> * <унарное выражение> <= 4 →

...→ x ∗ x + y ∗ y <= 4

Если проследить, как появляются в этой цепочке знаки операций, то стано-

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

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

дерева абстрактно-синтаксической структуры, в точности соответствующее

тому, что требуется.

Конец примера 5.3.1.

Пример показывает, что понятие приоритета операции становится фор-

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

ку. Но в этом случае для выявления приоритетов операций нужно просма-

5.3. ПРИОРИТЕТ ОПЕРАЦИЙ

267

тривать все длинное формальное определение <

выражения

>, так что с со-

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

объяснения порядка вычислений сложных выражений.

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

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

ся

Algol 68

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

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

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

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

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

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

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

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

Фиксированные по определению языка приоритеты операций — локаль-

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

операции — это свойство вводимых в программе обозначений операции, ко-

торое не является контекстно-свободным. Поэтому возможно «растворение»

фиксированных приоритетов в синтаксисе, а определяемые приоритеты тре-

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

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

ра. Именно поэтому в языке

С++

возможности определения операций огра-

ничены: из чисто прагматических соображений разработчики языка позво-

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

ций, для которых фиксированы приоритеты. Понятно, что это решение отри-

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

Задания для самопроверки

1. Расклассифицируйте остальные вхождения операций в выражение (5.1).

2. Переведите выражение (5.2) в обратную польскую запись. Изучите ее

и объясните, почему в языке

АЛМО

использовалась обратная польская

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

представлениях транслируемых программ?

3. Проанализировав представления 5.2.4, покажите, когда не стоит поль-

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

один условный оператор с конъюнкцией условий.

268

ГЛАВА 5. ВЫРАЖЕНИЯ

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

первая строчка (5.4)?

5. Объясните причины,почему в первом операторе (5.3) присваивание це-

лочисленной

значения вещественного выражения

a/b

корректно.

Глава 6

Разветвление вычислений

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

слений связываются с условным оператором и оператором выбора. Эти сред-

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

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

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

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

ние во всех реализациях структурного программирования. Она выступает во

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

ему. Поэтому она нуждается в очень серьезном анализе.

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

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

§ 6.1. РАЗБОР СЛУЧАЕВ

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

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

раторов перехода. В принципе, условные операторы и операторы перехода

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

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

эффективной реализации разветвлений.

Однако очень ненадежно использовать только перечисленнные выше сред-

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

нием структурности и снижением наглядности программ. И то, и другое при-

водит к снижению качества программ и к ухудшению их модифицируемости.

6.1.1. Цепочка условий

269

270

ГЛАВА 6. РАЗВЕТВЛЕНИЕ ВЫЧИСЛЕНИЙ

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

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

<число><операция><число>

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

симые подзадачи:

1. ввод данных в заданном формате;

2. подсчет и вывод результата.

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

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

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

деляется третьяподзадача:

3. диагностика корректности результата счета.

Последнюю из упомянутых подзадач естественнее всего осуществлять пу-

тем задания значений (кодов) возврата, соответствующих вариантам завер-

шения выполнения программы.В данном случае уместно предусмотреть сле-

дующие варианты завершения (в приводимом перечне значения возвратов

даны в скобках):

нормальное завершение (код возврата = 0);

ошибка в формате ввода (код возврата = -1);

непредусмотренная операция (код возврата = -2);

деление на ноль (код возврата = -3).

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

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

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

симость. Сделать это можно с помощью определения имен четырех специ-

альных констант с указанными значениями:

const int OK= 0;

const int SYNTAX_ERROR= -1;

const int BAD_OPERATION= -2;

const int ZERO_DIVISION= -3;

6.1. РАЗБОР СЛУЧАЕВ

271

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

лать это можно будет достаточно просто, модифицировав представленные

только что строки.

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

та — оператор возврата функции с соответствующим аргументом:

return

<код возврата>

;

Этот оператор встретится в программе столько раз, сколько потребуется.

Общий контекст, в котором взаимодействуют подзадачи ввода данных в

заданном формате и подсчета и вывода результата — это три переменные:

ﬂoat x, y; /* переменные, представляющие аргументы */

char operation; /* переменная, представляющая операцию */

Для нужд второй из наших подзадач полезно определить переменную

ﬂoat result;

которая будет хранить результат счета.

В данном конкретном случае можно было бы договориться о совмеще-

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

result

Однако единственный аргумент в пользу такого совмещения — экономия па-

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

нятности) программы и потенциальной возможности ее расширения (нельзя

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

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

раз).

С учетом приведенного комментария подзадача ввода данных в заданном

формате решается следующим образом:

printf( “Введите выражение для вычисления в виде \n“);

printf( <число><операция><число>:\n“);

/* Приглашение к вводу */

if( 3 != scanf( “%f%c%f“, &x, &operation, &y ) ) /*!!!*/

{

printf( "Синтаксическая ошибка!\n");

return SYNTAX_ERROR;

}

printf( “Введено выражение %f %c %f\n”, x, operation, y );

Многие начинающие программисты вместо строки,помеченной как

/*!!!*/

написали бы что-то подобное

272

ГЛАВА 6. РАЗВЕТВЛЕНИЕ ВЫЧИСЛЕНИЙ

scanf( "%f%c%f", &x, &operation, &y );

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

да. Но этот подход хуже предложенного по следующим причинам.

• Последующий содержательный анализ осмысленен, лишь если заведо-

мо знать, что введено два числа и один символ.

• Библиотечная функция

scanf

вырабатывает в качестве результата число

корректно введенных значений.

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

3 != scanf( “%f%c%f“, &x, &operation, &y )

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

ную информацию.

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

пользованием набора вложенных условных операторов:

if ( operation == ’+’ ) result = x + y;

else if ( operation == ’-’ ) result = x - y;

else if ( operation == ’*’ ) result = x * y;

else if ( operation == ’/’ )

if ( y == 0 )

{

printf( ”Попытка деления на 0!\n”);

return ZERO_DIVISION;

};

else result = x / y;

else

{

printf (”Недопустимая операция!);

return BAD_OPERATION;

};

В принципе это довольно наглядно, пока случаев не слишком много. Кас-

кад вложенных условных операторов — это достаточно типичное их исполь-

зование, а потому, к примеру, в

Алголе 68

для него придумана специальное

синтаксическое оформление (три варианта):

•

если усл1 то действие 1 инес усл2 то действие 2 ... иначе действие

F все

6.1. РАЗБОР СЛУЧАЕВ

273

•

if усл1 then действие 1 elif усл2 then действие 2 ... else действие F ﬁ

•

( усл1 |действие 1 |: усл2 |действие 2 ... |действие F )

6.1.2. Переключение

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

граничения действий проверяется значение одного и того же выражения,

наиболее важен на практике по следующим причинам:

• Он вполне типичен при построении серий проверок условий,и поэтому

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

мах.

• Он довольно часто может быть реализован эффективно.

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

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

Программа 6.1.1

выбрать по значению оценка из

2=> отчислиться;

3=> зубы на полку;

4,5=> стипендия;

5=> аспирантура

конец

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

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

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

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

ков:

const label[1:n] Метки=(Делай_1,...,Делай_n);

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

фрагмент вида:

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

му конкретному языку программирования. Конструкции, практически изоморфные данной,

есть в языках

FORTRAN

Algol 60

274

ГЛАВА 6. РАЗВЕТВЛЕНИЕ ВЫЧИСЛЕНИЙ

Делай_1: <программа действий 1>;

go to Метка_завершения;

Делай_2: <программа действий 2>;

go to Метка_завершения;

...

Делай_n: <программа действий n>;

go to Метка_завершения;

...

Метка_завершения: ...

В таком случае оператор выбора представляется транслятором (или про-

граммистом на машинном языке) в виде единственного оператора перехода:

go to Метки[i];

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

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

дусмотренной в языке

. Реализация в

лишь слегка облагорожена по срав-

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

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

через оператор выбора.

Стандарт языка

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

ный оператор (

-оператор) и так называемый

switch

-оператор, что соответ-

ствует их общему назначению: организации разветвляющихся вычислений:

<оператор выбора> ::= “

” “(” <условие> “)” <оператор>

[ “

else

” <оператор> ]? |“

switch

” “(” <условие> “)” <оператор>

В данном определении не отражено, что

switch

-оператор совместно с ва-

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

не авторы стандарта вынуждены приводить дополнительные разъяснения о

том, что <оператор> должен включать в себя операторы вида (один из вари-

антов конструкции <помеченный оператор>):

“

case

” <константное выражение> “:” <оператор>

либо

“

default

:” <оператор>

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

<Константное выражение> после “

case

” должно представлять значение,

которое может быть выработано <условием> (с учетом преобразований ти-

пов). Конструкция “

default

:” <оператор> выполняется, когда <условие> не

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