Задача анализа свойств состояний

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

Задача анализа свойств состояний (Data flow analysis problem) — Рассматривается полурешетка свойств (L,\sqcap), не содержащая бесконечных цепей, множество преобразователей свойств F и функция M, ставящая в соответствие каждой дуге u анализируемого уграфа G=(V,U) функцию эффекта дуги M(u)\in F.

Прямая задача анализа свойств состояний формулируется как задача нахождения так называемой полной разметки — такой функции A:V\rightarrow L, что

A(p)=\sqcap\{f_{\alpha} (a_0):\alpha \mbox{ --- } путь от начальной вершины до  p\},

где a_0 — некоторое свойство, сопоставляемое с начальной вершиной уграфа, а f_{\alpha} — функция эффекта пути, полученная композицией функций эффектов составляющих его дуг. Указанная задача алгоритмически неразрешима и допускает эффективное решение лишь для узких своих подклассов таких, как, например, дистрибутивные задачи анализа свойств состояний, в которых F состоит только из дистрибутивных функций. Поэтому обычно рассматриваются алгоритмы нахождения приближенных решений задачи, связанных с нахождением корректных разметок — таких B:V\rightarrow L, что B(p)\sqsubseteq f_{\alpha}(a_0) для любых вершины p и пути \alpha из a_0 в p.

В отличие от прямой обратная задача анализа свойств состояний предполагает известными начальное свойство для конечной вершины уграфа и обратное направление применения функций эффектов дуг.

В общей постановке с каждой дугой уграфа могут связываться функции ее эффектов как в прямом, так и в обратном направлении.

Другие названия — Задача потокового анализа и Задача глобального анализа потока данных.

Литература

  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
  • Котов В.Е., Сабельфельд В.К. Теория схем программ. — М.: Наука, 1991.