Э. Таненбаум - Архитектура компьютера (1127755), страница 102
Текст из файла (страница 102)
Предположим, что формула состоит из переменных, двухоперандных операторов +, —, *, /, а также левой и правой скобок. Чтобы отметить конец формулы, мы будем вставлять символ после ее последнего символа и перед первым символом следующей формулы. На рис. 5.15 схематично показана железная дорога из Нью-Йорка в Калифорнию с ответвлением, ведущим в Техас. Каждый символ формулы представлен одним вагоном. Поезд движется на запад (налево). Перед стрелкой каждый вагон должен останавливаться и узнавать, должен ли он двигаться прямо в Калифорнию, или ему нужно по пути заехать в Техас.
Вагоны, содержащие переменные, всегда направляются в Калифорнию и никогда не едут в Техас. Вагоны, содержащие все прочие символы, должны перед прохождением стрелки узнавать о содержимом ближайшего вагона, отправившегося в Техас. В таблице на рис. 5.16 показана зависимость ситуации от того, какой вагон отправился в Техас последним и какой вагон находится у стрелки. Первый вагон (помеченный символом 1) всегда отправляется в Техас. 41 О Глава 5. Уровень архитектуры набора команд А х ( В + С ) Калифорния Нью-Йорк епезнодорожная стрелка Д Рис. 6.15.
Каждый вагон представляет собой один символ в формуле, которую нужно переделать из инфиксной формы в постфиксную Числа соответствуют следующим ситуациям: К Вагон на стрелке направляется в Техас. 2. Последний вагон, направившийся в Техас, разворачивается и направляется в Калифорнию. 3. Вагон, находящийся на стрелке, и последний вагон, отправившийся в Техас, угоняются и исчезают (то есть, оба удаляются). 4. Остановка. Символы, находящиеся на калифорнийской ветке, представляют собой формулу в обратной польской записи, если читать слева направо.
5. Остановка. Произошла ошибка. Изначальная формула была некорректно сбалансирована. Ваюн на развилке + Р х l ( ) в Я в» Е~, + Ф о Явф~ Р в с Ф х он х в Л с 3 Рис. 5.1б. Алгоритм преобразования инфиксной записи в постфиксную После каждого действия производится новое сравнение вагона, находящегося у стрелки (это может быть тот же вагон, что и в предыдущем сравнении, а может Адресация 41 1 быть следующий вагон), и вагона, который на данный момент последним ушел на Техас. Этот процесс продолжается до тех пор, пока не будет достигнут шаг 4. Отметим, что линия на Техас используется как стек, где отправка вагона в Техас — это помещение элемента в стек, а разворот отправленного в Техас вагона в сторону Калифорнии — это выталкивание элемента из стека.
Порядок следования переменных в инфиксной и постфиксной записи одинаков. Однако порядок следования операторов не всегда один и тот же. В обратной польской записи операторы появляются в том порядке, в котором они будут выполняться. В табл. 5.5 даны примеры инфиксных формул и их эквивалентов в обратной польской записи. Таблица В.б. Некоторые примеры инфиксных выражений и ик эквиваленты в обратной польской записи Обратная польская запись Инфиксная запись Вычисление формул в обратной польской записи Обратная польская запись идеально подходит для вычисления формул на компьютере со стеком. Формула состоит из и символов, каждый из которых является либо операндом, либо оператором. Алгоритм для вычисления формулы в обратной польской записи с использованием стека прост.
Нужно просто прочитать обратную польскую запись слева направо. Если встречается операнд, его нужно поместить в стек. Если встречается оператор, нужно выполнить заданную им операцию. Таблица 5.6 иллюстрирует вычисление машиной 1)Ъ'М следующего выражения: (8 ь 2 х 5) / (1 + 3 х 2 — 4), Соответствующая формула в обратной польской записи выглядит так: 8 2 5 х + 1 3 2 х + 4 —,(, В таблице мы ввели команды умножения и деления 1М0(. и 101Ч. Число на вершине стека — это правый операнд (а не левый). Это очень важно для операций деления и вычитания, поскольку порядок следования операндов в данном случае имеет значение (в отличие от операций сложения и умножения). Другими словами, команда 101Ч действует следующим образом: сначала в стек помещается числитель, потом знаменатель, и тогда операция дает правильный результат.
Отметим, что преобразовать обратную польскую запись в 1) "т'М-код очень легко: нужно просто двигаться по формуле в обратной польской записи, записывая по А+ Вхс Ах В+С АхВ+С 0 (А+ В)1(С вЂ” О) Ах В/С ((А+ В) х С + 0)у(Е+ Е+ В) АВСх+ АВхС+ АВхСОх+ АВ+С0 — У А В х С! АВ+Схо+ЕЕ+В+/ 412 Глава 5. Уровень архитектуры набора команд одной команде для каждого символа. Если символ является константой или пе- ременной, нужно вписывать команду помещения этой константы или перемен- ной в стек, если символ является оператором, нужно вписывать команду для вы- полнения данной операции.
Таблица 6.6. Использование стека для вычисления формулы в обратной польской записи Швг Оставшаяся цепочка Команда Стек 1 825х+132х+4 †/ 2 25х+132х+4 †/ 3 5х+132х+4 †! 4 х+132х+4 †! 5 +132х+4 †/ 5 132х+4 †! 7 32х+4 †/ 8 2х+4 †/ 9 х+4 †/ 1О +4 — ! 11 4 — / 12 — ! 13 / В!РОВН 8 В!РОЗН 2 В!РОВН 5 8,2 8,2,5 !М01. 8, 10 !А00 18 В!РОВН 1 В!РОВН 3 В!РОВН 2 18, 1 18, 1, 3 18, 1, 3, 2 18, 1, 8 !МО!.
!А00 18, 7 В!РОВН 4 18, 7, 4 18, 3 !ВОВ ГО!Н Режимы адресации в командах перехода До сих пор мы рассматривали только те команды, которые оперируют данными. Командам перехода (а также командам вызова процедур) также нужны особые режимы адресации для определения целевого адреса. Режимы адресации, о которых мы говорили в предыдущих подразделах, применимы и к большинству команд перехода.
Один из возможных режимов — прямая адресация, когда целевой адрес просто полностью включается в команду. Другие режимы адресации тоже имеют смысл. Косвенная регистровая адресация позволяет программе вычислить целевой адрес, поместить его в регистр, а затем перейти по полученному адресу. Такой способ дает максимальную гибкость, поскольку целевой адрес вычисляется во время выполнения программы. Но он также оставляет лазейку для бессчетного числа трудно обнаруживаемых ошибок. Индексная адресация, при которой известно смещение от регистра, также является вполне приемлемой.
Этот режим обладает теми же характеристиками, что и косвенная регистровая адресация. Еще один режим — относительная адресация по счетчику команд. В данном случае для получения целевого адреса смещение (со знаком), находящееся в самой команде, прибавляется к счетчику команд. По сути, это индексная адресация, где в качестве регистра используется счетчик команд. Адресация 41 Э Ортогональность кодов операций и режимов адресации С точки зрения программного обеспечения команды и режимы адресации должны иметь регулярную структуру с минимальным числом форматов команд.
При такой структуре компилятору гораздо проще порождать нужный код. Все коды операций должны поддерживать любые режимы адресации, если это имеет смысл. Более того, для всех регистровых режимов должны быть доступны все регистры, включая указатель фрейма (РР), указатель стека (ЯР) и счетчик команд (РС). Рассмотрим форматы 32-разрядных команд для трехадресной машины (рис.
5.17). Здесь поддерживаются до 256 кодов операций. В варианте 1 формата каждая команда имеет два входных регистра (источника) и один выходной регистр (приемник). Этот формат используется для всех арифметических и логических команд. Биты В 1 З з б Выходной Входной Входной регистр регистр 2 регистр 1 Код операции Код операции 1 ыхолной ходной регистр регистр 1 Смещение 3 Код операции Смещение Рис. 6.1 г.
Форматы команд дпя трехадресной машины Неиспользованное 8-разрядное поле в конце команды может потребоваться для дальнейшей дифференциации команд. Например, можно иметь один код для всех операций с плавающей точкой, а различаться зти операции будут по дополнительному полю. Кроме того, если установлен бит 23, тогда задействуется вариант 2 формата, а второй операнд уже является не регистром, а 13-разрядной непосредственной константой со знаком.
Команды ЕОАО и 5ТОйЕ тоже могут использовать зтот формат для обращения к памяти при индексном способе адресации. Необходимо также иметь небольшое число дополнительных команд (например, команд условных переходов), но они легко подходят под вариант 3 формата. Например, можно приписать один код операции каждому (условному) переходу, вызову процедуры и т. д., тогда останется 24 бита для смещения по счетчику команд. Если предположить, что это смещение считается в словах, диапазон будет составлять 32 Мбайт. Несколько кодов операций можно зарезервировать для команд ЕОАО и 5ТОкЕ, которым нужны длинные смещения в варианте 3 формата.
Теперь рассмотрим структуру двухадресной машины, в которой в качестве любого операнда может использоваться слово из памяти (рис. 5.18). Такая 414 Глава б. Уровень архитектуры набора команд машина умеет складывать слово памяти с регистром, регистр со словом памяти, два регистра и два слова памяти. В настоящее время обращение к памяти связано со значительными издержками, поэтому такая структура не очень распространена, но если с развитием технологий обрагцаться к памяти станет менее накладно, получится простое и эффективное решение. Машины РОР-11 и НАХ, в которых использовались похожие форматы, были очень популярны и доминировали на рынке мини-компьютеров в течение двух десятилетий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
