Русская Википедия:Доступное выражение

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

Литература

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