Теория и реализация языков программирования



             

Атрибутная схема для алгоритма сопоставления образцов


Алгоритмы 9.5 и 9.6 являются "универсальными" в том смысле, что конкретные грамматики выражений и образцов являются, по-существу, параметрами этих алгоритмов. В то же время, для каждой конкретной грамматики можно написать свой алгоритм поиска образцов. Например, в случае нашей грамматики выражений и приведенных на рис. 9.25

образцов алгоритм 9.6 может быть представлен атрибутной грамматикой, приведенной ниже.

Наследуемый атрибут Match содержит упорядоченный список (вектор) образцов для сопоставления в поддереве данной вершины. Каждый из образцов имеет вид либо <op op-list> (op - операция в данной вершине, а op- list - список ее операндов), либо представляет собой нетерминал N. В первом случае op-list "распределяется" по потомкам вершины для дальнейшего сопоставления. Во втором случае сопоставление считается успешным, если есть правило N

op fPatig, где w состоит из образцов, успешно сопоставленных потомкам данной вершины. В этом случае по потомкам в качестве образцов распределяются элементы правой части правила. Эти два множества образцов могут пересекаться. Синтезируемый атрибут Pattern - вектор логических значений, дает результат сопоставления по вектору-образцу Match.

Таким образом, при сопоставлении образцов могут встретиться два случая:

  1. Вектор образцов содержит образец <op fPatig>, где op - операция, примененная в данной вершине. Тогда распределяем образцы Pati по потомкам и сопоставление по данному образцу считаем успешным (истинным), если успешны сопоставления элементов этого образца по всем потомкам.
  2. Образцом является нетерминал N. Тогда рассматриваем все правила вида N
    op fPatig. Вновь распределяем образцы Pati по потомкам и сопоставление считаем успешным (истинным), если успешны сопоставления по всем потомкам. В общем случае успешным может быть сопоставление по нескольким образцам.

Отметим, что в общем случае в потомки одновременно передается неско-лько образцов для сопоставления. В приведенной ниже атрибутной схеме не рассматриваются правила выбора покрытия наименьшей стоимости (см.


Содержание  Назад  Вперед