ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение высшего профессионального образования
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ,
ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
МИРЭА
"УТВЕРЖДАЮ" "СОГЛАСОВАНО"
Декан факультета Кибернетики Председатель учебно-методической
______________проф. Романов М.П. комиссии по специальности
"_____"__________ 2006 г. прикладная математика
_____________проф. Самохин А.Б.
"_____"__________2006 г.
РАБОЧАЯ ПРОГРАММА
дисциплины «Проектирование трансляторов»
Специальность 230401 "Прикладная математика"
Специализация – "Программное обеспечение систем радиоэлектронной аппаратуры",
очная форма образования
Составлена на основании Государственных требований к минимуму содержания и уровню подготовки инженера по специальности 230401, ДС.08.
Факультет: Кибернетика
Кафедра: № 536 при ОАО «Концерн радиостроения «Вега»
Объем учебной нагрузки и виды отчетности
| Число часов | |
| Лекции | |
| Лабораторные занятия | --- |
| Практические занятия (семинары) | |
| Самостоятельная работа студентов | |
| ВСЕГО | |
| Курсовые проекты и работы (номер семестра) | |
| Зачеты | |
| Экзамены (номер семестра) |
Москва 2006
- ЦЕЛИ И ЗАДАЧИ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ,
ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ
Цель изучения дисциплины.
Получение:
-представления о методах и возможностях аппарата формальных грамматик и средств разработки трансляторов;
-знаний теоретических основ и практических приемов аппарата формальных грамматик;
-умений применения аппарата формальных грамматик для проектирования и разработки трансляторов;
-опыта использования, применения средств построения трансляторов.
1.2. Задачи изучения дисциплины:
- обучение на лекциях теоретическим основам аппарата формальных грамматик;
- освоение и вырабатывание на семинарах практических навыков применения аппарата формальных грамматик и средств разработки трансляторов;
- расширение представлений о возможностях и особенностях существующих формальных языков в ходе подготовки и выслушивания докладов
- наработка на лабораторных занятиях опыта проектирования и реализации трансляторов с использованием и без использования специализированных средств разработки трансляторов;
- закрепление усвоенных навыков на самостоятельных занятиях (включают контрольные работы и курсовой проект).
1.3. Перечень дисциплин и разделов, знание которых требуется для изучения данной дисциплины:
- алгоритмические языки;
- системное программирование и проектирование;
- основы программирования и работы на ЭВМ;
- математические основы информатики.
- СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Наименование тем, их содержание
2.1.1. Классификация и структура трансляторов.
2.1.2. Алфавит. Операции над символами алфавита. Определение грамматики.
2.1.3. Отношения и их свойства. Матрицы отношений и их построение. Отношения FIRST, LAST и их транзитивных замыканий.
2.1.4. Основные определения курса. Сентенциальная форма и предложение. Вывод и непосредственный вывод. Фраза, простая фраза, основа. Язык.
2.1.5. Синтаксические деревья. Неоднозначности: лексическая, синтаксическая, семантическая, грамматики, языка.
2.1.6. Классификация грамматик по Хомскому.
2.1.7. Операторы. Ассоциативность и приоритет.
2.1.8. Разбор и распознаватель. Определение и виды разбора: лексический и синтаксический, нисходящий и восходящий.
2.1.9. Лексический анализ. Сканер. Символ и лексема. Регулярные грамматики и регулярные выражения. Конечные автоматы.
2.1.10. Синтаксический анализ. Классификация анализаторов. Предикативный анализ и разбор с возвратами. Нисходящий рекурсивный распознаватель.
2.1.11. Семантический анализ. Атрибуты и атрибутивные грамматики. Восстановление после ошибок.
2.1.12. Грамматики предшествования и грамматики предшествования операторов.
2.1.13. LL(k)-грамматики. Множества FIRST и FOLLOW. Определение принадлежности грамматики LL(k) классу. Принцип работы и построение LL(k)-распознавателя.
2.1.14. LR(k)-грамматики. Перенос и свертка. LR(k)-распознаватели. Принцип работы и построение SLR(1)-распознавателя. Разрешение конфликтов LR-анализа.
2.1.15. Временная сложность и затраты памяти распознавателей. Распознаватели КЯК, Эрли, Ульмана, Томита, ЯНРОВ.
2.1.16. Организация таблицы символов. Таблицы символов, имеющие блочную структуру. Таблица видов. Организация таблицы видов. Описатели.
2.1.17. Формы записи внутреннего представления кода. Инфиксная и обратная польская запись операций. Деревья.
2.1.18. Средства разработки трансляторов. Их классификации и основные представители.
2.1.19. Построитель анализаторов FLEX (LEX).
2.1.20. Построитель анализаторов BISON (YACC).
2.1.21. Построитель анализаторов ANTLR.
2.1.22. Грамматики TAG, PEG, TDPL. Построение компилятора.
Распределение времени по темам дисциплины
| Отводимое время | |||
| Часов | № недели | № семестра | |
| 2.1.1-2.1.2 | |||
| 2.1.3 | |||
| 2.1.4 | |||
| 2.1.5-2.1.6 | |||
| 2.1.7-2.1.8 | |||
| 2.1.9 | |||
| 2.1.10 | 7,8 | ||
| 2.1.11 | 9,10 | ||
| 2.1.12 | 11-12 | ||
| 2.1.13 | 13-15 | ||
| 2.1.14 | 16-18 | ||
| 2.1.15 | |||
| 2.1.16 | |||
| 2.1.17 | 3,4 | ||
| 2.1.18 | 5,6 | ||
| 2.1.19 | 7,8 | ||
| 2.1.20 | 9,10 | ||
| 2.1.21 | 11-14 | ||
| 2.1.22 | 15-18 | ||
| ВСЕГО (часов) |
Лабораторные работы
Лабораторные занятия учебным планом не предусмотрены
Практические занятия
| № п/п | Темы практических занятий (семинаров) | № семестра | № недели | часы |
| 1. | Построение формальных грамматик | |||
| 2. | Построение матриц отношений | |||
| 3. | Редукция основы | |||
| 4. | Выдача грамматик для самостоятельных работ | |||
| 5. | Построение деревьев, классификация грамматик | |||
| 6. | Построение сканера, регулярных выражений PCRE | |||
| 7. | Построение рекурсивного распознавателя | 7,8 | ||
| 8. | Слушание докладов | 9,10 | ||
| 9. | Построение распознавателя предшествования | 11,12 | ||
| 10. | Построение LL(1) распознавателя | 13-15 | ||
| 11. | Построение SLR(1) распознавателя | 16-18 | ||
| 12. | Оценка временной сложности | |||
| 13. | Разработка таблиц символов | |||
| 14. | Работа с обратной польской записью | 3,4 | ||
| 15. | Освоение средств разработки трансляторов | 5,6 | ||
| 16. | Освоение FLEX | 7,8 | ||
| 17. | Освоение BISON | 9,10 | ||
| 18. | Освоение ANTLR | 11-14 | ||
| 19. | Реализация семантических процедур | 15-18 | ||
| ВСЕГО (часов) |
Cамостоятельная работа студентов
Курсовые работы и проекты
| № п.п. | Курсовая работа (или проект) | Объем в часах | Время выдачи задания (неделя) | Срок сдачи (неделя) |
| Курсовая работа | ||||
| ВСЕГО (часов) |
Тематика курсовых работ:
1. Интерпретатор языка BASIC.
2. Интерпретатор подмножества языка Pascal.
3. Интерпретатор подмножества языка C.
4. Конвертор (X)HTML в текст c wiki-разметкой.
5. Конвертор SQL-запросов БД разных производителей
6. Математический пакет для расчета производных функций.
7. Построитель LALR(1) распознавателей.
8. Построитель LL(k) распознавателей.
9. Калькулятор, оптимизированный по скорости повторных вычислений с подстановкой.
10. Произвольная тема (согласованная с преподавателем).
Самостоятельные задания
| № п.п. | Вид и темы самостоятельных Заданий | Объем в часах | Время выдачи задания (неделя) | Срок сдачи (неделя) |
| Темы для самостоятельного изучения | ||||
| 1.1 | Построение грамматики, поиск основы | |||
| 1.2 | Построение лексического анализатора | |||
| 1.3 | Построение рекурсивного нисходящего распознавателя | |||
| 1.4 | Построение матриц отношений FIRST и LAST | |||
| 1.5 | Построение LL(1) распознавателя | |||
| 1.6 | Построение SLR(1) распознавателя | |||
| ВСЕГО (часов) |
2.4.3. Прочие виды самостоятельной работы:
- подготовка к занятиям по конспектам и литературе (п.3) - 1 час в неделю (36 часов за два семестра)
ВСЕГО ЧАСОВ ПО РАЗДЕЛУ 2.4 ___ 81
