Выбор дерева вывода наименьшей стоимости
T-грамматики, описывающие системы команд, обычно
являются неоднозначными. Чтобы сгенерировать код для некоторой входной цепочки, необходимо выбрать одно из возможных деревьев вывода. Это дерево должно представлять желаемое качество кода, например размер кода и/или время выполнения.
Для выбора дерева из множества всех построенных деревьев вывода можно использовать атрибуты стоимости, атрибутные формулы, вычисляющие их значения, и критерии стоимости, которые оставляют для каждого нетерминала
единственное применимое правило. Атрибуты стоимости сопоставляются всем нетерминалам, атрибутные формулы - всем правилам T-грамматики.
Предположим, что для вершины n обнаружено применимое правило

где zi






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

стоимости. Отсутствие примененных правил обозначается через 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

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