Delphi World - Лекции по конструированию компиляторов - Часть 11
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Лекции по конструированию компиляторов - Часть 11

Автор: В.А.Серебряков

8.5. Трансляция целых выражений

Трансляция выражений различных типов управляется синтаксически благодаря наличию указателя типа перед каждой операцией. Мы рассмотрим некоторые наиболее характерные проблемы генерации кода для выражений. Система команд МС68020 обладает двумя особенностями, сказывающимися на генерации кода для арифметических выражений (то же можно сказать и о генерации кода для выражений типа "множества"):

1) один из операндов выражения (правый) должен при выполнении операции находиться на регистре, поэтому если оба операнда не на регистрах, то перед выполнением операции один из них надо загрузить на регистр;

2) система команд довольно "симметрична", т.е. нет специальных требований к регистрам при выполнении операций (таких, например, как пары регистров или требования четности и т.д.).

Поэтому выбор команд при генерации арифметических выражений определяется довольно простыми таблицами решений. Например, для целочисленного сложения такая таблица приведена на рис.8.12.

                    Правый операнд А2
                      R          V
           +-----------------------------+
 Левый     |   R | ADD A1,A2 | ADD A2,A1 |
 операнд   |-----+-----------+-----------|
    A1     |   V | ADD A1,A2 | MOVE A1,R |
           |     |           | ADD A2,R  |
           +-----------------------------+

                       Рис. 8.12

Здесь имеется в виду, что R - операнд на регистре, V - операнд - переменная или константа. Такая таблица решений должна также учитывать коммутативность операций. Эта таблица решений реализуется следующим правилом:

RULE
IntExpr ::= 'PLUS' IntExpr IntExpr
SEMANTICS
if (Address<2>.AddrMode<>D)
   and (Address<3>.AddrMode<>D) then
       Address<0>.AddrMode:=D;
       Address<0>.Addreg:=GetFree(RegSet);
       Emit2(MOVE,Address<2>,Address<0>);
       Emit2(ADD,Address<2>,Address<0>);
else if (Address<2>.AddrMode=D) then
        Emit2(ADD,Address<3>,Address<2>);
        Address<0>:=Address<2>);
     else Emit2(ADD,Address<2>,Address<3>);
          Address<0>:=Address<3>);
end  end.

8.6. Распределение регистров при вычислении арифметических выражений

Одной из важнейших задач при генерации кода является распределение регистров. Рассмотрим хорошо известную технику распределения регистров при трансляции арифметических выражений, называемую алгоритмом Сети-Ульмана. Пусть система команд машины имеет неограниченное число универсальных регистров, в которых выполняются арифметические команды. Рассмотрим, как можно сгенерировать код, используя для данного арифметического выражения минимальное число регистров.

                            |
                           / \
                       R1 /\  \
                          --  /\
                          R2 /\ \
                             -- /\
                            Rn /\ \
                               --  \
                                   /\LR
                                 L/\/\R
                                  ----

                            Рис. 8.13

Предположим сначала, что распределение регистров осуществляется по простейшей схеме слева-направо, как изображено на рис. 8.13. Тогда к моменту генерации кода для поддерева LR занято n регистров. Пусть поддерево L требует nl регистров, а поддерево R - nr регистров. Если nl=nr, то при вычислении L будет использовано nl регистров и под результат будет занят n+1-й регистр. Еще nr (=nl) регистров будет использовано при вычислении R. Таким образом, общее число использованных регистров будет равно n+nl+1. Если nl>nr, то при вычислении L будет использовано nl регистров. При вычислении R будет использовано nr=lr

         Рис. 8.14                 Рис. 8.15

2) если вершина имеет прямых потомков с метками l1 и l2, то в качестве метки этой вершины выбираем большее из чисел l1 или l2 либо число l1+1, если l1=l2. Эта разметка позволяет определить, какое из поддеревьев требует большего количества регистров для своего вычисления. Затем осуществляется распределение регистров для результатов операций.

Правила распределения регистров:

1) Корню назначается первый регистр.

2) Если метка левого потомка меньше метки правого, то левому потомку назначается регистр на единицу больший, чем предку, а правому - с тем же номером (сначала вычисляется правое поддерево и его результат помещается в регистр R). Если же метка левого потомка больше или равна метке правого потомка, то наоборот, сначала вычисляется левое поддерево и его результат помещается в регистр R (рис. 8.15). После этого формируется код по следующим правилам.

Правила генерации кода:

1) если вершина - правый лист с меткой 1, то ей соответствует код LOAD X,R, где R - регистр, назначенный этой вершине, а X - адрес переменной, связанной с вершиной (рис. 8.16.б);

2) если вершина внутренняя и ее левый потомок - лист с меткой 0, то ей соответствует код

Код правого поддерева
Op X,R

где снова R - регистр, назначенный этой вершине, X - адрес переменной, связанной с вершиной, а Op - операция, примененная в вершине (рис. 8.16.а);

3) если непосредственные потомки вершины не листья и метка правой вершины больше метки левой, то вершине соответствует код

  Код правого поддерева
  Код левого поддерева
  Op R+1,R

где R - регистр, назначенный внутренней вершине, и операция Op, вообще говоря, не коммутативная (рис. 8.17 б)).

    R                R             R                R
    |                |             |                |
   / \              / \           / \              / \
  /   \R         R /   \        R/   \R+1      R+1/   \R
 X    /\          /\    X       /\   /\          /\   /\
(0)   --          --   (1)      --   --          --   --
    а)               б)            а)               б)

          Рис. 8.16                   Рис. 8.17

Если метка правой вершины меньше или равна метке левой вершины, то вершине соответствует код

  Код левого поддерева
  Код правого поддерева
  Op R,R+1
  MOVE R+1,R

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

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

RULE
Expr ::= IntExpr
SEMANTICS
Reg<1>:=1; Left<1>:=true.

RULE
IntExpr ::= Term AddOp IntExpr
SEMANTICS
Left<1>:=true; Left<3>:=false;
Label<0>:=if Label<1>=Label<3>
          then Label<1>+1
          else Max(Label<1>,Label<3>);
Reg<1>:=if Label<1> < Label<3>
            then Reg<0>+1
            else Reg<0>;
Reg<3>:=if Label<1> < Label<3>
            then Reg<0>
            else Reg<0>+1;
Code<0>:=if Label<1>=0
        then Code<3>||Code<2>
             ||Code<3>||","||Reg<0>
        else if Label<1> < Label<3>
        then Code<3>||Code<1>||Code<2>||
             Reg<0>+1||","||
             Reg<0>
        else Code<1>||Code<3>||Code<2>||
             Reg<0>||","||Reg<0>+1
             ||"MOVE"||Reg<0>+1
             ||","||Reg<0>.
IntExpr ::= Term =>
              Left<1>:=Left<0>; Code<0>:=Code<1>;
              Label<0>:=Label<1>; Reg<1>:=Reg<0>.

RULE
Term::= Factor MultOp Term
SEMANTICS
Left<1>:=true; Left<3>:=false;
Label<0>:=if Label<1>=Label<3>
          then Label<1>+1
          else Max(Label<1>,Label<3>);
Reg<1>:=if Label<1> < Label<3>
            then Reg<0>+1
            else Reg<0>;
Reg<3>:=if Label<1> < Label<3>
            then Reg<0>
            else Reg<0>+1;

Code<0>:=if Label<1>=0
        then Code<3>||Code<2>

             ||Code<3>||",""||Reg<0>
        else if Label<1> < Label<3>
        then Code<3>||Code<1>||Code<2>||
             Reg<0>+1||","||
             Reg<0>
        else Code<1>||Code<3>||Code<2>||
             Reg<0>||","||Reg<0>+1
             ||"MOVE"||Reg<0>+1
             ||","||Reg<0>.

RULE
Term ::= Factor
SEMANTICS
Left<1>:=Left<0>; Code<0>:=Code<1>;
Label<0>:=Label<1>; Reg<1>:=Reg<0>.

RULE
Factor ::= Ident
SEMANTICS
Label<0>:=if Left<0> then 0 else 1;
Code<0>:=if not Left<0> then
   "LOAD"||Reg<0>||","||Val<1>
        else Val<1>.

RULE
Factor ::= ( IntExpr )
SEMANTICS
Left<2>:=Left<0>; Code<0>:=Code<2>;
Label<0>:=Label<2>; Reg<2>:=Reg<0>.

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

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

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

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

                         Expr
                           |
                        IntExpr
                         / |  \  Left=true
                       /   |    \Label=2
                    /      |      \Reg=1
            Term         AddOp      IntExpr
           / | \  Left=true|          /  | \  Left=false
          /  |   \Label=1   |        /    |   \Label=2
         /   |     \Reg=2   |      /      |     \
        /    |       \      +    /        |       \
   Factor MultOp    Term      Factor   MultOp   Term
 |Left=true |       |Left=false |Left=true |     |Left=false
 |Label=0   |       |Label=1    |Label=0   |     |Label=1
 |Reg=2     *       |Reg=3      |Reg=1     *     |Reg=1
Ident             Ident       Ident          Factor
 A                  B            C            | Left=false
                                              | Label=1
                             -----------------  Reg=1
                           /|\
                         (  |  )
                         IntExpr
                          / | \  Left=false
                        /   |   \Label=1
                      /     |     \Reg=1
                  Term    AddOp IntExpr
               |Left=true   |        | Left=false
               |Label=0     |        | Label=1
               |Reg=2       +        | Reg=1
            Factor                 Term
               |Left=true            | Left=false
               |Label=0              | Label=1
               |Reg=2                | Reg=1
             Ident                 Factor
               D                     | Left=false
                                     | Label=1
                                     | Reg=1
                                   Ident
                                     E

                    Рис. 8.18.

Атрибутированное дерево для выражения A*B+C*(D+E) приведено на рис. 8.18. При этом будет сгенерирован следующий код:

 LOAD E,R1
 ADD D,R1
 MUL C,R1
 LOAD B,R2
 MUL A,R2
 ADD R2,R1

Приведенная атрибутная схема требует двух проходов по дереву выражения. Рассмотрим теперь другую атрибутную схему, в которой достаточно одного обхода для генерация программы для выражений с оптимальным распределением регистров [9]. Пусть мы произвели разметку дерева разбора так же, как и в предыдущем алгоритме. Назначение регистров будем производить в соответствии со схемой рис. 8.19.

Левому потомку всегда назначается регистр, равный его метке, а правому - его метке, если она не равна метке его левого брата, и метке +1, если метки равны. Поскольку более сложное поддерево всегда вычисляется раньше более простого, его регистр результата имеет больший номер, чем любой регистр, используемый при вычислении более простого поддерева, что гарантирует правильность использования регистров.

                  | ^
                  | | Label
                 / \
               /     \
             /         \
    Left=0 /Label-->Left\
          /\             /\ Reg<0>:=if (Left<0>=Label<0>)
         /  \           /  \           &(Left<0>#0)
        /    \         /    \       then Label<0>+1
       /      \       /\    /\      else Label<0>
      /        \     /  \  /  \
      ----------     ----  ----

                  Рис. 8.19.

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

RULE
Expr ::= IntExpr
SEMANTICS
Code<0>:=Code<1>; Left<1>:=true.
RULE
IntExpr ::= Term AddOp IntExpr
SEMANTICS
Left<1>:=true; Left<3>:=false;
Label<0>:=if Label<1>=Label<3>
          then Label<1>+1
          else Max(Label<1>,Label<3>);
Code<0>:=if Label<3> > Label<1> then
           if Label<1>=0 then
              Code<3>||Code<2>||Code<1>
              ||","||Label<3>
           else Code<3>||Code<1>||Code<2>||
                Label<1>||","||Label<3>
        else if Label<3> < Label<1> then
                Code<1>||Code<3>||Code<2>||
                Label<1>||","||Label<3>||
                "MOVE"||Label<3>||","||
                Label<1>
        else {Label<3>=Label<1>}
                Code<3>||"MOVE"||Label<3>||
                ","||Label<3>+1||Code<1>||
                Code<2>||Label<1>||","||
                Label<1>+1.

RULE
IntExpr ::= Term
SEMANTICS
Left<1>:=Left<0>; Code<0>:=Code<1>;
Label<0>:=Label<1>.

RULE
Term ::= Factor MultOp Term
SEMANTICS
Left<1>:=true; Left<3>:=false;
Label<0>:=if Label<1>=Label<3>
          then Label<1>+1
          else Max(Label<1>,Label<3>);
Code<0>:=if Label<3> > Label<1> then
           if Label<1>=0 then
              Code<3>||Code<2>||Code<1>
              ||","||Label<3>
           else Code<3>||Code<1>||Code<2>||
                Label<1>||","||Label<3>
        else if Label<3> < Label<1> then
                Code<1>||Code<3>||Code<2>||
                Label<1>||","||Label<3>||
                "MOVE"||Label<3>||","||
                Label<1>
        else {Label<3>=Label<1>}
                Code<3>||"MOVE"||Label<3>||
                ","||Label<3>+1||Code<1>||
                Code<2>||Label<1>||","||
                Label<1>+1.

RULE
Term ::= Factor
SEMANTICS
Left<1>:=Left<0>; Code<0>:=Code<1>;
Label<0>:=Label<1>.

RULE
Factor ::= Ident
SEMANTICS
Label<0>:=if Left<0> then 0 else 1;
Code<0>:=if Left<0> then Val<1>
        else "LOAD"||Val<1>||"R1".

RULE
Factor ::= ( IntExpr )
SEMANTICS
Left<2>:=Left<0>; Code<0>:=Code<2>;
Label<0>:=Label<2>.

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

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

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

RULE
MultOp ::= '/'
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) и результат заслать во 2
             регистр

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

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

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

A & B эквивалентно if A then B else False,
A v B эквивалентно if A then True else B.

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

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

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

RULE
BoolExpr ::= BoolExpr '&' BoolExpr
SEMANTICS
FalseLab<1>:=FalseLab<0>; TrueLab<1>:=NodeLab<3>;
FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>.

RULE
BoolExpr ::= BoolExpr 'V' BoolExpr
SEMANTICS
TrueLab<1>:=TrueLab<0>; FalseLab<1>:=NodeLab<3>;
FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>.

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

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

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

         TrueLab                    TrueLab
       FalseLab\                  FalseLab\
           / | \\                      /| \\
          / / \ \\                    // \ \\
         / / & \ \\                  // V \ \\
        / /     \ \\                //     \ \\
FalseLab /       \ \TrueLab  TrueLab/       \ \TrueLab
        /         \FalseLab        /         \ FalseLab
TrueLab<-------NodeLabel      FalseLab<---NodeLabel

                    Рис. 8.20.

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

                 F V ( F & T & T ) V T
                 | FalseLab=False
                 1 TrueLab=True
                /
TrueLab=True   / V \
FalseLab=2    /     \  FalseLab=False
              F      2 TrueLab=True
                    / \
     TrueLab=True  / V \
    FalseLab=3    /     \
                 /       \
                 4        3
                / \       |
TrueLab=5      / & \      T
FalseLab=3    /     \   TrueLab=True
             /       \  FalseLab=3
             F        5
                     / \
      TrueLab=6     / & \                   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 для значения, равного T, и переход на метку False для значения F. Это утверждение является частным случаем следующего.

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

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

                         | FalseLab0
                         | TrueLab0
                        / \
                       / & \
FalseLab1=FalseLab0   /     \  FalseLab2=FalseLab0
TrueLab1=NodeLab2    /       \ TrueLab2=TruLab0
                    /\       /\
                   /  \     /  \
                   ----     ----

                             147
                         | FalseLab0
                         | TrueLab0
                        / \
                       / V \
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. Добавим теперь новое правило в предыдущую грамматику:

BoolExpr ::= Ident
SEMANTICS
 else GOTO FalseLab<0>>;

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

1: if Ident=T then GOTO True else GOTO 2
2:
4: if Ident=T then GOTO 5 else GOTO 3
5: if Ident=T then GOTO 6 else GOTO 3
6: if Ident=T then GOTO True else GOTO 3
3: if Ident=T then GOTO True else GOTO False

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

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

Действительно, по правилам наследования атрибутов TrueLab и FalseLab, в правилах для дизъюнкции и конъюнкции либо FalseLab, либо TrueLab принимает значение метки следующего поддерева. Кроме того, как значение FalseLab, так и значение TrueLab, передаются в правое поддерево от предка. Таким образом, самый правый потомок всегда имеет одну из меток TrueLab или FalseLab, равную метке правого брата соответствующего поддерева. Учитывая порядок генерации команд, получаем утверждение. Дополним теперь атрибутную грамматику следующим образом:

RULE
Expr ::= BoolExpr
SEMANTICS
FalseLab<1>:=False; TrueLab<1>:=True;
Sign<1>:=false.

RULE
BoolExpr ::= BoolExpr & BoolExpr
SEMANTICS
FalseLab<1>:=FalseLab<0>; TrueLab<1>:=NodeLab<3>;
FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>;
Sign<1>:=false; Sign<3>:=Sign<0>.

RULE
BoolExpr ::= BoolExpr V BoolExpr
SEMANTICS
TrueLab<1>:=TrueLab<0>; FalseLab<1>:=NodeLab<3>;
FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>;
Sign<1>:=true; Sign<3>:=Sign<0>.

RULE
BoolExpr ::= not BoolExpr
SEMANTICS
FalseLab<1>:=TrueLab<0>; TrueLab<1>:=FalseLab<0>;
Sign<1>:=not Sign<0>.

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

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

RULE
BoolExpr ::= Ident
SEMANTICS
if Sign<0>
then  else GOTO FalseLab<0>>
else  else GOTO TrueLab<0>>;

Правила наследования атрибута Sign приведены на рис. 8.24.

false |          true |        false |      true |
     or              or             and         and
     /\              /\             /\          /\
    /  \            /  \           /  \        /  \
   /    \          /    \         /    \      /    \
true   false    true  true     false false  false true

              true |        false |
                   |              |
                  not            not
                   |              |
                   |              |
                 false          true

                      Рис. 8.24

Программу желательно сформировать таким образом, чтобы else- метка была как раз меткой следующей вершины. Как это можно сделать, следует из утверждения 4.

Утверждение 4. В каждой терминальной вершине, метка ближайшего правого для нее поддерева равна значению атрибута FalseLab этой вершины, тогда и только тогда, когда значение атрибута Sign этой вершины равно true, и наоборот, метка ближайшего правого для нее поддерева равна значению атрибута TrueLab этой вершины, тогда и только тогда, когда значение атрибута Sign равно false.

Эти два утверждения позволяют заменить последнее правило атрибутной грамматики следующим образом:

RULE
BoolExpr ::= Ident
SEMANTICS
if Sign<0>
then >
else >.

В свою очередь, при генерации машинных команд это правило

можно заменить на следующее:

RULE
BoolExpr ::= Ident
SEMANTICS
;
if Sign<0> then >
else >.

Если элементом логического выражения является сравнение, то генерируется команда, соответствующая знаку сравнения (beq для =, bne для <>, bge для >= и т.д.), если атрибут sign соответствующей вершины имеет значение true, и отрицание (bne для =, beq для <>, blt для >= и т.д.), если атрибут sign имеет значение false.

Приведем несколько примеров. Выражение A AND (B OR C) транслируется в последовательность команд рис. 8.25. Выражение (NOT((A=B)OR(C<>D)))AND(not((EH))) транслируется в последовательность команд рис. 8.26.

              TST A                      CMP A,B
              BEQ False                  BEQ False
              TST B                      CMP C,D
              BNE True                   BNE False
              TST C                      CMP E,F
              BEQ False                  BGE False
        True:                            CMP G,H
       False:. . .                       BGT False
                                    True:
                                   False:

                Рис. 8.25            Рис. 8.26
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования