В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 28
Текст из файла (страница 28)
ГЕНЕРАЦИЯ ОПТИМАЛЬНОГО КОДА МЕТОДАМИ СИНТАКСИЧЕСКОГО АНАЛИЗА175// Первый терминал a[i] уже успешно сопоставлен{h=[A->a[i].y];do // найти a[i]y, сопоставимое с a[i]..a[i+l[i]-1]{Пусть h==[A->u.Xv];if (X in T)if (X==a[j]) j=j+1; else break;else // X in Nif (имеется X->w in r[j]) j=j+l[j]; else break;h=[A->uX.v];//перейти к следующему символу}while (j==i+l[i]);} // l[i]>1if (j==i+l[i]) r[i]=r[i] + { (A->a[i]y) }} // for по правилам A -> a[i] y// Сопоставить цепные правилаwhile (существует правило C->A из P такое, чтоимеется некоторый элемент (A->w) в r[i]и нет элемента (C->A) в r[i])r[i]=r[i] + { (C->A) };} // for по iПроверить, принадлежит ли (S->w) множеству r[0];Множества r[i] имеют размер O(|P |). Можно показать, что алгоритмимеет временную и емкостную сложность O(n).Рассмотрим вновь пример рис.
9.15. В префиксной записи приведенный фрагмент программы записывается следующим образом:=+ax+@++by@+iz5На рис. 9.18 приведен результат работы алгоритма. Правила вычисления стоимости приведены в следующем разделе. Все возможные выводы входной цепочки (включая оптимальный) можно построить, используя таблицу l длин префиксных выражений и таблицу r применимых правил.Пусть G – это T-грамматика. Для каждой цепочки z из L(G) можнопостроить абстрактное синтаксическое дерево соответствующего выражения (рис.
9.15). Мы можем переписать алгоритм так, чтобы он принимал на входе абстрактное синтаксическое дерево выражения, а не цепочку. Этот вариант алгоритма приведен ниже. В этом алгоритме дерево выражения обходится сверху вниз и в нем ищутся поддеревья, сопоставимые с правыми частями правил из G. Обход дерева осуществляется процедурой 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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
