2 курс, осенний и весенний семестры
Лекции - 70 часов
Форма итогового контроля - экзамен

Темы лекций

Сравнительный обзор языков программирования. Языки программирования Фортран, Алгол-60, Кобол, Бейсик, ПЛ/I, Алгол-68, Форт, Пролог, Си, Модула-2, Ада, С++, Оберон, Оберон-2, Ява.

Объектно-ориентированное программирование.

Основы теории формальных языков. Формальные языки. Словарь, цепочка. Способы определения языка, примеры.

Порождающие грамматики Н. Хомского. Порождение предложений языка. Сентенции и сентенциальные формы.

Дерево разбора. Эквивалентность и однозначность грамматик.

Иерархия порождающих грамматик по Н. Хомскому.

Автоматные грамматики и конечные автоматы. Построение и преобразование графа переходов конечного автомата для заданной автоматной грамматики.

Использование конечного автомата для распознавания автоматного языка.

Синтаксические диаграммы автоматной грамматики.

Регулярные выражения и регулярные множества. Эквивалентность регулярных выражений и автоматных грамматик.

Контекстно-свободные грамматики. Однозначность КС-грамматики. Левосторонний и правосторонний вывод. Нисходящий и восходящий разбор КС-языков. Общий алгоритм распознавания КС-языков. Самовложение в КС-грамматиках.

Синтаксический анализ КС-языков методом рекурсивного спуска.

Требование детерминированного распознавания. LL(k) и LL(1) - грамматики. Левая и правая рекурсия.

Грамматика и синтаксический анализ арифметических выражений.

Включение действий в синтаксис. Семантические процедуры.

Табличный LL(1) – анализатор.

Польская запись выражений. Алгоритм вычисления выражений в польской записи.

Перевод арифметических выражений в польскую запись.

Метод стека с приоритетами трансляции выражений в польскую запись (алгоритм Э. Дейкстры).

Интерпретация выражений.

Трансляция языков программирования.. Описание языков программирования.

Лексический анализатор.

Таблицы транслятора. Области действия имен.

Виртуальная машина для простого языка.

Трансляция описаний. Распределение памяти для переменных.

Трансляция выражений.

Трансляция операторов.

Трансляция процедур без параметров.

Трансляция процедур с параметрами-значениями и локальными переменными.

Трансляция процедур-функций.

Генерация кода для параметров-переменных.

Трансляция линейных массивов.

Язык ассемблера для виртуальной машины.

Конструкция простого двухпроходного ассемблера.

Автоматизация построения и мобильность трансляторов.

 

Литература

Основная

1. Алгоритмический язык Алгол-60. Модифицированное сообщение. М., Мир, 1982
2. Вирт Н. Алгоритмы + структуры данных = программы. М., Мир, 1985
3. Вирт Н. Программирование на языке Модула-2. М., Мир
4. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М. Мир, 1975
5. Джермейн К. Программирование на IBM/360. М., Мир, 1978 (описания языков Кобол, ПЛ/1 и Фортран)
6. Джехани Н. Язык Ада. М., Мир, 1988
7. Керниган Б. Ричи Д. Фьюэр Язык программирования Си. Задачи по языку Си. М., Финансы и статистика, 1985
8. Кетков Ю. Л. Диалог на языке бейсик для мини- и микро-ЭВМ. М., Наука, 1988
9. Лингер Р., Миллс Х., Уитт Б. Теория и практика структурного программирования. М., Мир, 1982
10. Мёссенбёк Х. Вирт Н. Язык программирования Оберон-2. Институт компьютерных систем, ЕТН, Цюрих, 1996.
11. Рейуорд-Смит В. Дж. Теория формальных языков. Вводный курс. М., Радио и связь, 1988
12. Свердлов С. З. Введение в методы трансляции. Вологда, Русь, 1994

Дополнительная

1. N.Wirth. Theory and Techniques of Compiler Construction. Addison-Wesley, 1996.
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М., Мир, 1978
3. Баррон Д. Введение в языки программирования. М., Мир, 1980
4. Бек Л. Введение в системное программирование. М., Мир, 1988
5. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М., Мир, 1975
6. Зелковиц М., Шоу А., Геннон Дж. Принципы разработки программного обеспечения. М., Мир, 1982
7. Кауфман В. Ш. Языки программирования. Концепции и принципы. М., Радио и связь, 1993
8. Лебедев В. Н. Введение в системы программирования. М., Статистика, 1975
9. Пратт Т. Языки программирования: разработка и реализация. М., Мир, 1979
10. Язык компьютера. М., Мир, 1989

---

Университет | Отделение прикладной математики | Рабочие программы