Алгоритм. Построение ДАГ по синтаксическому дереву

Вход

Синтаксическое дерево

Выход

ДАГ

Идея

Проходим дерево снизу вверх и, включая дедупликацию узлов

Алгоритм

/** Узел исходного синтаксического дерева */
public interface ParseNode {
	/**
	 * Имя операции или идентификатор/константа
	 */
    String op();
    /**
     * Дети (может быть пустым списком)
     */
    List<ParseNode> children();
}
 

import java.util.*;
 
public final class DagNode {
 
    private final String op;
    private final List<DagNode> children;
 
    public DagNode(String op, List<DagNode> children) {
        this.op = op;
        this.children = List.copyOf(children);
    }
 
    public String op() { return op; }
    public List<DagNode> children() { return children; }
 
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof DagNode node)) return false;
        return op.equals(node.op) && children.equals(node.children);
    }
 
    @Override
    public int hashCode() {
        return Objects.hash(op, children);
    }
 
    @Override
    public String toString() {
        return op + children;
    }
}

import java.util.*;
 
public final class DagBuilder {
 
    /** Таблица уникальных узлов DAG */
    private final Map<DagNode, DagNode> unique = new HashMap<>();
 
	/**
	 * @param root синтаксическое дерево
	 */
    public DagNode build(ParseNode root) {
        return buildRecursively(root);
    }
 
    private DagNode buildRecursively(ParseNode node) {
        // Рекурсивно строим DAG для всех детей
        List<DagNode> childDags = new ArrayList<>();
        for (ParseNode child : node.children()) {
            childDags.add(buildRecursively(child));
        }
 
        // Создаём узел-кандитат в DAG
        DagNode candidate = new DagNode(node.op(), childDags);
 
        // Проверяем есть ли уже такой узел
        DagNode existing = unique.get(candidate);
        if (existing != null) {
            // используем существующий узел
            return existing;
        }
 
		// Добавляем узел-кандидат в таблицу
        unique.put(candidate, candidate);
        return candidate;
    }
}