Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.289

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

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

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

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

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

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

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

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

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

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

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

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

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

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