Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 25
Текст из файла (страница 25)
8.29 получим значения атрибутов, приведенные нарис. 8.34. Здесь M обозначает Match, P - Pattern, C - Const, R - Reg.167M=<'=' '+' R C R>P=<t>C>>=++M=<<'+' R C>,<'+' R R>,<'+' R <'@' '+' RP=<t,t,f>const(a) const(x)@M=<R,R,R> M=<C,R,<'@'C>>'+' R C>>P=<t,t,t> P=<t,t,f>const(5)M=<C,R,<'@''+' RP=<t,t,f>M=<<'@' '+' R C,M=<'+' R C><'@' R>><'+' R R>,P=<t,f><'+' R <'@' '+' R C>>P=<f,t,t>+M=<<'+' R C>M=<<'@' '+' R C,<'+' R R>+@<'@' R>><'+' R <'@'P=<t,t>'+' R CP=<t,t,fconst(b)const(y)M=<<'+' R C>,M=<R,R,R>M=<C,R,<'+' R R>,P=<t,t,t><'@''+'R C>>+<'+' R <'@' '+' RC>>P=<t,t,f>P=<t,t,f>const(i)M=<R,R,R>P=<t,t,t>const(z)M=<C,R,<'@' '+' R C>>P=<t,t,f>Рис.
8.348.9.3. Выбор дерева вывода наименьшей стоимостиT-грамматики, описывающие системы комад, обычно являютсянеоднозначными. Чтобы сгенерировать код для некоторой входнойцепочки, необходимо выбрать одно из возможных деревьев вывода. Этодерево должно представлять желаемое качество кода, например размеркода и/или время выполнения.Для выбора дерева из множества всех построенных деревьев выводаможно использовать атрибуты стоимости, атрибутные формулы,вычисляющие их значения, и критерии стоимости, которые оставляют длякаждого нетерминала единственное применимое правило. Атрибутыстоимости сопоставляются всем нетерминалам, атрибутные формулы 168всем правилам T-грамматики.Предположим, что для вершины n обнаружено применимое правилоp:A::=z0 X0 z1...Xk zk, где zi из T* для 0<=i<=k и Xj из N для 1<=j<=k.Вершина n имеет потомков n1,...,nk, которые соответствуют нетерминаламX1,...,Xk.
Значения атрибутов стоимости вычисляются в порядке снизувверх. Вначале атрибуты стоимости инициализируются неопределеннымзначением UndefinedValue. Предположим, что значения атрибутовстоимости для всех потомков n1,...,nk вершины n вычислены. ЕслиформулаA.a=f(Xi.b,Xj.c,...) для 1<=i,j<=kсопоставлена правилу p, то выполняется формулаn.a=f(ni.b,nj.c,...),вычисляющая для правила p значение атрибута a нетерминала A ввершине n. Для всех примененных правил ищется такое, которое даетминимальное значение стоимости.
Отсутствие примененных правилобозначается через undefined, значение которого полагается большимлюбого определенного значения.Добавим в алгоритм 8.2 реализацию атрибутов стоимости, формулих вычисления и критериев отбора. Из алгоритма можно исключить поискподвыводов, соответствующих правилам, для которых значение атрибутастоимости не определено. Структура данных, представляющая вершинудерева, принимает следующий вид:struct Tnode {Tterminal op;Tnode * son[MaxArity];struct * {unsigned CostAttr;Tproduction Production;} nonterm [Tnonterminal];OperatorAttributes ...Тело процедуры PARSE принимает вид{ for (i=Arity(n->op);i>=0;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]))169{ВычислитьАтрибутыСтоимостиДля(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);}}}Когда выбрано дерево вывода "наименьшей" стоимости,вычисляются значения атрибутов, сопоставленных вершинам деревавывода, и генерируются соответствующие машиннные команды.Вычисление значений атрибутов, генерация кода осуществляются впроцессе обхода выбранного дерева вывода сверху вниз, слева направо.Обход выбранного дерева вывода выполняется процедурой вычислителяатрибутов, на вход которой поступают корень дерева выражения иаксиома грамматики.
Процедура использует правило p:A::=z 0 X0 z1...Xk zk,связанное с указанной вершиной n, и заданный нетерминал A, чтобыопределить соответствующие им вершины n1,...,nk и нетерминалыX1,...,Xk. Затем вычислитель рекурсивно обходит каждую вершину ni, имеяна входе нетерминал Xi.170Литература1.2.3.4.5.6.7.8.9.10.11.12.13.14.Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools. N.Y.:Addison-Wesley, 1986.Грис Д.
Построения компиляторов для цифровых вычислительных машин.М.: Мир, 1975.Fraser C.W., Hanson D.R. A Retargetable compiler for ANSI C.// SIGPLANNotices. 1991. V 26.Надежин Д.Ю., В.А.Серебряков, В.М.Ходукин. Промежуточный язык Лидер(предварительноесообщение)//Обработкасимвольнойинформации.М.: ВЦ АН СССР, 1987. С.
50-63.Ахо А., Ульман Д. Теория синтаксического анализа, перевода икомпиляции. М.: Мир, 1978.Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы.М.: Мир, 1976.Лавров С.С., Гончарова Л.И. Автоматическая обработка данных. Хранениеинформации в памяти ЭВМ. М.: Наука, 1971.Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организацииинформации// ДАН СССР. 1962. Т. 146.
N 2. С. 263-266.Курочкин В.М. Алгоритм распределения регистров для выражений за одинобход дерева вывода//2 Всес. конф "Автоматизация производстваППП и трансляторов". 1983. С. 104-105.Emmelman H.,Schroer F.W.,Landweher R. BEG-a generator for efficient backends// ACM SIGPLAN. 1989. V.11. N 4.p.227-237Aho A.U.,Ganapathi M.,Tjiang S.W. Code generation using tree matching anddynamic programing// ACM Trans. Program. Languages andSystems.1989. V.11.N 4.A. Bezdushny, V.
Serebriakov. The use of the parsing method for optimal codegeneration and common subexpression elimination//Techn. et Sci.Inform. 1993. V.12. N.1. P.69-92.Graham S.L., Harrison M.A., Ruzzo W.L. Am improved context-free recognizer//ACM Trans. Program. Languages and Systems. 1980. N.2.Harrison M.A. Introduction to formal language theory. Reading, Mass.: AddisonWesley, 1978.171.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
