Стандартные схемы

Стандартные схемы (Standard schemata) — схемы алголоподобных программ, исследование которых составляет основное содержание общей теории схем программ.

В отличие от схем Мартынюка стандартные схемы учитывают разбиение памяти на переменные и позволяют исследовать более широкий класс преобразований программ, включающий уже и такие преобразования, как, например, экономия общих подвыражений.

Однако как подкласс крупноблочных схем стандартные схемы запрещают структурность операторов и переменных и, таким образом, моделируют лишь узкий класс реальных программ. Каждый оператор в такой схеме является либо преобразователем — оператором, изменяющим состояние памяти, либо распознавателем — оператором, осуществляющим выбор для исполнения одного из нескольких своих преемников. Преобразователь содержит одно обязательное присваивание и имеет одну исходящую дугу, а распознаватель не содержит присваиваний и имеет две исходящие дуги, одна из которых называется плюс-стрелкой (или 1-дугой), а вторая — минус-стрелкой (или 0-дугой).

См. также

• Крупноблочная схема программ,
• Неинтерпретированные схемы,
• Схема программ,
• Схема с косвенной адресацией,
• Схема с распределенной памятью,
• Схемы Лаврова,
• Схемы Мартынюка,
• Схемы Янова.

Литература

• Ершов А.П. Избранные труды. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.

• Котов В.Е., Сабельфельд В.К. Теория схем программ.— М.: Наука, 1991..