Программа дисциплины «Специализация»

Министерство образования и науки РФ

Государственное образовательное учреждение

высшего профессионального образования

Омский государственный университет

им.

Институт математики и информационных технологий

Кафедра математической логики и логического программирования

«Утверждаю»

Проректор по учебной работе

_________________

«_____» _________________ 20__ г.

Программа дисциплины

«Специализация»

(Формальные языки и методы трансляции)

Цикл ГОС ВПО ДС

входит в число дисциплин по выбору регионального компонента

к следующим образовательным профессиональным программам

подготовки специалистов

Специальность	Код специальности	Форма обучения
Прикладная математика и информатика	010501.65	Очная

Омск – 2010 г.

ЛИСТ СОГЛАСОВАНИЯ РАБОЧЕЙ ПРОГРАММЫ

Программа дисциплины «Формальные языки и методы трансляции»

разработана заведующим кафедрой МЛЛП ОмГУ к. ф.-м. н. .

Программа рассмотрена и одобрена на заседании кафедры

математической логики и логического программирования

(протокол № 2 от «20» сентября 2010 г.)

Программа разработана в соответствии с Государственным образовательным стандартом высшего профессионального образования РФ по следующим специальностям:

«Прикладная математика и информатика»

и согласована с факультетом, осуществляющими профессиональную подготовку по этим специальностям и направлениям.

Директор института

математики и информационных технологий

Распределение общего объема часов по видам учебной деятельности

Курс	Семестр	Объем часов (по видам работ)
Аудиторные занятия	Самостоятельная работа студентов
Всего		Всего
Лекции	Практи-ческие занятия	Семинары	Лабораторные занятия	Другие виды	Курсовая работа	Реферат	Индивидуальные задания	Другие виды
5	9	30	30					15			15
5	10	30	30					15			15

Общая трудоемкость дисциплины: 90 часов.

Формы промежуточного контроля: экзамен (5, 6 семестры). Форма текущего контроля: проверка домашних заданий.

Цели и задачи дисциплины.

Требования к уровню освоения содержания дисциплины

Целью дисциплины является первоначальное знакомство с технологией разработки трансляторов, а также теории конечных автоматов и формальных языков, лежащей в ее основе.

В результате изучения дисциплины студент должен:

знать

·  основные результаты теории конечных автоматов,

·  понятие формальной грамматики, свойства контекстно-свободных языков,

·  основные этапы трансляции и технологии их реализации.

Иметь представление

·  о связях теории формальных языков и технологиях разработки трансляторов.

Для изучения данной дисциплины студенты должны освоить курсы «Языки программирования и методы трансляции», «Дискретная математика».

Тематический план

(с распределением общего бюджета времени в часах)

Курс	Семестр	Раздел дисциплины, содержание	Всего	Аудиторные занятия (часов)	Самостоятельная работа студента	Формы контроля (промежуточного, текущего, итогового)
Лекции	Семинарские (практические) занятия	Лабораторные занятия
5	9	1. Основы теории конечных автоматов.	10	10			5	Экзамен. Проверка домашних работ.
5	9	2. Основы теории формальных грамматик.	12	12			5	Экзамен. Проверка домашних работ.
5	9	3. LL - и LR-грамматики.	8	8			5	Экзамен. Проверка домашних работ.
5	10	4. Основные фазы трансляции. Синтаксически управляемый перевод.	12	12			6	Экзамен. Проверка домашних работ.
5	10	5. Построение основных частей транслятора.	18	18			9	Экзамен. Проверка домашних работ.

Содержание дисциплины

Программа лекций

Раздел	Содержание лекции	Кол-во часов
	1 семестр
1	Формальные языки. Операции над языками. Способы задания языков. Задачи лексического и синтаксического разборов. Регулярные языки. Примеры. Регулярные выражения и определения.	2
1	Детерминированные и недетерминированные конечные автоматы. Автоматные языки.	2
1	Эквивалентность недетерминированных и детерминированных конечных автоматов.	2
1	Минимизация конечных автоматов. Устранение недостижимых и неразличимых состояний.	2
1	Построение по регулярному выражению конечного автомата.	2
2	Понятие формальной грамматики. Вывод в грамматике. Язык грамматики. Иерархия Хомского. Задача синтаксического анализа.	2
2	Контекстно-свободные грамматики. Правые и левые выводы.	2
2	Деревья разбора в контекстно-свободных грамматиках. Однозначные грамматики.	2
2	Преобразования грамматик. Устранение бесполезных символов. Устранение цепных и e-правил. Устранение левой рекурсии.	2
2	Простые алгоритмы синтаксического разбора. Нисходящий разбор с возвратами. Восходящий разбор с возвратами.	2
2	Восходящий разбор с возвратами	2
4	LL-грамматики и их свойства. Множества FIRST и FOLLOW.	2
4	Алгоритмы построения множеств FIRST и FOLLOW.	2
4	Алгоритм синтаксического разбора для LL(1)-грамматик. Построение управляющей таблицы.	2
4	LR-грамматики и их свойства. Подклассы LR-грамматик. Алгоритм синтаксического разбора для SLR(1)-грамматик. Построение управляющей таблицы.	2
	2 семестр
3	Основные фазы трансляции. Задачи лексического и синтаксического разбора.	2
3	Библиотеки регулярных выражений, их использование..	2
3	Реализация лексического анализатора.	2
3	Схемы синтаксически управляемого перевода.	2
3	S-атрибутивные СУ-схемы, их реализация.	2
3	Примеры СУ-схем.	2
4	Выражения типа. Реализация системы проверки типов на базе СУ-схем.	2
4	Трехадресный код. Различные языки промежуточного представления.	2
4	Трансляция объявлений переменных.	2
4	Трансляция арифметических выражений.	2
4	Трансляция логических и смешанных выражений. Неявные преобразования типов.	2
4	Трансляция логических выражений. Технология обратных поправок.	2
4	Трансляция основных управляющих инструкций.	2
4	Трансляция выражений, содержащих обращение к элементам массивов.	2
4	Трансляция вызовов процедур и функций.	2
	Всего	60

Требования к уровню освоения программы и формы текущего

промежуточного и итогового контроля

Требования к выполнению индивидуальных домашних работ:

1.  работа считается выполненной успешно, если решено не меньше 90% задач;

2.  если студент не справился с работой, то ему предлагаются дополнительные задания на экзамене по соответствующей теме.

Требования к проведению экзамена:

1.  экзаменационный билет состоит из двух теоретических вопросов и одного практического, которые охватывают различные разделы учебной программы семестра;

2.  на подготовку ответа на билет дается 1 час;

3.  теоретические вопросы формулируются в соответствии с перечнем вопросов к экзамену, предлагаемому студентам для подготовки;

4.  в процессе подготовки к ответу не разрешается использовать какую-либо дополнительную литературу.

Учебно-методическое обеспечение

Список литературы

Основная

№	Наименование	Число экз.
1	. Системное программное обеспечение. – СПб. [и др.]: Питер, 2010.	80

Дополнительная

4.  . Теория автоматов : Учеб. для вузов - СПб. : Питер, 2003.

5.  , Дж. Д. Ульман. Теория синтаксического анализа, перевода и компиляции: [монография: в 2 т.] / – М.: Мир, 1978.

6.  А. Ахо, М. Лам, Р. Сети, Д. Ульман. Компиляторы. Принципы, технологии, инструменты. – М.: Вильямс, 2008.

7.  Дж. Хопкрофт, Р. Мотвани, Д. Ульман Введение в теорию автоматов, языков и. — М.: Вильямс, 2002.

8.  Касьянов по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. — C. 112.

Методические указания (рекомендации) преподавателю

При изложении материала целесообразно его структурировать, выделять наиболее важные моменты (интонацией, письменно: обвести в рамку, поставить на полях восклицательный знак и т. п. – на это следует особо указать студентам). Рекомендуется использовать проектор и слайды при чтении лекций.

Методические указания для студентов

Важно не допустить возникновения пробелов в усвоении теоретического материала и в умении решать задачи. Это возможно при условии регулярного посещения лекций и практических занятий, обязательном выполнении домашних заданий и активном общении с преподавателем.

Методические указания по организации

внеаудиторной самостоятельной работы студентов

Тема, раздел	Всего часов	Задания для самостоятельной работы	Список литературы для подготовки	Форма контроля
1. Основы теории конечных автоматов.	5	Изучение учебных пособий, выполнение домашних работ	[1, 2, 3–7]	Индивидуальные беседы и консультации. Экзамен.
2. Основы теории формальных грамматик.	5	Изучение учебных пособий, выполнение домашних работ	[2, 4, 5]	Индивидуальные беседы и консультации. Экзамен. проверкой
3. LL - и LR-грамматики.	5	Изучение учебных пособий, выполнение домашних работ	[2, 4]	Индивидуальные беседы и консультации. Экзамен.
4. Основные фазы трансляции. Синтаксически управляемый перевод.	6	Изучение учебных пособий, выполнение домашних работ	[2, 4, 5]	Индивидуальные беседы и консультации. Экзамен.
5. Построение основных частей транслятора.	9	Изучение учебных пособий, выполнение домашних работ	[2, 4, 5]	Индивидуальные беседы и консультации. Экзамен.
ВСЕГО	30

Приложение 1

Вопросы для подготовки к экзамену

1 семестр

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

2 семестр

Основные фазы трансляции. Задачи лексического и грамматического анализа. Построение лексического анализатора. Понятие СУ-схемы. Работа СУ-схемы. Простая система проверки типов на базе СУ-схем. Трансляция объявлений переменных. Трансляция арифметических, логических и смешанных выражений. Работа с массивами, в том числе многомерными. Технология обратных поправок. Трансляция основных управляющих инструкций. Трансляция вызовов процедур и функций.