Атрибутное дерево: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Атрибутное дерево''' (''[[Attribute tree]]'') | '''Атрибутное дерево''' (''[[Attribute tree]]'') — [[дерево вывода]] в ''[[КС-Грамматика|КС-грамматике]]'' <math>G</math>, [[вершина|вершины]] которого помечены соответствующими атрибутами ''[[атрибутная грамматика|атрибутной грамматики]]'' с основой <math>G</math>. '''Атрибутное дерево''' называется заполненным, если каждому его атрибуту присвоено некоторое конкретное значение. | ||
Правила вычисления атрибутов, составляющие атрибутную грамматику, определяют, как и по значениям каких атрибутов данной вершины и атрибутов ее соседей в [[дерево|дереве]] ([[отец вершины ордерева|отца]], [[сын|сыновей]] и [[брат вершины v|братьев]]) можно вычислить тот или иной ее атрибут. При этом для любой вершины дерева значения ее [[синтезируемый атрибут|синтезируемых атрибутов]] вычисляются без использования атрибутов ее отца и братьев, а значения [[наследуемый атрибут|наследуемых]] | Правила вычисления атрибутов, составляющие атрибутную грамматику, определяют, как и по значениям каких атрибутов данной вершины и атрибутов ее соседей в [[дерево|дереве]] ([[отец вершины ордерева|отца]], [[сын|сыновей]] и [[брат вершины v|братьев]]) можно вычислить тот или иной ее атрибут. При этом для любой вершины дерева значения ее [[синтезируемый атрибут|синтезируемых атрибутов]] вычисляются без использования атрибутов ее отца и братьев, а значения [[наследуемый атрибут|наследуемых]] — без использования атрибутов ее сыновей. | ||
Таким образом, значениями синтезируемых атрибутов информация передается по дереву снизу вверх, что позволяет синтезировать внутренний контекст для [[корень|корня]] любого [[поддерево|поддерева]]. Наследуемые атрибуты переносят информацию по дереву сверху вниз и позволяют определять внешний контекст корня любого поддерева. | Таким образом, значениями синтезируемых атрибутов информация передается по дереву снизу вверх, что позволяет синтезировать внутренний контекст для [[корень|корня]] любого [[поддерево|поддерева]]. Наследуемые атрибуты переносят информацию по дереву сверху вниз и позволяют определять внешний контекст корня любого поддерева. | ||
| Строка 11: | Строка 11: | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. | * Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998. | ||
Текущая версия от 16:24, 18 ноября 2010
Атрибутное дерево (Attribute tree) — дерево вывода в КС-грамматике [math]\displaystyle{ G }[/math], вершины которого помечены соответствующими атрибутами атрибутной грамматики с основой [math]\displaystyle{ G }[/math]. Атрибутное дерево называется заполненным, если каждому его атрибуту присвоено некоторое конкретное значение.
Правила вычисления атрибутов, составляющие атрибутную грамматику, определяют, как и по значениям каких атрибутов данной вершины и атрибутов ее соседей в дереве (отца, сыновей и братьев) можно вычислить тот или иной ее атрибут. При этом для любой вершины дерева значения ее синтезируемых атрибутов вычисляются без использования атрибутов ее отца и братьев, а значения наследуемых — без использования атрибутов ее сыновей. Таким образом, значениями синтезируемых атрибутов информация передается по дереву снизу вверх, что позволяет синтезировать внутренний контекст для корня любого поддерева. Наследуемые атрибуты переносят информацию по дереву сверху вниз и позволяют определять внешний контекст корня любого поддерева.
См. также
Литература
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.