Разработка компиляторов


         

в рассмотрение полурешетку, представляющую собой


Введем в рассмотрение полурешетку, представляющую собой декартову степень 2|V| исходной полурешетки L и введем в рассмотрение функцию F на ней. Данная функция принимает на вход элемент <before1, after1, ..., before|V|, after|V|> и возвращает элемент, полученный применением функций, построенных на предыдущем шаге, к соответствующим аргументам. Иными словами, если, например, для вершины 10 графа потока управления предшественниками являются вершины 2 и 3, то двадцатым элементом возвращаемого F значения будет g10,2(after2, after3) .
Легко видеть, что функция F является монотонной. Кроме того, можно показать, что ее произвольная неподвижная точка является решением системы уравнений (*), поскольку произвольный элемент решетки L2ґ|V|определяет пару разметок before , after .
Наконец, итерирование функции F, начиная с наименьшего элемента, дает в конце концов наименьшую неподвижную точку и, следовательно, искомое решение задачи анализа потоков данных.

Содержание  Назад  Вперед