Атрибутное вычисление: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Атрибутное вычисление''' (''Attribute evaluation'') - эффективность использования ''ат...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 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> является задачей [[топологическая сортировка|''топологической сортировки'']], допускающей эффективное решение.
который нужно при этом сделать, состоит в определении {\it
порядка} (''плана'' или ''стратегии'') ''вычисления''
--- такого линейного порядка <math>T(t)</math> на <math>W(t)</math>, который не
противоречит графу зависимости атрибутов дерева <math>t</math>. В
случае, когда грамматика ''корректна'', указанная задача
для заданного <math>t</math> является задачей ''топологической
сортировки'', допускающей эффективное решение.


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


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


После того как план вычисления <math>T(t)</math> найден, возможны два
После того как план вычисления <math>T(t)</math> найден, возможны два варианта его использования: вычислять, начиная с минимальных элементов, либо от максимальных элементов в отношении.
варианта его использования: вычислять, начиная с минимальных
Вычислители первого типа называются ''восходящими'' (''снизу вверх'' или ''управляемыми данными''), а второго ''нисходящими'' (''сверху вниз'' или ''управляемыми
элементов, либо от максимальных элементов в отношении.
Вычислители первого типа называются ''восходящими''  
(''снизу вверх'' или ''управляемыми данными''), а второго ---
''нисходящими'' (''сверху вниз'' или ''управляемыми
запросами'').  
запросами'').  
==Литература==
==Литература==
[Евстигнеев-Касьянов/98]
 
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.

Текущая версия от 16:22, 18 ноября 2010

Атрибутное вычисление (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.