Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 94
Текст из файла (страница 94)
8.1 не ясно, что следует вычислять раньше: -В или В**2; также непонятно, можно ли объединить две ссылки на идентификатор В в одну. К сожалению, как мы увидим позже, при наличии операций с побочными эффектами различные способы рен>ения этих вопросов могут привести к разным результатам, Как правило, в описании языка порядок вычисления выражений определяется на уровне древовидного представления, а определение точного порядка вычислений (например, порядка вычисления -В и 8**2) предоставляется разработчику языка. Однако прежде чем рассматривать проблемы, возникающие при определении точного порядка вычислений, следует ознакомиться с различными вариантами синтаксического представления выражений.
8.2. Вычисление арифметических выражений 335 Рис. 6.1. Древовидное представление формулы для нахождения корня квадратного уравнения Синтаксис выражений Если мы условимся представлять выражения при помощи деревьев, тогда для использования выражений в программах необходимо осуществить некоторую линеаризацию деревьев (то есть должна быть разработана система обозначений для записи деревьев в виделинейной последовательности символов). Рассмотрим наиболее распространенные способы записи.
Префиксная (польсквя префиксная) запись. Для обращения к функции в программе обычно имя функции пишется перед се аргументами, например Пх, у, 7). Такой способ записи можно распространить на все операции в выражениях. Так, в префиксной записи сначала записывается символ операции, а затем по порядку, слева направо — операнды.
Если операндом является операция, то применяется это же правило.Тогдадерево,изображенноенарис. 82,можнопредставитьввиде х + а Ь вЂ” с а. Поскольку + является бинарной операцией (то есть требует двух аргументов), то совершенно ясно, что аргументами для + являются а и Ь.
Аналогично, аргументами для операции — должны быть с и а. И наконец, аргументами для операции умножения х будут член, содержащий е, и член, содержащий —. В такой записи нет никакой неоднозначности, и нет необходимости применять скобки для точного определения последовательности операций при вычислении выражения, Поскольку свободный от скобок способ записи изобрел польский математик Лукашевич (1л1газтеъчю), то для обозначения этого способа записи и его производных применяется название польская запись.
336 Глава 8. Управление последовательностью действий рнс. 8.2. Древовидное представление простого выражения (в + Ы н (с — а) В языке 1ЛЯР используется один из вариантов этого способа записи, который иногда называют кембриджской польской зописью. В кембриджской польской записи операция и ее аргументы заключаются в скобки. Выражение принимает вид вложенного множества списков, в котором каждый список начинается с символа операции, за которым следуют списки, представляющие ее операнды.
В польской кембриджской записи выражение, отображенное на рис. 8.2, будет выглядеть следующим образом: (ь(+аЬ) (-са) ). Посмотрим, как будет выглядеть формула для вычисления корня квадратного уравнения в префиксной записи (для обозначения возведения в степень будем использовать символ Т, для квадратного корня — символ з(, а для унарного минуса — символ ): /+ Ь) -ТЬ2ХХ4асХ2а польская запись (/("( Ы( )(-(Т Ь 2)(Х(Х 4 а)с))))(х 2 а)) кембрнлжская польская запись Постфиксная (суффиксная, или обратная польская) запись. Постфиксная запись похожа на префикс ную запись, однако символ, обозначающий операцию, расположен после списка операндов. Таким образом, выражение, приведенное на рис.8.2,будет выглядеть как: а Ь + с а - х. Инфиксная запись.
Ипфиксная запись наилучшим образом подходит для бинарных (двучленных) операций. При инфиксной записи символ операции пишется между двумя операндами. Поскольку в математике для обозначения основных арифметических и логических операций, а также операций сравнения используется именно инфиксная запись, то она широко применяется для тех же операций и в языках программирования, а в некоторых случаях она распространяется и на другие операции. Дерево выражения, изображенное на рис.
8.2, в инфи ксной форме записывается как (а + Ь) х (с — а). Для операций с количеством аргументов, большим двух (например, в условной тернарной операции языка С), инфиксная запись используется в несколько неуклюжей манере путем применения многократных инфиксных операции: (ехрг? гн . .аг). Семантика выражений Каждый из трех способов записи — префнксная, постфиксная и инфиксная — имеет определенные характеристики, полезные при разработке языков программирования. Принципиально онн различаются тем, как мы вычисляем значение каждого выражения, представленного в той или иной форме записи.
Ниже мы приводим 8.2. Вычисление арифметических выражений 337 алгоритмы вычисления (то есть семантику вычисления) для каждого способа записи выражений. Затем мы показываем, что у транслятора имеется возможность выбора: использовать непосредственно этот процесс или, немного изменив его, реализовать вычисление выражения более эффективно. Префиксное вычисление. С использованием префиксной записи мы можем вычислить ля>бее выражение за один просмотр.
Однако при этом необходимо знать количество аргументов для каждой операции. Именно по этой причине необходимо использовать различные символы для б>инарного вычитания (-) и унарного минуса ( ), чтобы различать их в записи выражения (или же следует использовать кембриджскую польскую запись со скобками). Помимо того что мы экономим на отсутствии скобок в выражениях, префиксная запись вообще имеет некоторые преимущества при разработке языков программирования. 1.
Как отмечалось, обычный вызов функций уже записан в прсфиксной форме. 2. Префиксную запись можно использовать для представления операций с любым количеством операндов, и поэтому она является наиболее общей, Для записи любого выражения необходимо выучить только одно синтаксическое правило. Например, для написания лк>бого выражения на языке 1.1ЯР достаточно освоить только кембриджскую польскую запись, и можно сказать, что после этого вам будут известны основные синтаксические правила этого языка. 3. Также префиксну>о запись относитслыю легко декодировать механически, поэтому нетрудно осуществить перевод префиксных выражений в простую последовательность кодов.
Этот последний пункт (простота транслирования в последовательность кодов) можно продемонстрировать следующим алгоритмом. Заданнос в прсфиксной форме выражение Р, состоящее из операций и операндов, можно вычислить с помощью стека. 1. Если очередной символ в выражении Р— символ операции, то помещаем его в вершину стека. устанавливаем счетчик аргументов так, чтобы он соответствовал количеству операндов, необходимых для вычисления данной операции.
(Если количество операндов равняется и, то такую операцию называют п-арной.) 2. Если следующий элемент — операнд, помешаем его в вершину стека. 3. Если верхние п записей в стеке — операнды, необходимые для вычисления верхней п-арной операции (например, если сложение ч. было последней операцией, занесенной в стек, н в него же было добавлено два операнда), то можно применить эту операцию к данным операндам.
После выполнения операции заменяем символ операции и и ее операндов на рсзулыат применения этой операции к соответствующим операндам. Хотя эта модель вычислений довольно проста, но и здесь существует некоторая сложность — после занесения очередного операнда в стек приходится проверять, имеем ли мы достаточное количество операндов для выполнения соотве~ствую- 338 Глава 8. Управление последовательностью действий щей операции. Чтобы избежать подобной проверки, следует использовать постфиксную запись. Постфнксное вычисление.
Поскольку в постфиксной записи операция следует непосредственно за своими операндами, то при считывании символа операции ее операнды уже известны, Таким образом, вычисление постфиксного выражения Р с использованием стека будет выглядеть следук>щим образом: 1. Если следующий элемент — операнд, помещаем его в стек. 2. Если очередной символ является символом п-арной операции, значит, и ее аргументов доллов| бить представлены п верхними элементами стека. Заменяем эти элементы на результат применения к ним соответствукицей операции. Как видно, стратегия вычислений прямая и легко реализуемая. Фактически в большинстве трансляторов эта стратегия является основой генерации кода для вычисления выражений. В процессе трансляции (см. главу 3) синтаксис выражений часто переводится в постфиксную форму. В этом случае для определения порядка генерируемого кода для вычисления значения выражения генератор кода может использовать приведенный выше алгоритм.
Иификсиое вычисление. Хотя инфш<сная запись широко распространена, ее использование в языках программирования создает некоторые особые проблемы. 1. Посколькуинфикснаязаписьподходиттолькодля бинарныхопераций,язык не может использовать только одну эту форму записи для выражений, но обязательно должен сочетать ее с префиксной (или постфиксной). Такое смешение делает, соответственно, трансляцию более сложной. Унарные операции и вызовы функций с несколькими аргументами должны быть исклк>- чениями из стандартных инфиксных свойств. 2.
Когда в выражении появляется более одной инфиксной операции, запись выражения становится неоднозначной, если не использовать скобки. Этот последний пункт можно проиллюстрировать на примере инфиксного выражения 2 х 3 + 4. Вы, несомненно, думаете, что значение этого выражения 10, но оно так же легко может оказаться равным 14. На рис. 8.3 показано, почему так может получиться. Когда вы впервые изучали сложение и умножение, вы выучили следующее правило: «Умножение делается прежде, чем сложение» (см. рис. 8.3, а). На самом деле, это всего-навсего соглашение, и математика могла бы развиваться так же успешно, если бы был принят обратный порядок действий (см, рис, 8.3, б).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
