Дэг выражения

Материал из WikiGrapp
Перейти к:навигация, поиск

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


Литература

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