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

Доступное выражение (Шаблон:Lang-en) в теории построения компиляторов — некоторое выражение $x+y$ в точке $p$ такое, что если любой путь от входного узла к $p$ вычисляет $x+y$ и после последнего вычисления до достижения $p$ нет последующих присваиваний переменным $x$ и $y$Шаблон:Sfn:

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

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

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

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

Описанные действия должны выполняться в указанном порядке, так как $x$ может совпадать с $y$ или $z$. После того, как достигнут конец блока, $S$ будет представлять собой множество сгенерированных выражений блока. Множество уничтоженных выражений представляет собой множество всех выражений, например, $y+z$, таких, что $y$ или $z$ определяется в блоке, и при этом $y+z$ блоком не генерируетсяШаблон:Sfn.

Литература

• Шаблон:Книга:Ахо Компиляторы