Лекции по конструированию компиляторов. В.А. Серебряков (1134687), страница 21

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 21)

Приведенные соображения реализуются следующей атрибутной схемой:

RULE
Expr ::= IntExpr
SEMANTICS
Code<0>=Code<1>; Left<1>=true.
RULE
IntExpr ::= IntExpr Op IntExpr
SEMANTICS
Left<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>
+ "," + Label<3>
: Code<3> + Code<1> + Code<2> +
Label<1> + "," + Label<3>
: (Label<3> < Label<1>)
? Code<1> + Code<3> + Code<2> +
Label<1> + "," + Label<3> +
"MOVE" + Label<3> + "," +
Label<1>

: //Label<3>==Label<1>
Code<3> + "MOVE" + Label<3> +
"," + Label<3>+1 + Code<1> +
Code<2> + Label<1> + "," +
Label<1>+1.

RULE
IntExpr ::= Ident
SEMANTICS
Label<0>=(Left<0>) ? 0 : 1;
Code<0>=(Left<0>) ? Val<1>
: "LOAD" + Val<1> + "R1".

RULE
Op ::= '+'
SEMANTICS
Code<0>="ADD".

RULE
Op ::= '-'
SEMANTICS
Code<0>="SUB".

RULE
Op ::= '*'
SEMANTICS
Code<0>="MUL".

RULE
Op ::= '/'
SEMANTICS
Code<0>="DIV".

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

Для выражения A*B+C*(D+E) будет сгенерирован следующий код:

LOAD E,R1 - загрузить E на 1 регистр
ADD D,R1 - сложить D и E и результат заслать в 1
регистр
MUL C,R1 - умножить C на D+E с результатом в 1
регистре
MOVE R1,R2 - переслать результат в регистр R2
LOAD B,R1- загрузить B в 1 регистр
MUL A,R1 - умножить A на B с результатом в 1 регистре
ADD R1,R2 - сложить A*B и C*(D+E) и результат заслать
во регистр

В приведенных атрибутных схемах предполагалось, что регистров достаточно, чтобы правильно странслировать любое выражение. Если это не так, приходится усложнять схему трансляции и при необходимости сбрасывать содержимое регистров в память (или магазин).

8.7. Трансляция логических выражений

Логические выражения, включающие логическое умножение, логическое сложение и отрицание, можно вычислять как непосредственно, используя таблицы истинности, так и с помощью условных выражений, пользуясь очевидными правилами:

A AND B эквивалентно if A then B else False,

A OR B эквивалентно if A then True else B.

Если в качестве компонент выражений могут входить функции с побочным эффектом, то, вообще говоря, результат вычисления может зависеть от способа вычисления. В некоторых языках программирования не оговаривается, каким способом должны вычисляться логические выражения (например, в Паскале), в некоторых требуется, чтобы вычисления производились тем или иным способом (например, в Модуле-2 требуется, чтобы выражения вычислялись по приведенным формулам), в некоторых языках есть возможность явно задать способ вычисления (Си, Ада). Вычисление логических выражений непосредственно по таблицам истинности аналогично вычислению арифметических выражений, поэтому мы не будем их рассматривать отдельно. Рассмотрим подробнее способ вычисления с помощью приведенных выше формул (будем называть его "вычисления с условными переходами"). Иногда такой способ рассматривают как оптимизацию вычисления логических выражений.

Рассмотрим следующую атрибутную грамматику со входным языком логических выражений:

RULE
Expr ::= BoolExpr
SEMANTICS
FalseLab<1>=False; TrueLab<1>=True;
Code<0>=Code<1>.

RULE
BoolExpr ::= BoolExpr 'AND' BoolExpr
SEMANTICS
FalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;
FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;
Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.

RULE
BoolExpr ::= BoolExpr 'OR' BoolExpr
SEMANTICS
TrueLab<1>=TrueLab<0>; FalseLab<1>=NodeLab<3>;
FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;
Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.

RULE
BoolExpr ::= F
SEMANTICS
Code<0>=“GOTO FalseLab<0>“.

RULE
BoolExpr ::= T
SEMANTICS
Code<0>=“GOTO TrueLab<0>“.

Здесь предполагается, что все вершины дерева занумерованы и номер вершины дает атрибут NodeLab. Метки вершин передаются, как это изображено на рис. 8.20.

TrueLab FalseLab
FalseLab TrueLab





FalseLab TrueLab TrueLab FalseLab
FalseLab TrueLab
TrueLab NodeLabel FalseLab NodeLabel
AND OR
Рис. 8.20.

Сопоставим каждому атрибутированному дереву в этой атрибутной грамматике текст (трансляцию), полученный следующим образом в результате обхода дерева сверху вниз слева направо: при входе в вершину будем генерировать ее номер, в вершине F будем генерировать текст GOTO значение атрибута FalseLab<0>, в вершине T - GOTO значение атрибута TrueLab<0>. Например, для выражения F OR ( F AND T AND T ) OR T получим атрибутированное дерево и трансляцию, изображенные на рис. 8.21 и 8.22.:

F OR ( F AND T AND T ) OR T
| FalseLab=False
1 TrueLab=True

TrueLab=True OR
FalseLab=2 FalseLab=False
F 2 TrueLab=True

TrueLab=True OR
FalseLab=3

4 3
|
TrueLab=5 AND T
FalseLab=3 TrueLab=True
FalseLab=3
F 5

TrueLab=6 AND 1: GOTO 2
FalseLab=3 TrueLab=True 2:
FalseLab=3 4: GOTO 3
T 6 5: GOTO 6
| 6: GOTO True
T 3: GOTO True

Рис. 8.21 Рис. 8.22

Эту линеаризованную запись можно трактовать как программу вычисления логического значения: каждая строка может быть помечена номером вершины и содержать либо переход на другую строку, либо переход на True или False, что соответствует значению выражения true или false, либо пусто. Будем говорить, что полученная программа вычисляет (или интерпретирует) значение выражения, если в результате ее выполнения (от первой строки) мы придем к строке, содержащей GOTO True или GOTO False.

Утверждение 1. Для любого логического выражения, состоящего из констант, программа, полученная в результате обхода дерева этого выражения, завершается со значением логического выражения в обычной интерпретации, т.е. осуществляется переход на True для значения, равного true, и переход на метку False для значения false.

Это утверждение является частным случаем следующего.

Утверждение 2. В результате интерпретации поддерева с некоторыми значениями атрибутов FalseLab и TrueLab в его корне выполняется команда GOTO TrueLab, если значение выражения истинно, и команда GOTO FalseLab, если значение выражения ложно.

Доказательство можно провести индукцией по высоте дерева. Для деревьев высоты 1, соответствующих правилам BoolExpr ::= F и BoolExpr ::= T, утверждение очевидно из правил грамматики. Пусть дерево имеет высоту n>1. Зависимость атрибутов для дизъюнкции и конъюнкции приведена на рис. 8.23

FalseLab0
TrueLab0

AND
FalseLab1=FalseLab0 FalseLab2=FalseLab0
TrueLab1=NodeLab2 TrueLab2=TruLab0

FalseLab0
TrueLab0

OR
FalseLab1=NodeLab2 FalseLab2=FalseLab0
TrueLab1=TruLab0 TrueLab2=TruLab0




Рис. 8.23

Если для конъюнкции значение левого поддерева ложно и по индукции вычисление левого поддерева завершается командой GOTO FalseLab1, то и интерпретация всего дерева завершается командой GOTO FalseLab0 (=FalseLab1). Если значение левого поддерева истинно, то его интерпретация завершается командой GOTO TrueLab1 (=NodeLab2). Если значение правого поддерева ложно, то интерпретация всего дерева завершается командой GOTO FalseLab0 (=FalseLab2). Если же оно истинно, интерпретация всего дерева завершается командой GOTO TrueLab0 (=TrueLab2). Аналогично - для дизъюнкции.

Доказательство утверждения 1 следует из того, что метками вершины дерева логического выражения являются TrueLab=True и FalseLab=False.

Добавим теперь новое правило в предыдущую грамматику:

RULE
BoolExpr ::= Ident
SEMANTICS
Code<0>=”if (Val<1>==T)GOTO TrueLab<0>
else GOTO FalseLab<0>”;

Тогда, например, для предыдущего выражения получим следующую программу:

1: if (F==T) then GOTO True else GOTO 2
2:
4: if (F==T) GOTO 5 else GOTO 3
5: if (T==T) GOTO 6 else GOTO 3
6: if (T==T) GOTO True else GOTO 3
3: if (T==T) GOTO True else GOTO False

При каждом конкретном наборе данных эта программа превращается в программу вычисления логического значения.

Утверждение 3. В каждой строке программы, сформированной предыдущей атрибутной схемой, одна из меток совпадает с меткой следующей строки.

Характеристики

Список файлов лекций