МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГБОУ ВПО «Кемеровский государственный университет»

Новокузнецкий институт (филиал)

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

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

ФТД.5 Языки программирования и методы трансляции

для специальности 080801.65 Прикладная информатика (в экономике)

Новокузнецк 2013 г.

Сведения о разработке и утверждении рабочей программы дисциплины Рабочая программа дисциплины ФТД.5 Языки программирования и методы трансляции цикла ФТД составлена в соответствии с ООП специальности 080801.65 Прикладная информатика (в экономике).

Автор: Дмитриев В.В., к.т.н., доцент Рецензент:

Пояснительная записка 1. Цели и задачи дисциплины Цель: Знакомство с теоретическими основами языков программирования и методов трансляции.

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

Обучение по курсу базируется на знаниях, полученных студентами при изучении дисциплины «Информатика и программирование».

Итоговый контроль осуществляется в виде зачета. Промежуточный контроль знаний осуществляется в виде опросов по изученным темам.

Виды занятий и формы контроля Очная форма обучения Аудиторные занятия Самостоятельная Итоговая Семестр работа аттестация всего лекции лабораторные работы зачет 3 96 54 Итого 96 54 Очно-заочная форма обучения Аудиторные занятия Самостоятельная Итоговая Семестр работа аттестация всего лекции лабораторные работы зачет 3 96 8 Итого 96 8 Заочная форма обучения Аудиторные занятия Самостоятельная Итоговая Семестр работа аттестация всего лекции лабораторные работы зачет 2 96 8 Итого 96 8 1. Учебно-тематический план учебной дисциплины Объем часов Аудиторная работа Практи Лаб ческие орат Самос Название и содержание разделов, тем, Форма № Общ (или тоятел модулей контроля Лек орн ьная ий семина ции ые работа рские) заня заняти тия я 1 2 3 4 5 6 7 Очная форма обучения Основные концепции языков опрос 10 6 программирования Способы описание языка программирования Автоматы и преобразователи с магазинной памятью Промежуточные формы представления программ Разработка и реализация синтаксически управляемого перевода Основные концепции языков программирования Способы описание языка программирования Автоматы и преобразователи с магазинной памятью Промежуточные формы представления программ Разработка и реализация синтаксически управляемого перевода Очно-заочная и заочная формы обучения – зачет.

2.1 Лекционные занятия Тема № 1 Основные концепции языков программирования: Парадигмы языков программирования. Критерии оценки языков программирования. Объекты данных в языках программирования. Механизмы типизации. Время жизни переменных. Область видимости переменных. Типы данных. Выражения и операторы присваивания. Структура управления на уровне операторов. Подпрограммы.

Тема № 2 Способы описание языка программирования: Определение синтаксиса языка. Форма Бэкуса-Наура. Синтаксические диаграммы Вирта. Описание контекстных условий. Описание динамической семантики.

Тема № 3 Формальные грамматики и языки: Способы определения формальных языков. Формальные грамматики. Классификация формальных грамматик. Выводы и деревья выводов. Неоднозначность грамматик. Непустые, конечные и бесконечные языки. Эквивалентные преобразования КС-грамматик.

Нормальная форма Хомского. Нормальная форма Грейбах. Свойства замкнутости КСязыков.

Тема № 4 Конечные автоматы и преобразователи: Распознающий автомат.

Конечный автомат. Способы задания конечных автоматов. Детерминированные конечные автоматы. Автоматные грамматики и конечные автоматы. Решение проблемы принадлежности для конечных автоматов. Решение проблемы пустоты языка для конечных автоматов. Конечные преобразователи.

Тема № 5 Автоматы и преобразователи с магазинной памятью: Определение автомата с магазинной памятью. Расширенные МП-автоматы. Эквивалентность МПавтоматов и КС-грамматик. Детерминированные МП-автоматы. Преобразователи с магазинной памятью.

Тема № 6 Общие методы синтаксического анализа: Определение разбора.

Нисходящий разбор. Восходящий разбор. Моделирование недетерминированного МПпреобразователя. Алгоритм нисходящего разбора. Алгоритм восходящего разбора.

Алгоритм Эрли. LL(k)-грамматики. LR(k)-грамматики. Грамматики предшествования.

Тема № 7 Промежуточные формы представления программ: Польская запись.

Тетрады. Триады. Байт-код JVM.

Тема № 8 Формальные методы описания перевода: Перевод и семантика. СУсхемы. Транслирующие грамматики. Атрибутные транслирующие грамматики.

Методика разработки описания перевода. Пример разработки АТ-грамматики.

Тема № 9 Разработка и реализация синтаксически управляемого перевода:

L-атрибутные и S-атрибутные транслирующие грамматики. Форма простого присваивания. Атрибутные перевод для LL(1)-грамматик.

3. Учебно-методические обеспечение по дисциплине 3.1. Список основной учебной литературы 1. Кауфман В.Ш. Языки программирования. Концепции и принципы [Электронный ресурс]: Учебник. – М.: ДМК Пресс, 2010. – 464 с.

http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id= 3.2. Список дополнительной учебной литературы 1. Истомин Е.П. Высокоуровневые методы информатики и программирования [Текст]:

учебник для вузов / Е.П. Истомин, В.В. Новиков, М.В. Новикова. СПб: Андреевский издательский дом, 2008. – 228 с. – Гриф УМО «Рекомендовано».

2. Свердлов С.З. Языки программирования и методы трансляции [Текст] :- СПб. : Питер, 2007. - 637 с.

2. Опалева, Э. А. Языки программирования и методы трансляции [Текст] : учебное пособие для вузов. - СПб. : БХВ-Петербург, 2005. - 480 с. - Гриф УМО "Рекомендовано". ISBN 5-94157-327-8 : 194-78.

3. Пратт Т., Зелковиц М. Языки программирования: разработка и реализация [Текст]. 4-е изд. - СПб.: Питер, 2002. - 688 с.: ил.

3.2. Электронные ресурсы 1. Стивенс Р. Delphi. Готовые алгоритмы [Электронный ресурс]: Учебник. – М.: ДМК Пресс, 2007. – 384 с.

http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id= 2. Липман С., Лажойе Ж. Язык программирования С++. Полное руководство [Электронный ресурс]: Учебник. – М.: ДМК Пресс, 2007. – 1105 с.

http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id= 4. Формы текущего, промежуточного и рубежного контроля 4.1. Формы и порядок проведения контроля. Критерии оценки знаний студентов.

Примерный перечень вопрос для устного опроса.

Тема № 1. Основные концепции языков программирования Тема № 2. Способы описание языка программирования Тема № 3. Формальные грамматики и языки Тема № 4. Конечные автоматы и преобразователи Тема № 5. Автоматы и преобразователи с магазинной памятью Тема № 6. Общие методы синтаксического анализа Тема № 7. Промежуточные формы представления программ Тема № 8. Формальные методы описания перевода Тема № 9. Разработка и реализация синтаксически управляемого перевода 4.2. График самостоятельной работы 4.2.1. Для очной формы обучения Формы аудиторных учебных занятий (час.) Основные концепции языков программирования Способы описание языка программирования Формальные грамматики и языки Конечные автоматы и преобразователи Автоматы и преобразователи с магазинной Общие методы синтаксического анализа Промежуточные формы представления Формальные методы описания перевода Разработка и реализация синтаксически управляемого перевода 4.2.2. Очно-заочная форма обучения Формы аудиторных учебных занятий (час.) Основные концепции языков программирования Способы описание языка программирования Формальные грамматики и языки Конечные автоматы и преобразователи Автоматы и преобразователи с магазинной Общие методы синтаксического анализа Промежуточные формы представления Формальные методы описания перевода Разработка и реализация синтаксически управляемого перевода 4.3. Вопросы и задания для индивидуальной и самостоятельной работы 4.4. Примерный перечень вопросов к экзамену 1. Парадигмы языков программирования.

2. Критерии оценки языков программирования.

3. Объекты данных в языках программирования.

4. Механизмы типизации.

5. Время жизни переменных.

6. Область видимости переменных.

7. Типы данных.

8. Выражения и операторы присваивания.

9. Структура управления на уровне операторов.

10.Подпрограммы.

11.Способы описания языка программирования 12.Определение синтаксиса языка.

13.Форма Бэкуса-Наура.

14.Синтаксические диаграммы Вирта.

15.Описание контекстных условий.

16.Описание динамической семантики.

17.Формальные грамматики.

18.Способы определения формальных языков.

19.Формальные грамматики.

20.Классификация формальных грамматик.

21.Выводы и деревья выводов.

22.Неоднозначность грамматик.

23.Непустые, конечные и бесконечные языки.

24.Эквивалентные преобразования КС-грамматик.

25.Нормальная форма Хомского.

26.Нормальная форма Грейбах.

27.Свойства замкнутости КС-языков.

28.Распознающий автомат.

29.Конечный автомат.

30.Способы задания конечных автоматов.

31.Детерминированные конечные автоматы.

32.Автоматные грамматики и конечные автоматы.

33.Решение проблемы принадлежности для конечных автоматов.

34.Решение проблемы пустоты языка для конечных автоматов.

35.Конечные преобразователи.

36.Определение автомата с магазинной памятью.

37.Расширенные МП-автоматы.

38.Эквивалентность МП-автоматов и КС-грамматик.

39.Детерминированные МП-автоматы.

40.Преобразователи с магазинной памятью.

41.Определение разбора.

42.Нисходящий разбор.

43.Восходящий разбор.

44.Моделирование недетерминированного МП-преобразователя.

45.Алгоритм нисходящего разбора.

46.Алгоритм восходящего разбора.

47.Алгоритм Эрли.

48.LL(k)-грамматики.

49.LR(k)-грамматики.

50.Грамматики предшествования.

51.Промежуточные формы представления программ.

52.Польская запись.

53.Тетрады.

54.Триады.

55.Байт-код JVM.

56.Формальные методы описания перевода.

57.Перевод и семантика.

58.СУ-схемы.

59.Транслирующие грамматики.

60.Атрибутные транслирующие грамматики.

61.Методика разработки описания перевода.

62.Пример разработки АТ-грамматики.

63.Атрибутные перевод для LL(1)-грамматик.