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

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

рабочая программа дисциплины
Закреплена за кафедройКафедра информатики
Направление подготовки02.03.02. Фундаментальная информатика и информационные технологии
Форма обученияОчная
Общая трудоемкость6 ЗЕТ
Учебный план02_03_02_ФИиИТ-4-2019
Часов по учебному плану 216
в том числе:
аудиторные занятия 86
самостоятельная работа 103
контроль 27
Виды контроля по семестрам
экзамены: 6

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

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

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

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

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

разработана в соответствии с ФГОС:
ФГОС ВО Приказ Минобрнауки России от 12.03.2015 N 224 "Об утверждении федерального государственного образовательного стандарта высшего образования по направлению подготовки 02.03.02 Фундаментальная информатика и информационные технологии (уровень бакалавриата)" (Зарегистрировано в Минюсте России 01.04.2015 N 36674)

составлена на основании учебного плана:
02.03.02 Фундаментальная информатика и информационные технологии
утвержденного учёным советом вуза от 25.06.2019 протокол № 9.

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

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

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


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

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

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

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


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

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

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

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

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

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

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

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

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

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

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