В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 34
Текст из файла (страница 34)
Генерация кода: Val<1>.RULEIntExpr ::= ’(’ IntExpr ’)’SEMANTICSLabel<0>=Label<2>;Reg<2>=Reg<0>;Code<0>=Code<2>.RULEOp ::= ’+’SEMANTICSCode<0>="ADD".RULEOp ::= ’-’SEMANTICSCode<0>="SUB".RULEOp ::= ’*’SEMANTICSCode<0>="MUL".RULEOp ::= ’/’SEMANTICSCode<0>="DIV".Атрибутированное дерево для выражения A*B+C*(D+E)на рис. 9.9. При этом будет сгенерирован следующий код:MOVEMULMOVEADDMULADDMOVEприведеноB, R1A, R1E, R2D, R2C, R2R1, R2R2, R1Приведенная атрибутная схема требует двух проходов по дереву выражения. Рассмотрим теперь другую атрибутную схему, в которой генерацияпрограммы для выражений с оптимальным распределением регистров требуетлишь одного обхода [9].Пусть мы произвели разметку дерева разбора так же, как и в предыдущем алгоритме.
В качестве регистра результата вычисления поддерева будемназначать регистр с номером, равным метке вершины.9.6. Трансляция арифметических выражений181Рис. 9.9Левому потомку всегда назначается регистр, равный его метке, а правому— его метке, если она не равна метке его левого брата, и метке, увеличеннойна единицу, если метки равны. Поскольку более сложное поддерево всегдавычисляется раньше более простого, его регистр результата имеет большийномер, чем любой регистр, используемый при вычислении более простогоподдерева, что гарантирует правильность использования регистров.Приведенные соображения реализуются следующей атрибутной схемой:RULEExpr ::= IntExprSEMANTICSCode<0>=Code<1>; Left<1>=true.RULEIntExpr ::= IntExpr Op IntExprSEMANTICSLeft<1>=true; Left<3>=false;Label<0>=(Label<1>==Label<3>)? Label<1>+1: Max(Label<1>,Label<3>);Code<0>=(Label<3> > Label<1>)? (Label<1>==0)? Code<3> + Code<2> + Code<1>182Глава 9.
Генерация кода+ ",R" + Label<3>: Code<3> + Code<1> + Code<2> + "R"+Label<1> + ",R" + Label<3>: (Label<3> < Label<1>)? Code<1> + Code<3> + Code<2> + "R"+Label<1> + "," + Label<3> +"MOVE" + Label<3> + ",R" + Label<1>: // метки равныCode<3> + "MOVE R" + Label<3> +",R" + (Label<3>+1) + Code<1> +Code<2> + "R" + Label<1> + ",R" +(Label<1>+1).RULEIntExpr ::= IdentSEMANTICSLabel<0>=(Left<0>) ? 0 : 1;Code<0>=(Left<0>) ? Val<1>: "MOVE" + Val<1> + "R1".RULEIntExpr ::= ’(’ IntExpr ’)’SEMANTICSLabel<0>=Label<2>;Code<0>=Code<2>.RULEOp ::= ’+’SEMANTICSCode<0>="ADD".RULEOp ::= ’-’SEMANTICSCode<0>="SUB".RULEOp ::= ’*’SEMANTICSCode<0>="MUL".RULEOp ::= ’/’SEMANTICSCode<0>="DIV".9.7.
Трансляция логических выражений183Команды пересылки требуются для согласования номеров регистров, в которых выполняется операция, с регистрами, в которых должен быть выданрезультат. Это имеет смысл, когда эти регистры разные. Получиться этоможет из-за того, что по приведенной схеме результат выполнения операциивсегда находится в регистре с номером метки, а метки левого и правогоподдеревьев могут совпадать.Для выражения A*B+C*(D+E) будет сгенерирован следующий код:MOVE E, R1ADDMULMOVEMOVEMULADDD, R1C, R1R1, R2B, R1A, R1R1, R2В приведенных атрибутных схемах предполагалось, что регистров достаточно для трансляции любого выражения. Если это не так, то приходитсяусложнять схему трансляции и при необходимости сбрасывать содержимоерегистров в память (или магазин).Реализация этой атрибутной схемы приведена в программном приложениив пакете ToyLang.9.7.
Трансляция логических выраженийЛогические выражения, включающие логическое умножение, логическоесложение и отрицание, можно вычислять как непосредственно, используятаблицы истинности, так и с помощью условных выражений, основанных наследующих простых правилах:A AND BA OR Bэквивалентноэквивалентноif A then B else False,if A then True else B.Если в выражение могут входить функции с побочным эффектом, то,вообще говоря, результат вычисления зависит от способа вычисления. В некоторых языках программирования не оговаривается, каким способом должнывычисляться логические выражения (например, в Паскале); в некоторых требуется, чтобы вычисления производились конкретным способом (например,в Модуле-2 требуется, чтобы выражения вычислялись по приведенным формулам); в некоторых языках есть возможность явно задать способ вычисления(Си, Ада).
Вычисление логических выражений непосредственно по таблицамистинности аналогично вычислению арифметических выражений, поэтому мыне будем их рассматривать отдельно. Рассмотрим подробнее способ вычисления с помощью приведенных выше формул (будем называть его вычислением184Глава 9. Генерация кодас условными переходами). Иногда такой способ рассматривают как оптимизацию вычисления логических выражений.Рассмотрим следующую атрибутную грамматику со входным языком логических выражений:RULEExpr ::= BoolExprSEMANTICSFalseLab<1>=False; TrueLab<1>=True;Code<0>=Code<1>.RULEBoolExpr ::= BoolExpr ’AND’ BoolExprSEMANTICSFalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= BoolExpr ’OR’ BoolExprSEMANTICSFalseLab<1>=NodeLab<3>; TrueLab<1>=TrueLab<0>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= FSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + FalseLab<0>.RULEBoolExpr ::= TSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + TrueLab<0>.Здесь предполагается, что все вершины дерева занумерованы и номер вершины дает атрибут NodeLab.
Метки вершин передаются, как это изображенона рис. 9.10.Рис. 9.109.7. Трансляция логических выражений185Таким образом, каждому атрибутированному дереву в этой атрибутной грамматике сопоставляется код, полученный в результате обхода дерева сверху-вниз слева-направо следующим образом. При входе в вершинуBoolExpr генерируется ее номер, в вершине F генерируется текст GOTOзначение атрибута FalseLab<0>, в вершине T — GOTO значение атрибутаTrueLab<0>.
Например, для выраженияF OR ( F AND T AND T ) OR Tполучим атрибутированное дерево, изображенное на рис. 9.11, и кодРис. 9.111:7:GOTO2:8:4:9: GOTO5:10:GOTO6:GOTO3:GOTOTrue: ...False: ...236TrueTrueЭту линеаризованную запись можно трактовать как программу вычисления логического значения: каждая строка может быть помечена номеромвершины и содержать либо переход на другую строку, либо переход на Trueили False, что соответствует значению выражения true или false. Будем186Глава 9. Генерация кодаговорить, что полученная программа вычисляет (или интерпретирует)значение выражения, если в результате ее выполнения (от первой строки)мы придем к строке, содержащей GOTO True или GOTO False.Утверждение 9.1.
В результате интерпретации поддерева с некоторыми значениями атрибутов FalseLab и TrueLab в его корне выполняетсякоманда GOTO TrueLab, если значение выражения истинно, или командаGOTO FalseLab, если значение выражения ложно.Д о к а з а т е л ь с т в о . Применим индукцию по высоте дерева. Для деревьев высоты 1, соответствующих правиламBoolExpr ::= F, BoolExpr ::= T,справедливость утверждения следует из соответствующих атрибутных правил. Пусть дерево имеет высоту n > 1. Зависимость атрибутов для дизъюнкции и конъюнкции приведена на рис.
9.12.Рис. 9.12Если для конъюнкции значение левого поддерева ложно и по индукции вычисление левого поддерева завершается командой GOTO FalseLab<1>,то получаем, что вычисление всего дерева завершается командой переходаGOTO FalseLab<0> (= FalseLab<1>). Если же значение левого поддерева истинно, то его вычисление завершается командой перехода GOTO TrueLab<1>(= NodeLab<3>). Если значение правого поддерева ложно, то вычисление всего дерева завершается командой GOTO FalseLab<0> (= FalseLab<3>). Еслиже оно истинно, вычисление всего дерева завершается командой переходаGOTO TrueLab<0> (= TrueLab<3>). Аналогично — для дизъюнкции.Утверждение 9.2.
Для любого логического выражения, состоящегоиз констант, программа, полученная в результате обхода дерева этого9.7. Трансляция логических выражений187выражения, завершается со значением логического выражения в обычнойинтерпретации, т. е. осуществляется переход на True для значения, равного true, и переход на метку False для значения false.Д о к а з а т е л ь с т в о . Это утверждение является частным случаемпредыдущего.
Его справедливость следует из того, что метки корня дереваравны соответственно TrueLab = True и FalseLab = False.Добавим теперь новое правило в предыдущую грамматику:RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" + "if (" + Val<1> + ")GOTO"+ TrueLab<0> + "else GOTO" + FalseLab<0>.Тогда, например, для выражения A OR (B AND C AND D) OR E получимследующую программу:1:7:if (A) GOTO True else GOTO 22:8:4:9: if (B) GOTO 5 else GOTO 35:10:if (C) GOTO 6 else GOTO 36:if (D) GOTO True else GOTO 33:if (E) GOTO True else GOTO FalseTrue: ...False: ...При каждом конкретном наборе данных эта программа превращаетсяв программу вычисления логического значения.Утверждение 9.3.
В каждой строке программы, сформированнойпредыдущей атрибутной схемой, одна из меток внутри условногооператора совпадает с меткой следующей строки.Д о к а з а т е л ь с т в о . Действительно, по правилам наследования атрибутов TrueLab и FalseLab, в правилах для дизъюнкции и конъюнкциилибо атрибут FalseLab, либо атрибут TrueLab принимает значение меткиследующего поддерева. Кроме того, как значение FalseLab, так и значениеTrueLab, передаются в правое поддерево от предка. Таким образом, самыйправый потомок всегда имеет одну из меток TrueLab или FalseLab, равнуюметке правого брата соответствующего поддерева. Учитывая порядок генерации команд, получаем справедливость утверждения.Дополним теперь атрибутную грамматику следующим образом:RULEExpr ::= BoolExprSEMANTICSFalseLab<1>=False; TrueLab<1>=True;Sign<1>=false;188Глава 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
