Атрибутное дерево

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

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

См. также

• Атрибутное вычисление,
• Граф составной зависимости,
• Задача трансляции.

Литература

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