В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1134643), страница 29
Текст из файла (страница 29)
Обход дерева осуществляется процедурой PARSE. После обхода поддерева данной вершины в нейприменяется процедура MATCHED, которая пытается найти все образцы,сопоставимые поддереву данной вершины. Для этого каждое правилообразец разбивается на компоненты в соответствии с встречающимися внем операциями. Дерево обходится справа налево только для того, что-ГЛАВА 9. ГЕНЕРАЦИЯ КОДА176Операция=+ax+@++by@+iz5Длина15311119831143111Правила (стоимость)2(22)4(5)5(6)1(2)1(2)4(14) 5(17)7(11)5(11) 6(9)4(5)5(6)1(2)1(2)7(7)3(4)4(5)5(6)1(2)1(2)1(2)Рис.
9.18:бы иметь соответствие с порядком вычисления в алгоритме 9.1. Очевидно, что можно обходить дерево вывода и слева направо.Структура данных, представляющая вершину дерева, имеет следующую форму:struct Tnode {Tterminal op;Tnode * son[MaxArity];setofTproduction RULEs;};В комментариях указаны соответствующие фрагменты алгоритма 9.1.Алгоритм 9.2Tnode * root;bool MATCHED(Tnode * n, Titem h){ bool matching;пусть h==[A->u.Xvy], v== v1 v2 ... vm, m=Arity(X);if (X in T)// сопоставление правилаif (m==0) // if l[i]==1if (X==n->op) //if X==a[j]return(true);elsereturn(false);9.9. ГЕНЕРАЦИЯ ОПТИМАЛЬНОГО КОДА МЕТОДАМИ СИНТАКСИЧЕСКОГО АНАЛИЗА177else // if l[i]>1if (X==n->op) //if X==a[j]{matching=true;for (i=1;i<=m;i++) //j=j+l[j]matching=matching && //while (j==i+l[i])MATCHED(n->son[i-1],[A->uXv’.vi v"y]);return(matching); //h=[A->uX.v]}elsereturn(false);else // X in N поиск подвыводаif (в n^.RULEs имеется правило с левой частью X)return(true);elsereturn(false);}void PARSE(Tnode * n){for (i=Arity(n->op);i>=1;i--)// for (i=n; i>=1;i--)PARSE(n->son[i-1]);n->RULEs=EMPTY;for (каждого правила A->bu из P такого, что b==n->op)if (MATCHED(n,[A->.bu])) //if (j==i+l[i])n->RULEs=n->RULEs+{(A->bu)};// Сопоставление цепных правилwhile (существует правило C->A из P такое, чтонекоторый элемент (A->w) в n->RULEsи нет элемента (C->A) в n->RULEs)n->RULEs=n->RULEs+{(C->A)};}Основная программа// Предварительные вычисленияПостроить дерево выражения для входной цепочки z;root = указатель дерева выражения;// Распознать входную цепочкуPARSE(root);Проверить, входит ли во множество root->RULEsправило с левой частью S;Выходом алгоритма является дерево выражения для z, вершинам которого сопоставлены применимые правила.
С помощью такого дереваможно построить все выводы для исходного префиксного выражения.ГЛАВА 9. ГЕНЕРАЦИЯ КОДА1789.9.3Выбор дерева вывода наименьшей стоимостиT-грамматики, описывающие системы команд, обычно являются неоднозначными. Чтобы сгенерировать код для некоторой входной цепочки, необходимо выбрать одно из возможных деревьев вывода. Это дерево должно представлять желаемое качество кода, например размер кодаи/или время выполнения.Для выбора дерева из множества всех построенных деревьев выводаможно использовать атрибуты стоимости, атрибутные формулы, вычисляющие их значения, и критерии стоимости, которые оставляют длякаждого нетерминала единственное применимое правило.
Атрибуты стоимости сопоставляются всем нетерминалам, атрибутные формулы – всемправилам T-грамматики.Предположим, что для вершины n обнаружено применимое правилоp : A → z0 X1 z1 ... Xk zk ,где zi ∈ T ∗ для 0 6 i 6 k и Xj ∈ N для 1 6 j 6 k. Вершина n имеет потомков n1 , ... , nk , которые соответствуют нетерминалам X1 , ... , Xk . Значения атрибутов стоимости вычисляются обходя дерево снизу вверх. Вначале атрибуты стоимости инициализируются неопределенным значением UndefinedValue.
Предположим, что значения атрибутов стоимости длявсех потомков n1 , ... , nk вершины n вычислены. Если правилу p сопоставлена формулаa(A) = f (b(Xi ), c(Xj ), ...) для 1 6 i, j 6 k,то производится вычисление значения атрибута a нетерминала A в вершине n. Для всех примененных правил ищется такое, которое дает минимальное значение стоимости. Отсутствие примененных правил обозначается через Undefined, значение которого полагается большим любого определенного значения.Добавим в алгоритм 9.2 реализацию атрибутов стоимости, формулих вычисления и критериев отбора.
Из алгоритма можно исключить поиск подвыводов, соответствующих правилам, для которых значение атрибута стоимости не определено. Структура данных, представляющая вершину дерева, принимает следующий вид:struct Tnode {Tterminal op;Tnode * son[MaxArity];struct * { unsigned CostAttr;Tproduction Production;} nonterm [Tnonterminal];OperatorAttributes ...Тело процедуры PARSE принимает вид9.9. ГЕНЕРАЦИЯ ОПТИМАЛЬНОГО КОДА МЕТОДАМИ СИНТАКСИЧЕСКОГО АНАЛИЗА179{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 → z0 X1 z1 ... Xk zk ,связанное с указанной вершиной n, и заданный нетерминал A, чтобыопределить соответствующие им вершины n1 , ... , nk и нетерминалы X1 , ... , Xk .Затем вычислитель рекурсивно обходит каждую вершину ni , имея навходе нетерминал Xi .1809.9.4ГЛАВА 9. ГЕНЕРАЦИЯ КОДААтрибутная схема для алгоритма сопоставления образцовАлгоритмы 9.1 и 9.2 являются “универсальными” в том смысле, чтоконкретные грамматики выражений и образцов являются, по-существу,параметрами этих алгоритмов. В то же время, для каждой конкретнойграмматики можно написать свой алгоритм поиска образцов.
Например, в случае нашей грамматики выражений и приведенных на рис. 9.16образцов алгоритм 9.2 может быть представлен атрибутной грамматикой, приведенной ниже.Наследуемый атрибут Match содержит упорядоченный список (вектор) образцов для сопоставления в поддереве данной вершины. Каждыйиз образцов имеет вид либо <op op–list> (op – операция в данной вершине, а op–list – список ее операндов), либо представляет собой нетерминал N . В первом случае op–list “распределяется” по потомкам вершины для дальнейшего сопоставления.
Во втором случае сопоставлениесчитается успешным, если есть правило N → op {P ati }, где w состоит из образцов, успешно сопоставленных потомкам данной вершины. Вэтом случае по потомкам в качестве образцов распределяются элементыправой части правила. Эти два множества образцов могут пересекаться. Синтезируемый атрибут Pattern – вектор логических значений, даетрезультат сопоставления по вектору-образцу Match.Таким образом, при сопоставлении образцов могут встретиться дваслучая:1. Вектор образцов содержит образец <op {P ati }>, где op – операция,примененная в данной вершине.
Тогда распределяем образцы P atiпо потомкам и сопоставление по данному образцу считаем успешным (истинным), если успешны сопоставления элементов этого образца по всем потомкам.2. Образцом является нетерминал N . Тогда рассматриваем все правила вида N → op {P ati }. Вновь распределяем образцы P ati по потомкам и сопоставление считаем успешным (истинным), если успешны сопоставления по всем потомкам.
В общем случае успешнымможет быть сопоставление по нескольким образцам.Отметим, что в общем случае в потомки одновременно передаетсянесколько образцов для сопоставления.В приведенной ниже атрибутной схеме не рассматриваются правилавыбора покрытия наименьшей стоимости (см. предыдущий раздел). Выбор оптимального покрытия может быть сделан еще одним проходом подереву, аналогично тому, как это было сделано выше.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
