Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 24
Текст из файла (страница 24)
Мы предполагаем, что в грамматикенет циклов в применении цепных правил. Построение всех вариантованализа для T-грамматики дано ниже в алгоритме 8.1. Тип Titem валгоритме 8.1 ниже служит для описания ситуаций (т.е. правил вывода ипозиции внутри правила). Тип Tterminal - это тип терминального символаграмматики, тип Tproduction - тип для правила вывода.Алгоритм 8.1:Tterminal a[n];setofTproduction r[n];int l[n];// l[i] - длина a[i]-выраженияTitem h;// используется при поиске правил,//сопоставимых с текущей подцепочкой// Предварительные вычисленияДля каждой позиции i вычислить длину a[i]-выражения l[i];// Распознование входной цепочкиfor (int i=n-1;i>=0;i--){for (для каждого правила A -> a[i] y из P){//считаем,что l[i]=0 для символов-не знаков//операцийint j;if (l[i]>0){j=i+1;h=[A->a[i].y];do //Сопоставимы ли a[i]y и a[i]..a[i+l[i]-1]{Пусть h==[A->u.Xv]if(X в T)if (X==a[j]) j=j+1; else break;else // X в Nif (X->w в r[j]) j=j+l[j];else break;h=[A->uX.v];}// Перейти к следующему символу161while( j!=i+l[i]);r[i]=r[i]+{(A->a[i]y)};}//for// Проверить цепные правилаwhile (существует правило C->A из P такое, чтоимеется некоторый элемент (A->w) в r[i]и нет элемента (C->A) в r[i])r[i]=r[i]+{(C->A)};Проверить, принадлежит ли (S->w) множеству r[0];r[i]={A->aiV1...Vm}1aiml[i]Рис.
8.32Работа алгоритма иллюстрируется рис. 8.32. Множества r[i] имеютразмер O(|P|). Очевидно, что алгоритм имеет временную и емкостнуюсложность O(n).Рассмотрим вновь пример рис. 8.29. В префиксной записиприведенный фрагмент программы записывается следующим образом:=+ax+@++by@+iz5На рис. 8.33 приведен результат работы алгоритма. Правилавычисления стоимости приведены в разделе 8.9.3.162Операция Длина Правила(стоимость=+ax+@++by@+iz514200987200320002(22)4(5)1(2)1(2)4(16)7(13)5(15)4(5)1(2)1(2)3(6)4(5)1(2)1(2)1(2)5(6)5(17)6(11)5(6)7(7)5(6)Рис. 8.33Пусть G - это T-грамматика. Для каждой цепочки z из L(G) можнопостроить дерево выражения.
Мы можем переписать алгоритм так, чтобыон работал с деревьями выражений, а не с префиксными выражениями.Этот вариант алгоритма приведен ниже. В этом алгоритме деревовыражения обходится сверху вниз и в нем ищутся поддеревья,сопоставимые с правыми частями правил из G. Обход дереваосуществляется процедурой PARSE. После обхода поддерева даннойвершины в ней применяется процедура MATCHED, которая пытаетсянайти все образцы, сопоставимые поддереву данной вершины.
Для этогокаждое правило-образец разбивается на компоненты в соответствии свстречающимися в нем операциями. Дерево обходится справа налевотолько для того, чтобы иметь соответствие с порядком вычисления валгоритме 8.1. Очевидно, что можно обходить дерево вывода и слеванаправо.Структура данных, представляющая вершину дерева, имеетследующую форму:struct Tnode {Tterminal op;Tnode * son[MaxArity];setofTproduction RULEs;};В комментариях указаны соответствующие фрагменты алгоритма8.1.163Алгоритм 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]==0if (X==n->op) //if X==a[j]return(true);else return(false);else // if l[i]>0if (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);}//matchvoid PARSE(Tnode * n);{//PARSEfor (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= указатель дерева выражения;164// Распознать входную цепочкуPARSE(root);Проверить, входит ли во множество root->RULEsправило с левой частью S;}Выходом алгоритма является дерево выражения для z, вершинамкоторого сопоставлены применимые правила.
Если T-грамматиканеоднозначная, то можно построить несколько различных выводов длязаданной входной цепочки.Алгоритмы 8.1 и 8.2 "универсальные" в том смысле, что конкретныеграмматики выражений и образцов являются, по-существу, параметрамиэтих алгоритмов. Для каждой конкретной грамматики можно написатьсвой алгоритм поиска образцов.
Например, в случае нашей грамматикивыражений и приведенных на рис. 8.30 образцов алгоритм 8.2 может бытьпредставлен атрибутной грамматикой, приведенной ниже. Для каждогоправила имеется два типа образцов: "внутренние", соответствующиеправилам-образцам, и "внешние", приходящие сверху через атрибут Matchпредка. Атрибут Match представлен как вектор образцов вида <Pattern 1, ...Patternn>. Каждый из образцов имеет вид либо <op op-list>, где op операция в данной вершине, а op-list - список ее операндов, либо образец это нетерминал N. В первом случае op-list "распределяется" по потомкамвершины для дальнейшего сопоставления, во втором сопоставлениесчитается успешным, если есть правило N->w, где w - состоит из образцов,успешно сопоставленных потомкам данной вершины. Помимо атрибутаMatch, образцы могут задаваться и в соответствии с правилами, возможноприменимыми в данной вершине.
Эти два множества образцов могутпересекаться. Синтезируемый атрибут Pattern (также вектор) даетрезультат сопоставления по вектору-образцу Match.RULEStat ::= '=' Expr Expr/*Этому правилу соответствует один образец 2. Поэтому в качествеобразцов потомков через их атрибуты Match передаются, соответственно,<'+' Reg Const> и <Reg>.*/SEMANTICSMatch<2>=<'+' Reg Const>:Match<3>=<Reg>;Pattern<0>[1]=Pattern<2>[1]&Pattern<3>[1].RULEExpr ::= '+' Expr Expr165/*Образцы, соответствующие этому правилу, следующие:(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.*/SEMANTICSMatch<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.RULEExpr ::= '@' Expr/*Образцы, соответствующие этому правилу, следующие:(3) Reg -> '@' '+' Reg Const(7) Reg -> '@' RegСоответственно, атрибуту Match второго символа в качествеобразцов при сопоставлении могут быть переданы <'+' Reg Const>(образец 3) или <Reg> (образец 7).Из анализа других правил можно заключить, что при сопоставленииобразцов предков левой части данного правила атрибуту Match могут бытьпереданы образцы <'@' '+' Reg Const> (из образца 6) и Reg.*/SEMANTICSMatch<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.166RULEExpr ::= ConstSEMANTICSif (Pattern<0> содержит Const в j-й позиции)Pattern<0>[j]=true;Остальным значениям Pattern<0> присвоить false.Для дерева рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
