Доступное выражение () в теории построения компиляторов — некоторое выражение в точке такое, что если любой путь от входного узла к вычисляет и после последнего вычисления до достижения нет последующих присваиваний переменным и :
Блок уничтожает выражение , если он присваивает (или может присваивать) и и после этого не вычисляет заново. Блок генерирует выражение , если он вычисляет и не выполняет последующих переопределений и .
Основное применение информации о доступных выражениях — поиск глобальных общих подвыражений.
Можно вычислить множество генерируемых выражений для каждой точки блока, проходя от начала до конца блока. В точке, предшествующей блоку, сгенерированных выражений нет. Если в точке доступно множество выражений , a представляет собой точку после с инструкцией между ними, то мы образуем множество доступных в выражений следующим образом:
Добавляем к выражение . Удаляем из все выражения, включающие переменную .
Описанные действия должны выполняться в указанном порядке, так как может совпадать с или . После того, как достигнут конец блока, будет представлять собой множество сгенерированных выражений блока. Множество уничтоженных выражений представляет собой множество всех выражений, например, , таких, что или определяется в блоке, и при этом блоком не генерируется.
Примечания
Литература
Категория:Теория компиляторов Категория:Формальные методы