Разработка компиляторов
Поток управления
Данный способ описания программы применяется тогда, когда необходимо описать преобразования потока управления, которые не требуют анализа потоков данных.
Алфавит операторов в этом случае содержит выделенный пустой оператор (). Будем требовать, чтобы разметка графа потока управления сопоставляла пустой оператор только тем вершинам, для которых число исходящих дуг не превосходит единицы. Два слова в алфавите операторов объявляются эквивалентными в том и только том случае, когда они равны с точностью до вхождения пустых операторов.
Для определения эквивалентности программ, записанных в данном формализме, введем понятие слова, соответствующего пути в графе потока управления, а именно, для произвольного пути p слово w(p) в алфавите операторов получается последовательным выписыванием символов, которыми помечены вершины p .
Будем говорить, что две программы (G1, ?1) и (G2, ?2) эквивалентны, тогда и только тогда, когда существует такое отображение m между вершинами G1 и G2, что для произвольной вершины v графа G1 и произвольного пути p , начинающегося в ней, найдется путь p' в графе G2, начинающийся в вершине m(v) , для которого слова w(p) и w(p') эквивалентны.
