Обход статического дерева даёт обратную Польскую запись выражения. Однако в языках типа АЛГОЛ-60 имеются условные выражения с динамически изменяемым порядком действий. Условное выражение можно изобразить динамическим деревом. Обход динамического дерева даёт обратную Польскую запись условного выражения.
Для изображения динамических деревьев введём метки, которыми могут помечаться листья и некоторые узлы динамических деревьев. Введём также две операции:
условный переход по значению «ложь» (УПЛ);
безусловный переход (БП).
Операция УПЛ имеет два операнда: первый — логическое выражение, а второй -метка. Если логическое выражение истинно, то операция УПЛ пропускается, а если ложно, то происходит переход на метку. Ветвь динамического дерева с узлом УПЛ показана на рисунке 1. В АЛГОЛЕ-60 такую конструкцию называют условием.
В операции БП имеется лишь один операнд - метка (рис.2). Результат операции БП -переход на метку.
В деревьях, изображающих простые и арифметические и логические выражения, которые рассматривались до сих пор, каждый узел соответствовал некоторой арифметической или логической операции, а каждая ветвь — операнду. Число ветвей, исходящих из узла, было равно числу операндов операции, изображаемой узлом. Это обеспечивало наглядность графического изображения выражений. Чтобы сохранить принцип соответствия числа ветвей числу операндов, в динамических деревьях приходится вводить пустые узлы. Такому узлу не соответствует никакая операция а количество исходящих из него ветвей произвольно.
При изображении условных выражений пустой узел отвечает разветвлением вычислительного процесса. Разветвление - есть выбор в ходе вычислений одной из нескольких альтернатив, например выбор одного нескольких возможных значений операнда.
Рисунок 1 Графическое изображение операции УСЛОВНЫЙ ПЕРЕХОД ПО ЗНАЧЕНИЮ ЛОЖЬ.
Рисунок 2 Графическое изображение операции БЕЗУСЛОВНЫЙ ПЕРЕХОД.
В дальнейшем пустые узлы будут использоваться также для объединения нескольких последовательно выполняемых действий.
Используя операции УПЛ и БП, арифметическое АЛГОЛА-60 y+( if a > b then x+1 else 2) (1)
можно изобразить деревом, показанным на рис.3. Обход этого дерева даёт следующую обратную Польскую запись.
Здесь стрелками показаны возможные переходы.
Такая запись пригодна для вычисления условного выражения путём интерпретации. Однако для транслятора компилирующего типа она неудобна, поскольку в записи не указана явно переменная, которой присваивается значение условного выражения. Это затрудняет компиляцию машинных команд.
Рисунок 3 Дерево для интерпретации условного выражения.
Для компилятора удобно иметь обратную польскую запись, в которой явно фигурирует переменная (одна и та же для всех ветвей), получающая значение условного выражения х+1 и2 в исходной записи (1)операторами присваивания
rl:=x+l br:=2.
Тогда получается дерево, изображенное на рис.4 ,а обратная польская запись получается в виде
у a b > m1 УПЛ r1 x1 + := m2 БП m1 : r12 := + (3)
Изменения в обратную польскую запись вносит алгоритм перевода пи обработке символов then и else
Запись (3) легко транслирует в машинные команды. Процесс трансляции показан в таблице 1. Трансляция выполняется подпрограммами отдельных операций.
Рисунок 4 Дерево для компиляции условного выражения
Рисунок 5 Дерево для компиляции условного выражения, содержащего условное булево выражение.
Действия, программируемые каждой подпрограммой, указаны в таблице. Генерируемые машинные команды не приводятся, поскольку они не зависят от конкретной машины. Пояснений требует лишь подпрограмма операции БП, которая помимо формирования команды безусловного перехода на метку, являющуюся её операндом, удаляет из обрабатываемой строки операнд, предшествующий этой метке, и уничтожает тем самым в обрабатываемой строке «след» первой ветви условного выражения.
Таблица 1 Перевод условного выражения в машинные команды
| № | Обрабатываемая часть | Программируемые и дополнительные действия | Имя подпрограммы |
| 1 | Yab> | R(l):=a>b | > |
| 2 | Уг(1)т(1)УПЛ | Ifr(l)thengotom(l) Здесь возможна оптимизация путём объединения формируемой команды с предыдущей, Удаление из строки г( 1) | УПЛ |
| 3 | Yr(l)x 1 + | R^-x+l | + |
| 4 | Yr(l)r(2):= | R(l):=r(2) | •= |
| 5 | Уг(1)т(2)БП | Возможна оптимизация путём объединения с предыдущей командой | БП |
| 6 | Ym(l): | Go to m(2) Удаляется идентификатор г( 1) | '• |
| 7 | Yr(l)2:= | Занесение адреса метки т(1) в таблицу меток и удаление из строки т(1): | * |
| 8 | Y r(l)m(l): | R(1):=2 | . |
| 9 | Yr(l)+ | Занесение адреса метки т(2) в таблицу меток и удаление из строки т(2): | + |
| 10 | R(1) | Трансляция закончена |
|
Заметим, что при переводе в машинные команды операнды операций управления УПЛ и БП удаляются из обрабатываемой строки. Этим отличается их обработка от обработки арифметических и логических операций, а также операций присваивания, а так же операций присваивания, которые оставляют в обрабатываемой строке имя(адрес) рабочей переменной, содержащей результат.
Операция «:»заносит в таблицу меток адрес очередной машинной команды, которая будет формироваться в объектной программе, а её операнд (метка) удаляется из обрабатываемой строки.
Операция УПЛ и БП позволяют строить деревья и, следовательно, получать обратную польскую запись для сколь угодно сложных условных выражений на рис.5 показано дерево, соответствующее выражению
у + (if if а=1 u*w else w*zthen x+1 else x-1) (4)
Рисунок 6 Дерево для компиляции условного выражения, содержащего условное арифметическое выражение.
и пригодное для последующей компиляции объектной программы, а на рис.6 изображено дерево, отвечающее выражению
у+( ifa>b then x+1 else ifa=b then x else x-1) (5)
Это дерево также порождает обратную польскую запись, приспособленную для последующей компиляции.
Читателю предлагается самостоятельно определить упрощения в деревьях для случая, когда предусматривается непосредственная интерпретация обратной польской записи
0 коммент.:
Отправить комментарий