Разработка компиляторов
Итеративный алгоритм
Основной проблемой описанного выше подхода является проблема остановки алгоритма. Действительно, в какой момент процесс уточнения разметки должен прекратиться? Очевидно, в тот момент, когда получено решение задачи анализа потоков данных. Однако поскольку решение задачи неизвестно, то и воспользоваться этим наблюдением напрямую оказывается невозможным. Поэтому для определения завершаемости алгоритма используется другой принцип - принцип достижения неподвижонй точки.
Частично-упорядоченное множество X будем называть множеством конечной высоты N тогда и только тогда, когда длины всех строго возрастающих последовательностей элементов X ограничены N. Это означает, что для произвольной возрастающей последовательности начиная с некоторого места все элементы становятся одинаковыми.
Рассмотрим теперь функция перехода F, удовлетворяющую соотношению F(?)? для произвольной разметки ?. Понятно, что при таком условии при итерировании F начиная с некоторого места будет достигнута ее неподвижная точка. Множество X и функция перехода F подбираются таким образом, чтобы эта неподвижная точка являлась решением задачи анализа потоков данных.
На слайде приведена схема итеративного алгоритма анализа потоков данных.
Далее мы более детально рассмотрим возможную природу множества фактов X, множества разметок и преобразователей F.
