Приоритет оператора по сравнению с порядком оценки

Question

Термины «приоритет оператора» и «порядок вычисления» очень часто используются в программировании и чрезвычайно важны для программиста. И, насколько я понимаю, эти два понятия тесно связаны; один не может обойтись без другого, говоря о выражениях.

Давайте рассмотрим простой пример:

int a=1;  // Line 1
a = a++ + ++a;  // Line 2
printf("%d",a);  // Line 3

Теперь очевидно, что Line 2 ведет к неопределенному поведению, поскольку Точки последовательности в C и C ++ включают в себя:

1. Между вычислением левого и правого операндов && (логический И), || (логическое ИЛИ) и запятая операторы. Например, в выражение *p++ != 0 && *q++ != 0, все побочные эффекты подвыражения *p++ != 0 завершено до любой попытки доступа к q.

2. Между оценкой первого операнда троичного оператор "вопросительный знак" и второй или третий операнд. Например, в выражении a = (*p++) ? (*p++) : 0 есть точка последовательности после первый *p++, то есть уже был увеличен ко времени выполняется второй экземпляр.

3. В конце полного выражения. Эта категория включает в себя выражение заявления (такие как назначение a=b;), возвратные заявления, управляющие выражения if, switch, операторы while или do-while и все три выражения в выражении for.

4. Перед вводом функции в вызов функции. Порядок, в котором аргументы оцениваются не указано, но эта точка последовательности означает, что все их побочные эффекты завершены, прежде чем функция поступил. В выражении f(i++) + g(j++) + h(k++), f вызывается с параметр исходного значения i, но i увеличивается перед вводом тело f. Точно так же j и k являются обновляется перед вводом g и h соответственно. Тем не менее, это не указано в каком порядке f(), g(), h() ни в каком порядке i, j, k увеличиваются. Значения j и Следовательно, k в теле f undefined. 3 Обратите внимание, что функция Звоните f(a,b,c) не использование оператор запятой и порядок оценка для a, b и c не определено.

5. При возврате функции после копирования возвращаемого значения в вызывающий контекст. (Эта точка последовательности указывается только в стандарте C ++; это присутствует только неявно в C).

6. В конце инициализатора; например, после оценки 5 в декларации int a = 5;.

Итак, пройдя по пункту № 3:

В конце полного выражения. В эту категорию входят операторы выражений (например, присваивание a = b;), операторы return, управляющие выражения операторов if, switch, while или do-while и все три выражения в операторе for.

Line 2 явно ведет к неопределенному поведению. Это показывает, как неопределенное поведение тесно связано с точками последовательности .

Теперь давайте возьмем другой пример:

int x=10,y=1,z=2; // Line 4
int result = x<y<z; // Line 5

Теперь очевидно, что Line 5 сделает переменную result store 1.

Теперь выражение x<y<z в Line 5 можно оценить как:

x<(y<z) или (x<y)<z. В первом случае значение result будет 0, а во втором случае result будет 1. Но мы знаем, что когда Operator Precedence is Equal/Same - Associativity вступает в игру, следовательно, оценивается как (x<y)<z.

Это то, что сказано в этой статье MSDN :

Приоритет и ассоциативность операторов C влияют на группирование и оценку операндов в выражениях.Приоритет оператора имеет смысл, только если присутствуют другие операторы с более высоким или низким приоритетом.Выражения с операторами более высокого приоритета вычисляются первыми.Старшинство также можно описать словом «связывание».Считается, что операторы с более высоким приоритетом имеют более жесткую привязку.

Теперь о статье выше:

В ней упоминается «Выражения с операторами с более высоким приоритетом вычисляются первыми."

Возможно, это звучит неправильно.Но я думаю, что статья не говорит что-то не так, если мы считаем, что () также является оператором x<y<z - это то же самое, что и (x<y)<z.Я рассуждаю так: если ассоциативность не вступит в игру, тогда оценка полных выражений станет неоднозначной, поскольку < не является точкой последовательности .

Кроме того, другойссылка, которую я нашел, говорит об этом на Приоритет оператора и ассоциативность :

На этой странице перечислены операторы C в порядке приоритета (от высшего к низшему).Их ассоциативность указывает, в каком порядке применяются операторы равного приоритета в выражении.

Итак, во втором примере int result=x<y<z мы можем видеть здесь, что во всех 3 выражениях есть x, y и z, поскольку простейшая форма выражения состоит из одной литеральной константы или объекта.Следовательно, результат выражений x, y, z будет там rvalues ​​, то есть 10, 1 и 2 соответственно.Следовательно, теперь мы можем интерпретировать x<y<z как 10<1<2.

Теперь, ассоциативность не вступает в игру, так как теперь у нас есть 2 выражения для оценки, либо 10<1, либо 1<2, и поскольку приоритет оператора такой же, они оцениваются слева.вправо ?

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

int myval = ( printf("Operator\n"), printf("Precedence\n"), printf("vs\n"),
printf("Order of Evaluation\n") );

Теперь в приведенном выше примере, поскольку оператор comma имеет такой же приоритет, выражения вычисляются left-to-right и возвращаемое значение последнего printf() сохраняется в myval.

В SO / IEC 9899: 201x в J.1 Неуказанное поведение в нем упоминается:

Порядок, в котором оцениваются подвыражения, и порядок, в котором происходят побочные эффекты, за исключением случаев, указанных для функции-call (), &&, ||,?: и запятойоператоры (6.5).

Теперь я хотел бы знать, было бы неправильно сказать:

Порядок оценки зависит от приоритета операторов, оставляя случаиНеуточненное поведение.

Я хотел бы быть исправленесли в чем-то были допущены ошибки, я сказал в своем вопросе.Причина, по которой я разместил этот вопрос, заключается в том, что статья MSDN заставила меня задуматься.Это в Ошибка или нет?

Answer 1

Да, статья MSDN содержит ошибку, по крайней мере, в отношении стандартов C и C ++ ¹ .

Сказав это, позвольте мне начать с примечания о терминологии: в стандарте C ++ они (в основном - есть несколько ошибок) используют «оценку» для обозначения вычисления операнда и «вычисление значения» ссылаться на проведение операции. Таким образом, когда (например) вы делаете a + b, каждый из a и b оценивается, тогда выполняется вычисление значения для определения результата.

Понятно, что порядок вычислений значений (в основном) контролируется приоритетом и ассоциативностью - управление вычислениями значений - это, в основном, определение того, что приоритет и ассоциативность равны . Остальная часть этого ответа использует «оценку» для ссылки на оценку операндов, а не для вычисления вычислений.

Теперь, что касается порядка оценки, определяемого по приоритету, нет, это не так! Это так просто. Просто для примера, давайте рассмотрим ваш пример x<y<z. Согласно правилам ассоциативности, это разбирается как (x<y)<z. Теперь рассмотрим оценку этого выражения на стековой машине. Для него вполне допустимо сделать что-то вроде этого:

 push(z);    // Evaluates its argument and pushes value on stack
 push(y);
 push(x);
 test_less();  // compares TOS to TOS(1), pushes result on stack
 test_less();

Это оценивает z до x или y, но все равно оценивает (x<y), а затем сравнивает результат этого сравнения с z, как и положено.

Резюме: порядок оценки не зависит от ассоциативности.

Приоритет такой же. Мы можем изменить выражение на x*y+z и по-прежнему оценивать z до x или y:

push(z);
push(y);
push(x);
mul();
add();

Резюме: порядок оценки не зависит от приоритета.

Когда / если мы добавим побочные эффекты, это останется прежним. Я думаю, что образовательно думать о побочных эффектах, как о выполняемых отдельным потоком выполнения, с join в следующей точке последовательности (например, конец выражения). Так что что-то вроде a=b++ + ++c; может быть выполнено примерно так:

push(a);
push(b);
push(c+1);
side_effects_thread.queue(inc, b);
side_effects_thread.queue(inc, c);
add();
assign();
join(side_effects_thread);

Это также показывает, почему очевидная зависимость также не обязательно влияет на порядок оценки. Даже если a является целью назначения, это все равно оценивает a до , оценивая либо b, либо c. Также обратите внимание, что, хотя я написал это как «поток» выше, это также может быть пул потоков, все выполняющиеся параллельно, так что вы не получите никакой гарантии о порядке один шаг по сравнению с другим либо.

Если бы аппаратное обеспечение не имело прямой (и дешевой ) поддержки поточно-ориентированных очередей, это, вероятно, не использовалось бы в реальной реализации (и даже тогда это маловероятно). Помещение чего-либо в потокобезопасную очередь, как правило, требует гораздо больше накладных расходов, чем выполнение одного приращения, поэтому трудно представить, чтобы кто-нибудь когда-либо делал это в реальности. Концептуально, однако, идея соответствует требованиям стандарта: когда вы используете операцию до / после увеличения / уменьшения, вы указываете операцию, которая произойдет через некоторое время после оценки этой части выражения, и будет выполнена в следующая точка последовательности.

Редактировать: хотя это не совсем многопоточность, некоторые архитектуры допускают такое параллельное выполнение. Для пары примеров процессоры Intel Itanium и VLIW, такие как некоторые DSP, позволяют компилятору назначать ряд команд для параллельного выполнения. Большинство машин VLIW имеют определенный размер «пакета» команд, который ограничивает количество команд, выполняемых параллельно. Itanium также использует пакеты инструкций, но указывает бит в пакете инструкций, чтобы сказать, что инструкции в текущем пакете могут выполняться параллельно с инструкциями в следующем пакете. Используя подобные механизмы, вы получаете инструкции, выполняемые параллельно, как если бы вы использовали несколько потоков в архитектурах, с которыми большинство из нас более знакомы.

Резюме: порядок оценки не зависит от очевидных зависимостей

Любая попытка использовать значение до следующей точки последовательности приводит к неопределенному поведению - в частности, «другой поток» (потенциально) изменяет эти данные в течение этого времени, и у вас есть нет способсинхронизировать доступ с другим потоком.Любая попытка его использования приводит к неопределенному поведению.

Просто для примера (по общему признанию, теперь довольно надуманного), представьте, что ваш код работает на 64-битной виртуальной машине, но реальное оборудование - 8.процессорКогда вы увеличиваете 64-битную переменную, она выполняет последовательность, которая выглядит примерно так:

load variable[0]
increment
store variable[0]
for (int i=1; i<8; i++) {
    load variable[i]
    add_with_carry 0
    store variable[i]
}

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

Этот точный пример может быть довольно надуманным, но менее экстремальной версией (например, 64-битная переменная на32-разрядный компьютер) на самом деле довольно распространен.

Заключение

Порядок оценки не зависит от приоритета, ассоциативности или (обязательно) от очевидных зависимостей.Попытка использовать переменную, к которой был применен предварительный / последующий инкремент / декремент в любой другой части выражения, действительно дает полностью неопределенное поведение.Хотя реальный сбой маловероятен, вы определенно не гарантированно получите либо старое, либо новое значение - вы можете получить что-то еще полностью.

---

¹ Я не проверял эту конкретную статью, но довольно много статей MSDN рассказывают о Microsoft Managed C ++ и / или C ++ / CLI (или специфичны для их реализации C ++), но мало или ничего не указывают на то, что онине относится к стандарту C или C ++Это может создать ложное представление о том, что они утверждают, что правила, которые они решили применить к своим собственным языкам, фактически применяются к стандартным языкам.В этих случаях статьи не являются технически ложными - они просто не имеют ничего общего со стандартом C или C ++.Если вы попытаетесь применить эти операторы к стандарту C или C ++, результат будет ложным.

Answer 2

Единственный способ, которым приоритет влияет на порядок оценки, - это создает зависимости; в противном случае они ортогональны. Вы имеете тщательно отобранные тривиальные примеры, в которых зависимости, созданные приоритет в конечном итоге полностью определяет порядок оценки, но это не так в общем, правда. И не забывайте, что многие выражения имеют два эффекта: они приводят к значению, и у них есть побочные эффекты. Эти два не обязательно должны происходить вместе, поэтому даже при зависимостях форсировать определенный порядок оценки, это всего лишь порядок оценка ценностей; не влияет на побочные эффекты.

Answer 3

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

Если у вас есть выражение, скажем, x+y*z, вы можете переписать его в дерево выражений:

Применение правил приоритета и ассоциативности:

x + ( y * z )

После применения правил приоритета и ассоциативности вы можете спокойно о них забыть.

В виде дерева:

  x
+
    y
  *
    z

Теперь листьями этого выражения являются x, y и z. Это означает, что вы можете оценить x, y и z в любом порядке, а также это означает, что вы можете оценить результат * и x в любом порядке.

Теперь, поскольку у этих выражений нет побочных эффектов, вам все равно. Но если они это сделают, порядок может изменить результат, и поскольку порядок может быть любым, что решит компилятор, у вас есть проблема.

Теперь точки последовательности вносят некоторый порядок в этот хаос. Они эффективно режут дерево на секции.

x + y * z, z = 10, x + y * z

после приоритета и ассоциативности

x + ( y * z ) , z = 10, x + ( y * z)

дерево:

      x
    +
        y
      *
        z
  , ------------
      z
    =
      10     
  , ------------
      x
    +
        y
      *
        z   

Верхняя часть дерева будет оценена до середины, а средняя до нижней.

Answer 4

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

Я просто собираюсь повторить то, что я сказал здесь . Что касается стандартов C и C ++, то эта статья имеет недостатки. Приоритет влияет только на то, какие токены считаются операндами каждого оператора, но это никак не влияет на порядок вычисления.

Итак, ссылка только объясняет, как Microsoft реализовала вещи, а не как сам язык работает.

Answer 5

Приоритет не имеет ничего общего с порядком оценки и наоборот.

Приоритет правила описывают, как выражение в скобках должно заключаться в скобки, когда выражение смешивает операторы разных типов.Например, умножение имеет более высокий приоритет, чем сложение, поэтому 2 + 3 x 4 эквивалентно 2 + (3 x 4), а не (2 + 3) x 4.

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

Возьмите пример

y = ++x || --y;   

По правилу приоритета оператора он будет заключен в скобки, поскольку (++/-- имеет более высокий приоритет, чем ||, который имеет более высокий приоритет, чем =):

y = ( (++x) || (--y) )   

Порядок вычисления логического ИЛИ || гласит, что (C11 6.5.14)

the ||оператор гарантирует слева направо оценку.

Это означает, что левый операнд, то есть подвыражение (x++), будет оцениваться первым.Из-за короткого замыкания; Если первый операнд сравнивается с неравенством 0, второй операнд не оценивается , правый операнд --y не будет оцениваться, хотя он заключен в скобки до (++x) || (--y).

Answer 6

Я думаю, что это только проблемное выражение

a++ + ++a

, потому что

a = a++ + ++a;

подходит сначала в 3., а затем в правиле 6.: завершите оценку до назначения.

Итак,

a++ + ++a

получает для a = 1, полностью оцененного как:

1 + 3   // left to right, or
2 + 2   // right to left

Результат тот же = 4.

An

a++ * ++a    // or
a++ == ++a

будет иметь неопределенные результаты.Не так ли?