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

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

Закреплена за кафедройКафедра информатики
Направление подготовки02.03.01. Математика и компьютерные науки
Форма обученияОчная
Общая трудоемкость3 ЗЕТ
Учебный план02_03_01_МиКН-4-2020
Часов по учебному плану 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 Математика и компьютерные науки
утвержденного учёным советом вуза от 30.06.2020 протокол № 6.

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

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

Заведующий кафедрой
Козлов Д.Ю., доцент, к.ф.-м.н.

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

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

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

Протокол от 30.06.2020 г. № 6
Заведующий кафедрой Козлов Д.Ю., доцент, к.ф.-м.н.

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 8 ПК-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 8 ПК-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 8 ПК-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 8 ПК-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 8 ПК-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 4 ПК-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 2 ПК-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 2 ПК-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 2 ПК-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 2 ПК-7 Л2.1, Л1.1

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

5.1. Контрольные вопросы и задания
в приложении
5.2. Темы письменных работ (эссе, рефераты, курсовые работы и др.)
в приложении
5.3. Фонд оценочных средств
в приложении
Приложения
Приложение 1.   МиКН_ФОС_ТАЯиТранс_20-21.docx

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

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Кауфман В.Ш. Языки программирования. Концепции и принципы: Учебник М.: ДМК Пресс // ЭБС "Лань", 2011 https://e.lanbook.com/reader/book/1270/#1
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Вирт Н. Алгоритмы и структуры данных: М.: ДМК Пресс, 2010 https://e.lanbook.com/book/1261
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
Название Эл. адрес
Э1 Алгоритмы. Методы. Исходнинки http://algolist.manual.ru
Э2 Курс в Moodle "Теория алгоритмических языков и трансляторов" https://portal.edu.asu.ru/course/view.php?id=1037
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. Материально-техническое обеспечение дисциплины

Аудитория Назначение Оборудование
106Л помещение для хранения и профилактического обслуживания учебного оборудования Стеллажи – 3 шт. осциллограф, паяльная станция, источник тока, переносные ноутбуки
107Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 18 посадочных мест; компьютеры: марка HP, модель ProOne 400 - 18 единиц; проектор: марка SMART, модель UF70 - 1 единица; интерактивная доска: марка SMART Board модель SMB680 - 1 единица
110М лаборатория информационных технологий - компьютерный класс – учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; рабочее место преподавателя; доска магнитно-маркерная 1 шт.; компьютеры: марка NAIO Corp Z520 - 14 ед.
109М лаборатория информационных технологий - компьютерный класс – учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 13 посадочных мест; рабочее место преподавателя; доска магнитно-маркерная 1 шт.; компьютеры: марка NAIO Corp Z520 - 13 ед.
202Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка HP - 14 единиц; мониторы: марка ASUS модель VS197DE - 14 единиц
205Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 9 посадочных мест; компьютеры: марка КламаС Офис, мониторы: марка ACER модель V223HQL - 8 единиц; доска интерактивная Triumph MULTI TOUCH 78 + проектор NEC UM280X в комплекте
204Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка DEPO модель Neos 260 - 14 единиц; Интерактивная доска Smart board 680 IV со встроенным проектором v25
203Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка ASUS модель i5-6500 - 14 единиц
207Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка DEPO модель Neos 260, мониторы: марка Philips модель 227E3LHSU - 14 единиц
519М электронный читальный зал с доступом к ресурсам «ПРЕЗИДЕНТСКОЙ БИБЛИОТЕКИ имени Б.Н. Ельцина» - помещение для самостоятельной работы Учебная мебель на 46 посадочных мест; 1 Флипчарт; компьютеры; ноутбуки с подключением к информационно-телекоммуникационной сети "Интернет" и доступом в электронную информационно-образовательную среду; стационарный проектор: марка Panasonic, модель PT-ST10E; стационарный экран: марка Projecta, модель 10200123; система видеоконференцсвязи Cisco Telepresence C20; конгресс система Bosch DCN Next Generation; 8 ЖК-панелей
Учебная аудитория для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска)

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

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