Министерство образования и науки Российской Федерации
Южно-Уральский государственный университет
Механико-математический факультет
Кафедра системного программирования
УТВЕРЖДАЮ
Декан мех.-мат. факультета
____________ А.Д. Дрозин
11.11.2004
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Разработка трансляторов
для студентов, обучающихся по программе магистерской подготовки
010500.68.11 (510211) "Системное программирование"
направления 010500.68 (510200) "Прикладная математика и информатика"
Челябинск-2004
Курс посвящен введению в методы трансляции программ и охватывает следующие темы: модель транслятора, основы теории языков и формальных грамматик, организация лексического анализа и синтаксического разбора, генерация и оптимизация кода и автоматическая генерация трансляторов.
Основные понятия и определения. Общие особенности языков программирования и трансляторов. Обобщенная структура транслятора. Варианты взаимодействия блоков транслятора: многопроходная организация взаимодействия, однопроходная организация взаимодействия, комбинированные взаимодействия блоков транслятора.
Способы определения языков. Формальные грамматики. Грамматики с ограничениями на правила. Способы записи синтаксиса языка: метаязык Хомского, метаязык Хомского-Щутценберже, Бэкуса-Наура формы (БНФ).
Назначение и необходимость фазы лексического анализа. Транслитератор. Грамматики и распознаватели для лексического анализа. Связь между синтаксическими диаграммами и конечным автоматом. Связь между синтаксическими диаграммами и праволинейными грамматиками. Преобразование правой рекурсии в итерацию. Связь между синтаксическими диаграммами и грамматиками с левой рекурсией. Преобразование левой рекурсии в итерацию. Методы лексического анализа: организация непрямого лексического анализатора, организация прямого лексического анализатора.
Назначение синтаксического разбора. Классификация методов синтаксического разбора. Последовательность разбора. Использование просмотра вперед. Использование возвратов.
Применение автоматов с магазинной памятью для нисходящего разбора слева направо
Необходимость использования автоматов с магазинной памятью. Организация автомата с магазинной памятью. Общая связь между грамматиками и автоматами с магазинной памятью. Связь между S-грамматикой и автоматом с магазинной памятью. Построение автомата с магазинной памятью по q-грамматике. LL(1) - грамматики. Программная реализация нисходящего автомата с магазинной памятью.
Использование динамически порождаемых автоматов для нисходящего разбора слева направо
Семантический разрыв между формальными грамматиками и автоматами с магазинной памятью. Модель динамически порождаемых конечных автоматов. Графический метаязык для описания динамически порождаемых конечных автоматов. Использование синтаксических диаграмм для представления динамически порождаемых конечных автоматов, распознающих КС(1) грамматику.
Распределение оперативной памяти. Организация таблиц компилятора. Процедура генерации кода. Основные методы оптимизации кода.
Краткий обзор программных средств автоматической генерации интерпретаторов и компиляторов: LEX, YACC, BIZON и др.
№ п/п |
Тема |
Лекц. (час.) |
Практ. (час.) |
1. |
Общие сведения о трансляторах |
1 |
|
2. |
Основы теории языков и формальных грамматик |
1 |
|
3. |
Организация лексического анализа |
10 |
|
4. |
Организация синтаксического разбора |
10 |
|
5. |
Генерация кода |
6 |
|
6. |
Автоматическая генерация трансляторов |
2 |
6 |
|
ИТОГО |
30 |
6 |
1. Ахо А., Ульман Д., Сети Р. Компиляторы: принципы, технологии, инструментарий. - М.: Вильямс, 2001.
2. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.
3. Костельцов А.В. Построение интерпретаторов и компиляторов: использование программ BIZON, BYACC, ZUBR. - М.: Наука и техника, 2001.