Доступное выражение

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск


Доступное выражение (англ. Available expression) в теории построения компиляторов — некоторое выражение в точке , если любой путь от входного узла к вычисляет и после последнего такого вычисления до достижения нет последующих присваиваний переменным и [1].

  • Блок уничтожает выражение , если он присваивает (или может присваивать) и и после этого не вычисляет заново.
  • Блок генерирует выражение , если он вычисляет и не выполняет последующих переопределений и .

Основное применение информации о доступных выражениях — поиск глобальных общих подвыражений[1].

Можно вычислить множество генерируемых выражений для каждой точки блока, проходя от начала до конца блока. В точке, предшествующей блоку, сгенерированных выражений нет. Если в точке доступно множество выражений , a представляет собой точку после с инструкцией между ними, то мы образуем множество доступных в выражений следующим образом:[1]

  1. Добавляем к выражение .
  2. Удаляем из все выражения, включающие переменную .

Описанные действия должны выполняться в указанном порядке, так как может совпадать с или . После того как достигнут конец блока, будет представлять собой множество сгенерированных выражений блока. Множество уничтоженных выражений представляет собой множество всех выражений, например, , таких, что или определяется в блоке, и при этом блоком не генерируется[2].

Примечания[править | править вики-текст]

Литература[править | править вики-текст]