- •Министерство образования и науки рф
- •Основы построения трансляторов Курс лекций по дисциплине «Системное программное обеспечение» Красноярск 2010 г.
- •1. Место трансляторов в системном программном обеспечении. Основные фазы процесса трансляции
- •Генерация промежуточного представления
- •Генерация кода
- •Контрольные вопросы
- •2. Базовые понятия теории формальных языков и грамматик
- •2.1. Алфавиты, цепочки и языки. Основные понятия и определения
- •2.2. Представление языков
- •2.3. Грамматики
- •2.3.1. Формальное определение грамматики
- •2.3.2. Классификация грамматик и языков по Хомскому
- •2.3.3. Разбор цепочек
- •2.3.4. Преобразования грамматик
- •2.4. Задачи
- •3. Лексический анализ
- •Описание модельного языка
- •3.1. Сущность и задачи лексического анализа
- •3.2. Способы организации таблиц идентификаторов
- •Организация таблицы идентификаторов в виде неупорядоченного массива записей. Метод линейного поиска.
- •Организация таблицы идентификаторов в виде упорядоченного массива записей. Метод бинарного поиска.
- •Использование бинарного дерева поиска для построения таблицы идентификаторов.
- •Построение таблиц идентификаторов с использованием методов хеширования.
- •3.3. Методы и средства лексического анализа
- •3.4. Недетерминированный разбор
- •3.5 Разработка лексического анализатора для модельного языка Описание модельного паскалеподобного языка (м-языка):
- •Контрольные вопросы
- •4. Синтаксический и семантический анализ
- •4.1. Задачи и методы синтаксического анализа
- •4.2 Сущность метода рекурсивного спуска
- •Void error(); / функция обработки ошибок /
- •4.3. Условия применимости метода рекурсивного спуска
- •4.4. Синтаксический анализатор для м-языка
- •4.5. Семантический анализ
- •4.6. Семантический анализатор для м-языка
- •4.6.1. Обработка описаний
- •Int declare; / описан ? 1-"да", 0-"нет" /
- •Void ipush (int I); / значение I - в стек /
- •Int ipop (void); / из стека - целое /
- •4.6.2. Контроль контекстных условий в выражении
- •Void spush (char s); / значение s - в стек /
- •If (tid [I].Declare) / описан? /
- •4.6.3. Контроль контекстных условий в операторах
- •4.7. Задачи
- •5. Генерация внутреннего представления программ
- •5.1. Язык внутреннего представления программы
- •5.2 Синтаксически управляемый перевод
- •5.3 Генератор внутреннего представления программы на м-языке
- •5.4 Интерпретатор полиЗа для модельного языка
- •5.5 Задачи
- •Литература
Литература
Д. Грис. Конструирование компиляторов для цифровых вычислительных машин / Д. Грис. - М.: Мир, 1998.
Ф. Льюис, Д. Розенкранц, Р. Стирнз. Теоретические основы проектирования компиляторов / Ф. Льюис, Д. Розенкранц, Р. Стирнз. - М.: Мир, 1989.
А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции, Том 1,2. / А. Ахо, Дж. Ульман. - М.: Мир, 1995.
Ф. Вайнгартен. Трансляция языков программирования / Ф. Вайнгартен. - М.: Мир, 1987.
И. Л. Братчиков. Синтаксис языков программирования / И. Л. Братчиков. - М.: Наука, 1985.
С. Гинзбург. Математическая теория контекстно-свободных языков / С. Гинзбург. - М.: Мир, 1980.
Дж. Фостер. Автоматический синтаксический анализ / Дж. Фостер. - М.: Мир, 1985.
В. Н. Лебедев. Введение в системы программирования / В. Н. Лебедев. - М.: Статистика, 1975.
Л. Бек. Введение в системное программное обеспечение / Л. Бек.- М.: Мир,1989.
Р. Хантер. Основные концепции компиляторов / Р. Хантер. - Вильямс, 2002.
А.В. Ахо, Дж. Д. Ульман. Компиляторы: принципы, технологии и инструменты / А.В. Ахо, Дж. Д. Ульман. Вильямс, 2001.
Д. Э. Кнут. Искусство программирования, том 3. Сортировка и поиск / Д. Э. Кнут. Вильямс, 2000.
Д.Э. Кнут. Искусство программирования, том 1. Основные алгоритмы / Д.Э. Кнут. Вильямс, 2000.
А. В. Ахо, Дж. Д. Ульман. Структуры данных и алгоритмы / А. В. Ахо, Дж. Д. Ульман. Вильямс, 2000.
А. В. Гордеев, А. Ю. Молчанов. Системное программное обеспечение / А. В. Гордеев, А. Ю. Молчанов. Питер, 2001