CODOPT7 (Материалы к контрольным работам), страница 2

struct Tnode {
Tterminal op;
Tnode * son[MaxArity];
setofTproduction RULEs;
};

В комментариях указаны соответствующие фрагменты алгоритма 8.1.

Алгоритм 8.2:
Tnode * root;
bool MATCHED(Tnode * n, Titem h)
{bool matching;
int m=Arity(X);
пусть h==[A->u.Xvy], v== v1 v2 ... vm,
if (X in T)// сопоставление правила
if (m==0) //if l[i]==0
if (X==n->op) //if X==a[j]
return(true);
else return(false);
else // if l[i]>0
if (X==n->op) //if X==a[j]
{matching=true;
for (i=0;i<m;i++) //j=j+l[j]
matching=matching && //until j=i+l[i]
MATCHED(n->son[i],[A->uXv'.vi v"y]);
return(matching); //h=[A->uX.v]
}
else return(false);
else //X in N поиск подвывода
if (в n^.RULEs имеется правило с левой частью X)
return(true);
else return(false);
}//match

void PARSE(Tnode * n);
{//PARSE
for (i=Arity(n->op)-1;i>=0;i--)
//for (i=n-1; i>=0;i--)
PARSE(n->son[i]);
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)};
}//PARSE
//Предварительные вычисления
Построить дерево выражения для входной цепочки z;
root= указатель дерева выражения;
// Распознать входную цепочку
PARSE(root);
Проверить, входит ли во множество root->RULEs
правило с левой частью S;
}

Выходом алгоритма является дерево выражения для z, вершинам которого сопоставлены применимые правила. Если T-грамматика неоднозначная, то можно построить несколько различных выводов для заданной входной цепочки.

Алгоритмы 8.1 и 8.2 "универсальные" в том смысле, что конкретные грамматики выражений и образцов являются, по-существу, параметрами этих алгоритмов. Для каждой конкретной грамматики можно написать свой алгоритм поиска образцов. Например, в случае нашей грамматики выражений и приведенных на рис. 8.30 образцов алгоритм 8.2 может быть представлен атрибутной грамматикой, приведенной ниже. Для каждого правила имеется два типа образцов: "внутренние", соответствующие правилам-образцам, и "внешние", приходящие сверху через атрибут Match предка. Атрибут Match представлен как вектор образцов вида <Pattern₁, ... Pattern_n>. Каждый из образцов имеет вид либо <op op-list>, где op - операция в данной вершине, а op-list - список ее операндов, либо образец - это нетерминал N. В первом случае op-list "распределяется" по потомкам вершины для дальнейшего сопоставления, во втором сопоставление считается успешным, если есть правило N->w, где w - состоит из образцов, успешно сопоставленных потомкам данной вершины. Помимо атрибута Match, образцы могут задаваться и в соответствии с правилами, возможно применимыми в данной вершине. Эти два множества образцов могут пересекаться. Синтезируемый атрибут Pattern (также вектор) дает результат сопоставления по вектору-образцу Match.

RULE
Stat ::= '=' Expr Expr

/*Этому правилу соответствует один образец 2. Поэтому в качестве образцов потомков через их атрибуты Match передаются, соответственно, <'+' Reg Const> и <Reg>.*/

SEMANTICS
Match<2>=<'+' Reg Const>:
Match<3>=<Reg>;
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 второго и третьего символов в качестве образцов при сопоставлении могут быть переданы векторы <Reg, Reg, Reg> и <Const, Reg, <'@' '+' Reg Const>>, соответственно.

Из анализа других правил можно заключить, что при сопоставлении образцов предков левой части данного правила атрибуту Match символа левой части может быть передан образец <'+' Reg Const> (из образцов 2,3,6) или образец Reg.*/

SEMANTICS
Match<2>=<Reg,Reg,Reg>;
Match<3>=<Const,Reg,<'@' '+' Reg Const>>;
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) или <Reg> (образец 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.

M =<'=' '+' R C R> =
P=<t>
M=<<'+' R C>,
<'+' R R>,
+ + <'+' R <'@' '+' R C>>
P=<t,t,f>

const(a) const(x) @ const(5)
M=<R,R,R> M=<C,R,<'@' M=<C,R,<'@''+' R C>>
'+' R C>> P=<t,t,f>
P=<t,t,t> P=<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 C
P=<t,t,f
const(b) const(y) M=<<'+' R C>,
M=<R,R,R> M=<C,R, <'+' R R>,
P=<t,t,t> <'@''+'R C>>+ <'+' R <'@' '+' R C>>
P=<t,t,f> P=<t,t,f>

const(i) const(z)
M=<R,R,R> M=<C,R,<'@' '+' R C>>
P=<t,t,t> P=<t,t,f>

Рис. 8.34

8.9.3. Выбор дерева вывода наименьшей стоимости

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

Для выбора дерева из множества всех построенных деревьев вывода можно использовать атрибуты стоимости, атрибутные формулы, вычисляющие их значения, и критерии стоимости, которые оставляют для каждого нетерминала единственное применимое правило. Атрибуты стоимости сопоставляются всем нетерминалам, атрибутные формулы - всем правилам T-грамматики.

Предположим, что для вершины n обнаружено применимое правило p:A::=z₀ X₀ z₁...X_k z_k, где z_i из T* для 0<=i<=k и X_j из N для 1<=j<=k. Вершина n имеет потомков n₁,...,n_k, которые соответствуют нетерминалам X₁,...,X_k. Значения атрибутов стоимости вычисляются в порядке снизу вверх. Вначале атрибуты стоимости инициализируются неопределенным значением UndefinedValue. Предположим, что значения атрибутов стоимости для всех потомков n₁,...,n_k вершины 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]))

{ВычислитьАтрибутыСтоимостиДля(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₀ X₀ z₁...X_k z_k, связанное с указанной вершиной n, и заданный нетерминал A, чтобы определить соответствующие им вершины n₁,...,n_k и нетерминалы X₁,...,X_k. Затем вычислитель рекурсивно обходит каждую вершину n_i, имея на входе нетерминал X_i.

171