Атрибуты - это дополнительные значения, связанные с чем-то центральным.В случае AST вы можете рассматривать их как пары (attribute_name, attribute_value), связанные с каждым узлом AST, где имя атрибута соответствует некоторому интересному типу факта, а значение атрибута соответствует фактическому состоянию этого факта (например,, "(constants_in_subtree_count, 12)").
Унаследовано и синтезировано - это термины для описания того, как значения атрибута вычисляются для каждого узла AST, обычно связанные сПравило грамматики, которое создает узел AST, используя его дочерние элементы.
Синтезированные атрибуты - это атрибуты, значение которых вычисляется из значений атрибутов дочерних узлов и передаются up дерево.Часто значения синтезированных атрибутов объединяются, чтобы создать атрибут для родительского узла.Если у узла AST есть два дочерних элемента, каждый из которых имеет свои собственные атрибуты (constants_in_subtree_count, 5) и (constants_in_subtree_count, 7), то путем передачи этих атрибутов родительский объект может вычислить свой соответствующий атрибут (constants_in_subtree_count, 12).
Унаследованные атрибуты - это те, которые передаются от родителя к потомку.Если корень функции AST «знает», что тип возвращаемого значения функции (return_type, integer) в качестве атрибута, он может передать тип возвращаемого значения дочерним элементам корня функции, например, в тело функции.Где-то глубоко в этом дереве есть реальное выражение возврата;если он получает унаследованный атрибут (return_type, X), он может проверить, что вычисляемый результат имеет правильный тип.
На практике вы хотите иметь возможность определять произвольные наборы атрибутов для узлов, ипередавать их вверх и вниз по дереву для нескольких целей, необходимых для обработки AST (создание таблиц символов, построение потоковых графов управления, проверка типов, вычисление метрик и т. д.).Генератор грамматики атрибута является своего рода генератором синтаксического анализатора, который будет принимать грамматические правила, наборы определений атрибутов и правила о том, как вычислять синтезированные и унаследованные атрибуты для узлов, участвующих в каждом правиле.и генерирует как анализатор, так и AST-обходчик, который вычисляет все атрибуты.
Ценность этой идеи в том, что она обеспечивает принцип организации, поддерживаемый автоматизацией, который можно использовать для вычисления многих интересных вещей о AST вобычный способ.В противном случае вы можете закодировать все эти вещи, используя специальный код.
Наш DMS Software Reengineering Toolkit - это система манипулирования AST (на самом деле преобразования программы от источника к источнику), которая интенсивно использует параллельная оценка атрибута для вычисления всех видов полезного анализа по AST: обычные метрики, таблицы символов, проверки типов (как описанная выше проверка типа возврата), контроль и извлечение потока данных из кода, а также другие не-легко описываемые, но полезные результаты, вычисленные по поддеревьям («список побочных эффектов в этом выражении»).Почему параллельно?Что ж, вычисления атрибутов в поддеревьях по существу независимы, поэтому параллелизм уже есть, и когда вы имеете дело с действительно большими деревьями, производительность имеет значение.DMS часто имеет дело с тысячами единиц компиляции, каждая из которых производит (возможно, большой) AST.