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