|
Лекции по конструированию компиляторов - Часть 12
Автор: В.А.Серебряков 8.8. Выделение общих подвыражений Выделение общих подвыражений проводится на линейном участке и основывается на двух положениях. 1. Поскольку на линейном участке переменной может быть несколько присваиваний, то при выделении общих подвыражений необходимо различать вхождения переменных до и после присваивания. Для этого каждая переменная снабжается номером. Вначале номера всех переменных устанавливаются равными 0. При каждом присваивании переменной ее номер увеличивается на 1. 2. Выделение общих подвыражений осуществляется при обходе дерева выражения снизу вверх слева направо. При достижении очередной вершины (пусть операция, примененная в этой вершине, есть бинарная 'op'; в случае унарной операции рассуждения те же) просматриваем общие подвыражения, связанные с op. Если имеется выражение, связанное с op и такое, что его левый операнд есть общее подвыражение с левым операндом нового выражения, а правый операнд - общее подвыражение с правым операндом нового выражения, то объявляем новое выражение общим с найденным и в новом выражении запоминаем указатель на найденное общее выражение. Базисом построения служит переменная: если операндами обоих выражений являются одинаковые переменные с одинаковыми номерами, то они являются общими подвыражениями. Если выражение не выделено как общее, оно заносится в список операций, связанных с op (рис. 8.27).
|<-----| op |<-------|
/ \ / \
/ \ / \
+---->/\ /\<-----+ +-----/\ /\---+
| / \ / \ | | / \ / \ |
| ---- ---- | | ---- ---- |
| +-+---------------+
+--------------------+
Рис.8.27
Рассмотрим теперь реализацию алгоритма выделения общих подвыражений. Поддерживаются следующие глобальные переменные: Table - таблица переменных; для каждой переменной хранится ее номер (Count) и указатель на вершину дерева выражений, в которой переменная встретилась в последний раз в левой части (Last); OpTable - таблица списков общих подвыражений, связанных с каждой операцией (Addr - указатель на вершину дерева, List - продолжение списка); С каждой вершиной дерева выражения связана запись:
NodeType =
record Left -- левый потомок вершины;
Right -- правый потомок вершины;
Comm -- указатель на предыдущее общее подвыражение;
Flag -- признак, является ли поддерево
общим подвыражением;
Varbl -- признак, является ли вершина переменной;
VarCount -- номер переменной;
end;
Все общие подвыражения собраны в список (с типом элемента LisType), начинающийся с OpTable[Op], как это изображено на рис. 8.28.
|<------------|<-------------|<---------| | Op
/ \ / \ / \ OpTable
/ \ / \ / \
/\ /\ /\ /\ /\ /\
/ \ / \ / \ / \ / \ / \
---- ---- ---- ---- ---- ----
Рис. 8.28
Выделение общих подвыражений и построение дерева осуществляются приведенными ниже правилами. Атрибут Entry нетерминала Variable дает указатель на переменную в таблице. Атрибут Val символа Op дает код операции. Атрибут Node символов IntExpr и Assignment дает указатель на запись типа NodeType соответствующего нетерминала.
RULE
Assignment ::= Variable IntExpr
SEMANTICS
Table[Entry<1>].Count:=Table[Entry<1>].Count+1.
{Увеличить счетчик присваиваний переменной}
RULE
IntExpr ::= Variable
SEMANTICS
with Node<0>^ do with Table[Entry<1>] do
if Last<>NIL
{ Переменная уже была использована }
and Last^.VarCount = Count then
{ С тех пор переменной не было присваивания }
Flag:=true;
{ Переменная - общее подвыражение }
Comm:=Last;
{ Указатель на общее подвыражение }
else Flag:=false;
end;
Last:=^Node<0>; {Указатель на последнее
использование переменной}
VarCount:=Count; {Номер использования переменной}
Varbl:=true; {Выражение - переменная}
end end.
RULE
IntExpr ::= Op IntExpr IntExpr
SEMANTICS
var L:pointer to Listype; {Тип списков операции}
if Node<2>^.Flag and Node<3>^.Flag then
{ И справа, и слева - общие подвыражения }
L:=OpTable[Val<1>];
{ Начало списка общих подвыражений для операции }
while L<>nil do
if (Node<2>=L^.Left)
and (Node<3>=L^.Right)
{ Левое и правое поддеревья совпадают }
then exit
else L:=L^.List;{Следующий элемент списка}
end end
else L:=nil; {Не общее подвыражение}
end;
with Node<0>^ do
Varbl:=false; { Не переменная }
Comm:=L;
{Указатель на предыдущее общее подвыражение или nil}
if L<>nil then
Flag:=true; {Общее подвыражение}
Left:=Node<2>;
{ Указатель на левое поддерево }
Right:=Node<3>;
{ Указатель на правое поддерево }
else Flag:=false;
{ Данное выражение не может рассматриваться как общее }
{ Если общего подвыражения с данным не было,
включить данное в список для операции }
new(L);
L^.Addr:=^Node<0>;
L^.List:=OpTable[Val<1>];
OpTable[Val<1>]:=L;
end end.
Рассмотрим теперь некоторые простые правила распределения регистров при наличии общих подвыражений. Если число регистров ограничено, можно выбрать один из следующих двух вариантов. 1. При обнаружении общего подвыражения с подвыражением в уже просмотренной части дерева (и, значит, с уже распределенными регистрами) проверяем, расположено ли его значение на регистре. Если да, и если регистр после этого не менялся, заменяем вычисление поддерева на значение в регистре. Если регистр менялся, то вычисляем подвыражение заново. 2. Вводим еще один проход. На первом проходе распределяем регистры. Если в некоторой вершине обнаруживается, что ее поддерево общее с уже вычисленным ранее, но значение регистра потеряно, то в такой вершине на втором проходе необходимо сгенерировать команду сброса регистра в рабочую память. Выигрыш в коде будет, если стоимость команды сброса регистра + доступ к памяти в повторном использовании этой памяти не превосходит стоимости заменяемого поддерева. Поскольку стоимость команды MOVE известна, можно сравнить стоимости и принять оптимальное решение: то ли метить предыдущую вершину для сброса, то ли вычислять полностью поддерево. 8.9. Генерация оптимального кода методами синтаксического анализа 8.9.1. Сопоставление образцов Техника генерации кода, рассмотренная выше, основывалась на однозначном соответствии структуры промежуточного представления и описывающей это представление грамматики. Для генерации более качественного кода может быть применен подход, изложенный в настоящей главе. Этот подход основан на понятии "сопоставления образцов": командам машины сопоставляются некоторые "образцы", вхождения которых ищутся в промежуточном представлении программы, и делается попытка "покрыть" промежуточную программу такими образцами. Если это удается, то по образцам восстанавливается программа уже в кодах.
:=
|
-------------
/ \
+ +
/ \ / \
/ \ / \
const(a) const(x) @ const(5)
|
|
+
/ \
/ \
+ @
/ \ |
/ \ |
const(b) const(y) +
/ \
/ \
const(i) const(z)
Рис. 8.29
На рис. 8.29 показано промежуточное дерево для оператора a:=b[i]+5, где a,b,i - локальные переменные, хранимые со смещениями x,y,z в областях данных с одноименными адресами. Элемент массива b занимает память в одну машинную единицу. 0-местная операция const возвращает значение атрибута соответствующей вершины промежуточного дерева, указанного на рисунке в скобках после оператора. Одноместная операция '@' означает косвенную адресацию и возвращает содержимое регистра или ячейки памяти, имеющей адрес, задаваемый аргументом оператора.
+------------------------------------------------------+
|Но-| Образец |Машинная команда |Стоимость|
|мер| |Правило грамматики| |
|---+---------------------+----------------------------|
| 1 | const(c) | MOV #c,Ri | 2 |
| | | Reg->Const | |
|---+---------------------+-----------------------+----|
| 2 | := | MOV Rj,c(Ri) | 4 |
| | / \ | | |
| | / \ | | |
| | + reg(j) | | |
| | / \ | Stat->':=' '+' Reg | |
| |reg(i) const(c) | Const Reg | |
|---+---------------------+-----------------------+----|
| 3 | @ | MOV c(Rj),Ri | 4 |
| | | | | |
| | + | | |
| | / \ | | |
| | / \ |Contents -> '@' '+' Reg| |
| | reg(j) const(c) | Const | |
|---+---------------------+-----------------------+----|
| 4 | + | ADD #c,Ri | 3 |
| | / \ | | |
| | / \ | | |
| | reg(i) const(c) |Reg -> '+' Reg Const | |
|---+---------------------+-----------------------+----|
| 5 | + | ADD Rj,Ri | 2 |
| | / \ | | |
| | / \ | | |
| | reg(i) reg(j) | Reg -> '+' Reg Reg | |
|---+---------------------+-----------------------+----|
| 6 | + | ADD c(Rj),Ri | 4 |
| | / \ | | |
| | / \ | | |
| |reg(i) @ | | |
| | | | Reg -> '+' Reg '@' | |
| | + | '+' Reg Const | |
| | / \ | | |
| | reg(j) const(c) | | |
|---+---------------------+-----------------------+----|
| 7 | @ | MOV (R),R | 2 |
| | | | | |
| | Reg | Reg -> Contents | |
+------------------------------------------------------+
Рис. 8.30
----------[stat]----------------------------------
|2 := |
| / \ |
| + \ |
| / \ \ |
|reg(Ra) const(x) \ |
|const(a) \ |
| ------------------[reg(Rb)]------------------ |
| | 4 + | |
| | / \ | |
| | / const(5) | |
| | / | |
| | ---------------[reg(Rb)]------------------ | |
| | | 7 @ | | |
| | | | | | |
| | | -------------[reg(Rb)]---------------- | | |
| | | |6 + | | | |
| | | | / \ | | | |
| | | | / \ | | | |
| | | | ------[reg(Rb)]---- \ | | | |
| | | | |4 + | @ | | | |
| | | | | / \ | | | | | |
| | | | | / \ | | | | | |
| | | | | reg(Rb) const(y)| + | | | |
| | | | | const(b) | / \ | | | |
| | | | ------------------- / \ | | | |
| | | | / \ | | | |
| | | | reg(Ri) const(z) | | | |
| | | | const(i) | | | |
| | | -------------------------------------- | | |
| | ------------------------------------------ | |
| ---------------------------------------------- |
--------------------------------------------------
Рис. 8.31
На рис.8.30 показан пример сопоставления образцов машинным командам. Приведены два варианта задания образца: в виде дерева и в виде правила контекстно-свободной грамматики. Для каждого образца указана машинная команда, реализующая этот образец, и стоимость этой команды. Стоимость может определяться различными способами, и здесь мы не рассматриваем этого вопроса. На рис. 8.31 приведен пример покрытия промежуточного дерева рис. 8.29 образцами рис. 8.30. В рамки заключены фрагменты дерева, сопоставленные образцу правила, номер которого указывается в левом верхнем углу рамки. В квадратных скобках указаны результирующие вершины. Приведенное покрытие дает такую последовательность команд:
MOVE b,Rb ADD #y,Rb MOVE i,Ri ADD z(Ri),Rb MOV (Rb),Rb ADD #5,Rb MOVE a,Ra MOV Rb,x(Ra) Как правило, одни и те же конструкции исходной (или промежуточной) программы можно реализовать различными последовательностями машинных команд. Это соответствует тому, что имеются различные покрытия промежуточного представления. Задача выбора команд состоит в том, чтобы выбрать наилучший способ реализации того или иного действия или последовательности действий, т. е. выбрать в некотором смысле оптимальное покрытие. Для выбора оптимального покрытия было предложено несколько интересных алгоритмов, в частности использующих динамическое программирование [10,11]. Мы здесь рассмотрим алгоритм [12], комбинирующий возможности синтаксического анализа и динамического программирования, в основу которого положен синтаксический анализ неоднозначных грамматик (модифицированный алгоритм Кока, Янгера и Касами [13,14]) более эффективный в реальных приложениях. Этот же метод может быть применен и тогда, когда в качестве промежуточного представления используется дерево. 8.9.2. Синтаксический анализ для T-грамматик Обычно код генерируется из некоторого промежуточного языка с довольно жесткой структурой. В частности, для каждой операции известна ее размерность (число операндов). Назовем грамматики, удовлетворяющие этим ограничениям, T-грамматиками. Образцы, соответствующие машинным командам, задаются правилами грамматики (вообще говоря, неоднозначной). Генератор кода анализирует входное префиксное выражение и строит одновременно все возможные деревья разбора. После окончания разбора выбирается дерево с наименьшей оценкой. Затем по этому единственному оптимальному дереву генерируется код. Для T-грамматик все цепочки, выводимые из любого нетерминала A, являются префиксными выражениями с фиксированной арностью операций. Длины всех выражений из входной цепочки a1...an можно предварительно вычислить. Поэтому можно проверить, сопоставимо ли правило с подцепочкой ai...ak входной цепочки a1...an, проходя слева-направо по ai...ak. В процессе прохода по цепочке предварительно вычисленные длины префиксных выражений используются для того, чтобы перейти от одного терминала к следующему терминалу, пропуская подцепочки, соответствующие нетерминалам правой части правила. Цепные правила не зависят от операций, следовательно, их необходимо проверять отдельно. Применение одного цепного правила может зависеть от применения другого цепного правила. Следовательно, применение цепных правил необходимо проверять циклически до тех пор, пока нельзя применить ни одно из цепных правил. Мы предполагаем, что в грамматике нет циклов в применении цепных правил. Тип Titem в алгоритме 8.1 ниже служит для описания ситуаций (т.е. правил вывода и позиции внутри правила). Тип Tterminal - это тип терминального символа грамматики, тип Tproduction - тип для правила вывода.
r[i]={A->aiV1...Vm}
| /\
| / \
| 1 /\ /\m
| / \ / \
|---------|----------------|-----|
ai l[i]
Рис. 8.32
Алгоритм 8.1:
var
a:array[1..n] of Tterminal;
r:array[1..n] of set of Tproduction;
l:array[1..n] of INTEGER;
(* l[i] - длина a[i]-выражения*)
h:Titem;
(* используется при поиске правил, сопоставимых с
текущей подцепочкой*)
begin (* Предварительные вычисления *)
Для каждой позиции i вычислить длину a[i]-выражения l[i];
(* Распознование входной цепочки *)
for i:=n downto 1 do
for для каждого правила A -> a[i] y из P do
if l[i]>0 then
j:=i+1;
if l[i]>1 then (*Первый терминал a[i] уже проверен*)
h:=[A->a[i].y];
repeat (*Сопоставимы ли a[i]y и a[i]..a[i+l[i]-1]*)
Пусть h=[A->u.Xv]
if X в T then
if X=a[j] then j:=j+1 else exit end
else (* X в N *)
if X->w в r[j] then j:=j+l[j] else exit end
end;
h:=[A->uX.v]; (* Перейти к следующему символу*)
until j=i+l[i];
end (*l[i]>1*);
end (*l[i]>0*);
if j=i+l[i] then r[i]:=r[i]+{(A->a[i]y)} end
end (*for*);
(* Проверить цепные правила *)
while существует правило C->A из P такое, что
имеется некоторый элемент (A->w) в r[i]
и нет элемента (C->A) в r[i]
do r[i]:=r[i]+{(C->A)}
end
end; (* for i *)
Проверить, принадлежит ли (S->w) множеству r[1]
end
Работа алгоритма иллюстрируется рис. 8.32. Множества r[i] имеют размер O(|P|). Очевидно, что алгоритм имеет временную и емкостную сложность O(n). Рассмотрим вновь пример рис. 8.29. В префиксной записи приведенный фрагмент программы записывается следующим образом:
:= + a x + @ + + b y @ + i z 5 На рис. 8.33 приведен результат работы алгоритма. Правила вычисления стоимости приведены в разделе 8.9.3.
+-----------------------------+
|Операция|Длина| Правила |
| | | (стоимость) |
|--------+-----+--------------|
| := | 14 | 2(22) |
| + | 2 | 4(5) 5(6) |
| a | 0 | 1(2) |
| x | 0 | 1(2) |
| + | 9 | 4(16) 5(17)|
| @ | 8 | 7(13) |
| + | 7 | 5(15) 6(11)|
| + | 2 | 4(5) 5(6) |
| b | 0 | 1(2) |
| y | 0 | 1(2) |
| @ | 3 | 3(6) 7(7) |
| + | 2 | 4(5) 5(6) |
| i | 0 | 1(2) |
| z | 0 | 1(2) |
| 5 | 0 | 1(2) |
+-----------------------------+
Рис. 8.33
Пусть G - это T-грамматика. Для каждой цепочки z из L(G) можно построить дерево выражения. Мы можем переписать алгоритм так, чтобы он работал с деревьями выражений, а не с префиксными выражениями. Этот вариант алгоритма приведен ниже. В этом алгоритме дерево выражения обходится сверху вниз и в нем ищутся поддеревья, сопоставимые с правыми частями правил из G. Обход дерева осуществляется процедурой PARSE. После обхода поддерева данной вершины в ней применяется процедура MATCHED, которая пытается найти все образцы, сопоставимые поддереву данной вершины. Для этого каждое правило-образец разбивается на компоненты в соответствии с встречающимися в нем операциями. Дерево обходится справа налево только для того, чтобы иметь соответствие с порядком вычисления в алгоритме 8.1. Очевидно, что можно обходить дерево вывода и слева направо. Структура данных, представляющая вершину дерева, имеет следующую форму:
PTnode=^Tnode;
Tnode=record
op:Tterminal;
son:array[1..MaxArity] of PTnode;
rules:set of Tproduction
end;
В комментариях указаны соответствующие фрагменты алгоритма 8.1. Алгоритм 8.2:
var root:PTnode;
procedure PARSE(n:PTnode);
procedure MATCHED(n:PTnode; h:Titem);
var matching:boolean;
begin
пусть h=[A->u.Xvy], v= v1 v2 ... vm,
m=Arity(X)
if X in T then (* сопоставление правила *)
if m=0 then (*if l[i]=0*)
if X=n^.op (*if X=a[j]*)
then return(true) else return(false) end
else (* m>0 *) (*if l[i]>0*)
if X=n^.op then (*if X=a[j]*)
matching:=true;
for i:=1 to m do (*j:=j+l[j] *)
matching:=matching and (*until j=i+l[i]*)
MATCHED(n^.son[i],[A->uXv'.vi v"y])
end;
return(matching) (*h:=[A->uX.v]*)
else return(false) end
end
else (*X in N*) (* поиск подвывода *)
if в n^.rules имеется правило X->w in
then return(true) else return(false) end
end
end (* match *)
begin (*PARSE*)
for i:=Arity(n^.op) downto 1 do (*for i:=n downto1*)
PARSE(n^.son[i]) end;
n^.rules:={};
for каждого правила A->bu из P такого, что b=n^.op do
if MATCHED(n,[A->.bu]) (*if j=i+l[i]*)
then n^.rules:=n^.rules+{(A->bu)} end
end;
(* Сопоставление цепных правил *)
while существует правило C->A из P такое, что
некоторый элемент (A->w) в n^.rules
и нет элемента (C->A) в n^.rules
do n^.rules:=n^.rules+{(C->A)}
end
end;(*PARSE*)
begin
(* Предварительные вычисления *)
Построить дерево выражения для входной цепочки z;
root:= указатель дерева выражения;
(* Распознать входную цепочку *)
PARSE(root);
Проверить, принадлежит ли S->w множеству root^.rules;
end
Выходом алгоритма является дерево выражения для z, вершинам которого сопоставлены применимые правила. Если T-грамматика неоднозначная, то можно построить несколько различных выводов для заданной входной цепочки. Алгоритмы 8.1 и 8.2 "универсальные" в том смысле, что конкретные грамматики выражений и образцов являются, по- существу, параметрами этих алгоритмов. Для каждой конкретной грамматики можно написать свой алгоритм поиска образцов. Например, в случае нашей грамматики выражений и приведенных на рис. 8.30 образцов алгоритм 8.2 может быть представлен атрибутной грамматикой, приведенной ниже. Для каждого правила имеется два типа образцов: "внутренние", соответствующие правилам-образцам, и "внешние", приходящие сверху через атрибут Match предка. Атрибут Match представлен как вектор образцов вида . Каждый из образцов имеет вид либо , где op - оперция в данной вершине, а op-list - список ее операндов, либо образец - это нетерминал N. В первом случае op-list "распределяется" по потомкам вершины для дальнейшего сопоставления, во втором сопоставление считается успешным, если есть правило N->w, где w - состоит из образцов, успешно сопоставленных потомкам данной вершины. Помимо атрибута Match, образцы могут задаваться и в соответствии с правилами, возможно применимыми в данной вершине. Эти два множества образцов могут пересекаться. Синтезируемый атрибут Pattern (также вектор) дает результат сопоставления по вектору-образцу Match.
Rule Stat ::= Expr ':=' Expr Этому правилу соответствует один образец 2. Поэтому в качестве образцов потомков через их атрибуты Match передаются, соответственно, <'+' Reg Const> и .
Semantics Match<2>:=<'+' Reg Const>: Match<3>:=; Pattern<0>[1]:=Pattern<2>[1]&Pattern<3>[1]. Rule Expr ::= '+' Expr Expr Образцы, соответствующие этому правилу, следующие:
(4) Reg -> '+' Reg Const (5) Reg -> '+' Reg Reg (6) Reg -> '+' Reg '@' '+' Reg Const. Атрибутам Match второго и третьего символов в качестве образцов при сопоставлении могут быть переданы векторы и >, соответственно. Из анализа других правил можно заключить, что при сопоставлении образцов предков левой части данного правила атрибуту Match символа левой части может быть передан образец <'+' Reg Const> (из образцов 2,3,6) или образец Reg.
Semantics
Match<2>:=;
Match<3>:=>;
P:=Pattern<2>&Pattern<3>;
if Match<0> содержит образец <'+' Reg Const> в i-й позиции
Pattern<0>[i]:=Pattern<2>[1]&Pattern<3>[1];
if Match[0] содержит Reg в j-й позиции
Pattern<0>[j]:=(Pattern<2>[1]&Pattern<3>[1])
|(Pattern<2>[2]&Pattern<3>[2])
|(Pattern<2>[3]&Pattern<3>[3]);
Остальным значениям Pattern<0> присвоить false.
Rule Expr ::= '@' Expr Образцы, соответствующие этому правилу, следующие:
(3) Reg -> '@' '+' Reg Const (7) Reg -> '@' Reg Соответственно, атрибуту Match второго символа в качестве образцов при сопоставлении могут быть переданы <'+' Reg Const> (образец 3) или (образец 7). Из анализа других правил можно заключить, что при сопоставлении образцов предков левой части данного правила атрибуту Match могут быть переданы образцы <'@' '+' Reg Const> (из образца 6) и Reg.
Semantics Match<2>:=<<'+' Reg Const>,Reg>; if Match<0> содержит <'+' Reg Const> в i-й позиции Pattern<0>[i]:=Pattern<2>[1]; if Match<0> содержит Reg в j-й позиции Pattern<0>[j]:=Pattern<2>[1]|Pattern<2>[2]; Остальным значениям Pattern<0> присвоить false. Rule Expr ::= Const Semantics if Pattern<0> содержит Const в j-й позиции Pattern<0>[j]:=true; Остальным значениям Pattern<0> присвоить false. Для дерева рис. 8.29 получим значения атрибутов, приведенные на рис. 8.34. Здесь M обозначает Match, P - Pattern, C - Const, R - Reg. 8.9.3. Выбор дерева вывода наименьшей стоимости T-грамматики, описывающие системы комад, обычно являются неоднозначными. Чтобы сгенерировать код для некоторой входной цепочки, необходимо выбрать одно из возможных деревьев вывода. Это дерево должно представлять желаемое качество кода, например размер кода и/или время выполнения. Для выбора дерева из множества всех построенных деревьев вывода можно использовать атрибуты стоимости, атрибутные формулы, вычисляющие их значения, и критерии стоимости, которые оставляют для каждого нетерминала единственное применимое правило. Атрибуты стоимости сопоставляются всем нетерминалам, атрибутные формулы - всем правилам T-грамматики.
M=<':=' '+' R C R> :=
P= |
------------- M=<<'+' R C>,
/ \ <'+' R R>,
+ + <'+' R <'@' '+' R C>>
/ \ / \P=
/ \ / \
const(a) const(x) @ const(5)
M= M=>
'+' R C>> | P=
P= P= |
|
|M=<<'@' '+' R C,
M=<'+' R C>, | <'@' R>>
<'+' R R>, |P=
<'+' R <'@' '+' R C>>|
P= +
/ \
/ \
M=<<'+' R C> / \ M=<<'@' '+' R C,
<'+' R R> + @ <'@' R>>
<'+' R <'@' / \ | P=
'+' R C>> / \ |
P= / \ |
const(b) const(y) | M=<<'+' R C>,
M= M=,
P= <'@''+'R C>>+ <'+' R <'@' '+' R C>>
P= / \P=
/ \
const(i) const(z)
M= M=>
P= P=
Рис. 8.34
Предположим, что для вершины 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 реализацию атрибутов стоимости, формул их вычисления и критериев отбора. Из алгоритма можно исключить поиск подвыводов, соответствующих правилам, для которых значение атрибута стоимости не определено. Структура данных, представляющая вершину дерева, принимает следующий вид:
PTnode=^Tnode;
Tnode=record
op:Tterminal;
son:array[1..MaxArity] of PTnode;
nonterm: array[Tnonterminal] of record
CostAttr : ADDRESS;
Production : Tproduction;
end
OperatorAttributes: ...
end;
Тело процедуры PARSE принимает вид
begin for i:=Arity(n^.op) downto 1 do
PARSE(n^.son[i]) end;
for каждого A из N do WITH n^.nonterm[A]
CostAttr:=UndefinedValue;
production:=Undefined;
end;
for каждого правила A->bu из P такого, что b=n^.op do
if MATCHED(n,[A->.bu]) then
ВычислитьАтрибутыСтоимостиДля(A,n,(A->bu));
ПроверитьКритерийДля(A,n^.nonterm[A].CostAttr);
if (A->bu) лучше, чем ранее обработанное
правило для A then
Модифицировать(n^.nonterm[A].CostAttr)
n^.nonterm[A].production:=(A->bu)
end
end
end;
(* Сопоставить цепные правила *)
while существует правило C->A из P, которое
лучше, чем ранее обработанное правило для A
do
ВычислитьСатрибутыДля(C,n,(C->A));
ПроверитьКритерийДля(C,n^.nonterm[C].CostAttr);
if (C->A) is better then
Модифицировать(n^.nonterm[C].CostAttr)
n^.nonterm[C].production:=(C->A)
end
end
end;
Когда выбрано дерево вывода "наименьшей" стоимости, вычисляются значения атрибутов, сопоставленных вершинам дерева вывода, и генерируются соответствующие машиннные команды. Вычисление значений атрибутов, генерация кода осуществляются в процессе обхода выбранного дерева вывода сверху вниз, слева направо. Обход выбранного дерева вывода выполняется процедурой вычислителя атрибутов, на вход которой поступают корень дерева выражения и аксиома грамматики. Процедура использует правило p:A::=z0 X0 z1...Xk zk, связанное с указанной вершиной n, и заданный нетерминал A, чтобы определить соответствующие им вершины n1,...,nk и нетерминалы X1,...,Xk. Затем вычислитель рекурсивно обходит каждую вершину ni, имея на входе нетерминал Xi. |
Автор проекта: USU Software
Вы можете выкупить этот проект.