Дэг выражения: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Дэг выражения''' (Expression DAG) --- вид [[(Абстрактное) синтаксическое представл...)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Дэг выражения''' ([[Expression DAG]]) ---
'''Дэг выражения''' ([[Expression DAG]])
вид [[(Абстрактное) синтаксическое представление|''абстрактного синтаксического представления'']]
вид [[(Абстрактное) синтаксическое представление|''абстрактного синтаксического представления'']]
выражения, который идентифицирует его общие подвыражения.
выражения, который идентифицирует его общие подвыражения.
Подобно [[Дерево выражения| ''дереву выражения'']] '''дэг выражения''' имеет некоторую вершину для каждого
Подобно [[Дерево выражения| ''дереву выражения'']] '''дэг выражения''' имеет некоторую [[вершина|вершину]] для каждого
подвыражения выражения, причем внутренняя вершина изображает
подвыражения выражения, причем [[внутренняя вершина]] изображает
операцию, а ее сыновья --- операнды операции. Различие состоит в
операцию, а ее [[сын|сыновья]] — операнды операции. Различие состоит в
том, что вершина в дереве, изображающая общее подвыражение, имеет
том, что вершина в [[дерево|дереве]], изображающая общее подвыражение, имеет
более одного отца; в дереве выражения это общее подвыражение
более одного [[отец вершины ордерева|отца]]; в дереве выражения это общее подвыражение
можно представить за счет дублирования поддеревьев.
можно представить за счет дублирования [[поддерево|поддеревьев]].




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

Текущая версия от 17:03, 7 февраля 2011

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


Литература

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