Выбор дерева вывода наименьшей стоимости

T-грамматики, описывающие системы команд, обычно

являются неоднозначными. Чтобы сгенерировать код для некоторой входной цепочки, необходимо выбрать одно из возможных деревьев вывода. Это дерево должно представлять желаемое качество кода, например размер кода и/или время выполнения.

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

единственное применимое правило. Атрибуты стоимости сопоставляются всем нетерминалам, атрибутные формулы - всем правилам T-грамматики.

Предположим, что для вершины n обнаружено применимое правило

где zi

T* для 0

k и Xj

N для 1

k. Вершина n имеет потомков n1, ..., nk, которые соответствуют нетерминалам X1, ..., Xk. Значения атрибутов стоимости вычисляются обходя дерево снизу вверх.

Вначале атрибуты стоимости инициализируются неопределенным значением UndefinedValue. Предположим, что значения атрибутов стоимости для всех потомков n1, ..., nk вершины n вычислены. Если правилу p сопоставлена формула

то производится вычисление значения атрибута a нетерминала A в вершине n. Для всех примененных правил ищется такое, которое дает минимальное значение

стоимости. Отсутствие примененных правил обозначается через Undefined, значение которого полагается большим любого определенного значения.

Добавим в алгоритм 9.2 реализацию атрибутов стоимости, формул их вычисления и критериев отбора. Из алгоритма можно исключить поиск подвыводов, соответствующих правилам, для которых значение атрибута стоимости не определено. Структура данных, представляющая вершину дерева, принимает следующий вид:

struct Tnode {
    Tterminal op;
    Tnode * son[MaxArity];
    struct * { unsigned CostAttr;
               Tproduction Production;
             } nonterm [Tnonterminal];
OperatorAttributes ...

<
Тело процедуры PARSE принимает вид

void PARSE(Tnode *n)

{for (i=Arity(n->op);i>=1;i-)
     PARSE(n->son[i]);
     for (каждого A из N)
       {n->nonterm[A].CostAttr=UndefinedValue;
        n->nonterm[A].production=Undefined;
       }
     for (каждого правила A->bu из P
          такого, что b==n->op)
      if (MATCHED(n,[A->.bu]))
       {ВычислитьАтрибутыСтоимостиДля(A,n,(A->bu));
        ПроверитьКритерийДля(A,n->nonterm[A].CostAttr);
          if ((A->bu) лучше,
             чем ранее обработанное правило для A)
            {Модифицировать(n->nonterm[A].CostAttr);
             n->nonterm[A].production=(A->bu);
            }
       }
// Сопоставить цепные правила
while (существует правило C->A из P, которое
        лучше, чем ранее обработанное правило для A)
  {ВычислитьАтрибутыСтоимостиДля(C,n,(C->A));
   ПроверитьКритерийДля(C,n->nonterm[C].CostAttr);
   if ((C->A) лучше)
    {Модифицировать(n->nonterm[C].CostAttr);
     n->nonterm[C].production=(C->A);
    }
  }
}

Дерево наименьшей стоимости определяется как дерево, соответствующее минимальной стоимости корня. Когда выбрано дерево вывода

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

z0X1z1...Xkzk,

связанное с указанной вершиной n, и заданный нетерминал A, чтобы определить соответствующие им вершины n1, ..., nk

и нетерминалы X1, ..., Xk. Затем вычислитель рекурсивно обходит каждую вершину ni, имея на входе нетерминал Xi.

Содержание раздела