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