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

Вход

Дерево вывода слова, построенное по операторной грамматике $G$

Выход

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

Алгоритм

1. Листья дерева, помеченные терминалами, которые соответствуют какой-то операции в исходной грамматике $G$, удаляются. Соответствующие операторные терминалы связываются с родительской вершиной
2. Вершины дерева, соответствующие цепным правилам, “выводящих” в итоге $a\in \Sigma$ сворачиваются в одну вершину и помечаются $a$