Рабочая программа по дисциплине «Языки программирования и методы трансляции» для направления 010500 (510200) «Прикладная математика и информатика» Факультет систем управления
| Вид материала | Рабочая программа |
- Утверждены Методическим Советом иэупс, протокол №8 от 24. 04. 2008г. Языки программирования, 320.93kb.
- Программа дисциплины опд. Ф. 05. Языки программирования и методы трансляции для студентов, 92.34kb.
- Рабочая программа По дисциплине "Методы оптимизации " Для направления 010500 «Прикладная, 109.25kb.
- Рабочая программа по дисциплине: «Компьютерное моделирование» по направлению (010500), 61.06kb.
- Рабочая программа по дисциплине «Основы теории управления» для направления 010500 «Прикладная, 228.68kb.
- Рабочая программа по дисциплине «принятие управленческих решений» (по выбору) для специальности, 89.25kb.
- Программа дисциплины Численные методы для направления 010500. 62 «Прикладная математика, 159.87kb.
- Программа дисциплины математический анализ и обыкновенные дифференциальные уравнения., 139.76kb.
- Программа дисциплины Современная прикладная алгебра для направления 010500 Прикладная, 214.78kb.
- Программа государственного экзамена по направлению 010500. 62 прикладная математика, 57.44kb.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Томский государственный университет систем управления и радиоэлектроники
УТВЕРЖДАЮ
Проректор по учебной работе
__________ М.Т.Решетников
"____"_______________2007 г.
РАБОЧАЯ ПРОГРАММА
По дисциплине «Языки программирования и методы трансляции»
для направления 010500 (510200) — «Прикладная математика и информатика»
Факультет - систем управления
Профилирующая кафедра - Автоматизированных систем управления
Курс - 2
Семестр – 3,4
Учебный план набора 2005 и последующих лет
Распределение учебного времени:
Лекции - 35 часа
Лабораторные занятия - 52 часов
Практические занятия - 17 часов
Всего аудиторных занятий - 104 часов
Самостоятельная работа - 49 часа
Общая трудоемкость - 153 часов
Зачет - 3 семестр, Экзамен - 4 семестр
2007
Рабочая программа составлена в соответствии с Государственным образовательным стандартом по направлению подготовки 010500 (510200) — «Прикладная математика и информатика»
Рабочая программа обсуждена на заседании кафедры АСУ, протокол № __ от «__» _______ 2007 г.
Зав. обеспечивающей кафедрой А.М.Кориков
Рабочая программа согласована с факультетом, профилирующей и выпускающей кафедрами специальности.
Разработчик В.Т.Калайда
Декан ФСУ Н.В.Замятин
Зав. профилирующей кафедрой А.М.Кориков
1. Цели и задачи дисциплины
Языки программирования и методы трансляции – дисциплина входящая в цикл «Общепрофессиональные дисциплины направления» (ОПД.Ф.05), объединяющая знания в области теории формальных языков, формальных грамматик, теории автоматов и методов трансляции.
Целью данной дисциплины является систематическое рассмотрение основных понятий языков программирования; синтаксиса, семантики, формальных способов описания языков программирования; типов данных, способов и механизмов управления данными; методов и основных этапов трансляции; конструкции распределенного и параллельного программирования.
2. Требования к уровню освоения содержания дисциплины
В результате изучения курса студенты должны:
- знать теоретические основы методов проектирования и способы описания языков программирования, основные положения теории формальных грамматик и языков, методов синтаксического анализа и перевода для класса формальных языков, используемых для описания основных конструкций языков программирования, стандарты, используемые для языков программирования;
- уметь самостоятельно выполнять формальное описание синтаксиса и семантики, несложных процедурно - ориентированных и проблемно - ориентированных языков программирования, разрабатывать алгоритмы, реализующие методы синтаксического анализа и перевода для наиболее часто используемых классов формальных грамматик, пользоваться стандартными терминами и определениями, читать научные статьи и пользоваться литературой для самостоятельного решения научно - исследовательских задач, связанных с разработкой языков и реализацией систем программирования;
- иметь представление о перспективных направлениях работ и методических подходах в области формальных методов описания и введения стандартов, используемых для описания языков программирования.
3. Объем дисциплины и виды учебной работы
| Вид учебной работы | Всего часов | Семестр 3 | Семестр 4 |
| Общая трудоемкость дисциплины | 153 | | |
| Аудиторные занятия | 104 | 36 | 68 |
| Лекции | 35 | 18 | 17 |
| Практические занятия (ПЗ) | 17 | | 17 |
| Лабораторные работы (ЛР) | 52 | 18 | 34 |
| Самостоятельная работа | 49 | 25 | 24 |
| Курсовой проект (работа) | | | |
| Вид итогового контроля | | зачет | экзамен |
4. Содержание дисциплины
4.1. Разделы дисциплины и виды занятий
| № п/п | Раздел дисциплины | Лекции /самостоятельно | ПЗ /самостоятельно | ЛЗ /самостоятельно |
| 1 | Введение | 2/0 | | |
| 2 | Математические методы формального описания языка. | 6/6 | 7/ | |
| 3 | Введение в теорию компиляции. | 4/4 | | 18/8 |
| 4 | Теория языков. | 4/6 | | |
| 5 | Контекстно свободные грамматики. | 5/6 | 10/5 | |
| 6 | Автоматы с магазинной памятью. | 4/6 | | |
| 7 | Методы синтаксического анализа. | 4/4 | 7/3 | 34/17 |
| 8 | Включение действий в синтаксис. | 2/2 | | |
| 9 | Распределение памяти. | 2/2 | | |
| 10 | Исправление и диагностика ошибок. | 2/2 | | |
| ИТОГО | 35/16 | 17/8 | 52/25 | |
4.2. Содержание разделов дисциплины
Введение.
Краткая характеристика дисциплины, ее цели и задачи, порядок изучения материала, связи с другими дисциплинами учебного плана и место в подготовки инженеров по специальности 230105. Перечень дисциплин, усвоение которых необходимо студентам для изучения данной дисциплины. Основы методики и форм контроля самостоятельной работы, краткая характеристика учебной литературы. Организация компилятора.
Математические методы формального описания языка.
Множество цепочек. Операции над цепочками. Языки. Операции над языками. Итерация языка. Гомоморфизм. Алгоритмы. Частичные алгоритмы. Полные алгоритмы. Рекурсивные алгоритмы. Задание алгоритмов. Проблемы. Пример формального описания языка.
Введение в теорию компиляции.
Задание языков программирования. Синтаксис и семантика. Процесс компиляции. Лексический анализ. Работа с таблицами. Синтаксический анализ. Генерация кода. Алгоритм генерации кода. Оптимизация кода. Исправление ошибок. Анализ структурной схемы компилятора.
Теория языков.
Способы определения языков. Грамматики. Грамматики с ограничениями на правила. Распознаватели. Регулярные множества, их распознавание и порождение. Алгоритм решения системы линейных уравнений с регулярными выражениями. Регулярные множества и конечные автоматы. Проблема разрешимости.
Графическое представление конечных автоматов. Минимизация конечных автоматов. Алгоритм построения канонического конечного автомата.
Контекстно - свободные грамматики.
Основные понятия и определения. Деревья выводов. Преобразование КС-грамматик. Алгоритм устранения недостижимых символов. Алгоритм преобразования в грамматику без e-правил. Алгоритм устранения цепных правил.
Грамматика без циклов. Нормальная форма Хомского. Нормальная форма Грейбах. Алгоритм устранения левой рекурсии.
Автоматы с магазинной памятью.
Автоматы с магазинной памятью (МП-автоматы). Расширенные МП-автоматы. Недетерминированные и детерминированные МП-автоматы. Языки, допускаемые МП-автоматами. Эквивалентность МП-автоматов и КС-грамматик. Конечный преобразователь. Регулярный перевод. Преобразователь с магазинной памятью.
Методы синтаксического анализа.
Прямые и синтаксически ориентированные методы анализа. Нисходящая методика синтаксического анализа. LL(K)-грамматики. Алгоритмы разбора для LL(1)-грамматики. Метод рекурсивного спуска.
Алгоритм разбора для LR(K)-грамматики. S-грамматика. Алгоритмы построения управляющей таблицы LL(1)-грамматики Формальное определение алгоритма разбора типа "перенос-свертка". Грамматика предшествования. Простое, слабое, оперативное предшествование
Включение действий в синтаксис.
Получение четверок. Работа с таблицей символов.
Распределение памяти.
Стек времени прогона. Методы вызова параметров. Вызов по значению. Вызов по имени. Вызов по результату. Вызов по значению и результату. Вызов по ссылке. Куча. Счетчик ссылок. Сборка мусора.
Исправление и диагностика ошибок.
Типы ошибок. Лексические ошибки. Ошибки в употреблении скобок. Синтаксические ошибки. Режим переполоха. Исключение символов. Включение символов. Правила для ошибок. Сообщения о синтаксических ошибках. Контекстно-зависимые ошибки Ошибки, связанные с употреблением типов. Ошибки, допускаемые во время прогона. Ошибки, связанные с нарушением ограничений.
- Лабораторный практикум
| №п/п | № раздела дисциплины | Наименование работ | Объем (час) |
| 1 | 3 | Генерации и оптимизации промежуточного кода для арифметического выражения. | 18 |
| 2 | 7 | Построить грамматику и написать программы разбора описания структуры для языков Pascal и C++ методом рекурсивного спуска | 10 |
| 3 | 7 | Построить грамматику и построить таблицу разбора LL(1) и написать программу разбора описания структуры для языков Pascal и C++. | 12 |
| 4 | 7 | Построить грамматику, таблицу разбора LR(1) и написать программу разбора описания структуры для языков Pascal и C++. | 12 |
- Практикум
| №п/п | № раздела дисциплины | Наименование работ | Объем (час) |
| 1 | 5, | Разработать КС-грамматику (LL(1)) для описания структуры структуры для языков Pascal и C++. | 5 |
| 2 | 7 | Разработать КС-грамматику (LR(1)) для описания структуры структуры для языков Pascal и C++.. | 3 |
- Форма самостоятельной работы
| № п/п | Наменование работы | Кол-во часов | Форма контроля |
| 1. | Проработка лекционного материла | 16 | Экзамен |
| 2. | Подготовка к практическим и семинарским занятиям. Выполнение лабораторных работ. | 33 | Опрос и проверка на практических занятиях |
| | Всего часов самостоятельной работы по дисциплине | 49 | |
- Учебно-методическое обеспечение дисциплины
а) Основная литература:
1. Калайда В.Т. Теория вычислительных процессов и структур. Учебное пособие. – Томск: Изд. – во, ТУСУР, 2007 – 235 с. (50 экз.)
2. Ахо А., Ульман Дж. Теория синтаксического перевода и компиляции. Т.1,2. - М.: Мир, 1978 (2005) – 612 с. (6 экз.)
3. Хантер Р. Проектирование и конструирование компиляторов. — М.: Финансы и статистика, 1985 – 230 с. (6 экз.)
4. Молчанов А. Ю. Системное программное обеспечение: Учебник для вузов. СПб.: Питер, 2003. – 395 с. (8 экз.)
б) Дополнительная литература:
1. В.Дж.Райуорд-Смит. Теория формальных языков. Вводный курс. — М.: Радио и связь, 1988.
2. Льюис Ф., Розешкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. — М.: Мир, 1979. (2 экз.)
3. Вайгартен Ф. Трансляция языков программирования. М.: Мир, 1977.
- Контроль обучения: экзамен
Контроль обучения осуществляется в соответствии с рейтинговой системой. Рейтинговые оценки распределяются в соответствии с таблицей:
| Вид занятий | Оценка (балл) | Итог | |||
| Семестр 3 | | ||||
| Лекции | Контрольная точка №1 | Контрольная точка №2 | | ||
| 20 | 20 | 40 | |||
| Практикум | Задача 1 | Задача 2 | Задача 3 | Задача 4 | |
| 20 | 20 | 20 | 20 | 80 | |
| | 120 | ||||
| Лекции | Контрольная точка №1 | Контрольная точка №2 | | ||
| 20 | 20 | | |||
| | Задача 1 | Задача 2 | Задача 2 | Задача 2 | |
| 20 | 20 | 20 | 20 | | |
| | | | | | 120 |
Максимальный семестровый рейтинг = 120 баллов.
Контрольная точка № 1: контрольная работа по лекционному материалу.
Контрольная точка № 2: контрольная работа по лекционному материалу.
Максимально за контрольную работу – 30 баллов.
Зачет по курсу в 7 семестре автоматически выставляется при наличии 80-120 баллов.
Экзаменационная оценка «Отлично» по предмету выставляется автоматически при наличии 100–120 баллов за 8 семестр и защищенного курсового проекта на оценку «Отлично». Оценка «Хорошо» по предмету выставляется автоматически при наличии при наличии 80—99 баллов за 8 семестр и защищечноого курсовоого проекта на оценку не менее чем «Хорошо».
При недостаче баллов решаются дополнительные задачи (каждая задача = 10 баллов).
- Требования к обязательному минимуму содержания основной
образовательной программы по дисциплине
| ОПД.Ф.05 | Языки программирования и методы трансляции: |
| | основные понятия языков программирования; синтаксис, семантика, формальные способы описания языков программирования; типы данных, способы и механизмы управления данными; методы и основные этапы трансляции; конструкции распределенного и параллельного программирования. |