Атрибутное вычисление: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
GPN (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
'''Атрибутное вычисление''' (''[[Attribute evaluation]]'') | '''Атрибутное вычисление''' (''[[Attribute evaluation]]'') — эффективность использования [[атрибутная грамматика|''атрибутных грамматик'']] во многом зависит от способа решения задачи '''А.в.''' — нахождения значений атрибутов <math>W(t)</math> для [[атрибутное дерево|''атрибутного дерева'']] <math>t</math> заданной атрибутной грамматики. Первый шаг, | ||
который нужно при этом сделать, состоит в определении ''порядка'' (''плана'' или ''стратегии'') ''вычисления'' | который нужно при этом сделать, состоит в определении ''порядка'' (''плана'' или ''стратегии'') ''вычисления'' — такого линейного порядка <math>T(t)</math> на <math>W(t)</math>, который не | ||
противоречит [[графу зависимости атрибутов]] [[дерево|дерева]] <math>t</math>. В | противоречит [[граф зависимости атрибутов|графу зависимости атрибутов]] [[дерево|дерева]] <math>t</math>. В | ||
случае, когда [[грамматика]] ''[[корректная атрибутная грамматика|корректна]]'', указанная задача | случае, когда [[грамматика]] ''[[корректная атрибутная грамматика|корректна]]'', указанная задача | ||
для заданного <math>t</math> является задачей [[топологическая сортировка|''топологической сортировки'']], допускающей эффективное решение. | для заданного <math>t</math> является задачей [[топологическая сортировка|''топологической сортировки'']], допускающей эффективное решение. | ||
| Строка 11: | Строка 11: | ||
Детерминированные алгоритмы, в которых порядок заполнения атрибутного дерева фиксируется до начала вычисления атрибутов, разделяются на алгоритмы ''с жесткой стратегией'', в которых порядок заполнения один и тот же для всех атрибутных деревьев, и алгоритмы ''с гибкой стратегией'', в которых порядок заполнения определяется для конкретного атрибутного дерева. | Детерминированные алгоритмы, в которых порядок заполнения атрибутного дерева фиксируется до начала вычисления атрибутов, разделяются на алгоритмы ''с жесткой стратегией'', в которых порядок заполнения один и тот же для всех атрибутных деревьев, и алгоритмы ''с гибкой стратегией'', в которых порядок заполнения определяется для конкретного атрибутного дерева. | ||
После того как план вычисления <math>T(t)</math> найден, возможны два варианта его использования: вычислять, начиная с минимальных элементов | После того как план вычисления <math>T(t)</math> найден, возможны два варианта его использования: вычислять, начиная с минимальных элементов либо от максимальных элементов в отношении. | ||
Вычислители первого типа называются ''восходящими'' (''снизу вверх'' или ''управляемыми данными''), а второго | Вычислители первого типа называются ''восходящими'' (''снизу вверх'' или ''управляемыми данными''), а второго — ''нисходящими'' (''сверху вниз'' или ''управляемыми | ||
запросами''). | запросами''). | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998. | |||
Текущая версия от 15:30, 9 июля 2015
Атрибутное вычисление (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.