Теория вычислительных процессов и структур. Селиверстов М.Н. - 6 стр.

       24. Оптимизация программы: константные вычисления, вычисление общих подвы-
ражений, удаление недостижимого кода, устранение оператора goto. Оптимизации объ-
ектно-ориентированных языков.
       25. Синтез и генерация кода. Проблемы распределения регистров и временных пе-
ременных.

Теория схем программ

       26. Стандартные схемы: базис, операторы, граф.
       27. Интерпретация схемы, программа. Исполнение программы: допустимые це-
почки, значение программы.
       28. Эквивалентность, тотальность, пустота, свобода. Корректные отношения
эквивалентности.
       29. Свободные интерпретации. Теоремы Лакхэма-Парка-Патерсона.
       30. Двоичный двухголовочный автомат (ДДА): определение и свойства. Неразре-
шимость проблемы пустоты ДДА.
       31. Моделирование ДДА стандартной схемой. Неразрешимость проблем пустоты и
эквивалентности стандартных схем.
       32. Частичная разрешимость проблемы тотальности.
       33. Задача Поста и ее частичная разрешимость. Обратная задача Поста и ее не-
разрешимость.
       34. Сведение проблемы свободы схемы к задаче пустоты системы Поста. Нераз-
решимость проблемы свободы.
       35. Логико-термальная (ЛТ) эквивалентность стандартных схем: мотивация, оп-
ределение. Корректность ЛТ-эквивалентности.
       36. Разрешимость ЛТ-эквивалентности.
       37. Полная система ЛТ-эквивалентных преобразований.

Оптимизация программ

       38. Кодогенерация и ее связь с оптимизацией. Общее понятие об эквивалентных
(или почти эквивалентных) преобразованиях программ. Историческая справка. Анализ
программ как средство сбора контекстной информации. Общий план оптимизирующего
компилятора.
       39. Основные оптимизирующие преобразования: константные вычисления, общие
подвыражения, чистка циклов, удаление мертвого кода и т.д.
       40. Неформальная постановка. Классы входных языков и машинных архитектур.
Основные задачи кодогенерации: представление данных, проекция конструкций, согла-
шения о связях, выбор команд (instruction selection), распределение ресурсов.
       41. Представление программы для кодогенерации: таблица символов, абстрактное
синтаксическое дерево, ориентированный ациклический граф (DAG), граф управления
(CFG).
       42. Классические методы кодогенерации: атрибутирование, запрос-ответ.
       43. Синтаксически-управляемая генерация кода. Семантически-управляемая гене-
рация кода, атрибутные и аффиксные грамматики.
       44. Разбор деревьев и динамическое программирование.
       45. Определение управляющего графа программы, подграфа, достижимости, связ-
ности.
       46. Отношение обязательного предшествования (предоминирования) и обязатель-
ной преемственности (постдоминирования). Строгое и непосредственное предшествова-
ние. Алгоритмы построения отношения обязательного предшествования.



                                         6