Меню Главная Случайная статья Настройки Доступное выражение Материал из https://ru.wikipedia.org Доступное выражение (англ. 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] Добавляем к ${\displaystyle S}$ выражение ${\displaystyle y+z}$. Удаляем из ${\displaystyle S}$ все выражения, включающие переменную ${\displaystyle x}$. Описанные действия должны выполняться в указанном порядке, так как ${\displaystyle x}$ может совпадать с ${\displaystyle y}$ или ${\displaystyle z}$. После того, как достигнут конец блока, ${\displaystyle S}$ будет представлять собой множество сгенерированных выражений блока. Множество уничтоженных выражений представляет собой множество всех выражений, например, ${\displaystyle y+z}$, таких, что ${\displaystyle y}$ или ${\displaystyle z}$ определяется в блоке, и при этом ${\displaystyle y+z}$ блоком не генерируется[2]. Примечания 1 2 3 Компиляторы: принципы, технологии и инструменты, 2008, с. 735. Компиляторы: принципы, технологии и инструменты, 2008, с. 736. Литература Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е издание. — М.: «Вильямс», 2008. — 1184 с. — 1500 экз. — ISBN 978-5-8459-1349-4.