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

Переменные в программировании

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

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

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

Можно вычислить множество генерируемых выражений для каждой точки блока, проходя от начала до конца блока. В точке, предшествующей блоку, сгенерированных выражений нет. Если в точке ${\displaystyle p}$ доступно множество выражений ${\displaystyle S}$, a ${\displaystyle q}$ представляет собой точку после ${\displaystyle p}$ с инструкцией ${\displaystyle x=y+z}$ между ними, то мы образуем множество доступных в ${\displaystyle q}$ выражений следующим образом:[1]

1. Добавляем к ${\displaystyle S}$ выражение ${\displaystyle y+z}$.
2. Удаляем из ${\displaystyle S}$ все выражения, включающие переменную ${\displaystyle x}$.

Описанные действия должны выполняться в указанном порядке, так как ${\displaystyle x}$ может совпадать с ${\displaystyle y}$ или ${\displaystyle z}$. После того как достигнут конец блока, ${\displaystyle S}$ будет представлять собой множество сгенерированных выражений блока. Множество уничтоженных выражений представляет собой множество всех выражений, например, ${\displaystyle y+z}$, таких, что ${\displaystyle y}$ или ${\displaystyle z}$ определяется в блоке, и при этом ${\displaystyle y+z}$ блоком не генерируется[2].