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

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


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


См. также ''Атрибутное вычисление, Граф составной зависимости, Задача трансляции''.
==См. также==
 
* ''[[Атрибутное вычисление]],''
* ''[[Граф составной зависимости]],''
* ''[[Задача трансляции]].''
==Литература==
==Литература==
[Евстигнеев-Касьянов/98]
 
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.

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

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

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

См. также

Литература

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