Разработка компиляторов
Алгоритм с рабочим списком
увеличить изображение
Приведенный способ решения задачи анализа потоков данных может быть реализован с помощью алгоритма, приведенного на иллюстрации. Заметим, что технически нет необходимости в явном виде представлять декартову степень полурешетки и преобразователь F.
Очевидно, что достаточно привести запись алгоритма для прямой задачи.
Алгоритм производит итеративное перевычисление разметок, используя рабочий список вершин. Главным свойством этого списка является то, что он состоит из вершин, для предшественников которых значение разметок было изменено на предыдущем шаге. Таким образом, опустошение списка свидетельствует о том, что достигнута неподвижная точка.
Алгоритм начинает работу на начальной разметке и рабочем списке, состоящем из единственной вершины start (для обратной задачи - stop). Извлекая очередную вершину из рабочего списка, алгоритм вычисляет общую часть решения задачи по всем своим предшественникам и применяет к ней потоковую функцию, ассоциированную с данной вершиной. Если полученное значение отличается от текущего значения разметки after для данной вершины, то все ее наследники добавляются в рабочий список.
