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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Атрибутное дерево''' (''[[Attribute tree]]'') - [[дерево вывода]] в ''[[КС-Грамматика|КС-грамматике]]'' <math>G</math>, [[вершина|вершины]] которого помечены соответствующими атрибутами ''[[атрибутная грамматика|атрибутной грамматики]]'' с основой <math>G</math>. '''А.д.''' называется заполненным, если каждому его атрибуту присвоено некоторое конкретное значение.
'''Атрибутное дерево''' (''[[Attribute tree]]'') [[дерево вывода]] в ''[[КС-Грамматика|КС-грамматике]]'' <math>G</math>, [[вершина|вершины]] которого помечены соответствующими атрибутами ''[[атрибутная грамматика|атрибутной грамматики]]'' с основой <math>G</math>. '''Атрибутное дерево''' называется заполненным, если каждому его атрибуту присвоено некоторое конкретное значение.


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


Строка 11: Строка 11:
==Литература==
==Литература==


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

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

Атрибутное дерево (Attribute tree) — дерево вывода в КС-грамматике [math]\displaystyle{ G }[/math], вершины которого помечены соответствующими атрибутами атрибутной грамматики с основой [math]\displaystyle{ G }[/math]. Атрибутное дерево называется заполненным, если каждому его атрибуту присвоено некоторое конкретное значение.

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

См. также

Литература

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