Польская запись

Cтраница 3

Польская запись обходится совсем без скобок, но нам нужно заранее знать число операндов для каждого оператора; это условие часто бывает трудно выполнить, если допускается определение операции пользователем. Кроме того, отсутствие каких-либо указаний о структуре делает чтение сложного выражения в польской записи чрезвычайно трудным. Все префиксные записи имеют то преимущество, что операции с разным числом операндов записываются одинаково. Большие и малые различия обозначений в разных языках еще более усложняют положение. В АПЛ, например, как для примитивных операций, так и для операций, определяемых программистом, используется инфиксная запись, но без иерархии операций и с присоединением справа налево, а не слева направо. В Лиспе применяется только кембриджская польская запись. Во многих языках для основных арифметических, логических операций и операций отношения используется инфиксная запись, для встроенных унарных операций, вроде смены знака и логического not, - польская префиксная запись, и обычная математическая префиксная запись используется для всего остального, включая операции, определяемые программистом, и некоторые встроенные функции, такие, как синус и косинус. В языке Снобол 4 операции отношения изображаются в обычной префиксной записи, но к ним добавляется значительное число новых унарных и бинарных операций в польской префиксной и инфиксной записи соответственно. Как видно, никакого всеобщего соглашения о наилучшей записи выражений в языках программирования не существует. [31]

Эта новая совокупность правил проще не потому, что изменен порядок операций и операндов, а потому, что устранена необходимость в скобках и, следовательно, в тех соглашениях, которые позволяли иногда их опускать. Если в первом случае мы попытаемся игнорировать такие соглашения и потребуем, чтобы все выражения имели полный набор скобок, то грамматика для такой скобочной записи окажется столь же простой, как и для польской записи. [32]

Принципу стековой организации подчинена вся структура центрального процессора и система программирования. Система команд этих машин эквивалентна инверсной бесскобочной польской записи. Если арифметическое выражение записать в этой бесскобочной записи, то для того, чтобы его запрограммировать в системе команд машин Барроуз, достаточно имена операндов заменить на адреса их расположения в памяти, а символы операций - на коды соответствующих команд машины. Таким образом, выражение, развернутое в бесскобочную инверсную запись, по существу, является последовательностью команд для этих машин. [33]

ИНФ ( ОЩВ1 В2)) ( ИНФ ( В1) ОП ИНФ ( В2)) Преобразование состоит в том, чтобы найти знак операции и два операнда, которые образуют выражение. Знак операции вставляется между операндами, и получившееся выражение заключается в скобки. Конечно, операнды еще остаются в польской записи и для преобразования каждого из них требуются рекурсивные обращения к функции ИНФ. [34]

Есть два различных типа калькулятора. Различие между ними состоит в порядке введения операндов и математических операторов. Один из способов ввода называется алгебраической записью, а другой - польской записью. [35]

Он аппаратно выполняет функции перевода конструкций входного языка во внутренний язык машины. Следует отметить, что внутренний язык машины по своей структуре мало чем отличается от входного языка симбол. Основная функция транслятора заключается в том, что все выражения входного языка переводятся в инверсную польскую запись. Как известно, в машине МИР также происходит перевод входного языка в подобный ему внутренний язык машины. В машине МИР этот перевод осуществляется микропрограммами и программами одной мономашины, и процесс этот не совмещен с другими операциями ЭВМ МИР. [36]

Все это совершенно естественно, и было бы заманчиво принять упомянутое однородное правило вычислений. К сожалению, вычислять операнды перед применением операции не всегда правильно. Может возникнуть желание рассматривать такую условную операцию, просто как операцию с необычным синтаксисом и тремя операндами, что изображено на рис. 5.4. На самом деле именно так поступают в Лиспе, где кембриджская польская запись используется для условных операций, равно как и для всех других операций. Но здесь и возникает проблема с однородным правилом вычислений. Если мы вычислим операнды условного оператора IF на рис. 5.4, то в результате мы выполним как раз те действия, во избежание которых использовалась условная операция, а именно поделим V, на X, если X равен нулю. Ясно, что в этом случае мы не хотим, чтобы все операнды вычислялись перед применением операции. Вместо этого операнды операции IF следует передать невычис-ленными ( хотя бы последние два операнда) и предоставить операции определение порядка вычислений. [37]

Транслятор ПЛ / 1 или Бэйсик проверяет синтаксис исходного текста. Он распознает операторы языка и выполняет их обработку с помощью специальных модулей. Определив, что исходный текст ( оператор) не содержит ошибок, транслятор в случае программы на языке Бэйсик формирует макрокод для генерации машинных команд, а в случае языка ПЛ / 1 преобразует исходный текст оператора в инверсную польскую запись. Все протранслированные операторы сцепляются в порядке номеров следования исходных операторов. Результат работы трансляторов вместе с исходным текстом сохраняется в библиотеке абонента при выполнении подкоманды SAVE. Протранслированная программа абонента ( или отдельный оператор) может быть выполнена сразу или позже. Если для выполнения используется ранее сохраненная программа, та ее перетрансляция не выполняется. [38]

Простое выражение ( А В ( С - А в виде дерева. [39]

Нельзя, однако, сказать, что префиксная запись не имеет никакого значения. На самом деле обычная префиксная запись является стандартным математическим обозначением для большинства операций, отличных от бинарных арифметических и логических операций. Что еще важнее, префиксная запись может быть использована для изображения операций с любым числом операндов, и, таким образом, она универсальна: изучив лишь одно синтаксическое правило, мы сможем записать любое выражение. Например, в языке Лисп, где программы являются выражениями, стоит только овладеть кембриджской польской записью для выражений, и мы будем знать большую часть синтаксических правил языка. [40]

При выполнении каких-либо действий с арифметическими выражениями-на ЭВМ часто желательно поручить самой машине распознавать эквивалентность двух выражений. Так как в каждой семантике существует свое понятие эквивалентности, эквивалентность приходится проверять в каждой из них по отдельности. В литеральной семантике задача установления эквивалентности совершенно тривиальна: два выражения эквивалентны тогда и только тогда, когда они совпадают с точностью до литеры. В алгоритмической семантике эта задача также не очень трудна: нужно перевести каждое выражение в польскую запись, а затем сравнить полученные последовательности литеру за литерой. [41]

Страницы: 1 2 3