Разработка компиляторов
Для демонстрации сути задач анализа
Для демонстрации сути задач анализа потоков данных рассмотрим несколько примеров.
На иллюстрации приведен фрагмент программы. Вхождения одного и того же выражения (v+i)->b, обведенные сплошной линией, являются эквивалентными. В то же время вхождение того же самого выражения, обозначенное пунктирной линией, не эквивалентно первым двум, поскольку else-часть условного оператора содержит разрушающее присваивание.
Понятно, что для выяснения эквивалентности данных выражений необходимо перебрать все пути и убедиться, что ни в одном из них значения переменных, входящих в выражения, не меняются.
В качестве примера ограниченной полурешетки конечной высоты рассмотрим множество всех подмножеств букв латинского алфавита с операцией пересечения. Понятно, что данная полурешетка является ограниченной - в качестве наибольшего элемента выступает множество всех букв, в качестве наименьшего - пустое множество. Так как множество всех букв конечно, то высота данной полурешетки также будет конечной.
Рассмотрим функцию, которая к своему аргументу добавляет букву a. Легко видеть, что эта функция является монотонной. Наименьшей неподвижной точкой этой функции является множество, состоящее из единственной буквы a, множество всех ее неподвижных точек есть множество подмножеств букв, содержащих букву a.
Для демонстрации сути задач анализа потоков данных рассмотрим несколько примеров.
На иллюстрации приведен фрагмент программы. Вхождения одного и того же выражения (v+i)->b, обведенные сплошной линией, являются эквивалентными. В то же время вхождение того же самого выражения, обозначенное пунктирной линией, не эквивалентно первым двум, поскольку else-часть условного оператора содержит разрушающее присваивание.
Понятно, что для выяснения эквивалентности данных выражений необходимо перебрать все пути и убедиться, что ни в одном из них значения переменных, входящих в выражения, не меняются.
В качестве примера ограниченной полурешетки конечной высоты рассмотрим множество всех подмножеств букв латинского алфавита с операцией пересечения. Понятно, что данная полурешетка является ограниченной - в качестве наибольшего элемента выступает множество всех букв, в качестве наименьшего - пустое множество. Так как множество всех букв конечно, то высота данной полурешетки также будет конечной.
Рассмотрим функцию, которая к своему аргументу добавляет букву a. Легко видеть, что эта функция является монотонной. Наименьшей неподвижной точкой этой функции является множество, состоящее из единственной буквы a, множество всех ее неподвижных точек есть множество подмножеств букв, содержащих букву a.
