Дэг выражения: различия между версиями
Перейти к навигации
Перейти к поиску
KVN (обсуждение | вклад) (Создана новая страница размером '''Дэг выражения''' (Expression DAG) --- вид [[(Абстрактное) синтаксическое представл...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Дэг выражения''' ([[Expression DAG]]) | '''Дэг выражения''' ([[Expression DAG]]) — | ||
вид [[(Абстрактное) синтаксическое представление|''абстрактного синтаксического представления'']] | вид [[(Абстрактное) синтаксическое представление|''абстрактного синтаксического представления'']] | ||
выражения, который идентифицирует его общие подвыражения. | выражения, который идентифицирует его общие подвыражения. | ||
Подобно [[Дерево выражения| ''дереву выражения'']] '''дэг выражения''' имеет некоторую вершину для каждого | Подобно [[Дерево выражения| ''дереву выражения'']] '''дэг выражения''' имеет некоторую [[вершина|вершину]] для каждого | ||
подвыражения выражения, причем внутренняя вершина изображает | подвыражения выражения, причем [[внутренняя вершина]] изображает | ||
операцию, а ее сыновья | операцию, а ее [[сын|сыновья]] — операнды операции. Различие состоит в | ||
том, что вершина в дереве, изображающая общее подвыражение, имеет | том, что вершина в [[дерево|дереве]], изображающая общее подвыражение, имеет | ||
более одного отца; в дереве выражения это общее подвыражение | более одного [[отец вершины ордерева|отца]]; в дереве выражения это общее подвыражение | ||
можно представить за счет дублирования поддеревьев. | можно представить за счет дублирования [[поддерево|поддеревьев]]. | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998. | |||
Версия от 17:03, 7 февраля 2011
Дэг выражения (Expression DAG) — вид абстрактного синтаксического представления выражения, который идентифицирует его общие подвыражения. Подобно дереву выражения дэг выражения имеет некоторую вершину для каждого подвыражения выражения, причем внутренняя вершина изображает операцию, а ее сыновья — операнды операции. Различие состоит в том, что вершина в дереве, изображающая общее подвыражение, имеет более одного отца; в дереве выражения это общее подвыражение можно представить за счет дублирования поддеревьев.
Литература
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.