4625
правок
Glk (обсуждение | вклад) (Создана новая страница размером '''Атрибутное вычисление''' (''Attribute evaluation'') - эффективность использования ''ат...) |
KEV (обсуждение | вклад) Нет описания правки |
||
Строка 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>W(t)</math> для ''атрибутного | случае, когда [[грамматика]] ''[[корректная атрибутная грамматика|корректна]]'', указанная задача | ||
дерева'' <math>t</math> заданной атрибутной грамматики. Первый шаг, | для заданного <math>t</math> является задачей [[топологическая сортировка|''топологической сортировки'']], допускающей эффективное решение. | ||
который нужно при этом сделать, состоит в определении | |||
порядка | |||
--- такого линейного порядка <math>T(t)</math> на <math>W(t)</math>, который не | |||
противоречит графу зависимости атрибутов дерева <math>t</math>. В | |||
случае, когда грамматика ''корректна'', указанная задача | |||
для заданного <math>t</math> является задачей ''топологической | |||
сортировки'', допускающей эффективное решение. | |||
Алгоритм заполнения атрибутных деревьев может предполагать, | [[Алгоритм]] заполнения атрибутных деревьев может предполагать, что выбор стратегии заполнения и собственно вычисление по этой стратегии осуществляются ''динамически'', во время работы транслятора, построенного с помощью атрибутной грамматики, либо ''статически'', т.е. до работы | ||
что выбор стратегии заполнения и собственно вычисление по | транслятора. Они могут быть как ''детерминированными'', так и ''недетерминированными'', предполагающими произвольный порядок вычисления значений ''активных'' (т.е. тех, которые могут быть вычислены в данный момент) вхождений атрибутов в атрибутное дерево. Условия задержки | ||
этой стратегии осуществляются ''динамически'', во время | (соответственно активации) вхождения атрибута определяются отсутствием (соответственно наличием) значений аргументов семантического правила, вычисляющего значение данного вхождения атрибута. Таким образом, если ''граф зависимости атрибутов'' дерева ациклический, то, начиная с присваивания константного значения некоторому атрибуту, не имеющему заходящих [[дуга|дуг]] в [[граф|графе]] зависимостей, может происходить заполнение всего атрибутного дерева в порядке, зависящем от предыдущих вычислений. | ||
работы транслятора, построенного с помощью атрибутной | |||
грамматики, либо ''статически'', т.е. до работы | |||
транслятора. Они могут быть как ''детерминированными'', | |||
так и ''недетерминированными'', предполагающими | |||
произвольный порядок вычисления значений ''активных'' | |||
(т.е. тех, которые могут быть вычислены в данный момент) | |||
вхождений атрибутов в атрибутное дерево. Условия задержки | |||
(соответственно активации) вхождения атрибута определяются | |||
отсутствием (соответственно наличием) значений аргументов | |||
семантического правила, вычисляющего значение данного | |||
вхождения атрибута. Таким образом, если ''граф | |||
зависимости атрибутов'' дерева ациклический, то, начиная с | |||
присваивания константного значения некоторому атрибуту, не | |||
имеющему заходящих дуг в графе зависимостей, может | |||
происходить заполнение всего атрибутного дерева в порядке, | |||
зависящем от предыдущих вычислений. | |||
Детерминированные алгоритмы, в которых порядок заполнения | Детерминированные алгоритмы, в которых порядок заполнения атрибутного дерева фиксируется до начала вычисления атрибутов, разделяются на алгоритмы ''с жесткой стратегией'', в которых порядок заполнения один и тот же для всех атрибутных деревьев, и алгоритмы ''с гибкой стратегией'', в которых порядок заполнения определяется для конкретного атрибутного дерева. | ||
атрибутного дерева фиксируется до начала вычисления | |||
атрибутов, разделяются на алгоритмы ''с жесткой | |||
стратегией'', в которых порядок заполнения один и тот же для | |||
всех атрибутных деревьев, и алгоритмы ''с гибкой | |||
стратегией'', в которых порядок заполнения определяется для | |||
конкретного атрибутного дерева. | |||
После того как план вычисления <math>T(t)</math> найден, возможны два | После того как план вычисления <math>T(t)</math> найден, возможны два варианта его использования: вычислять, начиная с минимальных элементов, либо от максимальных элементов в отношении. | ||
варианта его использования: вычислять, начиная с минимальных | Вычислители первого типа называются ''восходящими'' (''снизу вверх'' или ''управляемыми данными''), а второго --- ''нисходящими'' (''сверху вниз'' или ''управляемыми | ||
элементов, либо от максимальных элементов в отношении. | |||
Вычислители первого типа называются ''восходящими'' | |||
(''снизу вверх'' или ''управляемыми данными''), а второго --- | |||
''нисходящими'' (''сверху вниз'' или ''управляемыми | |||
запросами''). | запросами''). | ||
==Литература== | ==Литература== | ||
[Евстигнеев-Касьянов/98] | [Евстигнеев-Касьянов/98] |