МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Алтайский государственный университет»

Теория алгоритмических языков и трансляторов

рабочая программа дисциплины
Закреплена за кафедройКафедра информатики
Направление подготовки02.03.01. Математика и компьютерные науки
Форма обученияОчная
Общая трудоемкость3 ЗЕТ
Учебный план02_03_01_МиКН-4-2019
Часов по учебному плану 108
в том числе:
аудиторные занятия 36
самостоятельная работа 72
Виды контроля по семестрам
зачеты: 6

Распределение часов по семестрам

Курс (семестр) 3 (6) Итого
Недель 19
Вид занятий УПРПДУПРПД
Лекции 18 18 18 18
Лабораторные 18 18 18 18
Сам. работа 72 72 72 72
Итого 108 108 108 108

Программу составил(и):
к.т.н., доцент, Михеева Т.В.

Рецензент(ы):
к.ф.-м.н., доцент, Пономарев И.В.

Рабочая программа дисциплины
Теория алгоритмических языков и трансляторов

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 02.03.01 Математика и компьютерные науки (уровень бакалавриата) (приказ Минобрнауки России от 07.08.2014г. №949)

составлена на основании учебного плана:
02.03.01 Математика и компьютерные науки
утвержденного учёным советом вуза от 25.06.2019 протокол № 9.

Рабочая программа одобрена на заседании кафедры
Кафедра информатики

Протокол от 22.06.2019 г. № 8
Срок действия программы: 2019-2020 уч. г.

Заведующий кафедрой
Жариков А.В., доцент, к.ф.-м.н.


Визирование РПД для исполнения в очередном учебном году

Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2019-2020 учебном году на заседании кафедры

Кафедра информатики

Протокол от 22.06.2019 г. № 8
Заведующий кафедрой Жариков А.В., доцент, к.ф.-м.н.


1. Цели освоения дисциплины

1.1.сформировать у студентов необходимую теоретическую базу и практические навыки, которые позволят на практике применять методы формального описания языков;
овладение основными методами проектирования и программирования лексических и синтаксических анализаторов языков;
овладение основными методами решения практических задач разработки программ обработки языков;
выработка умения самостоятельно расширять знания по математической лингвистике и применять их для решения прикладных задач.

2. Место дисциплины в структуре ООП

Цикл (раздел) ООП: Б1.В

3. Компетенции обучающегося, формируемые в результате освоения дисциплины

ПК-7 способностью использовать методы математического и алгоритмического моделирования при анализе управленческих задач в научно-технической сфере, в экономике, бизнесе и гуманитарных областях знаний
В результате освоения дисциплины обучающийся должен
3.1.Знать:
3.1.1.правила построения трансляторов;
методы лексического, синтаксического и семантического анализа алгоритмических языков;
принципы трансляции и интерпретации
3.2.Уметь:
3.2.1.строить КС-грамматики формальных языков;
выделять лексический и синтаксический уровень языка;
программировать основные классы трансляторов
3.3.Иметь навыки и (или) опыт деятельности (владеть):
3.3.1.методами анализа и трансляции алгоритмических языков

4. Структура и содержание дисциплины

Код занятия Наименование разделов и тем Вид занятия Семестр Часов Компетенции Литература
Раздел 1. Языки и грамматики.
1.1. Лингвистические средства программных систем. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
1.2. Порождающие грамматики и языки. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
1.3. Синтез контекстно-свободных грамматик. Лабораторные 6 1 ПК-7 Л2.1, Л1.1
1.4. Синтез контекстно-свободных грамматик. Сам. работа 6 4 ПК-7 Л2.1, Л1.1
Раздел 2. Синтаксический анализ
2.1. Дерево синтаксического анализа. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
2.2. Стратегии синтаксического анализа. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
2.3. Построение деревьев в процессе восходящего и нисходящего синтаксического анализа. Лабораторные 6 1 ПК-7 Л2.1, Л1.1
2.4. Восходящий и нисходящий синтаксический анализ. Сам. работа 6 4 ПК-7 Л2.1, Л1.1
Раздел 3. Раздел 3. Автоматы.
3.1. Порождающие грамматики и автоматы. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
3.2. Теоремы об автоматах с магазинной памятью и контекстно-свободных грамматиках. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
3.3. Синтез автоматов с магазинной памятью. Лабораторные 6 1 ПК-7 Л2.1, Л1.1
3.4. Синтез конечных автоматов. Сам. работа 6 4 ПК-7 Л2.1, Л1.1
Раздел 4. Формальное описание языков программирования.
4.1. Модель языка. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
4.2. Программная реализация модели языка. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
4.3. Построение контекстно-свободной грамматики языка. Лабораторные 6 1 ПК-7 Л2.1, Л1.1
4.4. Контекстно-свободные грамматики выражений с приоритетами операций. Сам. работа 6 2 ПК-7 Л2.1, Л1.1
Раздел 5. Структура компилятора.
5.1. Модель языка программирования и этапы перевода. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
5.2. Назначение блоков лексического, синтаксического и семантического анализа. Лабораторные 6 1 ПК-7 Л2.1, Л1.1
Раздел 6. Лексический анализ.
6.1. Лексика языка. Регулярные выражения и конечные автоматы. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
6.2. Построение конечного автомата лексики языка, реализация программы сканера. Лабораторные 6 1 ПК-7 Л2.1, Л1.1
6.3. Реализация программы сканера. Сам. работа 6 4 ПК-7 Л2.1, Л1.1
Раздел 7. Понятие синтаксического анализа.
7.1. Проблемы и особенности стратегий синтаксического анализа. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
7.2. Общая характеристика синтаксически ориентированных компиляторов. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
7.3. Синтез контекстно-свободных грамматик языков программирования. Лабораторные 6 1 ПК-7 Л2.1, Л1.1
7.4. Общие и специальные методы синтаксического анализа. Сам. работа 6 8 ПК-7 Л2.1, Л1.1
Раздел 8. Метод рекурсивного спуска реализации синтаксического анализа.
8.1. Построение и преобразование синтаксических диаграмм. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
8.2. Программная реализация синтаксических диаграмм. Лекции 6 1 ПК-7 Л2.1, Л1.1
8.3. Общие и специальные методы синтаксического анализа. Сам. работа 6 4 ПК-7 Л2.1, Л1.1
8.4. Программная реализация синтаксического анализатора методом рекурсивного спуска. Лабораторные 6 1 ПК-7 Л2.1, Л1.1
Раздел 9. Контекстные условия формальных языков.
9.1. Понятие контекстной зависимости. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
9.2. Типы контекстной зависимости для различных конструкций языков программирования. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
9.3. Контекстные зависимости для формирования бинарного дерева подчинения. Лабораторные 6 1 ПК-7 Л2.1, Л1.1
9.4. Контекстная зависимость языков программирования. Сам. работа 6 4 ПК-7 Л2.1, Л1.1
Раздел 10. Семантический контроль и деревья подчинения.
10.1. Семантические таблицы компилятора и их структура. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
10.2. Понятие семантической подпрограммы. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
10.3. Формирование бинарного дерева подчинения Лабораторные 6 1 ПК-7 Л2.1, Л1.1
10.4. Таблица приведений языка программирования и ее реализация Сам. работа 6 2 ПК-7 Л2.1, Л1.1
Раздел 11. Магазинные методы синтаксического анализа.
11.1. Автоматы с магазинной памятью как основа программирования универсального синтаксического анализатора. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
11.2. LL(1)-анализаторы. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
11.3. Построение управляющей таблицы LL(1)-анализатора. Лабораторные 6 2 ПК-7 Л2.1, Л1.1
11.4. Проблемы вычислительной сложности при реализации недетерминированных автоматов с магазинной памятью. Сам. работа 6 4 ПК-7 Л2.1, Л1.1
Раздел 12. Принципы интерпретации в процессе синтаксического анализа.
12.1. Принципы интерпретации. Лекции 6 0,5 ПК-7 Л2.1, Л1.1
12.2. Реализация интерпретации выражений. Лабораторные 6 2 ПК-7 Л2.1, Л1.1
12.3. Выделение памяти для конструкций языка в процессе интерпретации. Лекции 6 1 ПК-7 Л2.1, Л1.1
12.4. Алгоритмы интерпретации простейших типов данных. Сам. работа 6 8 ПК-7 Л2.1, Л1.1
Раздел 13. Интерпретация управляющих структур.
13.1. Понятие флага интерпретации и его использование. Лекции 6 1 ПК-7 Л2.1, Л1.1
13.2. Интерпретация циклических и ветвящихся процессов. Лекции 6 1 ПК-7 Л2.1, Л1.1
13.3. Реализация интерпретации. Лабораторные 6 2 ПК-7 Л2.1, Л1.1
13.4. Реализация интерпретации. Сам. работа 6 8 ПК-7 Л2.1, Л1.1
Раздел 14. Перевод и синтез кода.
14.1. Понятие промежуточного языка. Лекции 6 1 ПК-7 Л2.1, Л1.1
14.2. Способы представления промежуточного кода. Деревья, префиксная и постфиксная запись, триады и тетрады. Лекции 6 1 ПК-7 Л2.1, Л1.1
14.3. Структура промежуточного кода. Лабораторные 6 2 ПК-7 Л2.1, Л1.1
14.4. Типы промежуточных языков. Сам. работа 6 8 ПК-7 Л2.1, Л1.1
Раздел 15. Генерация кода и синтаксически управляемый перевод.
15.1. Понятие синтаксически управляемого перевода. Лекции 6 1 ПК-7 Л2.1, Л1.1
15.2. Модели естественных языков и этапы перевода с естественного языка на формальный. Лекции 6 1 ПК-7 Л2.1, Л1.1
15.3. Направления развития современных языковых программных систем. Сам. работа 6 8 ПК-7 Л2.1, Л1.1

5. Фонд оценочных средств

5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины
в приложении
5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.)
в приложении
5.3. Фонд оценочных средств для проведения промежуточной аттестации
в приложении

6. Учебно-методическое и информационное обеспечение дисциплины

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Кауфман В.Ш. Языки программирования. Концепции и принципы: Учебник М.: ДМК Пресс // ЭБС "Лань", 2011 e.lanbook.com
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Вирт Н. Алгоритмы и структуры данных: М.: ДМК Пресс, 2010 e.lanbook.com
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
Название Эл. адрес
Э1 Алгоритмы. Методы. Исходнинки algolist.manual.ru
6.3. Перечень программного обеспечения
MS Visual Studio
Microsoft Windows
Microsoft Office
7-Zip
AcrobatReader
6.4. Перечень информационных справочных систем
1. Образовательный портал АлтГУ http://portal.edu.asu.ru/
2. Электронный каталог НБ АлтГУ «Книги»: http://www.lib.asu.ru/app/elecat/elecat=index1?base=book
3. Издательство «Лань» [Электронный ресурс]: электронно-библиотечная система. – URL: http://e.lanbook.com/
4. Издательство «Юрайт» [Электронный ресурс]: электронно-библиотечная система. – URL: http://biblio-online.ru
5. ЭБС «Университетская библиотека online»: https://biblioclub.ru/
6. ЭБС АлтГУ: http://elibrary.asu.ru/

7. Материально-техническое обеспечение дисциплины

8. Методические указания для обучающихся по освоению дисциплины

Изучение дисциплины завершается зачетом. Успешное изучение дисциплины требует посещения лекций, активной работы на лабораторных работах, выполнения всех практических заданий преподавателя, ознакомления с основной и дополнительной литературой. Во время лекции студент должен вести краткий конспект. При этом обучающийся должен стараться найти ответы на затруднительные вопросы, используя рекомендуемую литературу или общедоступные ресурсы. Если ему самостоятельно не удалось разобраться в материале, необходимо сформулировать вопросы и обратится за помощью к преподавателю на консультации или ближайшей лекции. Выполнение студентами практических заданий направлено на:
- обобщение, систематизацию, углубление, закрепление полученных теоретических знаний по конкретным темам дисциплин;
- формирование необходимых профессиональных умений и навыков.
Помимо собственно выполнения практических заданий для каждого задания предусмотрена процедура защиты, в ходе которой преподаватель проводит устный или письменный опрос студентов для контроля понимания выполненных ими действий по теме занятия.
Самостоятельная работа.
- При изучении дисциплины не все вопросы рассматриваются на занятиях, часть вопросов рекомендуется преподавателем для самостоятельного изучения.
- Поиск ответов на вопросы и выполнение заданий для самостоятельной работы позволит вам расширить и углубить свои знания по курсу, применить теоретические знания в решении задач практического содержания, закрепить изученное ранее.
- Эти задания следует выполнять не «наскоком», а постепенно, планомерно, следуя порядку изучения тем курса.
- При возникновении вопросов обратитесь к преподавателю в день консультаций на кафедру.
- Выполнив их, проанализируйте качество их выполнения. Это поможет вам развивать умения самоконтроля и оценочные компетенции.
При подготовке к зачету в дополнение к изучению конспектов лекций, учебно-методических материалов и слайдов, необходимо пользоваться учебной литературой, рекомендованной настоящей программой. При подготовке к зачету нужно изучить определения всех понятий и теоретические подходы до состояния понимания материала, а также выполнить все практические задания в курсе.