Конструирование компиляторов


Конструирование компиляторов



Аннотация

В курсе изучаются основные вопросы разработки трансляторов с языков высокого уровня: лексические и синтаксические анализаторы, промежуточное представление программ, контекстный анализ, таблицы символов, организация памяти периода исполнения, трансляция выражений и операторов, распределение регистров в рабочей программе. Рассматриваются некоторые средства автоматизации процесса трансляции.

Содержание курса

Введение. Место компилятора в программном обеспечении. Структура компилятора.
Лексический анализ. Регулярные множества и регулярные выражения. Конечные автоматы. Построение детерминированного конечного автомата по регулярному выражению. Построение детерминированного конечного автомата с минимальным числом состояний. Программирование лексических анализаторов. Конструктор лексических анализаторов LEX.
Синтаксический анализ. Основные понятия и определения. Таблично - управляемый предсказывающий разбор (алгоритм разбора сверху - вниз, множества FIRST и FOLLOW, конструирование таблиц предсказывающего анализатора, LL(1)- грамматики, удаление левой рекурсии, левая факторизация, рекурсивный спуск, диаграммы переходов для рекурсивного спуска, восстановление после синтаксических ошибок). Разбор снизу-вверх типа сдвиг-свертка (основа, LR(k)-анализаторы, LR-грамматики, конфликты разбора типа сдвиг-свертка, восстановление после синтаксических ошибок).
Промежуточное представление программы. Представление в виде ориентированного графа. Трехадресный код. Линеаризованные представления. Организация информации в генераторе кода. Уровень промежуточного представления.
Элементы теории перевода. Преобразователи с магазинной памятью. Синтаксически управляемый перевод. Атрибутные грамматики (определение, атрибутированное дерево разбора, язык описания атрибутных грамматик).
Контекстные условия языков программирования. Описание областей видимости и блочной структуры. Структура среды Модула-2. Занесение в среду и поиск объектов. Управление данными и контроль типов.
Организация таблиц компилятора. Таблицы идентификаторов, таблицы символов и таблицы расстановки. Функции расстановки. Таблицы на деревьях. Реализация блочной структуры. Сравнение различных методов реализации таблиц.
Генерация кода. Модель машины. Динамическая организация памяти. Назначение адресов. Трансляция переменных. Трансляция арифметических выражений. Распределение регистров при вычислении арифметических выражений. Особенности трансляции логических выражений. Выделение общих подвыражений. Оптимизация кода методами синтаксического анализа сопоставление образцов, синтаксический анализ для Т-грамматик, выбор дерева вывода наименьшей стоимости). Системы автоматизации построения трансляторов. Система Супер. Система Yacc.

Литература

  • Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools. N.Y.: Addison-Wesley. 1986.

  • Грис Д. Построение компиляторов для цифровых вычислительных машин. М.: Мир. 1975.

  • Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. М.: Мир. 1978.

  • Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир. 1976.