Атрибутная схема для алгоритма сопоставления образцов
Алгоритмы 9.1 и 9.2 являются «универсальными» в том смысле, что конкретные грамматики выражений и образцов являются, по-существу, параметрами этих алгоритмов. В то же время, для каждой
конкретной грамматики можно написать свой алгоритм поиска образцов. Например, в случае нашей грамматики выражений и приведенных на рис. 9.16 образцов алгоритм 9.2 может быть представлен атрибутной грамматикой, приведенной ниже.
Наследуемый атрибут Match содержит упорядоченный список (вектор) образцов для сопоставления в поддереве данной вершины. Каждый из образцов имеет вид либо <op op-list> (op - операция в данной вершине, а op-list - список ее операндов), либо представляет
собой нетерминал N. В первом случае op-list «распределяется» по потомкам вершины для дальнейшего сопоставления. Во втором случае сопоставление считается успешным, если есть правило N
сопоставления по вектору-образцу Match.
Таким образом, при сопоставлении образцов могут встретиться два случая:
- Вектор образцов содержит образец <op {Pati}>, где op - операция, примененная в данной вершине. Тогда распределяем образцы Pati по потомкам и сопоставление по данному образцу считаем успешным (истинным), если успешны сопоставления элементов этого образца по всем потомкам.
- Образцом является нетерминал N. Тогда рассматриваем все правила вида N op {Pati}. Вновь распределяем образцы Pati по потомкам и сопоставление считаем успешным
(истинным), если успешны сопоставления по всем потомкам. В общем случае успешным может быть сопоставление по нескольким образцам.
Отметим, что в общем случае в потомки одновременно передается несколько образцов для сопоставления.
В приведенной ниже атрибутной схеме не рассматриваются правила выбора покрытия наименьшей стоимости (см.
предыдущий раздел). Выбор оптимального покрытия может быть сделан еще одним проходом по дереву, аналогично тому, как это было сделано
выше. Например, в правиле с '+' имеется несколько образцов для Reg, но реального выбора одного из них не осуществляется. Кроме того, не уточнены некоторые детали реализации. В частности, конкретный способ формирования векторов Match и Pattern. В тексте употребляется термин «добавить», что означает добавление к вектору образцов очередного элемента. Векторы образцов записаны в угловых скобках.
|
RULE Stat ::= '=' Reg Reg SEMANTICS Match=; Match=; Pattern[1]=Pattern[1]&Pattern[1]. |
|
RULE Reg ::= '+' Reg Reg SEMANTICS if (Match содержит Reg в позиции i) {Match=; Match=>; } if (Match содержит образец в позиции j) {добавить Reg к Match в некоторой позиции k; добавить Const к Match в некоторой позиции k; } if (Match содержит образец в позиции j) Pattern[j]=Pattern[k]&Pattern[k]; if (Match[0] содержит Reg в i-й позиции) Pattern[i]=(Pattern[1]&Pattern[1]) |(Pattern[2]&Pattern[2]) |(Pattern[3]&Pattern[3]). |
(4) Reg
(5) Reg
(6) Reg
Атрибутам Match второго и третьего символов в качестве образцов при сопоставлении могут быть переданы векторы и >, соответственно. Из анализа других
правил можно заключить, что при сопоставлении образцов предков левой части данного правила атрибуту Match символа левой части может быть передан образец
(из образцов 2, 3, 6) или образец Reg.
|
RULE Reg ::= '@' Reg SEMANTICS if (Match содержит Reg в i-й позиции) Match=,Reg>; if (Match содержит в j-й позиции) добавить к Match в k позиции; if (Match содержит Reg в i-й позиции) Pattern[i]=Pattern[1]|Pattern[2]; if (Match содержит в j-й позиции) Pattern[j]=Pattern[k]. |
|
(3) Reg
(7) Reg
Соответственно, атрибуту Match второго символа в качестве образцов при сопоставлении могут быть переданы (образец 3) или
(образец 7). Из анализа других правил можно заключить, что при сопоставлении образцов предков
левой части данного правила атрибуту Match могут быть переданы образцы
(из образца 6) и Reg.
|
RULE Reg ::= Const SEMANTICS if (Pattern содержит Const в j-й позиции) Pattern[j]=true; if (Pattern содержит Reg в i-й позиции) Pattern[i]=true. |
