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

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

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

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

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

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

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

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

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

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

  • Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман Компиляторы: принципы, технологии и инструменты = Compilers: Principles, Techniques, and Tools. — Издательский дом "Вильямс", 2008. — ISBN 0-321-48681-1.