Атрибутное вычисление

Атрибутное вычисление (Attribute evaluation) — эффективность использования атрибутных грамматик во многом зависит от способа решения задачи А.в. — нахождения значений атрибутов [math]\displaystyle{ W(t) }[/math] для атрибутного дерева [math]\displaystyle{ t }[/math] заданной атрибутной грамматики. Первый шаг, который нужно при этом сделать, состоит в определении порядка (плана или стратегии) вычисления — такого линейного порядка [math]\displaystyle{ T(t) }[/math] на [math]\displaystyle{ W(t) }[/math], который не противоречит графу зависимости атрибутов дерева [math]\displaystyle{ t }[/math]. В случае, когда грамматика корректна, указанная задача для заданного [math]\displaystyle{ t }[/math] является задачей топологической сортировки, допускающей эффективное решение.

Алгоритм заполнения атрибутных деревьев может предполагать, что выбор стратегии заполнения и собственно вычисление по этой стратегии осуществляются динамически, во время работы транслятора, построенного с помощью атрибутной грамматики, либо статически, т.е. до работы транслятора. Они могут быть как детерминированными, так и недетерминированными, предполагающими произвольный порядок вычисления значений активных (т.е. тех, которые могут быть вычислены в данный момент) вхождений атрибутов в атрибутное дерево. Условия задержки (соответственно активации) вхождения атрибута определяются отсутствием (соответственно наличием) значений аргументов семантического правила, вычисляющего значение данного вхождения атрибута. Таким образом, если граф зависимости атрибутов дерева ациклический, то, начиная с присваивания константного значения некоторому атрибуту, не имеющему заходящих дуг в графе зависимостей, может происходить заполнение всего атрибутного дерева в порядке, зависящем от предыдущих вычислений.

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

После того как план вычисления [math]\displaystyle{ T(t) }[/math] найден, возможны два варианта его использования: вычислять, начиная с минимальных элементов, либо от максимальных элементов в отношении. Вычислители первого типа называются восходящими (снизу вверх или управляемыми данными), а второго — нисходящими (сверху вниз или управляемыми запросами).

Литература

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.