Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 96
Текст из файла (страница 96)
Каждый нз способов записи выражений, перечисленных выше, имеет свои собственные недостатки, Инфнксная запись со своими неявными правилами при- 8,2. Вычисление арифметических выражений 343 оритетов и сочетательностью операций, а также с явным использованием (при необходимости) скобок дает довольно естественное представление для большинства арифметических и логических выражений и выражений сравнения.
Однако необходимость использования сложных неявных правил и префиксной (или другой) записи для операций, отличных от бинарных, усложняет трансляцию таких выражений. Инфиксная запись, лишенная неявных правил, является громоздкой из-за необходимости использовать большое количество скобок. Однако как в кембриджской польской, так и в обычной математической префиксной записи проблема со скобками все же присутствует. В польской записи вообще не используются скобки, но необходимо заранее знать количество операндов для каждой операции, а это условие обычно трудно выполнить (особенно если речь идет о расширении языка операциями, которые определены программистами), Наконец, отсутствие каких-либо структурирующих подсказок затрудняет чтение сложных выражений, записанных с помощью польской записи. Как префиксная, так и постфиксная запись имеет преимущество при записи операций с различным числом операндов.
8.2.2. Представление выражений во время выполнения программы Ранее были приведены алгоритмы для понимания семантики выражений, записанных во всех трех формах. Однако если сначала перевести каждое выражение н его древовидное представление, у транслятора появится возможность выбора эффективного способа вычисления выражения. Когда выражение может быть представлено в инфиксной форме, неявные правила приоритетов и сочетаемости операций позволяют на первой стадии трансляции установить основную древовидную управляющую структуру выражения. На второй, необязательной стадии принимаются уточненные решения, связанные с порядком вычисления, включая оптимизацию этого процесса. Выражения в своей исходной инфиксной форме в тексте программы трудны для декодирования, поз~ему их принято транслировать в выполняемую форму, легко декодируемую в процессе выполнения программы.
Среди используемых вариантов наиболее важны следующие, 1. Посзедовительяость машинных команд. Выражение транслируется прямо в машинные коды, две стадии трансляции объединяются в одну. Порядок команд отражает структуру управления последовательностью действий исходного выражения, На традиционных компьютерах для хранения промежуточных результатов такие последовательности машинных команд должны использовать явно выделяемую временную память, Конечно, представление в виде машинных кодов допускает использование аппаратного интерпретатора, что обеспечивает очень высокую скорость выполнения, 2. Древовидные структуры.
Выражение может быть преобразовано непосредственно в его естественное древовидное структурное представление (первый этап) с помощью программного интерпретатора. Его вычисление (второй этап) может быть затем осуществлено простым обходом дерева. Этот 344 Глава 8.
Управление последовательностью действий метод является основным для программно интерпретируемого языка 1.18Р, в котором во время выполнения вся программа представляется в виде древовидных структур. 3. Префиксния или постфикслая форма. Выражения, представленные в префиксной или постфиксной форме, можно вычислять с помощью приведенного выше простого алгоритма интерпретации (причем оба этапа осуществляются за один |наг). В некоторых компьютерах, основанных на стековой организации, машинный код, по существу, представлен в постфикспой форме. Префиксное представление является выполняемой формой программы во многих реализациях языка 81чьОВ01А. Выполнение осуществляется сканированием выражения слева направо, причем каждая операция рекурсивно вызывает интерпретатор для вычисления своих операндов. Вычисление выражения по его представлению в виде дерева Хотя трансляция выражений в программах в их представления в виде дерева иногда и вызывает затруднения, но на самом деле основная процедура трансляции проста, Вторая стадия, во время которой дерево преобразуется в выполняемую последовательность алемептарных операций, включает регпение большинства тонких вопросов, касающихся порялка вычисления выражения.
Мы цс собираемся здесь изучать сами алгоритмы генерации выполняемого кола па основе представления выражения в виде дерева, а всего лишь хотим рассмотреть те проблемы, касающиеся порядка вычисления выражений, которые возникают при точном определении генерируемого кода. Проблема 1. Унифицированные правила вычислений. При вычислении выражения или генерации кода для его вычисления кажется очевидным применение следующего унифицированного правила вычислений.
Для каждого узла, представляющего операцию в дереве выражения, сначала вычисляются все его операнды (или генерируется код для их вычисления), а затем к вычисленным операндам применяется операция (или генерируется код для применения операции). Поскольку всегда сначала вычисляются операнды, мы называем это правилом активного вычисления. Точный порядок выполнения этих вычислений не должен иметь значения, поэтому можно выбрать порядок вычисления операндов или независимых операций из соображений оптимизации использования временной памяти или каких-либо иных аппаратных характеристик компьютера. Этому правилу вычислений удовлетворяет любой из приведенных ниже порядков вычисления выражения (а+Ь) х (с-а), древовидная структура которого изображена на рис.
8.2. Порядок 1. Сначала вычисляем а ч Ь. 1. Извлекаем из памяти г-значение переменной а. 2. Извлекаем из памяти гзначение переменной Ь. 3. Складываем а и Ь, получая ф 4. Извлекаем из памяти г-значение переменной с. 5. Вычитаем а из с, получая е. 6. Перемножаем 0 н е, получая 1, являющееся г-значением выражения. 8.2. Вычисление арифметических выражений 345 Рис. 8.4. Выражение, содержащее условную операцию Порядок 2.
Вычисляем операнды до выполнения любой операции. 1. Извлекаем из памяти г-значение переменной с. 2. Извлекаем из памяти г-значение переменной О. 3, Извлекаем из памяти г-значение переменной а. 4. Вычитаем а из с, получая е. 5. Складгяваем а и Ь, получая 4. 6. Перемножаем 4 и е, получая Г. Все зто выглядит совершенно сстествсших и было бы заманчиво всегда применять это унифицированное правило вычислений. К сожалению, опо не всегда применимо.
Наилу пним примером являются выражения, содержащие условные операции. Например,следующеевыражениенаязыкеСг7 + (У = О? 'г 'х/Удсолержит встроенный оператор 11, который вычисляет Х/У, если У не равняется О. Может возникнуть желание рассматривать зту условную операцию просто как операцию с необычным синтаксисом и тремя операндами, как показано на рис. 8А.
На самом деле, например, в языке 1 !БР так и поступают, используя кембриджскую польскую запись для условных операций точно также, как и для любых других. Но здесь и возникает проблема с унифицированным правилом вычислений. Если мы применим это правило и вычислим сначала операнды условной операции, изображенной на рис. 8.4, мы сделаем как раз то, во избежание чего и понадобилось условие, а именно поделим а на у, даже сели у будет равен О, ясно, что в данном случае не следует вычислять все операнды перед применением операции.
Наоборот, операнды условной операции (или, по крайней мере, последние два) нужно оставить не вычисленными и предоставить самой операции определять порядок вычисления. Проблема с условными операциями наводит на мысль, что, вероятно, лучше будет использовать другое унифицированное правило вычислений, обычно называемое правилом ленивого вычисления; никогди не вычислять операнды перед применением операции, Наоборот, всегда оставлять операнды не вычисленными и позволять самой операции решать, необходимо ли их вычисление до выполнения операции. Это правило работает во всех случаях и теоретически могло бы использоваться как универсальное правило. Однако в большинстве случаев его реализация оказывается непрактичной.
Как, например, смоделировать передачу операции еще не вычисленных операндов? Это потребует выполнения значительного объе- 346 Глава 8. Управление последовательностью действий ма программного моделирования. Зачастую такой подход к вычислению выражений используется в интерпретируемых языках типа 1 1БР и Рго1ой, но для языков численных расчетов, например для С и РОСТКАХ, использование ленивого правила будет связано с непомерно высокими издержками. Два предложенных выше унифицированных правила вычислений — активное и ленивое — соответствуют двум распространенным методам передачи параметров в подпрограммы: по значению и по имени соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
