Что НРХОМ являются:
Устройства AST представляет собой структуру данных, представляющую исходный программный текст, который состоит из узлов, которые содержат узла типа а, и, возможно, буквенное значение, и список дочерних узлов. Тип узла соответствует тому, что OP вызывает «операции» (+, -, ...), но также включает в себя языковые команды (do, if, assign, call, ...), declarations (int, struct, ...) и литералы (число, строка, булево). [Неясно, какой OP означает «тип»]. (АСТ часто имеют дополнительную информацию в каждом узле, ссылаясь на исходную точку в исходном текстовом файле).
Каких НРХИ предназначены для:
OP кажется озадачен наличием НРХА в Eclipse.
АСТ используются для представления текста программы в форме, которая легче интерпретировать, чем исходный текст. Они обеспечивают средство для определения структуры или контента программы; иногда они используются для включения модификации программы («рефакторинг») путем изменения АСТ для программы, а затем восстановления текста из АСТ.
Сравнение AST для сходства не очень распространено в моем опыте, за исключением обнаружения клона и/или соответствия шаблонов.
Сравнение НРХА:
Сравнения НРХА для равенства легко: сравнить/буквальное значение типа корневого узла для обеспечения равенства; если не равно, сравнение завершено, иначе (рекурсивно) сравнивают дочерние узлы).
Сравнение АСТ схожести сложнее, потому что вы должны решить, как смягчить сравнение равенства. В частности, вы должны принять решение о точном определении сходства. Есть много способов определить это, некоторые довольно мелкие синтаксически, некоторые более семантически сложные.
В моей статье Clone Detection Using Abstract Syntax Trees описывается один из способов сделать это, используя подобие, определяемое как отношение количества разделяемых узлов, разделенное на количество узлов, общее количество в обоих деревьях. Общие узлы вычисляются путем сравнения деревьев сверху вниз с точкой, где какой-то ребенок отличается. (Фактическое сравнение - это вычисление антиунификатора). Эта подобная мера довольно мелкая, но она отлично работает в поиске клонов кода в больших программных системах.
С этой точки зрения, OPS примеры: игровая
int x = 1 + 2
String y = "1" + "2"
есть деревья, написанные, как S-выражения:
(declaration_with_assignment (int x) (+ 1 2))
(declaration_with_assignment (String y) (+ "1" "2"))
Это не очень похожи; они разделяют только корневой узел, тип которого - «объявление с назначением» и верхняя часть поддерева +. (Здесь число узлов составляет 12 с только двумя совпадающими узлами для подобия 2/12).
Они будут больше похожи:
int x = 1 + 2
float x = 1.0 + 2
(S-выражения)
(declaration_with_assignment (int x) (+ 1 2))
(declaration_with_assignment (float x) (+ 1.0 2))
которые разделяют заявление с назначением, надстройку узел, буквальное лист узел 2, и, возможно, в буквальном смысле узлы для integer 1 и float 1.0, в зависимости от того, хотите ли вы определить их как «равные» или нет, для подобия 4/12.
Если вы меняете одно из деревьев на дерево шаблонов, в котором некоторые «листья» являются переменными шаблона, вы можете использовать такие деревья шаблонов для поиска кода, который имеет определенную структуру.
Шаблон синтаксиса Поверхность:
?type ?variable = 1 + ?expression
с S-выражение
((declaration_with_assignment (?type ?varaible)) (+ 1 ?expression))
соответствует первым из примеров OP, но не второй.
Насколько я знаю, Eclipse не предлагает никаких способностей, основанных на шаблонах. Но они очень полезны в средствах анализа программ и/или программ. Для некоторых конкретных примеров, которые слишком долго для включения здесь, см. DMS Rewrite Rules
(Полное раскрытие: DMS - продукт моей компании. Я архитектор).