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

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

5.2. ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ

255

if ( x <= 1 )

if ( x <= y )

if ( x * x + y * y <= 4 )

printf( "Да\n");

else printf( "Нет\n");

return 0;

}

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

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

грамма.

Вопрос: а нельзя ли сократить повторения одного и того же оператора —

печати «Нет»? Если не использовать логических значений, то существует

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

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

программе

printf( "Нет\n");

. Один из самых ненаглядных, а потому плохих,

вариантов демонстрируется следующим фрагментом:

Программа 5.2.2

if ( 0 <= x )

if ( x <= 1 )

if ( x <= y )

if ( x * x + y * y <= 4 ) printf( "Да\n");

else goto lbl;

else lbl: printf( "Нет\n");

else goto lbl;

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

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

и от повторений не избавились!

Немного лучше следующий фрагмент:

Программа 5.2.3

256

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

if ( 0 <= x )

if ( x <= 1 )

if ( x <= y )

if ( x * x + y * y <= 4 )

{

printf( "Да\n");

goto lb;

}

printf( "Нет\n");

lb:...

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

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

Лучше в подобных случаях использовать сложные условия. Для этих це-

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

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

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

числовых типов

. Обычно отношениями являются операции сравнения, ска-

жем, в языке

C ==, <, >, <=, >=

Теперь сравните две формы представления программ анализа условий:

Программа 5.2.4

if (Условие1)

if (Условие

2) if ((Условие1)&&(Условие2)

if (Условие

3) && (Условие3))

{ Действие

_1_2_3} { Действие_1_2_3}

else { Действие_1_2_не

_3} /* Но только если нет противоречий */

else { Действие_1_не

_2} /*с другими действиями!*/

else { Действие_не_1

} else Действие_не_1

В языке

имеются операции:

— логическое И,

— логическое ИЛИ.

Операция “

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

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

есть true, и false в противном случае.

Операция “

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

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

из ее операндов есть true, и false, если оба они есть false.

Сравните с предикатами из курса логики.

5.2. ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ

257

Что касается операции НЕ,то в стандартном языке

она не представлена.

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

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

и в результате вырабатывала бы true при значении операнда false, и false в

противном случае.

Тем не менее,возможность добиться эффекта отрицания есть.Чтобы объ-

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

значений. В большинстве других языков (в частности, в расширении язы-

ка

C С++

) тип

bool

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

и можно использовать переменные и значения этого типа (

true

false

), не

зная, как они представляются на машинном уровне. В

такого типа нет, а

true

false

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

true

— это любое целое,

отличное от нуля, а

false

— нуль.

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

Программа 5.2.5

Тест логических значений

#include <stdio.h>

int main()

{

if ( 200 ) printf( "200 - это True.\n");

if ( -33 ) printf( "-33 - это True.\n");

if ( 0 ) printf( "0 - это False!\n");

return 0; /* нормальное завершение */

}

которая напечатает

200 - это True.

-33 - это True.

Это еще раз подчеркивает, что

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

шины с командами перехода по нулевому или ненулевому значению.

Так что вместо чего-либо подобного “

! (a>d)

” (как, к примеру, в

С++

, где

“!” — операция отрицания) приходится писать “

(a>d)== 0

”. Все булевы опе-

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

Стоит подчеркнуть явно, что тип

bool

C++

совсем не то же самое, что, к примеру, в

языке

Pascal

. Множество значений этого типа состоит из двух классов эквивалентности с

точки зрения логических операций: всех ненулевых значений и нулевого значения. Но экви-

258

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

Программа 5.2.6

Попадание точки в область

#include <stdio.h>

int main()

{

ﬂoat x, y;

printf( "Введите координаты в виде <число> <число>:");

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

if( 0 <= x ) && ( x <= 1 ) && ( x <= y ) && ( x*x + y*y <= 4 )

printf( "Да\n");

else printf( "Нет\n");

return 0;

}

Выполнение условного оператора в программе 5.2.6 в идеале должно было

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

ранда, разделенные знаками операции "&&", и, согласно определению этой

операции, если все четыре полученные значения есть "

true

",значением усло-

вия будет "

true

", в противном случае (т. е., когда хотя бы одно из отношений

ложно) значением условия будет "

false

". Тем самым выполняется требуемая

в условии задачи проверка.

Однако для языков

С++

это совсем не так. И различия с приведен-

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

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

когда какое-либо из уже вычисленных оказалось ложным. Аналогично, для

выяснения значения цепочки логических выражений, связанных операцией

ИЛИ (“||”), нет нужды вычислять все составляющие выражения, когда одно

из них оказалось истинным. По этим причинам в языке

С++

принято, что

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

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

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

ных операцией ИЛИ, это первое истинное значение).

Указанный порядок

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

логических значений

b1==b2

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

ны программисту как

true

Иногда ошибочно утверждают, что в языке

при вычислении логических выражений ис-

пользуется сильная трехзначная логика Клини (см., напр., [38]), которая работает с неопре-

5.2. ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ

259

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

Pascal

, и от всех остальных операций

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

выполняться в точности так, как фрагмент 5.2.3. Следовательно, с точки зре-

ния скорости выполнения обе записи эквивалентны. Для языка, в котором

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

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

ничего нельзя. К примеру, в системе программирования

Turbo Pascal

есть два

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

ют два случая:

• вычислять все логические операнды;

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

ния.

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

ное вычисление логических операций в

С++

. Для этого используются опера-

ции поразрядной логики (см. выше), которые для конкретных представлений

значений

true

false

работают правильно и заставляют вычислиться все опе-

ранды.

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

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

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

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

стоятельные программные единицы:

init

activate

run

terminate

. Каждая из

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

грамма выполнилась успешно. Если успешному выполнению

init

activate

run

terminate

приписать значение

true

,а неуспешному —

false

,что означает

возврат каждой из этих функций с соответствующим значением, то процесс

в целом наглядно представляется следующим фрагментом:

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

ложен (другой может быть и не определен).

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

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

при исполнении одного из них не фиксируется, если какой-либо другой приведет к удаче. А

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

обеспечивается. Анализ “логики”, используемой в языке

, см., напр., в книге [27].

260

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

if (init ( )

&& activate ( )

&& run ( )

&& terminate ( ))

{ ... }

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

Программа 5.2.1, а точнее формулы, вычисляющие значение отношения

x ∗ x + y ∗y <= 4 (5.5)

а также значение более сложного выражения

(0 <= x)&&(x <= 1)&&(x <= y)&&(x ∗ x + y ∗ y <= 4)

дают повод поговорить о приоритетах

выполнения операций. На рис. 5.2

изображена абстрактно-синтаксическая структура условия (5.5).Она дает чет-

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

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

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

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

текста программы? Вопрос не праздный, ведь, к примеру, выражение

x ∗ (x + y) ∗ y <= 4

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

но-синтаксическую структуру. В то же время, структура выражения

((x ∗ x) + (y ∗ y)) <= 4

совпадает с исходной.

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

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

нием. Можно следовать, например, такому определению:

Не путайте приоритеты операций с приоритетами процессов! Приоритеты операций —

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

сов — попятие семантическое, работающее на этапе исполнения программной системы.

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

261

Условие

Значение = 4

Операнд

Переме

ная

Операнд

Имя = x

Переме

ная

Операнд

Имя = x

Переменная

Операнд

Имя =

Переме

ная

Операнд

Имя =

Операнд

Константа

Операнд

Рис. 5.2. Абстрактно-синтаксическая структура условия

262

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

<выражение> ::=

<первичное выражение> [ <знак операции> <первичное выражение> ]*

<первичное выражение> ::=

<имя переменной> |

<константа> |

“(” <выражение> “) ”|

<знак унарной префиксной операции><первичное выражение> |

<первичное выражение><знак унарной постфиксной операции>

<знак операции> ::= /* здесь приводятся не все знаки операций! */

“* ” | “/ ”|/* знаки операций приоритета 2*/

“+ ” | “- ”|/* знаки операций приоритета 1*/

“< ” | “<= ” | “== ” | “!= ” | “>= ” | “>”/* знаки отношений приоритета 0*/

<знак унарной префиксной операции> ::=

& /* знаки остальных унарных операций пока не определяются */

<знак унарной постфиксной операции> ::=

++ /* знаки остальных унарных операций пока не определяются */

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

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

2. Операнды операций вычисляются совместно;

3. Скобки в выражении задают принудительный порядок вычислений, со-

ответствующий скобочной структуре.

4. Знакам операций приписываются приоритеты; в языке

C++

эти прио-

ритеты расставлены в соответствии со следующими правилами:

(a) знаки бинарных присваиваний (

и т. д.) получают низший

приоритет;

(b) знаки логических операций получают следующий приоритет за

знаками присваиваний;

приоритет за знаками логических операций;

(d) знаки операций отношений получают следующий приоритет за

знаками поразрядных логических операций;

(e) знаки операций сдвига получают следующий приоритет за знака-

ми отношений;

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

263

(f) знаки операций типа сложения получают приоритет, следующий

за приоритетом знаков отношений;

(g) знаки операций типа умножения получают приоритет, следующий

за приоритетом знаков операций типа сложения;

(h) унарные постфиксные операции получают наивысший приоритет;

(i) унарные префиксные операции получают высший приоритет по-

сле приоритета знаков постфиксных операций;

5. Если в текстовой записи выражения есть фрагмент вида

<операнд><знак операции(1)>

<операнд> <знак операции(2)>

...

<знак операции(n)><операнд>

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

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

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

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

выполняется операция 1, затем — операция 2, и так далее.

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

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

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

для этих целей).

Сначала рассмотрим упрощенный пример:

<первичное выражение> ::=<имя переменной> |

<константа> |“(”<выражение> “)”

<вторичное выражение> ::=<первичное выражение> |

<вторичное выражение> [ “*”|“/”] <первичное выражение>

<выражение> ::=<вторичное выражение> |

<выражение> [ “+ ” | “-”] <вторичное выражение>

<имя переменной> ::=“a ” | “b”

<константа> ::=“1” | “2”

Вывод выражения a ∗ (b + 1):

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

<вторичное выражение> →

<вторичное выражение> * <первичное выражение> →

<первичное выражение> * <первичное выражение> →

264

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

<первичное выражение> * (< выражение> )→

<имя переменной> * (< выражение> )→

a∗ (<выражение> )→

a∗ (<выражение> + <вторичное выражение> )→ ... →

a ∗ (b+ <вторичное выражение>)→

a ∗ (b+ <первичное выражение> )→

a ∗ (b+ <константа>)→

a ∗ (b + 1)

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

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

a выводится длинно:

<выражение>→<вторичное выражение>→

<первичное выражение> →<имя переменной>→ a

В языке

C++

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

<первичное выражение> ::= <имя переменной> |

<константа> |“(”<выражение> “)”

<постфиксное выражение> ::= <первичное выражение> |

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

/* элемент массива */|

<постфиксное выражение> “(”[ <список выражений> ]? “)”

/* вызов функции */|

<постфиксное выражение> [ “++”|“--”]

<список выражений>::=<выражение присваивания>[ “,”<выражение при-

сваивания> ]*

<унарное выражение> ::= <постфиксное выражение> |

[“++” | “--”] <унарное выражение> |

[“*” | “&” | “+” | “-” | “!” | “~”] <унарное выражение> |

“

sizeof

” <унарное выражение>

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

<выражение вида умножения> [“*” | “/” | “%”] <унарное выражение>

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

<выражение вида сложения> [“+” | “-”] <выражение вида умножения>

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

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

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

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