Реклама:

Мы уже отмечали, что очень желательно сделать машинные команды как можно короче. Предельный случай - команды без адресов. Как мы видели в главе 4, безадресные команды, например 1А00, возможны при наличии стека. В этом подразделе мы рассмотрим стековую адресацию более подробно.

Обратная польская запись

В математике существует древняя традиция помещать оператор между операндами (х + г/), а не после операндов (х у +). Форма с оператором между операндами называется инфиксной записью. Форма с оператором после операндов называется постфиксной, или обратной польской записью в честь польского логика Я. Лукасевича (1958), который изучал свойства этой записи.

Обратная польская запись имеет ряд преимуществ перед инфиксной записью при выражении алгебраических формул. Во-первых, любая формула может быть выражена без скобок. Во-вторых, она удобна для вычисления формул в машинах со стеками. В-третьих, инфиксные операторы имеют приоритеты, которые произвольны и нежелательны. Например, мы знаем, что а Ь + с значит (а Ь) + с, а не а (Ь + с), поскольку произвольно было определено, что умножение имеет приоритет над сложением. Но имеет ли приоритет сдвиг влево над логической операцией И? Кто знает? Обратная польская запись позволяет устранить такие недоразумения.

Существует несколько алгоритмов для превращения инфиксных формул в обратную польскую запись. Мы рассмотрим переработанный алгоритм, идея которого предложена Э. Дейкстра (Е. \\Л Букз^а). Предположим, что формула состоит из переменных, двухоперандных операторов +, -, *, /, а также левой и правой скобок. Чтобы отметить конец формулы, мы будем вставлять символ после ее последнего символа и перед первым символом следующей формулы.

На рис. 5.15 схематично показана железная дорога из Нью-Йорка в Калифорнию с ответвлением, ведущим в Техас. Каждый символ формулы представлен одним вагоном. Поезд движется на запад (налево). Перед стрелкой каждый вагон должен останавливаться и узнавать, должен ли он двигаться прямо в Калифорнию, или ему нужно по пути заехать в Техас. Вагоны, содержащие переменные, всегда направляются в Калифорнию и никогда не едут в Техас. Вагоны, содержащие все прочие символы, должны перед прохождением стрелки узнавать о содержимом ближайшего вагона, отправившегося в Техас.

В таблице на рис. 5.16 показана зависимость ситуации от того, какой вагон отправился в Техас последним и какой вагон находится у стрелки. Первый вагон (помеченный символом _1_) всегда отправляется в Техас.

Стековая адресация

Рис. 5.15. Каждый вагон представляет собой один символ в формуле, которую нужно переделать из инфиксной формы в постфиксную

Числа соответствуют следующим ситуациям:

1. Вагон на стрелке направляется в Техас.

2. Последний вагон, направившийся в Техас, разворачивается и направляется в Калифорнию.

3. Вагон, находящийся на стрелке, и последний вагон, отправившийся в Техас, угоняются и исчезают (то есть, оба удаляются).

4. Остановка. Символы, находящиеся на калифорнийской ветке, представляют собой формулу в обратной польской записи, если читать слева направо.

5. Остановка. Произошла ошибка. Изначальная формула была некорректно сбалансирована.

Стековая адресация

Рис. 5.16. Алгоритм преобразования инфиксной записи в постфиксную

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

Порядок следования переменных в инфиксной и постфиксной записи одинаков. Однако порядок следования операторов не всегда один и тот же. В обратной польской записи операторы появляются в том порядке, в котором они будут выполняться. В табл. 5.5 даны примеры инфиксных формул и их эквивалентов в обратной польской записи.

Таблица 5.5. Некоторые примеры инфиксных выражений и их эквиваленты в обратной польской записи

Инфиксная запись Обратная польская запись

А+ВхС А В С х +

АхВ+С АВхС+

AxB+CD ABxCDx+

(А + В)/(С -D) А В + С D - /

А х В/С А В х С /

((А + В) х С + D)/(E + F + G) AB + CxD + EF + G + /

Вычисление формул в обратной польской записи

Обратная польская запись идеально подходит для вычисления формул на компьютере со стеком. Формула состоит из п символов, каждый из которых является либо операндом, либо оператором. Алгоритм для вычисления формулы в обратной польской записи с использованием стека прост. Нужно просто прочитать обратную польскую запись слева направо. Если встречается операнд, его нужно поместить в стек. Если встречается оператор, нужно выполнить заданную им операцию.

Таблица 5.6 иллюстрирует вычисление машиной ЦУМ следующего выражения:

(8 + 2 х 5) / (1 + 3 х 2 - 4).

Соответствующая формула в обратной польской записи выглядит так:

825х+132х + 4-/.

В таблице мы ввели команды умножения и деления 1М111_ и Ю1\/. Число на вершине стека - это правый операнд (а не левый). Это очень важно для операций деления и вычитания, поскольку порядок следования операндов в данном случае имеет значение (в отличие от операций сложения и умножения). Другими словами, команда Ю1\/ действует следующим образом: сначала в стек помещается числитель, потом знаменатель, и тогда операция дает правильный результат. Отметим, что преобразовать обратную польскую запись в У УМ-код очень легко: нужно просто двигаться по формуле в обратной польской записи, записывая по одной команде для каждого символа. Если символ является константой или переменной, нужно вписывать команду помещения этой константы или переменной в стек, если символ является оператором, нужно вписывать команду для выполнения данной операции.

Таблица 5.6. Использование стека для вычисления формулы в обратной польской записи

Стековая адресация

Относительная индексная адресация || Оглавление || Режимы адресации в командах перехода