МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ИНФОРМАТИКИ
УТВЕРЖДАЮ
Декан факультета
« » ____________ 2010 г.
Рабочая программа дисциплины
ТЕОРИЯ АВТОМАТОВ И ФОРМАЛЬНЫХ ЯЗЫКОВ
Направление подготовки
230700 Прикладная информатика
Квалификация выпускника
Бакалавр
Форма обучения
Очная
Томск
2010
1. Цели освоения дисциплины – изучение теории формальных языков, автоматов и методов построения трансляторов.
2. Место дисциплины в структуре ООП бакалавриата
Дисциплина входит в профессиональныйный цикл, базовую часть.
Дисциплины-предшественники: дискретная математика, математическая логика, программирование.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
В результате освоения дисциплины обучающийся должен:
· Знать: теорию языков программирования; методы задания синтаксиса и семантики языков программирования; способы реализации элементов транслятора языков программирования; знать наиболее важные языки программирования и принципы их организации.
· Уметь: анализировать и задавать синтаксис и семантику языка программирования; реализовывать элементы транслятора языка программирования.
· Владеть: способами задания и анализа синтаксиса и семантики языков программирования; методами построения трансляторов.
Знания и умения соответствуют следующим общекультурным и профессиональным компетенциям ООП ВПО:
- способность использовать, обобщать и анализировать информацию, ставить цели и находить пути их достижения в условиях формирования и развития информационного общества (ОК-1);
- способность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности и эксплуатировать современное электронное оборудование и информационно-коммуникационные технологии в соответствии с целями образовательной программы бакалавра (ПК-3);
- способность ставить и решать прикладные задачи с использованием современных информационно-коммуникационных технологий (ПК-4);
- способность моделировать и проектировать структуры данных и знаний, прикладные и информационные процессы (ПК-9);
- способность применять к решению прикладных задач базовые алгоритмы обработки информации, выполнять оценку сложности алгоритмов, программировать и тестировать программы (ПК-10);
- способность применять методы анализа прикладной области на концептуальном, логическом, математическом и алгоритмическом уровнях (ПК-17);
- способность применять системный подход и математические методы в формализации решения прикладных задач (ПК-21);
4. Структура и содержание дисциплины «языки программирования»
Общая трудоемкость дисциплины составляет 3 зачетных единицы, 108 часов.
Содержание дисциплины
ЯЗЫКИ ПРОГРАММИРОВАНИЯ
1. Языки и порождающие грамматики
Язык, как множество цепочек символов. Порождающая грамматика. Классификация порождающих грамматик по Хомскому. Классификация языков. Задача распознавания принадлежности цепочки языку. Недетерминированная процедура распознавания для грамматики класса 0.
2. Автоматные языки и лексический анализ
Автоматные грамматики. Конечный автомат (КА). Недетерминированный КА. Преобразование недетерминированной грамматики в детерминированную. Праволинейные грамматики, их преобразование в автоматные. Регулярные выражения. Семантическая обработка в КА. Таблицы констант, идентификаторов. Преобразование анализируемого текста в лексическом анализаторе. Реализация лексического анализа в виде отдельного прохода и в виде вспомогательной процедуры.
3. Контекстно-свободные грамматики и синтаксический анализ
КС-грамматики. Магазинный автомат. Общий недетерминированный алгоритм анализа сверху-вниз. Общий недетерминированный алгоритм анализа снизу-вверх. Недетерминированность и неоднозначность КС-грамматики и языка. Преобразования КС-грамматики. Удаление из грамматики недостижимых и бесполезных символов. Форма Грейбах. Операторная форма.
4. Синтаксический анализ сверху-вниз
Детерминированный анализ сверху-вниз. Рекурсивный спуск. Преобразование грамматики для рекурсивного спуска. Обобщенная нормальная форма Грейбах. LL-грамматики. Построение и функционирование LL(1)-анализатора.
5. Синтаксический анализ снизу-вверх
Детерминированный анализ снизу-вверх. Грамматики простого предшествования (ПП). Построение отношений ПП. Нестрогое предшествование. Языки простого предшествования. Грамматики операторного предшествования (ОП). Построение отношений ОП. Расширенное предшествование и его применение на практике. LR-грамматики. Построение и функционирование LR(1)-анализатора.
6. Обратная польская строка как внутренний язык
Обратная польская строка (ОПС) для арифметических выражений. Интерпретатор ОПС. ОПС для условных и циклических конструкций. ОПС для процедур и функций. Стековое распределение памяти при вызове процедур и функций. ОПС для индексации массивов. Распределение памяти для массивов. Генерация ОПС при синтаксическом анализе сверху-вниз и снизу-вверх.
Лабораторные работы
Предусмотрена одна комплексная работа, выполняемая самостоятельно, в составе малой группы студентов (2-3 чел.).
Целью работы является реализация интерпретатора с простого языка программирования. Реализуемый язык должен содержать скалярные переменные и константы двух типов (один из них целый), одномерные массивы, а также следующие виды операторов: присваивания и формулы, условные операторы, циклы с условием, вложенные конструкции, описания и вызовы процедур.
№ п/п | Раздел дисциплины | Всего часов | Аудиторные занятия (час), в том числе | Самос-тояте-льная работа | Формы текущего контроля успеваемости | ||
лекции | семи-нары | лабора-торные занятия | |||||
1 | Языки и порождающие грамматики | 4 | 2 | 2 | Письменный контроль по теории | ||
2 | Автоматные языки и лексический анализ | 18 | 4 | 4 | 10 | Письменный контроль по теории. | |
3 | Контекстно-свободные грамматики и синтаксический анализ | 14 | 6 | 8 | Письменный контроль по теории. | ||
4 | Синтаксический анализ сверху-вниз | 26 | 6 | 6 | 14 | Письменный контроль по теории. | |
5 | Синтаксический анализ снизу-вверх | 10 | 4 | 6 | Письменный контроль по теории. | ||
6 | Обратная польская строка как внутренний язык | 36 | 10 | 8 | 18 | Письменный контроль по теории | |
ИТОГО: | 108 | 32 | 18 | 58 | Итоговый письменный контроль Сдача комплексной лабораторной работы |
5. Образовательные технологии
Лекции проводятся в сопровождении иллюстративного материала в форме презентаций. Самостоятельная работа проводится в компьютерном классе, оснащенном соответствующим программным обеспечением.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины
Виды самостоятельной работы студентов: повторение лекционного материала; разработка программ, реализующих отдельные элементы трансляторов в соответствии с заданием преподавателя.
Контроль самостоятельной работы студентов.
Текущий контроль – не менее 4-х раз в течение семестра в виде письменного ответа на теоретические вопросы по содержанию дисциплины; еженедельный контроль по реализации отдельных элементов трансляторов.
Промежуточная аттестация по итогам освоения дисциплины – итоговый письменный экзамен по теоретическим вопросам и сдача комплексной лабораторной работы.
7. Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:
1. Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1-2 / Пер. с англ. – М.: Мир, 1978.
2. Конструирование компиляторов для цифровых вычислительных машин / Пер. с англ. – М.: Мир, 1975.
3. Построение компиляторов / Пер. с англ. – М.: ДМК Пресс, 2010. – 192 с.
б) дополнительная литература:
3. Ершов в теоретическое программирование (беседы о методе). – М.: Наука, 1977. – 288 с.
в) программное обеспечение и Интернет-ресурсы:
1. Транслятор с языка Си или Паскаль в операционной системе Windows или Linux.
2. Программа для проведения презентаций – Power Point или аналогичная.
3. Интернет-браузер – Microsoft Explorer или аналогичный.
8. Материально-техническое обеспечение дисциплины
Лекционная аудитория должна быть оборудована проекционным оборудованием: компьютером и проектором, а также программными средствами для их функционирования.
Компьютерный класс, компьютеры должны быть объединены в локальную сеть с выходом в Интернет.
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ООП ВПО по направлению подготовки 230700 Прикладная информатика.
Автор – профессор
Рецензент – профессор
Программа одобрена на заседании кафедры теоретических основ информатики факультета информатики
от « » __________ 2010 года, протокол № ________ .
